The 2023 ICPC Asia EC Regionals Online Contest (I)vp补题

两个半小时半场，赛时过ADL，J题没来的及想清楚队友先过了
原题连接

J

结论：C2和C1圆心曼哈顿距离-$\sqrt{2}{R}_2$
最小点到C1所有点的期望证明过程：https://blog.csdn.net/qq_73631501/article/details/139090152

G 并查集 图

求概率，若要相连的点集内有$d_1,d_2$个点，那么就有$d_1\cdot d_2$种连接可能

const int N=1e6+10,M=6e3+10,mod=998244353,inf=1e9;
int fa[N],sz[N];
vector<int>e[N];
int findf(int x){if(x==fa[x])return x;return fa[x]=findf(fa[x]);
}
void merge(int x,int y){int fx=findf(x),fy=findf(y);if(fx==fy)return;fa[fy]=fx;sz[fx]+=sz[fy];
}
int qpow(int x,int a){int res=1;while (a){if(a&1)res=res*x%mod;a>>=1;x=x*x%mod;}return res%mod;
}
struct dot
{int u,v;
};
int inv(int x){return qpow(x,mod-2)%mod;
}
void solve(){int n;cin>>n;vector<dot>a(n+1),b(n+1);forr(i,1,n){fa[i]=i;sz[i]=1;}forr(i,1,n-1){cin>>a[i].u>>a[i].v;// merge(a[i].u,a[i].v);}int ans=1;forr(i,1,n-1){cin>>b[i].u>>b[i].v;//记录目标生成树的结构e[b[i].u].push_back(b[i].v);e[b[i].v].push_back(b[i].u);// 一开始想用并查集记录连通块的情况来判断给定生成树是否能满足，但是wa12 // int fc=findf(b[i].u),fd=findf(b[i].v);// if(fc!=fd){//     ans=0;//     break;// }}if(ans==0)return cout<<ans<<endl,void();forr(i,1,n){fa[i]=i;sz[i]=1;}forr(i,1,n-1){       int fu=findf(a[i].u),fv=findf(a[i].v);ans=ans*sz[fu]%mod*sz[fv]%mod;//这里参考https://www.cnblogs.com/Qiansui/p/17709840.htmlif(e[fu].size()<e[fv].size())swap(fu,fv);//优化int cnt=0;for(auto x:e[fv]){if(findf(x)==fu)cnt++;//生成树的结构符合a的连接else e[fu].push_back(x);}if(cnt!=1)return cout<<0<<endl,void();//成环或者没连上就不可能merge(fu,fv);}// cout<<ans<<endl;ans=inv(ans);cout<<ans<<endl;
}

I 状压

const int mod=998244353;
//dp[滚动数组][本位置符号][大、小写、数字出现状态] st[]记录上一位置每一状态的贡献总数
int dp[2][128][8],st[8];
int now=0;
void update(int c){//状态转移int bt;if('A'<=c&&c<='Z')bt=1;if('a'<=c&&c<='z')bt=2;if('0'<=c&&c<='9')bt=4;forr(i,0,7){//本位置是c符号对所有状态进行更新dp[now][c][i|bt]+=st[i]-dp[now^1][c][i]+mod,dp[now][c][i|bt]%=mod;//相邻的不能重复，所以要减去上个状态的本字符}
}
void solve(){int n;cin>>n;dp[0][0][0]=1;//开始之前的状态：没有符号，000string s;cin>>s;s=' '+s+' ';forr(i,1,n){now^=1;//挪到本位置forr(j,0,7){st[j]=0;forr(k,0,127)st[j]=(st[j]+dp[now^1][k][j])%mod;//对每个符号进行遍历，记录上一个位置的状态数}//本位置更新memset(dp[now],0,sizeof dp[now]);if(s[i]=='?'){//枚举本位置可能出现的符号forr(j,'A','Z')update(j);forr(j,'a','z')update(j);forr(j,'0','9')update(j);}else if('a'<=s[i]&&s[i]<='z'){update(s[i]);update(s[i]+('A'-'a'));//也可能变成大写}else update(s[i]);}int ans=0;forr(i,0,127)ans+=dp[now][i][7],ans%=mod;//只计算三种字符都有的状态cout<<ans%mod<<endl;
}

K 计算几何苦手 学习中