则填充 ? 的一种方案合法当且仅当对于任意前缀均有
c
n
t
r
≥
c
n
r
e
≥
c
n
t
d
cnt_r \ge cnr_e \ge cnt_d
cntr≥cnre≥cntd，且对于整个字符串
c
n
t
r
=
c
n
t
e
=
c
n
t
d
cnt_r = cnt_e = cnt_d
cntr=cnte=cntd。
可转化对于任意前缀均有
c
n
t
e
≥
c
n
t
d
cnt_e \ge cnt_d
cnte≥cntd，对于任意后缀均有
c
n
t
e
≥
c
n
t
r
cnt_e \ge cnt_r
cnte≥cntr，同时限制
c
n
t
r
,
c
n
t
e
,
c
n
t
d
≤
n
cnt_r, cnt_e, cnt_d \le n
cntr,cnte,cntd≤n，最后将多余的 ? 从左到右贪心地填成 red 即可。
#includetemplate<classT>inlinevoidread(T &res){char ch;bool flag =false; res =0;while(ch =getchar(),!isdigit(ch)&& ch !='-');
ch =='-'? flag =true: res = ch ^48;while(ch =getchar(),isdigit(ch))
res = res *10+ ch -48;
flag ? res =-res :0;}template<classT>inlinevoidput(T x){if(x >9)put(x /10);putchar(x %10+48);}template<classT>inlinevoid_put(T x){if(x <0)
x =-x,putchar('-');put(x);}template<classT>inlinevoidCkMin(T &x, T y){x > y ? x = y :0;}template<classT>inlinevoidCkMax(T &x, T y){x < y ? x = y :0;}template<classT>inline T Min(T x, T y){return x < y ? x : y;}template<classT>inline T Max(T x, T y){return x > y ? x : y;}template<classT>inline T Abs(T x){return x <0?-x : x;}template<classT>inline T Sqr(T x){return x * x;}using std::map;using std::set;using std::pair;using std::bitset;using std::string;using std::vector;using std::complex;using std::multiset;using std::priority_queue;typedeflonglong ll;typedeflongdouble ld;typedef complex<ld> com;typedef set<int>::iterator it;const ld pi =acos(-1.0);const ld eps =1e-8;constint N =3e5+5;constint Maxn =1e9;constint Minn =-1e9;constint mod =998244353;int T_data, n, top;int stk[N], num[3], cnt[3];char s[N];inlinevoidadd(int&x,int y){
x += y;
x >= mod ? x -= mod :0;}inlinevoiddec(int&x,int y){
x -= y;
x <0? x += mod :0;}inlineinttag(char ch){if(ch =='r')return0;if(ch =='e')return1;return2;}intmain(){read(T_data);while(T_data--){scanf("%s", s +1);
n =strlen(s +1);
cnt[0]= cnt[1]= cnt[2]=0;for(int i =1; i <= n;++i)if(s[i]!='?')++cnt[tag(s[i])];if(Max(Max(cnt[0], cnt[1]), cnt[2])> n /3)puts("No");else{
num[0]= n /3- cnt[0];
num[1]= n /3- cnt[1];
num[2]= n /3- cnt[2];bool flag =false;
cnt[2]= cnt[1]= cnt[0]= top =0;for(int i =1; i <= n;++i)if(s[i]=='?')
stk[++top]= i;elseif(s[i]!='r'){++cnt[tag(s[i])];if(cnt[2]> cnt[1]){if(!top){
flag =true;break;}else{
s[stk[top--]]='e';--num[1];++cnt[1];}}}if(flag){puts("No");continue;}
cnt[2]= cnt[0]= cnt[1]= top =0;for(int i = n; i >=1;--i)if(s[i]=='?')
stk[++top]= i;elseif(s[i]!='d'){++cnt[tag(s[i])];if(cnt[0]> cnt[1]){if(!top){
flag =true;break;}else{
s[stk[top--]]='e';--num[1];++cnt[1];}}}if(flag){puts("No");continue;}for(int i =1; i <= n;++i)if(s[i]=='?'){if(num[0])--num[0], s[i]='r';elseif(num[1])--num[1], s[i]='e';elseif(num[2])--num[2], s[i]='d';else{
flag =true;break;}}if(num[0]+ num[1]+ num[2]>0|| flag){puts("No");continue;}
cnt[0]= cnt[1]= cnt[2]=0;for(int i =1; i <= n;++i){++cnt[tag(s[i])];if(cnt[0]< cnt[1]|| cnt[1]< cnt[2]){
flag =true;break;}}if(cnt[0]!= cnt[1]|| cnt[1]!= cnt[2]|| flag){puts("No");continue;}elseputs("Yes");}}return0;}
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
EK. Killer Sajin’s Matrix
题目大意
给定
n
×
m
n \times m
n×m 的网格，要求填入恰好
k
k
k 个 1，使得每行每列均有奇数个 1。
n
,
m
,
k
≤
1
0
5
n,m,k\le 10^5
n,m,k≤105。
题解
考虑若每行每列 1 的个数是确定的要怎样确定最终的方案。
不难想到贪心地让 1 的个数最多的行去匹配 1 的个数最多的列。
因为我们要让每一行去匹配不同的列，将行和列中 1 的个数尽量平均地分配显然不会更劣，直接贪心即可。
#includetemplate<classT>inlinevoidread(T &res){char ch;bool flag =false; res =0;while(ch =getchar(),!isdigit(ch)&& ch !='-');
ch =='-'? flag =true: res = ch ^48;while(ch =getchar(),isdigit(ch))
res = res *10+ ch -48;
flag ? res =-res :0;}template<classT>inlinevoidput(T x){if(x >9)put(x /10);putchar(x %10+48);}template<classT>inlinevoid_put(T x){if(x <0)
x =-x,putchar('-');put(x);}template<classT>inlinevoidCkMin(T &x, T y){x > y ? x = y :0;}template<classT>inlinevoidCkMax(T &x, T y){x < y ? x = y :0;}template<classT>inline T Min(T x, T y){return x < y ? x : y;}template<classT>inline T Max(T x, T y){return x > y ? x : y;}template<classT>inline T Abs(T x){return x <0?-x : x;}template<classT>inline T Sqr(T x){return x * x;}using std::map;using std::set;using std::pair;using std::bitset;using std::string;using std::vector;using std::complex;using std::multiset;using std::priority_queue;typedeflonglong ll;typedeflongdouble ld;typedef complex<ld> com;typedef pair<int,int> pir;const ld pi =acos(-1.0);const ld eps =1e-8;constint N =1e5+5;constint Maxn =1e9;constint Minn =-1e9;constint mod =998244353;int T_data;int a[N], b[N];
priority_queue<pir> que;
vector<pir> ans, cur;inlinevoidadd(int&x,int y){
x += y;
x >= mod ? x -= mod :0;}inlinevoiddec(int&x,int y){
x -= y;
x <0? x += mod :0;}inlineboolcalc(int*a,int n,int m,int k){
k -= n;for(int i =1; i <= n;++i)
a[i]=1+(k /(n <<1))*2;
k %=(n <<1);if(k &1)returnfalse;for(int i =1; i <=(k >>1);++i)
a[i]+=2;for(int i =1; i <= n;++i)if(a[i]> m)returnfalse;returntrue;}intmain(){read(T_data);int n, m, k;while(T_data--){read(n);read(m);read(k);
ans.clear();if(k <Max(n, m)|| k >1ll* n * m){puts("No");continue;}else{if(!calc(a, n, m, k)||!calc(b, m, n, k)){puts("No");continue;}else{for(int i =1; i <= m;++i)
que.push(std::make_pair(b[i], i));bool flag =false;for(int i =1; i <= n;++i){while(a[i]){if(que.empty()){
flag =true;break;}
pir x = que.top();
que.pop();if(!x.first){
flag =true;break;}--x.first;
ans.push_back(std::make_pair(i, x.second));
cur.push_back(x);--a[i];}if(flag){
cur.clear();break;}for(pir x : cur)
que.push(x);
cur.clear();}if(flag)puts("No");else{puts("Yes");for(pir x : ans)printf("%d %d\n", x.first, x.second);}while(!que.empty())
que.pop();}}}return0;}
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
10K. You are given a tree…
题目大意
给定一棵
n
n
n 个点的有边权树，每个点有点权
a
i
a_i
ai。
要求选出一个至多
k
k
k 个点的子集，使得子集内点权两两不同且两两点之间的路径并边权和最大。
n
≤
5000
,
2
≤
k
≤
5
,
1
≤
a
i
≤
n
n \le 5000, 2 \le k \le 5, 1\le a_i\le n
n≤5000,2≤k≤5,1≤ai≤n。
设最优方案中的点权分别为
a
i
1
,
a
i
2
,
…
,
a
i
k
a_{i_1},a_{i_2},\dots,a_{ik}
ai1,ai2,…,aik，则单次找到最优解的概率为
k
!
k
k
\frac{k!}{k^k}
kkk!，重复做
T
T
T 次至少能找到一次最优解的概率为
1
−
(
1
−
k
!
k
k
)
T
1 - (1 - \frac{k!}{k^k})^T
1−(1−kkk!)T。
当
T
=
300
T = 300
T=300 时，找到最优解的概率已经足够大，时间复杂度
O
(
T
n
3
k
)
\mathcal O(Tn3^k)
O(Tn3k)。
#includetemplate<classT>inlinevoidread(T &res){char ch;bool flag =false; res =0;while(ch =getchar(),!isdigit(ch)&& ch !='-');
ch =='-'? flag =true: res = ch ^48;while(ch =getchar(),isdigit(ch))
res = res *10+ ch -48;
flag ? res =-res :0;}template<classT>inlinevoidput(T x){if(x >9)put(x /10);putchar(x %10+48);}template<classT>inlinevoid_put(T x){if(x <0)
x =-x,putchar('-');put(x);}template<classT>inlinevoidCkMin(T &x, T y){x > y ? x = y :0;}template<classT>inlinevoidCkMax(T &x, T y){x < y ? x = y :0;}template<classT>inline T Min(T x, T y){return x < y ? x : y;}template<classT>inline T Max(T x, T y){return x > y ? x : y;}template<classT>inline T Abs(T x){return x <0?-x : x;}template<classT>inline T Sqr(T x){return x * x;}using std::map;using std::set;using std::pair;using std::bitset;using std::string;using std::vector;using std::complex;using std::multiset;using std::priority_queue;typedeflonglong ll;typedeflongdouble ld;typedef complex<ld> com;typedef pair<int,int> pir;const ld pi =acos(-1.0);const ld eps =1e-8;constint N =5e3+5;constint S =1<<5;const ll Maxn =1e18;const ll Minn =-1e18;constint mod =998244353;int T_data, n, k, C;int a[N], col[N];
ll f[N][S][2], g[S], ans = Minn;inlinevoidadd(int&x,int y){
x += y;
x >= mod ? x -= mod :0;}inlinevoiddec(int&x,int y){
x -= y;
x <0? x += mod :0;}structarc{int to, cst;
arc *nxt;}p[N <<1],*adj[N],*P = p;inlinevoidlinkArc(int x,int y,int z){(++P)->nxt = adj[x]; adj[x]= P; P->to = y; P->cst = z;(++P)->nxt = adj[y]; adj[y]= P; P->to = x; P->cst = z;}inlinevoiddfs(int x,int Fa){
f[x][1<< col[a[x]]][0]= f[x][1<< col[a[x]]][1]=0;for(arc *e = adj[x]; e; e = e->nxt){int y = e->to;if(y == Fa)continue;dfs(y, x);}for(int s =1; s < C;++s)
g[s]= Minn;for(arc *e = adj[x]; e; e = e->nxt){int y = e->to, z = e->cst;if(y == Fa)continue;for(int s = C -1; s >=1;--s)for(int s1 =(s -1)& s; s1; s1 =(s1 -1)& s){
ll tmp =Max(f[y][s ^ s1][0], f[y][s ^ s1][1]);if(tmp > Minn){if(f[x][s1][1]> Minn)CkMax(f[x][s][1], f[x][s1][1]+ tmp + z);if(f[x][s1][0]> Minn)CkMax(f[x][s][0], f[x][s1][0]+ tmp + z);}}for(int s =1; s < C;++s)for(int s1 =(s -1)& s; s1; s1 =(s1 -1)& s)if(g[s1]> Minn){
ll tmp =Max(f[y][s ^ s1][0], f[y][s ^ s1][1]);if(tmp > Minn)CkMax(f[x][s][1], g[s1]+ tmp + z);}for(int s =1; s < C;++s){
ll tmp =Max(f[y][s][0], f[y][s][1]);if(tmp > Minn){CkMax(g[s], tmp + z);CkMax(f[x][s][0], tmp + z);}}}}inlinevoidsolve(){for(int i =1; i <= n;++i)if(col[a[i]]==-1)
col[a[i]]=rand()% k;for(int i =1; i <= n;++i)for(int j =1; j < C;++j)
f[i][j][0]= f[i][j][1]= Minn;dfs(1,0);for(int i =1; i <= n;++i)for(int s =1; s < C;++s)CkMax(ans, f[i][s][1]);for(int i =1; i <= n;++i)
col[i]=-1;}intmain(){srand(time(0));read(n);read(k);for(int i =1; i <= n;++i)read(a[i]), col[i]=-1;for(int i =1, u, v, w; i < n;++i){read(u);read(v);read(w);linkArc(u, v, w);}
C =1<< k;for(int i =1; i <=300;++i)solve();put(ans),putchar('\n');return0;}
