要活下去，总有一天我们能笑着缅怀过去的艰辛。
T1.zoo
找最小值的最大值的和，很绕口，但是这个让我联想起了货车运输，正是求图上两点路径最小值的最大值，做法自然是用最大生成树上找最小边的方法去卡这个限制。
那就好说了，按两点最小权值建边，建图，建树，然后呢？？？
我这里写了50分的O(n^2)暴力，对每个点来一次dfs统计，走人了。
正解提供了这样一种似曾相识的思路，学到了。
考虑Kruskal中合并两个联通块的情况，由于边是从大往小枚举的，这条边一定是连接这两个联通块的“瓶颈”边，也就是最小边，所以答案就要加上2*siz[u]*siz[v]*w
这就完啦，学会了一种神奇的思路。
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f; } const int MAXN=1000005; struct Edge{ int from,to; long long w; }e[MAXN<<1]; int ecnt; inline void add(int x,int y,int w){ e[++ecnt].from = x; e[ecnt].to = y; e[ecnt].w = w; } int n,m; long long val[MAXN]; int fa[MAXN]; int fnd(int x){ return x==fa[x]?x:fa[x]=fnd(fa[x]); } void cat(int x,int y){ fa[y]=x; } bool cmp(const Edge &x,const Edge &y){ return x.w>y.w; } unsigned long long siz[MAXN]; unsigned long long ans; int main(){ n=rd();m=rd(); for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1,val[i]=rd(); int x,y,w; for(int i=1;i<=m;i++){ x=rd();y=rd();w=min(val[x],val[y]); add(x,y,w); } sort(e+1,e+1+ecnt,cmp); int cnt=0,nx,ny; for(int i=1;i<=ecnt;i++){ x=e[i].from,y=e[i].to;w=e[i].w; nx=fnd(x),ny=fnd(y); if(nx==ny) continue; ans+=siz[nx]*siz[ny]*1ll*e[i].w; siz[nx]+=siz[ny]; cat(nx,ny); if(++cnt==n-1) break; } cout<<(ans<<1); return 0; }
T2.segment
考场没什么思路，磕了半天第三题，十分钟写的30分O(n^2)暴力
正解是这样考虑区间覆盖的，对于一个区间[u,v]，假设[l,r]能覆盖它，那必定有l<=u&&v<=r
那么我们可以开两个树状数组，分别记录左端点和右端点，这两个树状数组以权值为下表，可以方便地查出前缀和
两个前缀和相减就是答案啦
对于删除操作，只需要把对应位置-1。
这根本不segment tree...考场上第一反应居然是主席树版李超线段树？啥东西..
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; const int MAXN=1000005; int n,T; inline int rd(){ int ret=0,f=1;char c; while(c=getchar(),!isdigit(c))f=c=='-'?-1:1; while(isdigit(c))ret=ret*10+c-'0',c=getchar(); return ret*f; } struct BIT{ int t[MAXN]; void init(){memset(t,0,sizeof(t));} inline void update(int x,int w){for(int i=x;i<=n;i+=i&-i) t[i]+=w;} inline int query(int x){int ret=0;for(int i=x;i;i-=i&-i)ret+=t[i];return ret;} }; int savx[MAXN],savy[MAXN],opt[MAXN]; int bx[MAXN],by[MAXN]; BIT L,R; int id[MAXN]; void solve(){ L.init();R.init(); memset(id,0,sizeof(id)); n=rd(); int sum=0,tmp; for(int i=1;i<=n;i++){ opt[i]=rd(); if(!opt[i]){bx[i]=savx[i]=rd();by[i]=savy[i]=bx[i]+(++sum);id[sum]=i;} else{tmp=rd();tmp=id[tmp];bx[i]=savx[i]=savx[tmp];by[i]=savy[i]=savy[tmp];} } sort(bx+1,bx+1+n);sort(by+1,by+1+n); int totx=unique(bx+1,bx+1+n)-bx,toty=unique(by+1,by+1+n)-by; for(int i=1;i<=n;i++){ savx[i]=lower_bound(bx+1,bx+1+totx,savx[i])-bx;//%%%HSZ savy[i]=lower_bound(by+1,by+1+toty,savy[i])-by; } for(int i=1;i<=n;i++){ if(opt[i]){L.update(savx[i],-1);R.update(savy[i],-1);continue;} printf("%d ",R.query(savy[i])-L.query(savx[i]-1)); L.update(savx[i],1);R.update(savy[i],1); } } int main(){ T=rd();int t=T; while(T--) printf("Case #%d: ",t-T),solve(); return 0; }
T3.number
考虑这样一个事情，k严格小于max(n,m)，意味着，不存在一行或者一列，使得该行或该列全部被预先填好。
也就是说，每一行、列都会有至少一个空着的，可以考虑这样一个事情，在k=0的情况下：
对于第一列，共有n个元素，要填入奇数个-1，有C(n,1)+C(n,3)+C(n,5)+...种填法，SPLI学长讲过，这货就等于2^(n-1)
同理，每列亦如此，答案就是(n-1)*(m-1)，因为有一列是空出来的。
在考虑k的情况下，会发现，填入一个 k，答案就会除以二，所以答案就是(n-1)*(m-1)-k。
为什么这样对呢？因为之前说过，k严格小于max(n,m)
注意几个事情，当k>(n-1)*(m-1)时，要取0，也就是答案是pow(2,max(0,(n-1)*(m-1)-k))，以及当(n+m)为奇数，也就是(n&1)!=(m&1)时
考试的时候推出来式子，怕不稳就对着30写了个状压，大概这样
f[i][j]表示考虑到第i行，每列在前i行共填入了奇数/偶数个-1，用0和1表示
考虑转移，枚举i-1行和i行的状态j和k，填写了-1的位置就是v=j^k，判断这个v中是否是奇数个1（满足每行的限制），即可转移
问题是没仔细考虑空间！MLE
吸取教训，吸取教训。（其实写的那个式子没考虑和0取max，测出来也只有60分罢了）
#include<iostream> #include<cstdio> using namespace std; int n,m,k,MOD; typedef long long ll; ll qpow(ll x,ll y){ ll ret=1,base=x; while(y){ if(y&1)(ret*=base)%=MOD; (base*=base)%=MOD; y>>=1ll; } return ret; } int main(){ cin>>n>>m>>k; if((n&1)!=(m&1)) return puts("0"),0; int x,y,w; for(int i=1;i<=k;i++) cin>>x>>y>>w; cin>>MOD; cout<<qpow(2ll,max(0ll,1ll*(n-1)*(m-1)-k)); return 0; }
说起来，全场可能就我不知道发了两个大样例（虽然后来证明没什么用..）