题目

https://codeforces.com/contest/1657/problem/F

一个树上,每个点有小写字母

q个描述(<=4e5)

ai,bi 的简单路径得到字符串si , 注意方向可能a到b,也可能b到a

求一种满足上述所有描述的一种方案,或输出无法满足

范围

点数不超过4e5

字符串长度和不超过4e5

9s

1GB

题解

2-SAT

对于被字符串覆盖到的点, 如果正反字符相等,那么必定是这个字符

如果不等那么它也只有两种可能

于是问题变成了每个点有两种可能,并且选中其中一个时会决定它被覆盖的字符串上其它点的选择

这就是2-sat问题(每个点0/1 , 选定情况会决定其它的点情况,找一种可行方案)

2-sat问题的解法就是 建立有向图(注意这里是全部双向关系) ,求最大联通分量缩点,看是否有矛盾(一个点同时选了两个不同字符)

注意这里字符串在转化成图之前, 额外操作就是多个字符串覆盖到同一个点时, 有时能直接确定哪个字符是有效的,无效字符可以在转化前确定一部分

处理也很直白,同字符唯一确定,不同字符两个可能,多个字符串覆盖, 需要一个字符出现次数刚好是多个字符出现总次数一半

最大联通分量scc

上述处理以后就是scc的求解,这直接上tarjan

tarjan 主要就是

dfn 深度搜索访问记号

low 最小可达的前向点记号

stk 当前访问栈

res 结果数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
tarjan(u){
DFN[u] = Low[u] = ++Index//为节点u设定次序编号和Low初值
Stack.push(u) //将节点u压入栈中
for each(u,v) in E //枚举每一条边
if (v not visited) //如果节点v未被访问过
tarjan(v) //继续向下找
Low[u]=min(Low[u],Low[v])
else if (v in S) //如果节点v还在栈内
Low[u]=min(Low[u], DFN[v])
if ( DFN[u] == Low[u] ){ //如果节点u是强连通分量的根
component = {}
repeat{
v = S.pop//将v退栈,为该强连通分量中一个顶点
component.append(v)
until( u == v)
}
print component
}
}

代码

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
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(n);i++)
#define per(i,a,n) for (ll i=(ll)n-1;i>=a;i--)
#define pb push_back

const int N = 400000;
vector<int> p2[N+10];
int dep[N+10];
int fa[N+10];
char s[N+10];
map<char,vector<int> > p2charid[N+10];
vector<pair<int,char> > id2pchar;
vector<int> id2scc;
vector<vector<int> > scc2ids ;
vector<bool> vis ;
char ans[N+10];

class Tarjan{
vector<int> low;
vector<int> dfn;
stack<int> stk;
vector<int> res;
vector<vector<int> > p;
int n;
void scc(int v) {
static int id = 0;
low[v] = dfn[v] = ++id;
stk.push(v);
for(auto w:p[v]){
if(!dfn[w]){ // 未访问过
scc(w);
low[v] = min(low[v],low[w]);
} else if(!res[w]){ // 访问过但没有结果(在栈中)
low[v] = min(low[v],dfn[w]);
}
}
int u;
if(low[v] == dfn[v]) {
do{
res[u = stk.top()] = v;
stk.pop();
}while(u != v);
}
}
public:
Tarjan(int SZ):n(SZ){
low = vector<int>(n+1);
dfn = vector<int>(n+1);
stk = {};
res = vector<int> (n+1);
p = vector<vector<int> >(n+1);
}
vector<int> calc(){
rep(i,1,n+1){
if(!res[i]){
scc(i);
}
}
return res;
}
void p2(int i,int j){
p[i].pb(j);
}
};

void build(int idx,int father){
fa[idx] = father;
dep[idx] = dep[father]+1;
for(auto x:p2[idx]) {
if(x == father)continue;
build(x, idx);
}
}

// 因为要具体路径, LCA帮不上忙,直接暴力找
vector<int> getpath(int u,int v){
if(dep[u] > dep[v])swap(u,v);
vector<int> r1 = {};
vector<int> r2 = {};
while(dep[v] > dep[u]){
r1.push_back(v);
v = fa[v];
}
while(u != v){
r1.push_back(v);
v = fa[v];
r2.push_back(u);
u = fa[u];
}
r1.push_back(u);
per(i,0,r2.size()){
r1.push_back(r2[i]);
}
return r1;
}

