题意
给定一棵树，保证每个点的度数都是奇数。对树上的结点进行黑白染色。现给出目标颜色序列，要求找到一个初始颜色序列，使得经一次操作后得到目标颜色序列。
操作定义为：对每个结点，记目标颜色为与它相邻的结点中超过半数所具有的颜色。将所有结点的颜色同时修改为目标颜色。
题解
从特殊情况入手。考虑叶子结点和它的父亲。显然，具有相同父亲的叶子结点必然有相同的目标颜色。并且它们要求父亲的初始颜色即为它们的目标颜色。而它们的初始颜色显然取与父亲的目标颜色相同更优。（因为它们没有孩子，不会对孩子产生影响）
于是我们得到了这样一个贪心策略：进行dfs。对于一个结点，如果它的子结点中两种颜色相等，那么它要求父结点的初始颜色与它的目标颜色一致。而如果它的颜色没有被子结点要求，那么就取父结点的目标颜色。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
vector<int> g[maxn];
char tag[maxn],ans[maxn];
bool ok=1;
void dfs(int u,int fa)
{
int cnt0=0,cnt1=0;
for(auto v:g[u])
{
if(v==fa) continue;
dfs(v,u);
if(ans[v]!=tag[u]) cnt0++;
else cnt1++;
}
if(cnt0>cnt1) ok=0;
else if(cnt0==cnt1)
{
if(!ans[fa]) ans[fa]=tag[u];
else
{
if(ans[fa]!=tag[u]) ok=0;
}
}
if(!ans[u])
{
if(fa) ans[u]=tag[fa];
else ans[u]='B';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
ok=1;
for(int i=1;i<=n;i++) ans[i]=0,g[i].clear();
for(int i=1;i<n;i++)
{
int u,v;cin>>u>>v;
g[u].push_back(v),g[v].push_back(u);
}
for(int i=1;i<=n;i++) cin>>tag[i];
dfs(1,0);
if(!ok) cout<<-1<<'\n';
else
{
for(int i=1;i<=n;i++) cout<<ans[i];
cout<<'\n';
}
}
return 0;
}
|
题意
定义图的密度为边数与点数之比。要求构造一张密度为 D 的图，满足其任意导出子图的密度均小于 D。
题解
考虑完全图，可以得到图的密度的上界 D≤⌊2n−1⌋。对于满足该限制的 D，我们总可以构造出合法的图。具体做法是：将编号距离为 1,2,⋯,D 的点两两连边。然后就做完了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,d;cin>>n>>d;
if(d>(n-1)/2) cout<<"No"<<'\n';
else
{
cout<<"Yes"<<'\n';
for(int i=1;i<=d;i++)
for(int j=1;j<=n;j++)
cout<<j<<' '<<(j+i-1)%n+1<<'\n';
}
return 0;
}
|
题意
给出一张图，保证每个点的度数均为 3。对图上的结点进行黑白染色。要求构造一个目标颜色序列，使得不存在一个初始颜色序列，可以经一次操作得到该目标颜色序列。
操作定义为：对每个结点，记目标颜色为与它相邻的结点中超过半数所具有的颜色。将所有结点的颜色同时修改为目标颜色。
题解
直观的感受是，很多目标颜色序列都无法得到。所以我们可以采用随机化，然后用2-sat进行检验。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <bits/stdc++.h>
using namespace std;
const int maxn=50005;
vector<int> g0[maxn];
int ans[maxn];
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int rd(int l,int r) {return rnd()%(r-l+1)+l;}
int cnt,head[2*maxn];
struct Edge
{
int to,nxt;
}e[6*maxn];
void add(int u,int v)
{
e[++cnt]={v,head[u]};
head[u]=cnt;
}
int dfn[2*maxn],low[2*maxn],dfncnt,stk[2*maxn],instk[2*maxn],tp;
int scc[2*maxn],sc;
void tarjan(int u)
{
low[u]=dfn[u]=++dfncnt,stk[++tp]=u,instk[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if (!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(instk[v])
low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
sc++;
while(stk[tp]!=u)
{
scc[stk[tp]]=sc;
instk[stk[tp]]=0;
tp--;
}
scc[stk[tp]]=sc;
instk[stk[tp]]=0;
tp--;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
for(int i=1;i<=n;i++) g0[i].clear();
for(int i=1;i<=3*n/2;i++)
{
int u,v;cin>>u>>v;
g0[u].push_back(v),g0[v].push_back(u);
}
bool ok=0;
while(1)
{
cnt=dfncnt=tp=sc=0;
for(int i=1;i<=2*n;i++) head[i]=dfn[i]=low[i]=stk[i]=instk[i]=scc[i]=0;
for(int i=1;i<=n;i++) ans[i]=rd(0,1);
for(int i=1;i<=n;i++)
{
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
if(j!=k)
{
if(ans[i]) add(g0[i][j],g0[i][k]+n);
else add(g0[i][j]+n,g0[i][k]);
}
}
for(int i=1;i<=2*n;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;i++)
{
if(scc[i]==scc[i+n])
{
ok=1;
break;
}
}
if(ok)
{
for(int i=1;i<=n;i++)
if(ans[i]) cout<<'B';
else cout<<'W';
cout<<'\n';
break;
}
}
}
return 0;
}
|