不要问我为什么昨天考的今天才贴解题报告。。
第一题：
给定3个字符串，求它们的最长公共子序列。
解：
考试时知道肯定是LCS的二维再加一维，用三维，可天堂有路你不走，地狱无门你偏来。。。灵机一动想出来一个方法：先记下前两个的最长公共子序列（可能有多个），然后再一一与第三个字符串比较，找出三者的最长公共子序列。然后就GG了。想不通，思路应该是对的啊。所以又留了一道题来想。
然后三维的状态转移很好写。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<map> 6 #define maxn 125 7 using namespace std; 8 char a[maxn],b[maxn],c[maxn]; 9 int n,f[maxn][maxn][maxn]; 10 int main() 11 { 12 freopen("subq.in","r",stdin); 13 freopen("subq.out","w",stdout); 14 cin>>n; 15 scanf("%s%s%s",a+1,b+1,c+1); 16 for (int i=1;i<=n;i++) 17 for (int j=1;j<=n;j++) 18 for (int k=1;k<=n;k++) 19 { 20 f[i][j][k]=max(f[i-1][j][k],max(f[i][j-1][k],f[i][j][k-1])); 21 if (a[i]==b[j]&&b[j]==c[k]) 22 f[i][j][k]=f[i-1][j-1][k-1]+1; 23 } 24 cout<<f[n][n][n]; 25 return 0; 26 }
不要后悔。。。
第二题：
定义两个素数是连续的当且仅当这两个素数之间不存在其他的素数（如 7,11 ,(23,29)。给定N,K，在不超过N的正整数中求能够分解为K个连续的素数的和的最大的那个是多少。
解：
先开始连题都读错了，想着完了我肯定不会，这是唯一分解定理啊，数论没看过啊。然后再定睛几看，额，只是一个和而已好吗。下次要先把题读清楚。
然后就是先求出10^6以内的素数，然后 前缀和+二分答案。哦，因为一个二分模板的问题，哎。贴一个二分模板：
int l=1 , r=n+1; while(l<r) // the minimum line above P(x0,y0) { int m = (l+r)>>1; if(check(m)) r = m;//在下面； else l = m + 1; } return l-1;
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 1000005 6 #define ll long long 7 using namespace std; 8 int t,n[2005],k[2005],ma,su[maxn],idx; 9 ll he[maxn]; 10 bool zhi[maxn]; 11 void get_zhi(int x) 12 { 13 memset(zhi,true,sizeof(zhi)); 14 for (int i=2;i*i<=x;i++) 15 if (zhi[i]){ 16 for(int j=i*i;j<=x;j+=i) 17 if (zhi[j]){ 18 zhi[j]=false; 19 } 20 } 21 zhi[1]=false; 22 for (int i=2;i<=x;i++) 23 if (zhi[i]) { 24 //su[++idx]=i; 25 ++idx; 26 he[idx]=(ll)he[idx-1]+i; 27 } 28 } 29 void work(int x,int y) 30 { 31 int l=y,r=idx;//l 32 ll ans=-1; 33 while (l<=r){ 34 int mid=(l+r)>>1; 35 ll an=he[mid]-he[max(0,mid-y)]; 36 if (an<=x){l=mid+1;ans=an;} 37 else r=mid-1; 38 } 39 printf("%I64d ",ans); 40 /*if (he[l]-he[l-y]>x) { 41 l--;ans=he[l]-he[l-y]; 42 } 43 //if (l+1>y&&he[l]-he[l-y]>x) 44 else if (ans!=-1&&he[l]-he[l-y]>x&&l-1<=y) ans=-1; 45 if (l-y<0) ans=-1;*/ 46 //l+=1; 47 /*for (int i=l;i>=y;i--)//**** 48 { 49 if (i>idx) continue; 50 if (he[i]-he[i-y]<=1) {//**** 51 printf("-1 "); 52 return ; 53 } 54 else if (he[i]-he[i-y]<=x) { 55 printf("%I64d ",he[i]-he[i-y]); 56 return ; 57 } 58 } 59 printf("-1 ");*/ 60 } 61 int main() 62 { 63 freopen("dun.in","r",stdin); 64 freopen("dun.out","w",stdout); 65 cin>>t; 66 for (int i=1;i<=t;i++) 67 { 68 scanf("%d%d",&n[i],&k[i]); 69 if (n[i]>ma) ma=n[i]; 70 } 71 get_zhi(ma); 72 for (int i=1;i<=t;i++) 73 work(n[i],k[i]); 74 return 0; 75 }
第三题
有一个村庄在闹饥荒，善良而土豪的YGH决定给他们发放救济粮，该村庄有 n 户人家，每两户人家之间只有一条路可以互相到达，即这些人家之间形成一棵树。现在 YGH 会以这样的形式给他们发放粮食，选择两户人家，然后对这两个户人家路径上的所有人家都发放一袋种类为 w 的救济粮。在完成一系列发放任务后，YGH 想知道每一户人家收到的粮食中数量最多的是哪一种。
解：
40%：暴力。注意dfs的返回如果没有加判断，那么idx一直往下减就会下标超界。。然后就不知道哪里的值会被改了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define maxn 1005 6 using namespace std; 7 int n,q,road[maxn],idx; 8 int tot,he[maxn],ne[maxn*2],to[maxn*2]; 9 bool vis[maxn],can=false; 10 struct pp{ 11 int sum; 12 int w[maxn],num[maxn]; 13 }; 14 pp house[maxn]; 15 void add(int a,int b) 16 { 17 tot++;to[tot]=b;ne[tot]=he[a];he[a]=tot; 18 } 19 void update(int x,int y,int ad) 20 { 21 road[++idx]=x; 22 vis[x]=true; 23 if (x==y){ 24 while (idx) 25 { 26 int s=road[idx]; 27 bool yes=false; 28 for (int i=1;i<=house[s].sum;i++) 29 if (house[s].w[i]==ad){ 30 house[s].num[i]++; 31 yes=true; 32 break; 33 } 34 if(!yes){ 35 house[s].sum++; 36 house[s].w[house[s].sum]=ad; 37 house[s].num[house[s].sum]++; 38 } 39 idx--; 40 } 41 can=true; 42 return ; 43 } 44 for (int i=he[x];i;i=ne[i]) 45 if (!vis[to[i]]){ 46 vis[to[i]]=true; 47 update(to[i],y,ad); 48 if (can) return ;//回溯不加判断会下标超界 49 vis[to[i]]=false; 50 idx--; 51 } 52 } 53 int main() 54 { 55 freopen("rice.in","r",stdin); 56 freopen("rice.out","w",stdout); 57 cin>>n>>q; 58 for (int i=1;i<n;i++) 59 { 60 int x,y; 61 scanf("%d%d",&x,&y); 62 add(x,y); 63 add(y,x); 64 } 65 for (int i=1;i<=q;i++) 66 { 67 int x,y,z;idx=0;can=false; 68 memset(road,0,sizeof(road)); 69 memset(vis,0,sizeof(vis)); 70 scanf("%d%d%d",&x,&y,&z); 71 update(x,y,z); 72 } 73 for (int i=1;i<=n;i++) 74 { 75 int mx=0,cur=12345678; 76 for (int j=1;j<=house[i].sum;j++) 77 { 78 if (house[i].num[j]>mx) 79 mx=house[i].num[j]; 80 } 81 for (int j=1;j<=house[i].sum;j++) 82 if (house[i].num[j]==mx) { 83 if (house[i].w[j]<cur) cur=house[i].w[j]; 84 } 85 if (cur==12345678) cout<<"0"<<endl; 86 else printf("%d ",cur); 87 } 88 return 0; 89 } 90 //30 min
100%：树剖。先挖坑。