bool add(int u,int v, Tarjan &t){
vector<int> path = getpath(u, v);
// 只记录不确定的
vector<int>inc;
vector<int>dec;
rep(i,0,(int)path.size()){
int p = path[i];
char ch1 = s[i];
char ch2 = s[path.size() - 1 -i];
if(ch1 == ch2){ // 直接确定
if(ans[p] != 0 && ans[p] != ch1){
return false;
}
ans[p] = ch1; // 一个的改值, 两个的是 增加统计
}else{ // 先建立关系 不关心冲突
int id = id2pchar.size();
id2pchar.push_back({p,ch1});
p2charid[p][ch1].push_back(id);
inc.pb(id);

id = id2pchar.size();
id2pchar.push_back({p,ch2});
p2charid[p][ch2].push_back(id);
dec.pb(id);
}
}
assert(dec.size() == inc.size());
rep(i,0,(int)inc.size()){
t.p2(inc[i],inc[(i+1)%inc.size()]);
t.p2(dec[i],dec[(i+1)%dec.size()]);
}
return true;
}

bool checkscc(int scc){
vector<pair<int,char>> pch;
for(auto id:scc2ids[scc]){
auto [p, ch] = id2pchar[id];
if(ans[p] == ch || ans[p] == 0){
pch.push_back({p,ch});
}else{
return false;
}
}
sort(pch.begin(),pch.end());
rep(i,1,(int)pch.size()){
if(pch[i-1].first != pch[i].first) continue; // 同一个点
if(pch[i-1].second != pch[i].second) return false; // 不同字符
}
return true;
}

bool applyscc(int scc){
vis[scc] = true;
for(auto id:scc2ids[scc]){
auto [p, ch] = id2pchar[id];
if(ans[p] == ch)continue;
if(ans[p] == 0){
ans[p] = ch;
}else{
return false;
}
}
return true;
}

bool rmscc(int scc){
vis[scc] = true;
for(auto id:scc2ids[scc]){
if(id == 1)continue;
auto [p, ch] = id2pchar[id];
if(ans[p] == ch) return false; // 失效和已经填入的冲突
if(p2charid[p].count(ch)){
p2charid[p].erase(ch);
if(ans[p] == 0 && p2charid[p].size() == 0)return false; //
if(p2charid[p].size() == 1){
auto [ch,ids] = *p2charid[p].begin();
if(ans[p] != 0 && ans[p] != ch)return false;
ans[p] = ch;
for(auto id:ids){
if(!vis[id2scc[id]]){
int r = applyscc(id2scc[id]);
if(!r)return r;
}
}
}
}
}
return true;
}

int main(){
id2pchar.push_back({-1,'X'}); // 占位0
id2pchar.push_back({-1,'X'}); // 建立特殊失效节点, 下标为1
int n,q;
cin>>n>>q;
rep(i,0,n-1){
int u,v;
scanf("%d %d",&u,&v);
p2[u].push_back(v);
p2[v].push_back(u);
}
build(1,0); // 父节点和深度
Tarjan t(2*N+2);
rep(i,0,q){
int u,v;
scanf("%d %d",&u,&v);
scanf("%s",s);
bool r = add(u,v,t);
if(!r){
printf("NO\n");
return 0;
}
}
// 处理每个点明确不可能的情况
rep(i,1,n+1) {
if(ans[i]){ // 已确定的
for(auto [ch,ids]:p2charid[i]){
if(ch == ans[i])continue;
for(auto id: ids){
t.p2(1,id); // 失效的
t.p2(id,1); // 失效的
}
}
}else{ // 未确定的
if(p2charid[i].size() == 0){
ans [i] = 'a'; // 没有限制
}else { // 每次贡献两个不同的,那么答案要占恰好一半出现
int total = 0;
for(auto [ch,ids]:p2charid[i]){
total+=ids.size();
}
for(auto [ch,ids]:p2charid[i]){
if((int)ids.size()*2 != total){
for(auto id: ids){
t.p2(1,id); // 建立不可能
t.p2(id,1);
}
}
}
}
}
}
id2scc = t.calc();
scc2ids = vector<vector<int>>(id2pchar.size());
vis = vector<bool>(id2pchar.size());
rep(i,1,(int)id2pchar.size()){
scc2ids[id2scc[i]].pb(i);
}
// 处理掉直接不可能
bool r = rmscc(1);
if(!r){
printf("NO\n");
return 0;
}
rep(scc,2,(int)id2pchar.size()){
if(!scc2ids[scc].size())continue;
if(vis[scc])continue;
if(!checkscc(scc)){
bool r = rmscc(scc);
if(!r){
printf("NO\n");
return 0;
}
}else{
bool r = applyscc(scc);
if(!r){
printf("NO\n");
return 0;
}
}
}
rep(i,1,n+1){
if(!ans[i]){
printf("NO\n");
return 0;
}
}
printf("YES\n");
rep(i,1,n+1){
printf("%c",ans[i]);
}
printf("\n");
return 0;
}

