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