水题：有一个人站在(sx,sy)的位置，有n辆出租车，正向这个人匀速赶来，每个出租车的位置是(xi, yi) 速度是 Vi;求人最少需要等的时间；
单间循环即可；
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define N 102550
#define PI 4*atan(1.0)
#define mod 100000001
#define met(a, b) memset(a, b, sizeof(a))
typedef long long LL; int main()
{
int sx, sy, n;
double ans = INF;
scanf("%d %d %d", &sx, &sy, &n);
for(int i=; i<=n; i++)
{
int x, y, v;
scanf("%d %d %d", &x, &y, &v);
double d = sqrt((x-sx)*(x-sx)+(y-sy)*(y-sy));
ans = min(ans, d/v);
}
printf("%.7f\n", ans);
return ;
}
有n个物品，每个物品为ai元，某人每天有x元钱，求每天他能买几种的物品；
排序二分即可；
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define N 102550
#define PI 4*atan(1.0)
#define mod 100000001
#define met(a, b) memset(a, b, sizeof(a))
typedef long long LL; int a[N]; int main()
{
int n, m, num;
while(scanf("%d", &n)!=EOF)
{
for(int i=; i<n; i++)
scanf("%d", &a[i]);
sort(a, a+n);
scanf("%d", &m);
for(int i=; i<m; i++)
{
scanf("%d", &num);
int ans = upper_bound(a, a+n, num)-a;
printf("%d\n", ans);
}
}
return ;
}
简单dp：给你n个字符串，然后问这n个字符串要想变成字典序排列的字符串所需的代价是多少，每个字符串可以倒置，（倒置串 i 的代价是a[i]），或者不变；
可以用dp[i][0]表示前i个字符串已经是按字典序排列的，并且第i个字符串不倒置的最小代价；用dp[i][0]表示前i个字符串已经是按字典序排列的，并且第i个字符串倒置的最小代价；
所以公式很容易写出来；
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define oo 1000000000000000
#define N 102550
#define PI 4*atan(1.0)
#define mod 100000001
#define met(a, b) memset(a, b, sizeof(a))
typedef long long LL; int n;
LL a[N], dp[N][]; char s[][N]; void Strrev(char str[])
{
int len = strlen(str);
for(int i=, j=len-; i<j; i++, j--)
swap(str[i], str[j]);
} int main()
{
scanf("%d", &n);
for(int i=; i<=n; i++)
{
scanf("%I64d", &a[i]);
dp[i][] = dp[i][] = oo;
} int p = ; dp[][] = ; dp[][] = a[]; for(int i=; i<=n; i++)
{
p = p^;
scanf("%s", s[p]);
if(i == ) continue; strcpy(s[p+], s[p]);
Strrev(s[p+]);
strcpy(s[(p^)+], s[p^]);
Strrev(s[(p^)+]); if(strcmp(s[p], s[p^]) >= )
dp[i][] = min(dp[i][], dp[i-][]);
if(strcmp(s[p], s[(p^)+]) >= )
dp[i][] = min(dp[i][], dp[i-][]);
if(strcmp(s[p+], s[p^]) >= )
dp[i][] = min(dp[i][], dp[i-][] + a[i]);
if( strcmp(s[p+], s[(p^)+]) >= )
dp[i][] = min(dp[i][], dp[i-][] + a[i]);
}
LL ans = min(dp[n][], dp[n][]);
if(ans == oo)ans = -;
printf("%I64d\n", ans);
return ;
}
01字典树：有一个里面初始值只有 0 的集合，执行 n 个操作，每个操作有三种可能：
+ x把x添加到集合中去；
- X把x从集合中删去一个；保证集和中一定有x；
? x从集合中找到一个数y，使得x异或y最大化；
对于每个?操作输出对应的最大的值；
01字典树模板：把十进制数转化为二进制数，通过前补零的方法构成32位，然后从前到后依次添加到字典树中去；
在查找时，每次尽量查找当前位相反的数的那个位置， 因为异或是不同为1的；
#include<iostream>
#include<algorithm>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;
#define INF 0x3f3f3f3f
#define oo 1000000000000000
#define N 102550
#define PI 4*atan(1.0)
#define mod 100000001
#define met(a, b) memset(a, b, sizeof(a))
typedef long long LL; struct node
{
int sum, num;///sum表示有多少个数经过当前这个节点；num为从根节点到叶子节点表示的数；
node *Next[];///指向下一层的节点；
}; void Add(node *head, int x, int cnt)///把x对应的二进制01插入到字典树中去；共32位，前补零形式；
{
node *p = head;
for(int i=; i>=; i--)///这一点不太理解位运算的，但是相当于是把x转换成二进制，然后插入其中；
{
int k = (x>>i)&;
if(p->Next[k] == NULL)///当不存在当前节点时，开创新节点，并连接在对应位置；
{
node *q = new node();
p->Next[k] = q;
}
p = p->Next[k];///接着往下走；
p->sum += cnt;///更新节点经过数；
}
p->num = x;///结束的时候更新叶子节点对应的数；
} int Find(node *head, int x)
{
node *p = head;
for(int i=; i>=; i--)
{
int k = (x>>i)&;
if(p->Next[k^] != NULL && p->Next[k^]->sum > )///尽量找与k不同的；应为异或是不同为1，所以要想最大，就要尽量不同；
p = p->Next[k^];
else if(p->Next[k] != NULL && p->Next[k]->sum > )
p = p->Next[k];
}
return (p->num)^x;///返回对应的最大结果；
} int main()
{
int n, x; char ch; scanf("%d", &n); node *head = new node(); Add(head, , ); for(int i=; i<=n; i++)
{
scanf(" %c %d", &ch, &x);
if(ch == '+')
Add(head, x, );
else if(ch == '-')///删除，相当于更新sum即可；
Add(head, x, -);
else
{
int ans = Find(head, x);
printf("%d\n", ans);
}
}
return ;
}