总结

还是知识点不够, 一个是太久没写tarjan scc,一个是没搞过2-sat

参考

官方题解

E

https://codeforces.com/contest/1654/problem/E

给一数列,修改尽量少的值让整个数列等差

范围

n <= 1e5

1<= ai <= 1e5

5s

1GB

题解

实际上是二维点(i,ai),找直线经过最多的点

考虑增量 小于 sqrtn,那么选中斜率, 计算每个点沿着斜率与y轴交点 出现的最多次即可, 不要用map,用数组和清理数组实现

考虑增量 大于 sqrtn,以每个点作为起点,那么最多尝试这个点向后n/sqrt(n) 个点, 把这些点计算出现最多次数的斜率, 数量不多,可以用map

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

const int N = 100000;
int a[N+10];

int used[32000010];
int n;

int work(){
int SQRT = 316;
int ans = 0;
// 增量 <= SQRT;
rep(i,0,SQRT+1){
vector<int> rm;
rep(j,0,n){
// 非负便宜量
int v = a[j] + SQRT*N- j*i; // max = 31600000+100000
if(!used[v])rm.push_back(v);
ans = max(ans,++used[v]);
}
// clear
for(auto v:rm){
used[v] = 0;
}
}
// 增量 大于 SQRT
rep(j,0,n){ // 下标
map<int,int> kcnt;
rep(i,j+1,n){ // 增量
if(a[j] + (i-j) * SQRT > N) break;
if( (a[i] - a[j]) % (i-j) == 0){
kcnt[(a[i] - a[j]) / (i-j)]++;
}
}
for(auto [k,cnt]:kcnt){
// printf("a[%lld] = %d : k=%d cnt = %d\n",j,a[j],k,cnt+1);
ans = max(ans, cnt+1);
}
}
return ans;
}

int main(){
cin>>n;
rep(i,0,n){
scanf("%d",a+i);
}
int ans = work();
// 翻转
rep(i,0,n/2){
swap(a[i],a[n-1-i]);
}
printf("%d\n",n - max(ans,work()));
return 0;
}

总结

按照一个值,分段处理,每一段都是性能满足的

参考

官方题解

F

https://codeforces.com/contest/1654/problem/F

给一个字符串,长度$2^n$

找一个$j <= 2^n$, 让s[i^j] 字典序最小

范围

n <= 18

3s

512MB

题解

我的尝试

我想到,j的位是0或1实际上意味着 原字符串 的长度2^k 区间是否交换

而判断是否交换,可以局部贪心

问题是,存在字符相等的情况, 不知道怎么记录, 试了一下random 并不能骗分哈哈

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

// n => 2^n length lowercase letters
//
// t[i] = s[i ^ j]
//
// find j => minimal string
// n <= 18
// 2^n <= 262144
// bit1 ,一个一组,相邻交换
// bit2 ,2个一组,相邻交换
// bit3 ,3个一组,相邻交换
// bit4 ,4个一组,相邻交换

// ans(0..x)
// => min(ans(0..x/2),ans(x/2+1...x)) 最小的作为前缀
// 3**18 => 387420489

int n;
char s[270010];
int ans[270010][20];

