水题：有一个人站在(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=1; 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 ", ans); return 0; }
有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=0; i<n; i++) scanf("%d", &a[i]); sort(a, a+n); scanf("%d", &m); for(int i=0; i<m; i++) { scanf("%d", &num); int ans = upper_bound(a, a+n, num)-a; printf("%d ", ans); } } return 0; }
简单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][2]; char s[4][N]; void Strrev(char str[]) { int len = strlen(str); for(int i=0, j=len-1; i<j; i++, j--) swap(str[i], str[j]); } int main() { scanf("%d", &n); for(int i=1; i<=n; i++) { scanf("%I64d", &a[i]); dp[i][0] = dp[i][1] = oo; } int p = 0; dp[1][0] = 0; dp[1][1] = a[1]; for(int i=1; i<=n; i++) { p = p^1; scanf("%s", s[p]); if(i == 1) continue; strcpy(s[p+2], s[p]); Strrev(s[p+2]); strcpy(s[(p^1)+2], s[p^1]); Strrev(s[(p^1)+2]); if(strcmp(s[p], s[p^1]) >= 0) dp[i][0] = min(dp[i][0], dp[i-1][0]); if(strcmp(s[p], s[(p^1)+2]) >= 0) dp[i][0] = min(dp[i][0], dp[i-1][1]); if(strcmp(s[p+2], s[p^1]) >= 0) dp[i][1] = min(dp[i][1], dp[i-1][0] + a[i]); if( strcmp(s[p+2], s[(p^1)+2]) >= 0) dp[i][1] = min(dp[i][1], dp[i-1][1] + a[i]); } LL ans = min(dp[n][0], dp[n][1]); if(ans == oo)ans = -1; printf("%I64d ", ans); return 0; }
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[2];///指向下一层的节点； }; void Add(node *head, int x, int cnt)///把x对应的二进制01插入到字典树中去；共32位，前补零形式； { node *p = head; for(int i=31; i>=0; i--)///这一点不太理解位运算的，但是相当于是把x转换成二进制，然后插入其中； { int k = (x>>i)&1; 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=31; i>=0; i--) { int k = (x>>i)&1; if(p->Next[k^1] != NULL && p->Next[k^1]->sum > 0)///尽量找与k不同的；应为异或是不同为1，所以要想最大，就要尽量不同； p = p->Next[k^1]; else if(p->Next[k] != NULL && p->Next[k]->sum > 0) p = p->Next[k]; } return (p->num)^x;///返回对应的最大结果； } int main() { int n, x; char ch; scanf("%d", &n); node *head = new node(); Add(head, 0, 1); for(int i=1; i<=n; i++) { scanf(" %c %d", &ch, &x); if(ch == '+') Add(head, x, 1); else if(ch == '-')///删除，相当于更新sum即可； Add(head, x, -1); else { int ans = Find(head, x); printf("%d ", ans); } } return 0; }