题目链接 ：http://dutacm.club:7217/codesheaven/contest.php?cid=1021；
A题说是 KMP裸模板，等弱先把KMP一补；过几天再补；
B题，贪心，向将所有X.000小数读入（整数不管）这里有个读入的小技巧，默认所有数向下R；这是的关键就是找出范围了，每反向R一次。sum值要减1（比如0.75变成1，和0.75变成0，这差值就是1）。暴力枚举就好。
设 总共一共n个数，c1个小数,c2个整数 下界 n=c1+c2; low=max(0,n-c2),这里用max是因为害怕n-c2为负值.
上界 up=min(n,c1); 因为对半翻，上界最多就是n。
这里给出一个例子如 n=5/10,c1=7,c2=3; low=max(0,n-c2)=2;up=(n,c2)=5;
#include <iostream> #include<stdio.h> #include<algorithm> #include<string.h> #include<cmath> using namespace std; int T,n,sum,c1,c2; int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); sum=c1=c2=0; n<<=1; for(int a,b,i=1;i<=n;++i) { scanf("%d.%d",&a,&b); if(!b) ++c1; else sum+=b,++c2; } n>>=1; int low=max(0,n-c1),up=min(n,c2); int best=sum; for(int i=low;i<=up;++i) { best=min(best,abs(sum-i*1000)); } printf("%d.d\n",best/1000,best00); } return 0; } C题 拿上来就一顿DFS，BFS结果无线M,T,W,PE；
其实就是简单的DP。但对我来说还蛮难的；
//dp的时候分奇数和偶数两种情况 //1.当i为偶数时，i可以从i-1和i/2得到 //2.当i为奇数时，i可以从i-1得到，也可以从(i/2+1)先翻倍再减1得到 #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; const int maxn=1e7+20; long long dp[maxn]; int main() { long long x,y; int n;//黑人问好为什么n是long long 就wa； while(scanf("%d%I64d%I64d",&n,&x,&y)!=EOF) { memset(dp,0,sizeof(dp)); dp[0]=0; for(int i=1;i<=n;++i) { if(i%2==1) {dp[i]=min(dp[i-1]+x,dp[i/2+1]+x+y);} else {dp[i]=min(dp[i-1]+x,dp[i/2]+y);} } printf("%I64d\n",dp[n]); } return 0; } D题 是费用流，基本模板我会，但是那个残留网络找路径就不太会了
建图如下。
//很显然的费用流。源点到每个人流量为1，费用为0； 每个人到p流量为1费用为代码值×-1；每个人到q流量为1费用为运动值×-1；p到汇点流量为p费用为0；q到汇点流量为q费用为0.这样跑一次最小费用最大流，费用负一下就是最大化的值 此初跳过两道题。
G题 并查集，本来暴力建边然后TLE，具体都在代码里写了。
学长的话：套用分层图的概念就是，含有质因子p的所有数，构成一个‘层’，在这一层里是个完全子图
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn=1000006; bool ispr[maxn]; int prime[80000],pre[maxn];//判断素数，保存素数，保存j合数的最小素数i对应素数数组的下标cnt int cnt=0;//素数的个数 int head[180000],flag;//head数组保存邻接表的头，flag是边的个数 bool vis[180000];//标记是否读入 struct Edge { int to,next; void get(int a,int b) { to=a;next=b; } }edge[1400005];//边 void init() { cnt=0; memset(ispr,1,sizeof(ispr)); ispr[0]=ispr[1]=0; for(int i=2;i<=1000000;++i) { if(ispr[i]) { prime[++cnt]=i; pre[i]=cnt; for(int j=i<<1;j<=1000000;j+=i) { ispr[j]=0; if(!pre[j]) pre[j]=cnt; } } } } void add(int u,int v) { edge[flag].get(v,head[u]); head[u]=flag++; } void dfs(int u)//dfs去标记同一层的数。 { vis[u]=1; for(int v,i=head[u];i!=-1;i=edge[i].next) { v=edge[i].to; if(!vis[v]) dfs(v); } } int main() { init(); int T,n,tt=1; scanf("%d",&T); while(T--) { scanf("%d",&n); memset(head,-1,sizeof(int)*(cnt+n+3)); memset(vis,0,sizeof(bool)*(cnt+n+3)); flag=0; for(int a,i=1;i<=n;++i) { scanf("%d",&a); if(a==1) continue; int y=a;//a的副本 while(y>1) { int z=pre[y];//这块边是与下标相连的，因为每个质因子只对一个下标。 add(i+cnt,z);//抽像出来一个辅助点，把a所有的质因子都连边，形成一个层，然后对偶成点。 add(z,i+cnt);//比如15，6.就会通过3这个质因子连起来； while(!(y%prime[z])) y/=prime[z];//把所有的下标是z的质因子除干净以防止重边。 } } int ans=0; for(int i=1;i<=n;++i) { if(!vis[cnt+i]) { dfs(i+cnt),ans++; } } printf("Case %d: %d\n",tt++,ans); } return 0; }