int cmp(int p,int pwr,int l,int r){
// 自己所在的那一节
rep(i,0,(1<<pwr)){
if(s[(p + i) ^ l] < s[(p + (1<<pwr) + i) ^ r]) return -1;
if(s[(p + i) ^ l] > s[(p + (1<<pwr) + i) ^ r]) return 1;
}
// 对手那一行
rep(i,0,(1<<pwr)){
if(s[(p + (1<<pwr) + i) ^ l] < s[(p + i) ^ r]) return -1;
if(s[(p + (1<<pwr) + i) ^ l] > s[(p + i) ^ r]) return 1;
}
return 0;
}

ll tryRand(){
rep(i,1,n+1){
for(int p = 0;p < (1<<n); p += (1<<i)){
int lans = ans[p][i-1];
int rans = ans[p+(1<<(i-1))][i-1];
int res = cmp(p,i-1,lans,rans);
// TODO 相等的情况??????
if(res == 0){
// printf("fuck?\n");
if(rand()%2){
ans[p][i] = lans;
}else{
ans[p][i] = (rans | (1<<(i-1)));
}
} else if(res == -1){
ans[p][i] = lans;
}else{
ans[p][i] = (rans | (1<<(i-1)));
}
}
}
return ans[0][n];
}

int main(){
srand(time(NULL));
cin>>n;
scanf("%s",s);
int j = tryRand();
rep(t,0,180){
int k = tryRand();
rep(i,0,(1<<n)){
if(s[i ^ j] < s[i ^ k])break;
if(s[i ^ j] == s[i ^ k])continue;
j = k;
break;
}
}
rep(i,0,(1<<n)){
printf("%c", s[i ^ j]);
}
printf("\n");
return 0;
}

正解

实际上可以看成, 把 0~n-1排序

而排序是按照f(s,i)的字典序来比较大小的

这里的问题是 如果两两比较 依然复杂度完成不了, 如何减少比较和处理相等

考虑样例1: acba

1
2
3
4
0: acba
1: caab
2: baac
3: abca

最终期望得到

1
2
3
4
3: abca
0: acba
2: baac
1: caab

然而注意到,

首位的比较 就是 s[i]

第2位的比较 就是 s[i ^ (1<<0)]

第3位的比较 就是 s[i ^ (1<<1)]

第4位的比较 就是 s[i ^ (1<<2)]

而 一旦首位有非相等的大小关系了,之后也就不会改变相对顺序, 不想等时 才考虑后续排序


于是, 按首位排序

1
2
3
4
0: a
1: c
2: b
3: a

变为

1
2
3
4
0: a
3: a
2: b
1: c

记录大小顺序

1
2
3
4
0: a(0)
3: a(0)
2: b(1)
1: c(2)

按照第二位排序

1
2
3
4
0: ?c
1: ?a
2: ?a
3: ?b

得到

1
2
3
4
1: ?a
2: ?a
3: ?b
0: ?c

整体变为(注意首位不相等的要保持顺序)

1
2
3
4
3: ab
0: ac
2: ba
1: ca

记录大小顺序

1
2
3
4
3: ab(0)
0: ac(1)
2: ba(2)
1: ca(3)

这样所有位排序, 更新顺序即可

换句话说就是类似基数排序, 每次是对前缀相等的一系列值的下一位 进行排序

这里注意到看上去字符串长度,有1 << n, 但是实际上,上述排序只需要考虑2的幂次的

因为,[2..3] 的排序 实际是 ([0..1]^2)得到的排序

因为,[4..7] 的排序 实际是 ([0..3]^4)得到的排序

所以 虽然是基数排序,但是 能通过幂次 和记录大小的排序值 优化比较次数

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back

const int N = 1 << 18;
int n, a[N], val[N], tmp[N], now;
char s[N];

// x 在 y 前面
bool cmp(int x, int y) {
return (val[x] == val[y]) ?
val[x ^ now] < val[y ^ now] :
val[x] < val[y];
}

int main() {
cin>>n;
scanf("%s", s);
rep(i,0,1<<n){
val[i] = s[i] - 'a'; // [0,26), 实际表示的是以 (1<<pwr) 跨度排序 的 顺序下标,
a[i] = i; // 相当于 0 ~ 2^n-1 中 让s字典序最小的
}
rep(pwr,0,n) {
now = 1 << pwr; // 比较区间长度
sort(a, a + (1 << n), cmp);
int num = 0; // 离散化顺序值
rep(j,0,1<<n){
if (j > 0 && cmp(a[j - 1], a[j])) num ++; // f(a[j-1]) < f(a[j]) => num++; 明确j比前一个大
tmp[a[j]] = num;
}
rep(j,0,1<<n){
val[j] = tmp[j]; // 记录的是 now*2 长度 的 排序 序号
}
}

rep(i,0,1<<n){
putchar(s[i ^ a[0]]);
}

return 0;
}

