好不容易搞来的题目，不写一写怎么行呢。
不过难度真心不高（一小时K掉），都是老题+暴力题，没有欧洲玄学。
再说一句，这试卷是叶可禾出的吧。
T1 好老的题目，看到有多组数据我还怕了，以为有更流弊的算法。没想到减了数据范围。
首先把边sort一遍，因为要求，max-min最小，所以枚举最短边，然后向后找到第一条满足联通的边即可。
联通的话通过并查集就可以实现。
（没有联通要输-1，题目里没说）
CODE
#include<cstdio> #include<algorithm> using namespace std; const int N=205,M=1005,INF=2147483647; struct data { int l,r,s; }e[M]; int father[N],i,j,n,m,ans,s,t,q; bool flag; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline void write(int x) { if (x/10) write(x/10); putchar(x%10+'0'); } inline int comp(data a,data b) { return a.s<b.s; } inline int getfather(int k) { return father[k]==k?k:father[k]=getfather(father[k]); } int main() { freopen("find.in","r",stdin); freopen("find.out","w",stdout); read(n); read(m); for (i=1;i<=m;++i) read(e[i].l),read(e[i].r),read(e[i].s); sort(e+1,e+m+1,comp); read(q); while (q--) { read(s); read(t); ans=INF; for (i=1;i<=m;++i) { for (j=1;j<=n;++j) father[j]=j; flag=0; for (j=i;j<=m;++j) { int fx=getfather(e[j].l),fy=getfather(e[j].r); father[fx]=fy; if (getfather(s)==getfather(t)) { flag=1; break; } } if (e[j].s-e[i].s<ans&&flag) ans=e[j].s-e[i].s; } if (ans==INF) puts("-1"); else write(ans),putchar(' '); } return 0; }
T2 看这数据范围，看着猥琐的要求最大值。这就是一道传统的O（n^2) DP；
用f[i][j]表示取到第i行第j列时最大值，so
f[i][j]=max f[i-1][j-1]+a[i][j] (选a[i][j]这个点）
f[i][j-1]（不选a[i][j]这个点）
注意第i行的花纵坐标至少要从i开始枚举
因为DP顺序和读入顺序相同，所以可以一边读一边做
CODE
#include<cstdio> using namespace std; const int N=805; int n,m,x,f[N][N],ans=-2147483647,i,j; inline void read(int &x) { x=0; char ch=getchar(); int flag=1; while (ch<'0'||ch>'9') { if (ch=='-') flag=-1; ch=getchar(); } while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); x*=flag; } inline int max(int a,int b) { return a>b?a:b; } int main() { freopen("flowers.in","r",stdin); freopen("flowers.out","w",stdout); read(n); read(m); for (i=1;i<=n;++i) for (j=1;j<=m;++j) { read(x); if (j<i) continue; if (j==1) f[i][j]=x; else f[i][j]=max(f[i-1][j-1]+x,f[i][j-1]); } printf("%d",f[n][m]); return 0; }
（刚开始把读优打错了）
T3 感觉是一道很老的题目。
只需要维护一个队列，当队尾与队头之间的距离大于d时弹出即可。
每次ans+=tail-head即可。
注意将坐标排序一遍。
CODE
#include<cstdio> #include<algorithm> using namespace std; const int N=1e6+5; int n,d,ans,i,s[N],q[N],head=1,tail=1; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } int main() { freopen("spock.in","r",stdin); freopen("spock.out","w",stdout); read(n); read(d); for (i=1;i<=n;++i) read(s[i]); sort(s+1,s+n+1); q[1]=s[1]; for (i=2;i<=n;++i) { q[++tail]=s[i]; while (q[tail]-q[head]>d&&tail>head) ++head; ans+=tail-head; } printf("%d",ans); return 0; }
T4 最值得思考也最值得骂人的一道题。
看到题目和最近打过的一道并查集补集的题目很想像（Luogu 关押罪犯）然后没有犹豫地敲了并查集。
然后发现还要输出方案这一茬。
删光，又发现照样可以套染色的板子，然后奋不顾身地敲了一个BFS版本的，但发现只能直接跳出但不能统计个数。
所以只好用超级不熟悉的DFS版本了。
代码很简单（很容易背），用一个数组表示这个数是否使用，再用一个数组记录前面到这个点有多少条边（有边就不能加入队里）。
之后回溯寻找即可（玄学复杂度）
CODE
#include<cstdio> #include<vector> using namespace std; const int N=1005; vector <int> a[N]; int col[N],n,m,i,x,y,ans,q[N],tot; bool v[N],p[N]; inline void read(int &x) { x=0; char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); } inline void copy() { for (int i=1;i<=n;++i) p[i]=v[i]; } inline void dfs(int k) { if (k==n+1) { if (tot>ans) ans=tot,copy(); return; } if (!q[k]) { v[k]=1; tot++; for (int i=0;i<a[k].size();++i) q[a[k][i]]++; dfs(k+1); v[k]=0; tot--; for (int i=0;i<a[k].size();++i) q[a[k][i]]--; } dfs(k+1); } int main() { freopen("tribe.in","r",stdin); freopen("tribe.out","w",stdout); read(n); read(m); for (i=1;i<=m;++i) { read(x); read(y); a[x].push_back(y); a[y].push_back(x); } dfs(1); printf("%d ",ans); for (i=1;i<=n;++i) if (p[i]) printf("%d ",1); else printf("%d ",0); return 0; }