A题 Beru-taxi
随便搞搞。。
#include <cstdio>
#include <cmath>
using namespace std;
int a,b,n;
struct _
{
int x,y,v;
}p[];
double dis2(_ A)
{
return (a - A.x) * (a - A.x) + (b - A.y) * (b - A.y);
}
int main()
{
scanf("%d%d%d", &a, &b, &n);
; i < n; i++)
scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].v);
double ans = 1.0 * 0x3f3f3f3f;
; i < n; i++)
{
double temp = (double) sqrt(dis2(p[i])) / p[i].v;
)
ans = temp;
}
printf("%lf\n",ans);
;
}
就是找有几个不大于它的数嘛。sort一下，upperbound就行。
#include <cstdio>
#include <algorithm>
using namespace std;
+ ];
int main()
{
int n,q,x;
scanf("%d", &n);
; i < n; i++)
scanf("%d", &a[i]);
scanf("%d", &q);
sort(a,a+n);
; i < q; i++)
{
scanf("%d", &x);
int pos = upper_bound(a,a+n,x) - a;
printf("%d\n",pos);
}
;
}
C题 Hard problem
dp，加一个维度来表示，是否翻转过！！！
其次，WA了一次是因为这个判断的时候，不等号是要带等号的。>= <= 而不是> < ;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
+ ;
const LL INF = 1e17;
int c[maxn];
LL dp[maxn][];
string s[maxn];
int main()
{
int n;
cin>>n;
; i < n; i++)
cin>>c[i];
; i < n; i++)
cin>>s[i];
//init
; i < n; i++)
{
dp[i][] = INF;
dp[i][] = INF;
}
dp[][] = ;
dp[][] = c[];
string s10,s11,s20,s21;
; i < n; i++)
{
s10 = s11 = s[i-];
reverse(s11.begin(),s11.end());
s20 = s21 = s[i];
reverse(s21.begin(),s21.end());
if(s10 <= s20)
dp[i][] = min(dp[i][], dp[i-][]);
if(s11 <= s20)
dp[i][] = min(dp[i][], dp[i-][]);
if(s10 <= s21)
dp[i][] = min(dp[i][], dp[i-][] + (LL)c[i]);
if(s11 <= s21)
dp[i][] = min(dp[i][], dp[i-][] + (LL)c[i]);
}
LL ans = min(dp[n-][], dp[n-][]);
cout<<(ans == INF ? - : ans)<<endl;
;
}
据说是裸的字典树orz。
01字典树
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
#define mem(x,y) memset(x, y, sizeof(x))
#define lson l,m,rt << 1
#define rson m+1,r,rt << 1 | 1
const int INF = 0x3f3f3f3f;
;
int n;
;//种类数目调节
struct node
{
node *next[trie_size];
int cnt;
node()
{
; i < trie_size; i++)
next[i] = NULL;
cnt = ;
}
};
node *p, *root = new node();
void trie_insert(int x)
{
p = root;
; i >= ; i--)
{
<< i) ? : ;
if(p->next[num] == NULL)
p->next[num] = new node();
p = p->next[num];
p->cnt++;
}
}
void trie_delete(int x)
{
p = root;
;i >= ; i--){
<< i) ? : ;
p = p -> next[num];
p->cnt--;
}
}
int trie_query(int x)
{
;
p = root;
; i >= ; i--)
{
<< i) ? : ;
node *temp;
temp = p->next[num];
)
{
res += << i;
p = temp;
}
else
{
p = p->next[!num];
}
}
return res;
}
int main()
{
trie_insert();
scanf("%d", &n);
; i < n; i++)
{
char ch;
int x;
getchar();
scanf("%c%d", &ch, &x);
if(ch == '+')
{
trie_insert(x);
}
else if(ch == '-')
{
trie_delete(x);
}
else if(ch == '?')
{
int ans = trie_query(x);
printf("%d\n", ans);
}
}
;
}