pwr = 0, now = 1

如果字符 更小,则排在前面

如果字符 相等,则它^1位置的更小就排在前面, 如果依然相等,则认为当前论次比较它们两相等

修改val[i] = 表示选定异或值i, 让 s在i 的转换下, 前两位 在所有i 中的 顺序

pwr = 1, now = 2

注意到上面val意义已经变化

val[i] 表示的是 i 引起的转换 的前两位的排序值

如果排序值更小,则排在前面

如果排序值相等,则它^2位置的更小就排在前面, 如果依然相等,则认为当前论次比较它们两相等

修改val[i] = 表示选定异或值i, 让 s在i 的转换下, 前4位 在所有i 中的 顺序

pwr = 2, now = 4

val[i] 表示的是 i 引起的转换 的前4位的排序值

如果排序值更小,则排在前面

如果排序值相等,则它^4位置的更小就排在前面, 如果依然相等,则认为当前论次比较它们两相等

修改val[i] = 表示选定异或值i, 让 s在i 的转换下, 前8位 在所有i 中的 顺序

pwr = n, now = 2**n

val[i] 表示的是 i 引起的转换 的前now位的排序值

如果排序值更小,则排在前面

如果排序值相等,则它xor now 位置的更小就排在前面, 如果依然相等,则认为当前论次比较它们两相等

修改val[i] = 表示选定异或值i, 让 s在i 的转换下, 前now*2位 在所有i 中的 顺序

总结

每次排序,再记录顺序, 方便后续比较,而不仅仅排序就完了, 这个记录顺序很重要

参考

官方题解

D

https://codeforces.com/contest/1648/problem/D

3xn 左上角 走到 右下角,只能右和下两个方向的走,价值= 经过块的值的和

第一行,第三行直接可走,第二行需要额外代价v,开启[l,r]一段

问总获得价值最大值

范围

n <= 5e5

块上值 -1e9 ~ 1e9

可选扩展 5e5 个,扩展代价 1~1e9

题解

行走代价简化

走过的样子无非是

1
2
3
xxxxxx
xxxxxxx
xxxxxxxxx

拆分一下,

第一段: 第一行+,第二行-

第二段: 第二行+,第三行+

1
2
3
4
5
6
     i
++++++
-----
j
+++++++++++++
+++++++++

那么行走代价为s[i]+t[j]

剩下就是开放(i,j)的最小代价

状态与转移与范围最值

考虑从(1,1)走到(2,i), 其中当前使用的最右侧的开放端点是i

1
2
3
4
5
6
     ?
xxxxxx i
xxxxxxxx
[ ]
[ ]
[ ]

dp[i] = (1,1) -> (2,i)i 是当前最右侧开放的点, 上述条件下 , 最大的 s[?] - cost(?,i)

这里两点

  1. i 是某个区间右侧端点, 且走到了这个位置
  2. dp表示的是这样范围中最大的, 包含scost , 这里很神奇,没有t意味着,下面转移时并不用考虑第二行所选位置对dp的影响

也就是一个准确,一个范围最值


状态转移,

要么是通过第一行直接进入所选区间走到i,

要么就是先走到(2,j), 再在一个区间内走到i, 所以 j 在 [l-1,r]

1
2
3
4
5
6
     ?
xxxxxx j
xxxxxxxxx
[ ]
xxxxxx i
xxxxxxxxxxxxxx

dp[i] = max(dp[j] - cost(i,j).value)


剩下的就是最终的答案, 因为可能走到不是某个区间的终点,就去第三行了

1
2
3
4
5
     ?
xxxxxx i j
xxxxxxxxxxxxxx
xxxxxxx
[ ]

ans = max(dp[i] - cost(i,j).value + t[j])i,j 在某个区间内,i < j, 对于相等的情况 上面直接+t[i]就更新

换个角度,先固定一个区间,cost确定,再在这个区间里找 max(dp[i]+t[j])

其中i[l-1,r]


