题目

T1 食物中毒 [外链图片转存失败(img-W8VPYSyZ-1563335998340)(http://10.37.2.111/upload/image/20190525/20190525153421_86897.png)]T2 消息传递 [外链图片转存失败(img-pvrWtq3o-1563335998343)(http://10.37.2.111/upload/image/20190525/20190525153453_46410.png)] [外链图片转存失败(img-ardAqYji-1563335998345)(http://10.37.2.111/upload/image/20190525/20190525153453_95997.png)]T3 周年纪念日 [外链图片转存失败(img-JpffrW9X-1563335998346)(http://10.37.2.111/upload/image/20190525/20190525153524_85249.png)][外链图片转存失败(img-rQvmynCy-1563335998347)(http://10.37.2.111/upload/image/20190525/20190525153525_61442.png)] [外链图片转存失败(img-3y9Dea1Z-1563335998350)(http://10.37.2.111/upload/image/20190525/20190525153525_50609.png)] [外链图片转存失败(img-jlKG5sw0-1563335998352)(http://10.37.2.111/upload/image/20190525/20190525153525_67024.png)]

考试时忐忑的心理历程

（8：00 到11：30）

》》》》》》》》》》》》》8：32 第一题，搜索： 枚举每种药材选和不选，然后复杂度约为：$2^{20}=1048576$，还可以欸，但为了更快，可以用一个位运算哈希一下便于判断，哈希最大值为 $2^{50}$,要炸。。 第二题，图论（floyd或tarjan吧） 第三题，树形DP 》》》》》》》》》》》》》9：22 第一题大样例凉了 》》》》》》》》》》》》》9：52 第一题弃疗 第二题tarjan缩点后统计每个人的所属联通分量的点数是否大于1，如果是，T，否，F，假设它时间复杂度过得去吧 》》》》》》》》》》》》》10：12 第二题大数据过了 》》》》》》》》》》》》》10：24 第一题大数据过了 》》》》》》》》》》》》》10：42 第三题，kruskal建一个新图，然后乱搞应该可以拿到50pts，有希望拿到60pts，因为kruskal的复杂度为$O(logM)$,建图为$O(m)$,乱搞（dfs）为$O(N^2)$ , 总复杂度为$N^2$,这是紧的上限，大概可以吧，但是正确性堪忧。 》》》》》》》》》》》》》11：08 kruskal的正确性是伪的，只好乱搞了 》》》》》》》》》》》》》11：15 乱搞搞出来了，就是大样例呵呵呵 》》》》》》》》》》》》》11：30 做了点小优化，但是答案好像超过long long维护不了，就这样了吧

最后得分：210，预计得分：240 问题：审题缺乏精确度，模版不熟练（kruskal），心态波动太大

题解

T1

第一眼就看出是个搜索，但读漏了条件：药材中可能有两个相同的元素，导致我调了一个小时~~~~ 搜索策略也很easy啊，见代码吧：

#include<bits/stdc++.h> #pragma GCC optimize(2) using namespace std; #define loop(i,start,end) for(register int i=start;i<=end;++i) #define anti_loop(i,start,end) for(register int i=start;i>=end;--i) #define clean(arry,num) memset(arry,num,sizeof(arry)) #define max(a,b) ((a>b)?a:b) #define min(a,b) ((a<b)?a:b) #define ll long long template<typename T>void read(T &x){ x=0;char r=getchar();T neg=1; while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();} while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();} x*=neg; } int n,m; const int maxn=20+10,maxm=50+10; bool aim[maxm]; bool che[maxn][maxm]; bool sit[maxm]; inline void datasetting(){ clean(aim,0),clean(che,0);clean(sit,0); register int pos,pos2; loop(i,1,m){ read(pos); aim[pos]=true; }loop(i,1,n){ read(pos); loop(j,1,pos){ read(pos2); if(che[i][pos2]==false)che[i][pos2]=true; else che[i][pos2]=false; } } } bool dfs(int pos){ if(pos>n){ loop(i,1,50) if(sit[i]==0&&aim[i]==1)return false; return true; } loop(i,pos,n){ if(dfs(pos+1))return true; else{ loop(j,1,50)sit[j]=sit[j]^che[i][j]; if(dfs(pos+1))return true; else {loop(j,1,50)sit[j]=sit[j]^che[i][j];return false;} } } } int main(){ freopen("medicine.in","r",stdin); freopen("medicine.out","w",stdout); while(scanf("%d%d",&n,&m)!=EOF){ datasetting(); if(dfs(1))printf("Possible\n"); else printf("Impossible\n"); } return 0; } /************************************************************** Problem: 1474 User: mzg1802 Language: C++ Result: 正确 Time:640 ms Memory:1716 kb ****************************************************************/

T2

这道题算是瞎猫撞上死耗子了，正在我练tarjan的时候出这种题？？？ 这道题是缩点的经典套路，20min解决

#include<bits/stdc++.h> using namespace std; #define loop(i,start,end) for(register int i=start;i<=end;++i) #define anti_loop(i,start,end) for(register int i=start;i>=end;--i) #define clean(arry,num) memset(arry,num,sizeof(arry)) #define max(a,b) ((a>b)?a:b) #define min(a,b) ((a<b)?a:b) #define ll long long template<typename T>void read(T &x){ x=0;char r=getchar();T neg=1; while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();} while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();} x*=neg; } int n,m,cnt=0; const int maxn=100000+10,maxm=200000+10; struct node{int _v;int nxt;}edge[maxm]; int head[maxn]; inline void addl(int u,int v){ edge[cnt]._v=v; edge[cnt].nxt=head[u]; head[u]=cnt++; } int dfn[maxn],low[maxn],belong[maxn],num=0,col=0; int sta[maxn],top=0; int siz[maxn]; void tarjan(int u){ dfn[u]=low[u]=++num;sta[++top]=u; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i]._v; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); }else if(!belong[v])low[u]=min(low[u],dfn[v]); }if(dfn[u]==low[u]){ belong[u]=++col; ++siz[col]; while(top>=0&&sta[top]!=u){ belong[sta[top]]=col; ++siz[col]; --top; } --top; } } int main(){ freopen("message.in","r",stdin); freopen("message.out","w",stdout); read(n),read(m);clean(sta,0),clean(siz,0); clean(head,-1);clean(low,0),clean(dfn,0);clean(belong,0); register int xi,yi; loop(i,1,m){ read(xi),read(yi); addl(xi,yi); } loop(i,1,n) if(!dfn[i]) tarjan(i); loop(i,1,n){ if(siz[belong[i]]>1)printf("T\n"); else printf("F\n"); } return 0; } /************************************************************** Problem: 1475 User: mzg1802 Language: C++ Result: 正确 Time:68 ms Memory:6740 kb ****************************************************************/

T3

这道题我确实没想出来正解，但是下来后几个巨佬都说这是伟大的奶牛聚集加上一个最小生成树。 后来把这个坑补了，发现这个东西很有趣，主要有趣的地方在树的重心 重心：

对于一棵树n个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点数（或节点权值和）最小。换句话说，删除这个点后最大连通块（一定是树）的结点数最小。

从定义出发我们可以推出如下性质：

删除重心后最大连通块的结点数K最小，$K<=\frac{{\sum }_{i=1}^{n}P[i]}{2}$树的重心的位置和边权无关树中所有点到某个点的距离和中，到重心的距离和是最小的 （距离和 T=${\sum }_{i=1}^{n}dis[i]\times P[i]$,dis[i]是第i个点到重心的距离，P[i]是这个点的权值）

第一个结论是显然的，反证法可证 至于第2和3个结论的证明，我们可以借鉴带权中位数的证法，即调整法：

假设当前已经找到有一个重心设为u（如图），然后我们考虑将重心u经过边u->v向其四周的点移动，探究T的大小变化。若将重心由u移到v，设W为u，v连边的边权，则 T的增加量$△A=(P[a]+P[b]+P[c])\times W$ T的减少量$△B=P[d]\times W$ 而根据第一条性质，易有$P[a]+P[b]+P[c]>\frac{{\sum }_{i=1}^{n}P[i]}{2}>=P[d]$ 则$P[a]+P[b]+P[c]>P[d]$ 等式两边同时乘上$W$ 即$△A>△B$，即移动重心获得的T减少量少于增加量，故重心的距离和T最小，得证

而这道题还有一个细节，就是为什么kuskal后就可以满足最大边最小了呢？即为什么最小生成树的最大边权为生成树中最大边权最小的？我考试的时候用的是显然成立法，但其实很简单，可以用反证法证出来，

即：假如最小生成树（设为K）里面的最大边$l1$不是所有方案中最小的，其两端端点为u，v，那么必定有另一生成树（设为T）的最大边$l2$长度小于$l1$，则在T中，连接u，v两点的边$l3$的长度必定小于在K中的$l1$的长度（$l1>l2>l3$），与K为最小生成树的题设条件矛盾，得证

故本题确实是一个MST加一个树的重心就可以解决的问题，没有做出来是因为我对最小生成树的性质不熟悉和对重心不熟悉，总之一句话，还是太弱了，唉~~~~

#include<bits/stdc++.h> using namespace std; #define loop(i,start,end) for(register int i=start;i<=end;++i) #define anti_loop(i,start,end) for(register int i=start;i>=end;i) #define max(a,b) ((a>b)?a:b) #define min(a,b) ((a<b)?a:b) #define clean(arry,num) memset(arry,num,sizeof(arry)) #define ll long long template<typename T>void read(T &x){ x=0;char r=getchar();T neg=1; while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();} while(r>='0'&&r<='9'){x=(x<<1)+(x<<3)+r-'0';r=getchar();} x*=neg; } int n,m,cnt=0; const int maxn=1e5+10,maxm=2e5+10; struct node{int _v;int _w;int nxt;}edge[maxm<<1]; int head[maxn]; int P[maxn]; ll sum=0; inline void addl(int u,int v,int w){ edge[cnt]._v=v; edge[cnt]._w=w; edge[cnt].nxt=head[u]; head[u]=cnt++; } ll f[maxn];int h=INT_MAX; void dfs(int u,int fa){ f[u]=P[u];ll maxx=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i]._v; if(v==fa)continue; dfs(v,u); f[u]+=f[v]; maxx=max(maxx,f[v]); }if(maxx<(sum>>1)&&sum-f[u]<(sum>>1))h=min(h,u); } struct e{int s;int e;int w;}line[maxm]; int _f[maxn]; inline bool cmp(e a,e b){return a.w<b.w;} int findfa(int u){return _f[u]=((_f[u]==u)?u:findfa(_f[u]));} inline void buildgraph(){ sort(line+1,line+1+m,cmp); ll _sum=0,_time=0,_cny=0; loop(i,1,m){ int x=line[i].s; int y=line[i].e; int fx=findfa(x); int fy=findfa(y); if(fx!=fy){ addl(x,y,line[i].w); addl(y,x,line[i].w); _f[fx]=fy; _time=max(_time,line[i].w); _sum+=line[i].w;++_cny; }if(_cny>n-1)break; }printf("%lld %lld\n",_sum,_time); } int dis[maxn]; ll inner_dfs(int u,int fa){ ll res=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i]._v; if(v==fa)continue; dis[v]=dis[u]+edge[i]._w; res+=dis[v]*(ll)P[v]; res+=inner_dfs(v,u); }return res; } int main(){ #ifndef ONLINE_JUDGE freopen("datain2.txt","r",stdin); #endif // ONLINE_JUDGE clean(head,-1); read(n),read(m);loop(i,1,n)_f[i]=i; loop(i,1,n)read(P[i]),sum+=P[i]; loop(i,1,m)read(line[i].s),read(line[i].e),read(line[i].w); buildgraph(); dfs(1,0); clean(dis,0); printf("%d %lld\n",h,inner_dfs(h,0)); return 0; } /************************************************************** Problem: 1476 User: mzg1802 Language: C++ Result: 正确 Time:148 ms Memory:11208 kb ****************************************************************/

尽吾志也而不能至者，可以无悔矣，其孰能讥之乎？ ——王安石