好不容易搞来的题目，不写一写怎么行呢。
不过难度真心不高（一小时K掉），都是老题+暴力题，没有欧洲玄学。
再说一句，这试卷是叶可禾出的吧。
T1 好老的题目，看到有多组数据我还怕了，以为有更流弊的算法。没想到减了数据范围。
首先把边sort一遍，因为要求，max-min最小，所以枚举最短边，然后向后找到第一条满足联通的边即可。
联通的话通过并查集就可以实现。
（没有联通要输-1，题目里没说）
CODE
#include#include 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
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
#includeusing 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
（刚开始把读优打错了）
T3 感觉是一道很老的题目。
只需要维护一个队列，当队尾与队头之间的距离大于d时弹出即可。
每次ans+=tail-head即可。
注意将坐标排序一遍。
CODE
#include#include 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#include using namespace std;const int N=1005;vector 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