注意到上面的方案,一定经过了某个开放区间的终点,开放区间为 >= 1 个 ,所以还有一种情况,只开放了一个区间,i和j都在区间之中

上面最重要的是控制成了一个区间,但不一定是唯一一个区间

而上面的操作和只开放一个区间十分的像,都是开放一个区间,左dp[i],右t[j] 和(i < j) 左s[i],右t[j] (i <= j)

注意到对于左dp,右t的情况,i==j只会产生比最优更小的答案,所以可以考虑在最值处理时合并left[i] = min(dp[i],dp[i-1],s[i])

最后特化成只开放一个区间的问题

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define pb push_back
#define SEG_ROOT 1,0,n-1
#define SEG_L o<<1,l,m
#define SEG_R o<<1|1,m+1,r
const double pi = acos(-1.0);

const int N = 500'000;
ll s[N + 10];
ll t[N + 10];
ll dp[N + 10];
ll a[3][N + 10];
vector<tuple<int, int, ll> > rlv;

ll seg[2][N * 4 + 10];
ll segans[N * 4 + 10];
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll query(int o, int l, int r, int ql, int qr) {
if (l == ql && r == qr)
return seg[0][o];
int m = (l + r) / 2;
if (qr <= m) {
return query(SEG_L, ql, qr);
} else if (ql > m) {
return query(SEG_R, ql, qr);
} else {
return max(query(SEG_L, ql, m),
query(SEG_R, m + 1, qr));
}
}

void update(int o, int l, int r, int pos) {
if (l == r) {
seg[0][o] = dp[l];
return;
}
int m = (l + r) / 2;
if (pos <= m)
update(SEG_L, pos);
else
update(SEG_R, pos);
seg[0][o] = max(seg[0][o << 1], seg[0][o << 1 | 1]);
}

void build(int o, int l, int r) {
if (l == r) {
seg[0][o] = dp[l];
return;
}
int m = (l + r) / 2;
build(SEG_L);
build(SEG_R);
seg[0][o] = max(seg[0][o << 1], seg[0][o << 1 | 1]);
}

// [l,r]为开放段
void buildans(int o, int l, int r) {
if (l == r) {
// 可以dp到[l-1] 或[l]
seg[0][o] = max(max(dp[l], s[l]), l > 0 ? dp[l-1] : -INF);
seg[1][o] = t[l];
segans[o] = seg[0][o] + t[l];
return;
}
int m = (l + r) / 2;
buildans(SEG_L);
buildans(SEG_R);

seg[0][o] = max(seg[0][o << 1], seg[0][o << 1 | 1]);
seg[1][o] = max(seg[1][o << 1], seg[1][o << 1 | 1]);
segans[o] = max(seg[0][o << 1] + seg[1][o << 1 | 1],
max(segans[o << 1], segans[o << 1 | 1]));
};

// {最大值, 最大dp, 最大t}
vector<ll> qans(int o, int l, int r, int ql, int qr) {
if (ql == l && qr == r) {
return {segans[o], seg[0][o], seg[1][o]};
}
int m = (l + r) / 2;
if (qr <= m) {
return qans(SEG_L, ql, qr);
} else if (ql > m) {
return qans(SEG_R, ql, qr);
}
auto lres = qans(SEG_L, ql, m);
auto rres = qans(SEG_R, m + 1, qr);
return {max(max(lres[0], rres[0]), lres[1] + rres[2]), max(lres[1], rres[1]),
max(lres[2], rres[2])};
}

