俩红夹一绿。什么破分。。。
$T1$写的和正解差不多的随机化，然而特判有一句话写错了，$100 \rightarrow 0$
$T3$写的$70pts$部分分。然而并不知道哪里又写挂了，虽然思路没问题但是也是$70 \rightarrow 0$
$T3$大概是会正解的但是不太敢考场打$LCT$，必炸无疑，就算了（结果还是个$0$。。。）
得亏$T2$没炸。不然爆零是如此轻松。。。
本来是比较简单一套题怎么又能考成这样
T1：小B的棋盘
大意：有$n$个棋子，你可以再放$k$个，棋子之间不可重叠。问有多少可能的对称中心。$n \le 10^5,k \le 20$
首先一个奇怪的随机化：枚举配对关系来确定对称中心。
对于任意一个对称中心有$n$个配对关系。一共$n^2$种方案。所以每次有$\frac{1}{n}$的成功率。
随机次数足够就不会出错。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int S=100005,m=7000009;
4 int hsh(int x,int y){return ((x*19260817ll+y)%m+m)%m;}
5 struct hash_map{
6 int fir[m],tx[m],ty[m],l[m],ec;
7 bool find(int x,int y){for(int i=fir[hsh(x,y)];i;i=l[i])if(tx[i]==x&&ty[i]==y)return 1;return 0;}
8 void ins(int x,int y){int r=hsh(x,y);l[++ec]=fir[r];fir[r]=ec;tx[ec]=x;ty[ec]=y;}
9 }P,A;
10 struct Hash_map{
11 int fir[m],tx[m],ty[m],ec,v[m],l[m];
12 int&find(int x,int y){
13 int r=hsh(x,y);
14 for(int i=fir[r];i;i=l[i])if(tx[i]==x&&ty[i]==y)return v[i];
15 l[++ec]=fir[r];fir[r]=ec;tx[ec]=x;ty[ec]=y;return v[ec];
16 }
17 }M;
18 int x[S],y[S],n,k,ans,p[S];
19 int chk(int X,int Y,int r=k){cerr<<X<<' '<<Y<<endl;
20 for(int i=1;i<=n&&r>=0;++i)if(!P.find(X-x[i],Y-y[i]))r--;
21 return r>=0;
22 }
23 int main(){
24 scanf("%d%d",&n,&k);
25 if(n<=k)return puts("-1"),0;
26 for(int i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]),p[i]=i,P.ins(x[i],y[i]);
27 if(n<=100){
28 for(int i=1;i<=n;++i)for(int j=i;j<=n;++j)if(!A.find(x[i]+x[j],y[i]+y[j])){
29 A.ins(x[i]+x[j],y[i]+y[j]);
30 ans+=chk(x[i]+x[j],y[i]+y[j]);
31 }return printf("%d\n",ans),0;
32 }
33 while(clock()<950000){
34 random_shuffle(p+1,p+1+n);
35 for(int i=1;i<=n;++i){
36 int a=i,b=p[i];
37 if(a>b)swap(a,b); if(A.find(a,b))continue; A.ins(a,b);
38 int&z=M.find(x[a]+x[b],y[a]+y[b]);
39 if(z==1)ans+=chk(x[a]+x[b],y[a]+y[b]); z++;
40 }
41 }printf("%d\n",ans);
42 }
View Code
正解的话，考虑任意定义一个偏序关系（横纵坐标啥的）然后前$k+1$个和后$k+1$个一定至少存在一个配对关系。枚举就完了。$O(k^2n)$
T2：小B的夏令营
大意：$n+2$层的，每层$m$个房间楼，除了顶层和底层，每一天，每一层的最左侧和最右侧的一个房间都有$\frca{a}{b}$的概率被摧毁。
求$k$天之后整个房子还是一个联通块的概率。$n,m \le 1500,k \le 10^5$
暴力$dp$的话，可以设$dp[i][l][r]$表示第$i$层$[l,r]$还没坏的概率。$O(n^5)$
可以直接前缀和优化。$O(n^3)$
观察转移式子可知我们不需要维护原值而只需要维护前缀和数组。$O(n^2)$
1 #include<cstdio>
2 const int mod=1e9+7,S=1555;
3 int f[S],F[S],L[S],R[S],FL[S],FR[S],n,m,k,p,q,fac[100005],inv[100005],l[S],r[S];
4 int qp(int b,int t,int a=1){for(;t;t>>=1,b=1ll*b*b%mod)if(t&1)a=1ll*a*b%mod;return a;}
5 int C(int b,int t){return 1ll*fac[b]*inv[t]%mod*inv[b-t]%mod;}
6 int mo(int a){return a>=mod?a-mod:a;}
7 int main(){
8 scanf("%d%d%d%d%d",&n,&m,&p,&q,&k);
9 for(int i=fac[0]=1;i<=k;++i)fac[i]=1ll*i*fac[i-1]%mod;
10 inv[k]=qp(fac[k],mod-2);
11 for(int i=k-1;~i;--i)inv[i]=inv[i+1]*(i+1ll)%mod;
12 p=1ll*p*qp(q,mod-2)%mod; q=mod+1-p;
13 for(int i=0;i<=m&&i<=k;++i)f[i]=C(k,i)*1ll*qp(p,i)%mod*qp(q,k-i)%mod;
14 F[0]=f[0];
15 for(int i=1;i<=m;++i)F[i]=mo(F[i-1]+f[i]);
16 R[m]=L[1]=1;
17 for(int i=1;i<=m;++i)FR[i]=(FR[i-1]+1ll*f[i-1]*mo(mod+R[m]-R[i-1]))%mod;
18 for(int i=m;i>=1;--i)FL[i]=(FL[i+1]+1ll*f[m-i]*mo(mod+L[1]-L[i+1]))%mod;
19 for(int _=1;_<=n;++_){
20 for(int i=1;i<=m;++i)r[i]=mo((r[i-1]-1ll*f[m-i]*L[i+1]%mod*F[i-1]+1ll*f[m-i]*FR[i])%mod+mod);
21 for(int i=m;i>=1;--i)l[i]=mo((l[i+1]-1ll*f[i-1]*R[i-1]%mod*F[m-i]+1ll*f[i-1]*FL[i])%mod+mod);
22 for(int i=1;i<=m;++i)L[i]=l[i],R[i]=r[i];
23 for(int i=1;i<=m;++i)FR[i]=(FR[i-1]+1ll*f[i-1]*mo(mod+R[m]-R[i-1]))%mod;
24 for(int i=m;i>=1;--i)FL[i]=(FL[i+1]+1ll*f[m-i]*mo(mod+L[1]-L[i+1]))%mod;
25 }printf("%d\n",R[m]);
26 }
View Code
T3：小B的图
大意：$n$个点，边带权，两张联通图$A,B$。$A$图的边每选一条要额外付出$x$代价。$B$图的边$-x$。
多次给定不同的$x$求最小生成树。$n \le 10^5,|A|,|B| \le 2 \times 10^5,-10^9 \le x,w_i \le 10^9$
首先，不管什么$x$，你选出的边一定要么是$A$的最小生成树边，要么是$B$的最小生成树边。
我们搞出$A$的最小生成树，把$B$的边从小到大依次加入替代$A$边。
每条边替换时我们能知道这条边在$ \ge x_0$时才会被替换。
排个序然后每次询问二分就行。
很开心这次$LCT$没有调太久。。。
1 #include<bits/stdc++.h>
2 using namespace std;
3 char in[23333333],*p=in;
4 void In(int&x){x=0;int f=0;while(*p<48||*p>57)f=*p++=='-';while(*p>47&&*p<58)x=x*10+*p++-48;x=f?-x:x;}
5 const int S=500005,inf=1e9+7;
6 #define ll long long
7 int n,A,B,q,X[S],g[S],oA[S],oB[S]; ll ans[S];
8 struct E{int a,b,k,u;friend bool operator<(E x,E y){return x.k<y.k;}}e[S],Xe[S];
9 bool cmp(E a,E b){return a.u<b.u;}
10 int find(int x){return x==g[x]?x:g[x]=find(g[x]);}
11
12 int v[S],vp[S],mx[S],c[S][2],f[S],lz[S],s[S];
13 #define lc c[p][0]
14 #define rc c[p][1]
15 bool nr(int p){return c[f[p]][0]==p||c[f[p]][1]==p;}
16 void rev(int p){lz[p]^=1;swap(lc,rc);}
17 void down(int p){if(lz[p])rev(lc),rev(rc),lz[p]=0;}
18 void up(int p){mx[vp[p]=p]=v[p];for(int i=0;i<2;++i)if(mx[c[p][i]]>mx[p])mx[p]=mx[c[p][i]],vp[p]=vp[c[p][i]];}
19 void spin(int p){
20 int F=f[p],G=f[F],D=c[F][1]==p,B=c[p][!D];
21 if(nr(F))c[G][c[G][1]==F]=p; c[p][!D]=F; c[F][D]=B;
22 f[f[f[B]=F]=p]=G; up(F);
23 }
24 void push(int p){if(nr(p))push(f[p]);down(p);}
25 void splay(int p){push(p);for(;nr(p);spin(p)); up(p);}
26 void access(int r){for(int p=r,y=0;p;p=f[y=p])splay(p),rc=y,up(p);splay(r);}
27 void make(int p){access(p);rev(p);}
28 void link(int a,int b){make(a);f[a]=b;}
29 void split(int a,int b){make(a);access(b);}
30 void cut(int a,int b){split(a,b);f[a]=c[b][0]=0;up(b);}
31
32 int main(){
33 fread(in,1,23333333,stdin);
34 In(n);In(A);In(B);In(q); mx[0]=-inf;
35 for(int i=1;i<=A;++i)In(e[i].a),In(e[i].b),In(e[i].k);
36 sort(e+1,e+1+A);
37 for(int i=1;i<=n;++i)g[i]=i,v[i]=-1e9;
38 for(int i=1;i<=A;++i){
39 int x=find(e[i].a),y=find(e[i].b);
40 if(x==y)continue;
41 g[x]=y; ans[0]+=e[i].k;
42 v[i+n]=e[i].k; link(oA[i+n]=e[i].a,i+n); link(i+n,oB[i+n]=e[i].b);
43 }
44 for(int i=1;i<=B;++i)In(e[i].a),In(e[i].b),In(e[i].k);
45 sort(e+1,e+1+B);
46 for(int i=1;i<=n;++i)g[i]=i;
47 for(int i=1,z=0;i<=B;++i){
48 int x=find(e[i].a),y=find(e[i].b);
49 if(x==y)continue;
50 g[x]=y; split(e[i].a,e[i].b); int _=vp[e[i].b];
51 e[i].u=e[i].k-v[_]; Xe[++z]=e[i];
52 cut(oA[_],_); cut(oB[_],_); link(e[i].a,e[i].b);
53 }
54 sort(Xe+1,Xe+n,cmp);
55 for(int i=1;i<n;++i)X[i]=(Xe[i].u+1)/2,ans[i]=ans[i-1]+Xe[i].u;
56 for(int _=1,x;_<=q;++_){
57 In(x); int c=upper_bound(X+1,X+n,x)-X-1;
58 printf("%lld\n",ans[c]-1ll*c*x+1ll*(n-1-c)*x);
59 }
60 }
View Code