总结
前面三位 \(AK\) 大佬
这一套题的难度确实不高，仔细想一下每一道题应该都是能做出来的
但是 \(T1\) 一个 \(lct\) 的板子调了 \(3\) 个小时实在是说不过去
后面两道题没有时间思考，只能打暴力
所以板子打熟很重要
A. 选择
分析
\(lct\) 维护双联通分量
和长跑那道题挺像的
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<map>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
struct DSU{
int fa[maxn];
void init(){
for(rg int i=1;i<maxn;i++) fa[i]=i;
}
int zhao(rg int xx){
if(fa[xx]==xx) return xx;
return fa[xx]=zhao(fa[xx]);
}
}dsu;
struct LCT{
int rev[maxn],ch[maxn][2],fa[maxn],sta[maxn],tp;
void push_down(rg int da){
if(rev[da]==0) return;
rg int lc=ch[da][0],rc=ch[da][1];
rev[lc]^=1,rev[rc]^=1,rev[da]^=1;
std::swap(ch[da][0],ch[da][1]);
}
bool isroot(rg int da){
return ch[fa[da]][0]!=da&&ch[fa[da]][1]!=da;
}
void xuanzh(rg int x){
rg int y=fa[x];
rg int z=fa[y];
rg int k=(ch[y][1]==x);
if(!isroot(y)) ch[z][ch[z][1]==y]=x;
fa[x]=z;
ch[y][k]=ch[x][k^1];
fa[ch[x][k^1]]=y;
ch[x][k^1]=y;
fa[y]=x;
}
void splay(rg int x){
sta[tp=1]=x;
for(rg int i=x;!isroot(i);i=fa[i]) sta[++tp]=fa[i];
for(rg int i=tp;i>=1;i--) push_down(sta[i]);
while(!isroot(x)){
rg int y=fa[x];
rg int z=fa[y];
if(!isroot(y)){
(ch[y][1]==x)^(ch[z][1]==y)?xuanzh(x):xuanzh(y);
}
xuanzh(x);
}
}
void access(rg int x){
for(rg int y=0;x;y=x,x=dsu.zhao(fa[x])){
splay(x);
ch[x][1]=y;
fa[y]=x;
}
}
void makeroot(rg int x){
access(x);
splay(x);
rev[x]^=1;
push_down(x);
}
int findroot(rg int x){
access(x);
splay(x);
push_down(x);
while(ch[x][0]){
x=ch[x][0];
push_down(x);
}
splay(x);
return x;
}
void split(rg int x,rg int y){
makeroot(x);
access(y);
splay(y);
}
void link(rg int x,rg int y){
makeroot(x);
fa[x]=y;
}
void dfs(rg int now,rg int rt){
dsu.fa[now]=rt;
if(ch[now][0]) dfs(ch[now][0],rt);
if(ch[now][1]) dfs(ch[now][1],rt);
}
void ad(rg int x,rg int y){
x=dsu.zhao(x),y=dsu.zhao(y);
if(x==y) return;
if(findroot(x)!=findroot(y)){
link(x,y);
} else {
split(x,y);
dfs(y,y);
}
}
}lct;
int n,m,q,x[maxn],y[maxn];
int op[maxn],op1[maxn],op2[maxn],jud[maxn],ans[maxn];
std::map<std::pair<int,int>,int> mp;
int main(){
n=read(),m=read(),q=read();
for(rg int i=1;i<=m;i++){
x[i]=read(),y[i]=read();
if(x[i]>y[i]) std::swap(x[i],y[i]);
mp[std::make_pair(x[i],y[i])]=i;
}
rg char ch;
for(rg int i=1;i<=q;i++){
scanf(" %c",&ch);
op1[i]=read(),op2[i]=read();
if(op1[i]>op2[i]) std::swap(op1[i],op2[i]);
if(ch=='Z'){
op[i]=1;
jud[mp[std::make_pair(op1[i],op2[i])]]=1;
op1[i]=mp[std::make_pair(op1[i],op2[i])];
} else {
op[i]=2;
}
}
dsu.init();
for(rg int i=1;i<=m;i++){
if(!jud[i]){
lct.ad(x[i],y[i]);
}
}
for(rg int i=q;i>=1;i--){
if(op[i]==1){
lct.ad(x[op1[i]],y[op1[i]]);
} else {
if(dsu.zhao(op1[i])==dsu.zhao(op2[i])) ans[i]=1;
}
}
for(rg int i=1;i<=q;i++){
if(op[i]==2){
if(ans[i]) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
B. 三元组
分析
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e6+5,mod=1e9+7;
inline int addmod(rg int now1,rg int now2){
return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int mulmod(rg long long now1,rg int now2){
return now1*=now2,now1>=mod?now1%mod:now1;
}
int t,n,ans,suml[maxn],sumr[maxn],m,cfl1[maxn],cfl2[maxn],cfr1[maxn],cfr2[maxn],f[maxn];
char s1[maxn],s[maxn];
void adl(rg int l,rg int r,rg int a0,rg int d){
cfl1[l+1]=addmod(cfl1[l+1],d);
cfl1[r+1]=addmod(cfl1[r+1],mod-d);
cfl2[l]=addmod(cfl2[l],a0);
cfl2[r+1]=addmod(cfl2[r+1],mod-a0);
cfl2[r+1]=addmod(cfl2[r+1],mod-mulmod(r-l,d));
}
void adr(rg int l,rg int r,rg int a0,rg int d){
cfr1[l+1]=addmod(cfr1[l+1],d);
cfr1[r+1]=addmod(cfr1[r+1],mod-d);
cfr2[l]=addmod(cfr2[l],a0);
cfr2[r+1]=addmod(cfr2[r+1],mod-a0);
cfr2[r+1]=addmod(cfr2[r+1],mod-mulmod(r-l,d));
}
void solve(){
memset(suml,0,sizeof(suml));
memset(sumr,0,sizeof(sumr));
memset(f,0,sizeof(f));
memset(cfl1,0,sizeof(cfl1));
memset(cfl2,0,sizeof(cfl2));
memset(cfr1,0,sizeof(cfr1));
memset(cfr2,0,sizeof(cfr2));
ans=0;
m=n*2+1;
s[0]='$';
for(rg int i=1;i<=m;i++){
if(i&1) s[i]='#';
else s[i]=s1[i>>1];
}
for(rg int i=1,mids=0,r=0;i<=m;i++){
if(i<=r) f[i]=std::min(f[2*mids-i],r-i+1);
while(s[i+f[i]]==s[i-f[i]]) f[i]++;
if(i+f[i]-1>r) r=i+f[i]-1,mids=i;
}
for(rg int i=1;i<=m;i++) f[i]--;
for(rg int i=1;i<=m;i++){
if(!f[i]) continue;
if(i&1){
adl(i/2+1,i/2+1+f[i]/2-1,i/2,mod-1);
adr(i/2-f[i]/2+1,i/2,i/2+f[i]/2,mod-1);
} else {
if(f[i]>1){
adl(i/2+1,i/2+f[i]/2,i/2-1,mod-1);
adr(i/2-(f[i]/2),i/2-1,i/2+f[i]/2,mod-1);
}
}
}
for(rg int i=1;i<=n;i++) cfl1[i]=addmod(cfl1[i-1],cfl1[i]),cfr1[i]=addmod(cfr1[i-1],cfr1[i]);
for(rg int i=1;i<=n;i++) cfl2[i]=addmod(cfl2[i],cfl1[i]),cfr2[i]=addmod(cfr2[i],cfr1[i]);
for(rg int i=1;i<=n;i++) cfl2[i]=addmod(cfl2[i-1],cfl2[i]),cfr2[i]=addmod(cfr2[i-1],cfr2[i]);
for(rg int i=1;i<=n;i++) cfl2[i]=addmod(cfl2[i],i),cfr2[i]=addmod(cfr2[i],i);
for(rg int i=1;i<n;i++) ans=addmod(ans,mulmod(cfl2[i],cfr2[i+1]));
printf("%d\n",ans);
}
int main(){
t=read();
while(t--){
scanf("%s",s1+1);
n=strlen(s1+1);
solve();
}
return 0;
}
C. 最有价值
分析
最大权闭合子图
先把所有的贡献加起来
对于每一组 \((i,j)\) 新开一个点
由源点向这个点连收益为 \(w_{i,j}+w_{j,i}\) 的点
由这个点向 \(i\) 代表的点和 \(j\) 代表的点连无穷大的边，表示强制选
由每一个位置向它所属的数字连无穷大的边，代表强制选数字
向汇点连边权为 \(a[i]\) 的边
由每一种数字向汇点连边权为 \(b[i]-a[i]\) 的边
用总贡献减去最小割就行了
代码
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
#include<map>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=2e4+5,maxm=105;
int h[maxn],h2[maxn],tot=2,s,t,n,m,w[maxm][maxm];
struct asd{
int to,nxt,val;
}b[maxn*20];
void ad(rg int aa,rg int bb,rg int cc){
b[tot].to=bb;
b[tot].nxt=h[aa];
b[tot].val=cc;
h[aa]=tot++;
}
int q[maxn],head,tail,dep[maxn],mmax;
bool bfs(){
for(rg int i=1;i<=mmax;i++){
h[i]=h2[i];
dep[i]=0;
}
q[head=tail=1]=s;
dep[s]=1;
while(head<=tail){
rg int now=q[head++];
for(rg int i=h[now];i!=-1;i=b[i].nxt){
rg int u=b[i].to;
if(b[i].val && !dep[u]){
dep[u]=dep[now]+1;
q[++tail]=u;
}
}
}
return dep[t]!=0;
}
int dfs(rg int now,rg int ac1){
if(now==t) return ac1;
rg int ac2=0;
for(rg int i=h[now];i!=-1;i=b[i].nxt){
h[now]=i;
rg int u=b[i].to;
if(b[i].val && dep[u]==dep[now]+1){
rg int nans=dfs(u,std::min(b[i].val,ac1));
b[i].val-=nans;
b[i^1].val+=nans;
ac1-=nans;
ac2+=nans;
}
if(ac1==0) break;
}
if(ac2==0) dep[now]=0;
return ac2;
}
int ans=0,T,wa[maxn],wb[maxn];
char ss[maxn];
int main(){
T=read();
while(T--){
memset(h,-1,sizeof(h));
tot=2,ans=0;
n=read();
scanf("%s",ss+1);
s=1,t=2,mmax=n+2;
for(rg int i=0;i<=9;i++) wa[i]=read(),wb[i]=read();
for(rg int i=1;i<=n;i++){
for(rg int j=1;j<=n;j++){
w[i][j]=read();
if(i!=j) ans+=w[i][j];
}
}
for(rg int i=1;i<=n;i++){
ad(i+2,ss[i]-'0'+1+mmax,0x3f3f3f3f);
ad(ss[i]-'0'+1+mmax,i+2,0);
}
for(rg int i=0;i<=9;i++){
ad(i+1+mmax,t,wb[i]-wa[i]);
ad(t,i+1+mmax,0);
}
for(rg int i=1;i<=n;i++){
ad(i+2,t,wa[ss[i]-'0']);
ad(t,i+2,0);
}
mmax+=10;
for(rg int i=1;i<=n;i++){
for(rg int j=i+1;j<=n;j++){
mmax++;
ad(s,mmax,w[i][j]+w[j][i]);
ad(mmax,s,0);
ad(mmax,i+2,0x3f3f3f3f);
ad(i+2,mmax,0);
ad(mmax,j+2,0x3f3f3f3f);
ad(j+2,mmax,0);
}
}
for(rg int i=1;i<=mmax;i++) h2[i]=h[i];
while(bfs()) ans-=dfs(s,0x3f3f3f3f);
printf("%d\n",ans);
}
return 0;
}