int main() {
int n, q;
scanf("%d %d", &n, &q);
ll a2 = 0;
rep(i, 0, 3) {
rep(j, 0, n) { scanf("%lld", &a[i][j]); }
}
rep(i, 0, n) a2 += a[2][i];
s[0] = a[0][0];
rep(i, 1, n) { s[i] = s[i - 1] + a[0][i] - a[1][i - 1]; }
t[0] = a2 + a[1][0];
rep(i, 1, n) { t[i] = t[i - 1] + a[1][i] - a[2][i - 1]; }

rep(i, 0, q) {
int r, l;
ll v;
scanf("%d %d %lld", &l, &r, &v);
rlv.pb({r - 1, l - 1, v});
}
ll ans = -INF;
// 按右端点排序
sort(rlv.begin(), rlv.end());
// 处理 使用一次区间直接进入的
vector<int> pos; // 单调队列
unsigned long itr = 0;
rep(i, 0, n){
dp[i] = -INF;
}
rep(i, 0, n) { // 下标
while (pos.size() && s[pos.back()] <= s[i]) {
pos.pop_back();
}
pos.pb(i);
while (itr < rlv.size() && get<0>(rlv[itr]) == i) {
// 区间内最大值
dp[i] = max(
dp[i],
s[*lower_bound(pos.begin(), pos.end(), get<1>(rlv[itr]))] -
get<2>(rlv[itr])); // cost > 0选自己没影响
if (dp[i] != -INF) {
ans = max(ans, dp[i] + t[i]);
// printf("dp[%lld] => %lld\n", i, dp[i]);
}
itr++;
}
}
build(SEG_ROOT);
itr = 0;
for(auto [r,l,v]:rlv){
// 注意可以上一个结束的位置[?..l-1] 和当前 [l..r] 是相邻而不是重叠
// dp[i] = max(dp[<i] - cost);
ll newdpi = query(SEG_ROOT, max(0,l-1), max(0,r-1)) - v;
if (newdpi > dp[r]) {
dp[r] = newdpi;
ans = max(ans, dp[r] + t[r]);
// printf("update: dp[%lld] => %lld\n", i, dp[i]);
update(SEG_ROOT, r);
}
}
buildans(SEG_ROOT);
// [l...r] => [l..m] [m+1,r]
for (auto [r, l, v] : rlv) {
auto qres = qans(SEG_ROOT, l, r);
if (qres[0] <= -INF)
continue;
ans = max(ans, qres[0] - v);
}
printf("%lld\n", ans);

return 0;
}

总结

一个核心的点就是区间覆盖,转换成刚好走到以某个区间结束的动规,感觉要是一个纯的动规还可能想到,合在一起竟然卡住了

参考

官方题解

C202044zxy

cggghh

Sstee1XD

某岛

D

https://codeforces.com/contest/1641/problem/D

n(1e5)个数组

每个数组长度为m(<=5), 包含值(<1e9), 每个数组有总代价w(<=1e9)

找出两个数组,让它们的值没有重复,且代价和最小,求最小代价

题解

  1. 随机映射到0-15,注意同一个数一定映射到相同数,不同数可能映射到相同数, 多次运行提高概率期望到2, orz(见YB Lin 的链接)

  2. 集合数学性质

一个集合属于A,又属于B,

如果该集合个数为奇数,则+1

如果该集合个数为偶数(包含空集合),则-1

那么,如果A,B有公共元素,则结果为0,否则为1

然后维护一个Trie树,上面是所有子集


把原数组按照w排序

利用Trie树找到首个合法的组合i,j

因为要答案最小,所以 i < i’, 则有 j’< j

代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i, a, n) for (ll i = a; i < n; i++)
#define pb push_back
#define all(a) a.begin(), a.end()

// trie 树, 用index取代指针
// 集合按照从小到大 展开存成树节点
struct node { // 只会新增不会移除, cnt为0 和 移除等价
unordered_map<int, int> next; // [值] => 树节点index
int cnt;
};

vector<node> g;

int new_node() {
g.push_back(node{{}, 0});
return g.size() - 1;
}

// 新把数组变化 放入trie树
void add(const vector<int>& x,
int c /* 1(加入) or -1(移除) */,
int v = 0 /* trie 树 节点 index*/,
int i = 0 /* 遍历数组下标 */) {
if (i == x.size()) {
g[v].cnt += c; // 在trie树 的所有集合表示的位置都+1
return;
}
// 不存在创建新节点
if (!g[v].next.count(x[i]))
g[v].next[x[i]] = new_node();
add(x, c, v, i + 1); // 不选择当前的情况
add(x, c, g[v].next[x[i]], i + 1); // 选择当前的情况
}

