题意：找到相邻差值最大的差值。
分析：水题，直接做。
/**************************************** * File Name: 226a.cpp * Author: sky0917 * Created Time: 2014年01月24日 23:33:21 ****************************************/ #include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 100005; int v[maxn]; int main(){ int n, m; int a, b, c; int x; while (scanf("%d %d",&n,&x)!=EOF){ int ma = 0; int re = 0; for (int i=0; i<n; i++){ scanf("%d",&v[i]); } for (int i=1; i<n; i++){ if (v[i-1] - v[i] > re){ re = v[i-1] - v[i]; } } printf("%d\n",max(0, re-x)); } return 0; }
题意：给出一个字符串 s (1?≤?|s|?≤?5000)，问这个字符串中有多少个子串中含有至少一个“bear”单词。
分析：遍历一遍字符串，维护一个cnt，表示枚举的子串的开头位置的最左端
例如： acbeartbear
第一次发现 bear 之后,假如b的位置为 i ，那么：res += (i-cnt+1)*(len-i-3)
然后 cnt = i+1，这样就不会出现重复枚举的情况了。
/**************************************** * File Name: 226b.cpp * Author: sky0917 * Created Time: 2014年01月24日 23:33:26 ****************************************/ #include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 5005; char s[maxn]; int main(){ while (scanf("%s",&s)!=EOF){ long long res = 0; long long len = strlen(s); long long cnt = 0; for (long long i=0; i<len-3; i++){ if (s[i]==‘b‘ && s[i+1]==‘e‘ && s[i+2]==‘a‘ && s[i+3]==‘r‘){ long long l = i-cnt+1; long long r = len - i - 3; res += l * r; cnt = i+1; } } printf("%I64d\n",res); } return 0; }
题意： 有 n (1?≤?n?≤?106) 个数，x1,?x2,?...,?xn (2?≤?xi?≤?107). 还有 m (1?≤?m?≤?50000) 个询问，每个询问为：l,r
表示要求出[l, r]区间中所有的质数 p 的 f (p) 之和，f (p) 表示n个数中能被p整除的数的个数。
分析： 可以先打一个sqrt(1E7)范围的素数表，然后遍历一遍 n 个数，对每个数分解质因数，并用标记
数组标记，例如某个数有质因子 p，那么vis[p]++, 最后处理出一个sum[i] 数组，sum[i]表示vis[i]
数组中前 i 项的和，对于询问 l， r 输出 sum[r] - sum[l-1] 即可。
/**************************************** * File Name: 226c.cpp * Author: sky0917 * Created Time: 2014年01月24日 23:33:45 ****************************************/ #include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1000005; int ma; int v[maxn*10]; int vis[10003]; int p[10004]; int tp; void print(){ tp = 0; for (int i=2; i<10000; i++){ if (!vis[i]){ p[tp++] = i; for (int j=i*2; j<10000; j+=i){ vis[j] = 1; } } } } void cal(int x){ for (int i=0; p[i]*p[i] <= x && i<tp; i++){ if (x % p[i] == 0){ v[p[i]]++; while (x % p[i] == 0){ x /= p[i]; } } } if (x != 1){ v[x]++; } } int val[maxn]; int sum[maxn*10]; int main(){ int n, m; int va; print(); while (scanf("%d",&n)!=EOF){ ma = 0; for (int i=0; i<n; i++){ scanf("%d",&val[i]); if (val[i] > ma) ma = val[i]; } for (int i=0; i<n; i++){ cal(val[i]); } for (int i=1; i<=ma; i++){ sum[i] = sum[i-1] + v[i]; } scanf("%d",&m); int l, r; while (m--){ scanf("%d %d",&l, &r); if (l > ma){ printf("0\n");continue; } r = min(ma, r); printf("%d\n",sum[r]-sum[l-1]); } } return 0; }
题意： 有 n（n<20) 个灯，每个灯有一个自己可以照亮的角度di，现在某个人要从(l,0) 走到（r,0)的位置，需要一开始调整
好灯的角度，使得这个人一路上都可以被灯照到，这个人走的路线是一条线段，问这个最多能走多远，当然最多不会超过
r 位置。
分析：状态压缩DP+向量旋转。
dp[st] 表示在 s 状态下，最远走的位置，s中..001010.. 1表示用了那个灯，0表示没用，然后枚举没有用的灯，让其
一开始的向量为（dp[st]-x0, -y0) 逆时针转 di 度得到新的向量，求出其和x轴的交点（x1，0)
那么dp[st|(1<<j)] = max(dp[st|(1<<j)], x1)
最后输出dp[st] 和 r 的最小值 再减去 l 就好。
注意一个情况，就是旋转过程中可能出现与x轴没有交点的情况，这个时候把 dp[st|（1<<j)] = r 就可以了。
/**************************************** * File Name: 226d.cpp * Author: sky0917 * Created Time: 2014年01月25日 0:50:46 ****************************************/ #include <map> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const double p = acos(-1.0); double dp[1<<21]; int n; double l, r; struct node{ double x, y, di; }q[22]; int main(){ while (scanf("%d %lf %lf",&n,&l,&r)!=EOF){ for (int i=0; i<n; i++){ scanf("%lf %lf %lf",&q[i].x,&q[i].y,&q[i].di); } int st = 1<<n; for (int i=0; i<st; i++){ dp[i] = -9999999.0; } dp[0] = l; for (int i=0; i<st; i++){ for (int j=0; j<n; j++){ if (((1<<j)&i) == 0){ int sta = i | (1<<j); double x = dp[i] - q[j].x; double y = -q[j].y; double a = x*cos(p*q[j].di/180)-y*sin(p*q[j].di/180); double b = x*sin(p*q[j].di/180)+y*cos(p*q[j].di/180); if (b >= 0){ dp[sta] = r; continue; } double tmp = y*a/b+q[j].x; dp[sta] = max(dp[sta], tmp); } } } printf("%.10lf\n",min(r, dp[st-1])-l); } return 0; }