这场真的是减压赛，真水
A
超简单的组合数问题，把[1,n]每个数单独考虑，然后选取比它大的就行，其他随意排列。
#include<bits/stdc++.h> using namespace std; const int N=5005,mod=998244353; int n,ans,fac[N*N],inv[N*N]; int qpow(int a,int b) { int ret=1; while(b) { if(b&1)ret=1ll*ret*a%mod; a=1ll*a*a%mod,b>>=1; } return ret; } int C(int a,int b){return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;} int main() { int T;scanf("%d",&T); fac[0]=1;for(int i=1;i<=5000*5000;i++)fac[i]=1ll*fac[i-1]*i%mod; inv[5000*5000]=qpow(fac[5000*5000],mod-2); for(int i=5000*5000;i;i--)inv[i-1]=1ll*inv[i]*i%mod; while(T--) { scanf("%d",&n); ans=0; for(int i=1;i<=n;i++)ans=(ans+1ll*C(n*n-i,n-1)%mod*fac[n]%mod*fac[n*n-n]%mod*n)%mod; printf("%d ",ans); } }
C
树形DP，f[i][0/1/2]表示没选这个点/选了这个点但是它的儿子一个都没选/选了这个点且至少选了一个儿子，直接转移即可
#include<bits/stdc++.h> using namespace std; const int N=1e5+7,mod=998244353; int n,f[N][3]; vector<int>G[N]; void dp(int u,int fa) { int p1=1,p2=1,p3=1; for(int i=0;i<G[u].size();i++) if(G[u][i]!=fa) { dp(G[u][i],u); p1=1ll*p1*(f[G[u][i]][0]+f[G[u][i]][2])%mod; p2=1ll*p2*f[G[u][i]][0]%mod; p3=1ll*p3*(1ll*f[G[u][i]][0]+f[G[u][i]][1]+f[G[u][i]][2])%mod; } f[u][0]=p1,f[u][1]=p2,f[u][2]=(p3-p2+mod)%mod; } int main() { int T;scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++)G[i].clear(); for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),G[x].push_back(y),G[y].push_back(x); dp(1,0); int ans=(f[1][0]+f[1][2])%mod; printf("%d ",ans); } }
D
发现lowbit操作最多操作31次后，就变成了*2，打个标记即可，类似于区间开根号那题，代码略。
E
过于签到
H
比较有意思的构造题，首先可以想到如果该位置是1，进行DRUL回到原点，答案就是(1*2+2)/2-2=0，然后对0进行DRU可以变成(0*2+2)/2=1，并向右平移一位，然后如果是0那么D以后也是0。
这样偶数的情况很好处理，把它拆分成若干二进制位，先一直右移到距离最后一列为二进制位是1的个数。然后就是二进制加乘了。
算下步数，最多是100*7+100=800步
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n; ll k; int main() { int T; scanf("%d%d",&T,&n); while(T--) { scanf("%lld",&k); if(k&1){puts("-1");continue;} int num=0; for(int i=1;i<=53;i++)if(k&(1ll<<i))++num; int nx=1,ny=1; printf("DRUL"); while(n-nx>num)printf("DRUDRUL"),++nx; while(n-ny>=53)printf("D"),++ny; for(int i=53;i>=2;i--) { if(k&(1ll<<i))printf("R"),++nx; printf("D"),++ny; } if(k&2)printf("R"),++nx; puts(""); } }
I
过于签到
#include<bits/stdc++.h> using namespace std; int n,p,c[8]={0,7,27,41,49,63,78,108}; int main() { int T;scanf("%d",&T); while(T--) { scanf("%d",&n); int tot=0; for(int i=1,x;i<=n;i++)scanf("%d",&x),tot+=c[x]; if(tot>=120)tot-=50; else if(tot>=89)tot-=30; else if(tot>=69)tot-=15; printf("%d ",tot); } }
K
简单的离线问题，把边按边权从大到小排序，询问也从大到小，这样从大到小依次加边，边加边计算答案
#include<bits/stdc++.h> using namespace std; const int N=2e5+7,mod=998244353; struct node{int id,p;}q[N]; struct edge{int x,y,z;}e[N]; int n,m,Q,sz[N],fa[N]; long long ret,ans[N]; bool emp(edge a,edge b){return a.z>b.z;} bool qmp(node a,node b){return a.p>b.p;} int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} int main() { int T;scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&Q); ret=0; for(int i=1;i<=n;i++)sz[i]=1,fa[i]=i; for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z); sort(e+1,e+m+1,emp); for(int i=1;i<=Q;i++)scanf("%d",&q[i].p),q[i].id=i; sort(q+1,q+Q+1,qmp); for(int i=1,j=0;i<=Q;i++) { while(j<m&&e[j+1].z>=q[i].p) { ++j; int x=find(e[j].x),y=find(e[j].y); if(x!=y) { ret-=1ll*sz[x]*(sz[x]-1)/2+1ll*sz[y]*(sz[y]-1)/2; sz[x]+=sz[y],fa[y]=x; ret+=1ll*sz[x]*(sz[x]-1)/2; } } ans[q[i].id]=ret; } for(int i=1;i<=Q;i++)printf("%lld ",ans[i]); } }
未完待续……