// 初始全是0
// 如果和 已经加入的 某个数组重合,那么与这个数组贡献的cnt 的结果为 0
// 如果和 已经加入的 某个数组不重合,那么与这个数组贡献的cnt 的结果为 1
// 而trie上的贡献是满足**累加**性质,所以与 trie树直接计算cnt
// 如果为0,则和所有数组现有的都冲突,否则存在一个数组和它没有重合
int get_cnt(const vector<int>& x, int v = 0, int i = 0) {
if (i == x.size()) {
return g[v].cnt;
}
int res = get_cnt(x, v, i + 1); // 第i位 不选
if (g[v].next.count(x[i])) // 第i位 存在(集合存在) 并选择
res -= get_cnt(x, g[v].next[x[i]] /* trie 树的下一个节点 */,
i + 1); // 奇偶加减交替
return res;
}

int main() {
int n, k;
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
vector<pair<int, vector<int>>> a = vector(n, make_pair(0, vector<int>(k, 0)));
rep(i, 0, n) {
rep(j, 0, k) {
cin >> a[i].second[j]; // 读入每个数组
}
cin >> a[i].first; // 数组权重
}
rep(i, 0, n) { // 数组内按照值排序
sort(all(a[i].second));
}
sort(all(a)); // 按权重排序
new_node(); // trie 根节点 空集合
int res = -1;
int i = 0;
// 和 trie 树中 任何一个重复 都会 让 get_cnt > 0
while (i < n && !get_cnt(a[i].second)) {
// 首个一定加入, 如果和现有所有数组都冲突,那么加入trie树
// 如果存在一个不是和所有都冲突的 , 会触发 get_cnt 不为0
add(a[i].second, 1);
i += 1;
}
if (i >= n) {
cout << -1 << "\n";
return 0;
}
// i 是首个 与 [0...i-1]中某个不会冲突的
int j = i;
// 从i倒向查找
while (get_cnt(a[i].second)) { // 直到所有都冲突,找到一个最小的j
j -= 1;
add(a[j].second, -1); // 每次从trie树中移除一个
}
// j < i 互相不冲突, 最小的i对应的最小的j
res = a[i].first + a[j].first;
// j' < j < i < i'
for (i += 1; i < n && j > 0; ++i) {
while (get_cnt(a[i].second)) { // 循环直到 和 前面都冲突
j -= 1; // 找一个 最小的j 让 i和j不冲突
add(a[j].second, -1); // 移除
}
// 不一定是有效值(可能i,j是冲突的),但是因为代价排序关系,保证不会影响最小值
res = min(res, a[i].first + a[j].first);
}
cout << res << "\n";
return 0;
}

总结

  1. 先按照价值排序,
  2. 再从小到大找到首个和前面某个不冲突的
  3. 找到前面最小的与当前不冲突的,确定一个合法j < i
  4. i增加,每次找更小的j与新的i不冲突的,或者找不到跳过这个i, 每次更新最小值

关键的核心就是,trie树保存的是两两冲突的数组的所有集合,而与trie树 做子集重合get_cnt运算,如果与已加入的所有都有重合则总结果为0,否则大于0, 相当于trie能帮助完成批量判断

ref

官方题解

YB Lin 概率映射 sosdp 乱搞

neweryyy

题目

https://projecteuler.net/problem=516

题意

n < 10^12, phi(n)的值仅包含质因数2,3,5的所有n的和,mod2^32

题解

欧拉函数

$\phi(n) = n(1-\frac{1}{p_0})(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots$

其中$p_i$均为$n$的质数因数

性质:

$\phi(x)\phi(y)=\phi(xy), gcd(x,y)==1$

$\phi(prime)\phi(x)=(prime-1)\phi(x), gcd(x,prime)==1$

题目转换

$n = 2^{q_0}3^{q_1}5^{q_2} p_0p_1p_2\cdots$

其中$p_i + 1$ 是只包含$2,3,5$ 质因子的数

广搜2,3,5

$x => 2x,3x,5x$

广搜小于$10^{12}$的所有只包含质因数$2,3,5$的数

质数判别

小于$2^{64}$里的质因数可以 Miller-Robin算法 常数级别 判别

二分

$n = 2^{q_0}3^{q_1}5^{q_2} p_0p_1p_2\cdots$

后面又可以拆分成$2^{q_0}3^{q_1}5^{q_2}$ 和 $p_0p_1p_2\cdots$

右边每个质数最多一次方,直接生成所有的积,左边还是上面求的

要两部分数组内容乘积小于n, 可以左侧枚举二分右侧,右侧枚举二分左侧都一样的, 通过前缀和辅助得到和

Ref

Euler’s totient function

0%