每日 Ad-hoc
P11022 「LAOI-6」Yet Another Graph Coloration Problem
我们考虑进行DFS生成树。
那么生成完后，每任意两点之间必定存在一条简单路径。
那么当此时，有一条非树边，则这个边所连的其中一个点的所有子树都存在到其他点的第二条路径。（即一条全走树边，一条走过这条非树边）
按照这个思路处理即可。
//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=2e5+10;
int n,m,sum[N];
bool vis[N],col[N],ans;
vector <int> g[N];
void dfs (int u,int fa) {
vis[u]=1;
for (int v:g[u]) {
if (v==fa) continue;
if (vis[v]) {
if (!ans) {
ans=1;
col[u]=1;
}
}
else {
dfs(v,u);
}
}
}
void dfscolor (int u,int cl) {
vis[u]=1;
col[u]=(col[u]||cl);
for (int v:g[u]) {
if (!vis[v]) dfscolor(v,col[u]);
}
}
signed main() {
Cios;
int T;
cin>>T;
while (T--) {
cin>>n>>m;
for (int i=1;i<=n;i++) {
g[i].clear();
vis[i]=0;
col[i]=0;
ans=0;
}
for (int i=1;i<=m;i++) {
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
bool fl=0;
for (int i=1;i<=n;i++) {
if (vis[i]==0||ans==0) {
fl=1;
cout<<"-1\n";
break;
}
}
if (fl) continue;
for (int i=1;i<=n;i++) vis[i]=0;
dfscolor(1,0);
for (int i=1;i<=n;i++) cout<<"WB"[col[i]];
cout<<"\n";
}
return 0;
}容斥原理
容斥原理，小学二年级都学过。
设 中有 种不同的属性，第 种属性称为 ，拥有属性 的几何记为 ，则：
P5664 [CSP-S 2019] Emiya 家今天的饭
//hanser!!!!!!!
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define int long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
intc N=105,M=2005,mod=998244353;
int n,m,a[N][M],sum[N],g[N][N],dp[N][2*N];
signed main() {
Cios;
cin>>n>>m;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) cin>>a[i][j],(sum[i]+=a[i][j])%=mod;
}
g[0][0]=1;
for (int i=1;i<=n;i++) {
g[i][0]=g[i-1][0];
for (int j=1;j<=n;j++) g[i][j]=(g[i-1][j]+g[i-1][j-1]*sum[i]%mod)%mod;
}
int res=0;
for (int l=1;l<=m;l++) {
memset(dp,0,sizeof dp);
dp[0][n]=1;
for (int i=1;i<=n;i++) {
for (int t=n-i;t<=n+i;t++) {
dp[i][t]=((dp[i-1][t]+dp[i-1][t+1]*(sum[i]-a[i][l]))%mod+dp[i-1][t-1]*a[i][l]%mod)%mod;
}
}
for (int i=1;i<=n;i++) res=(res+dp[n][n+i])%mod;
}
int ans=0;
for (int i=1;i<=n;i++) ans=(ans+g[n][i])%mod;
cout<<(ans-res+mod)%mod;
return 0;
}
评论（0）
暂无评论