2023大联盟2比赛总结

比赛链接

反思

T1

奇怪的贪心和构造题一直是我的软肋部分

T2

简单题

T3

也不难

T4

套路没学过，感觉还是太菜了

题解

A

考虑先给图随便染色，然后调整
因为每个点的度数为 $3$，所以如果有 $x\to u\to v$ 的颜色全部相同，那么修改 $u$ 的颜色一定能使 $u$ 符合条件，然后就用队列存储调整的点，一直调整即可
估算一下时间复杂度是 $O(n)$ 级别的，肯定不会调整很多次

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=200100;
int col[N],deg[N];
bool inq[N];
vector<int> G[N];
queue<int> que;
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
void upd(int x){deg[x]=0;for(int v:G[x]) if(col[v]==col[x]) deg[x]++;if(deg[x]>=2&&!inq[x]) inq[x]=1,que.push(x);
}
void work(){int n=read(),m=read();while(!que.empty()) que.pop();for(int i=1;i<=n;i++) G[i].clear(),inq[i]=0;for(int i=1;i<=m;i++){int x=read(),y=read();G[x].pb(y),G[y].pb(x);}for(int i=1;i<=n;i++) col[i]=0;for(int i=1;i<=n;i++) upd(i);int cnt=0;while(!que.empty()){int u=que.front();que.pop();inq[u]=0;if(deg[u]<2) continue;cnt++;if(cnt>m) break;col[u]^=1;upd(u);for(int v:G[u]) upd(v);}if(!que.empty()) puts("GG");else{for(int i=1;i<=n;i++) printf("%d ",col[i]);puts("");return;}
}
int main(){freopen("classical.in","r",stdin);freopen("classical.out","w",stdout);int T=read();while(T--) work();fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

B

感觉这才是本场比赛的签到题
可以发现操作类似冒泡排序，然后手玩一下样例发现答案为逆序对数
无解情况判一下奇偶性即可
时间复杂度 $O(nlogn)$

#include <bits/stdc++.h>
#define lowbit(x) x&-x
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N=1000100;
int n,p[N],tr[N],a[2][N],b[2][N];
pii pos[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
void add(int x){ for(;x<=n;x+=lowbit(x)) tr[x]++;}
int ask(int x){int res=0;for(;x;x-=lowbit(x)) res+=tr[x];return res;
}
int main(){freopen("rotate.in","r",stdin);freopen("rotate.out","w",stdout);n=read();for(int i=1;i<=n;i++) a[0][i]=read();for(int i=1;i<=n;i++) a[1][i]=read();for(int i=1;i<=n;i++) b[0][i]=read();for(int i=1;i<=n;i++) b[1][i]=read();for(int i=1;i<=n;i++) pos[b[0][i]]={0,i},pos[b[1][i]]={1,i};//check -1for(int i=1;i<=n;i++){int x=a[0][i];if(!pos[x].first&&pos[x].second==i) continue;if(((pos[x].first-i)&1)!=(pos[x].second&1)){ puts("-1");exit(0);}}for(int i=1;i<=n;i++) p[i]=pos[a[0][i]].second;LL ans=0;for(int i=n;i>=1;i--) ans+=ask(p[i]),add(p[i]);printf("%lld\n",ans);fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

C

这道题最重要的想法是：分治
考虑对于左上角 $(x_1,y_1)$，右下角 $(x_2,y_2)$ 的矩形求出覆盖矩形内所有 $1$ 的方案数，这可以枚举行和列的分割线，递归下去求解
时间复杂度 $O(n^5)$，需要加一些剪枝就能卡过去了

#include <bits/stdc++.h>
using namespace std;
bool Mbe;
const int N=65;
int n,s[N][N],f[N][N][N][N];
bool a[N][N];
char str[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
inline void chkmin(int &x,int y){ if(y<x) x=y;}
int calc(int lx,int ly,int rx,int ry){ return s[rx][ry]-s[lx-1][ry]-s[rx][ly-1]+s[lx-1][ly-1];}
int solve(int lx,int ly,int rx,int ry){auto &t=f[lx][ly][rx][ry];if(t!=-1) return t;if(!calc(lx,ly,rx,ry)){ t=0;return 0;}if(rx-lx+1<ry-ly+1){bool flg=1;for(int i=ly;i<=ry;i++) if(!calc(lx,i,rx,i)){ flg=0;break;}if(flg){ t=ry-ly+1;return t;}}else{bool flg=1;for(int i=lx;i<=rx;i++) if(!calc(i,ly,i,ry)){ flg=0;break;}if(flg){ t=rx-lx+1;return t;}}t=max(rx-lx+1,ry-ly+1);//枚举分割线for(int i=lx;i<rx;i++){int tmp=solve(lx,ly,i,ry);if(tmp<t) chkmin(t,tmp+solve(i+1,ly,rx,ry));}for(int j=ly;j<ry;j++){int tmp=solve(lx,ly,rx,j);if(tmp<t) chkmin(t,tmp+solve(lx,j+1,rx,ry));}return t;
}
bool Med;
int main(){freopen("detection.in","r",stdin);freopen("detection.out","w",stdout);// fprintf(stderr,"%.3lf MB\n",(&Mbe-&Med)/1048576.0);n=read();for(int i=1;i<=n;i++){scanf("%s",str+1);for(int j=1;j<=n;j++) a[i][j]=str[j]=='T';}for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];memset(f,-1,sizeof(f));printf("%d\n",solve(1,1,n,n));fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}

D

感觉是套路题
首先 $O(n^2)$ 的树形 $dp$ 是好做的
考虑 $k=1$ 的部分分，这一部分有一个经典的想法：考虑答案即为 $\prod si{z}_{每一个联通快}$，直接做仍是 $O(n^2)$ 的，重要：考虑它的组合意义，即为在每个连通块内选一个点的方案数，这个可以令 $f_{i,0/1}$ 表示 $i$ 所在的连通块是否选过点的方案和，时间复杂度 $O(n)$，期望得分 $50pts$

考虑一步转化是： $s^k=\sum _{i=0}^k\left\{\genfrac{}{}{0ex}{}{k}{i}\right\}{s}^{\underline{i}}=\sum _{i=0}^k\left\{\genfrac{}{}{0ex}{}{k}{i}\right\}\left(\genfrac{}{}{0ex}{}{s}{i}\right)i!$
考虑 $\left\{\genfrac{}{}{0ex}{}{k}{i}\right\}$ 和 $i!$ 都是好算的，主要是 $\left(\genfrac{}{}{0ex}{}{s}{i}\right)$，这个可以根据组合意义用 $dp$ 计算，即令 $f_{i,j}$ 为 $i$ 的联通快内选 $j$ 个点的方案和，但 $j\le k$，所以时间复杂度 $O(nk)$

#include <bits/stdc++.h>
using namespace std;
const int N=100100,K=110,P=1e9+7;
int n,m,fac[K],siz[N],t[K];
int e[N],ne[N],h[N],idx;
int stir2[K][K];
int f[N][K],g[N];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
void dfs(int u){f[u][0]=f[u][1]=1,siz[u]=1;for(int i=h[u];~i;i=ne[i]){int v=e[i];dfs(v);for(int j=0;j<=min(m,siz[u]+siz[v]);j++) t[j]=0;for(int j=0;j<=siz[u];j++) t[j]=1ll*f[u][j]*g[v]%P;// for(int j=0;j<=m;j++) cout<<t[j]<<' ';cout<<'\n';for(int j=0;j<=siz[u];j++) for(int k=0;k<=min(siz[v],m-j);k++)t[j+k]=(t[j+k]+1ll*f[u][j]*f[v][k])%P;siz[u]=min(m,siz[u]+siz[v]);for(int j=0;j<=siz[u];j++) f[u][j]=t[j];}for(int i=0;i<=m;i++) g[u]=(g[u]+1ll*stir2[m][i]*fac[i]%P*f[u][i])%P;
}
int main(){freopen("calc.in","r",stdin);freopen("calc.out","w",stdout);n=read(),m=read();stir2[0][0]=1;for(int i=1;i<=m;i++)for(int j=1;j<=i;j++) stir2[i][j]=(stir2[i-1][j-1]+1ll*j*stir2[i-1][j])%P;fac[0]=1;for(int i=1;i<=m;i++) fac[i]=1ll*fac[i-1]*i%P;memset(h,-1,sizeof(h));for(int i=2;i<=n;i++) add(read(),i);dfs(1);printf("%d\n",g[1]);fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}