「解题报告」Codeforces Round 668 (Div. 2)

两场 Div.2 爆肝上蓝系列……

比赛链接

A. Permutation Forgery

这题是精心构造样例给选手降智啊….卡了我半小时 /kk
实际上反过来输出就好了啊…

1
2
3
4
const int CN = 110;
int a[CN], n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = n; i >= 1; i--) printf("%d ", a[i]); puts("");

B. Array Cancellation

容易发现答案就是后缀和的最大值…证明显然啊,就算了吧…

1
2
3
4
5
6
#define int long long
const int CN = 1e5 + 5;
int n, a[CN];
n = read(); for(int i = 1; i <= n; i++) a[i] = read();
int ans = max(0ll, a[n]); for(int i = n - 1; i; i--) a[i] += a[i + 1], ans = max(ans, a[i]);
printf("%lld", ans), puts("");

C. Balanced Bitstring

容易发现模 $k$ 相同的位置, 字符应当是相同的,那么模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int CN = 1e6 + 10;
int T, n, k; char a[CN], s[CN];
ios :: sync_with_stdio(false);
cin >> n >> k >> a;

for(int i = 0; i < k; i++) s[i] = '?'; bool flag = true;
for(int i = 0; i < n && flag; i++)
if(a[i] != '?') {
if(s[i % k] == '?') s[i % k] = a[i];
else if(s[i % k] != a[i]) flag = false;
}

int cnt0 = 0, cnt1 = 0;
for(int i = 0; i < k; i++)
cnt1 += (s[i] == '1'), cnt0 += (s[i] == '0');
if(cnt0 > (k / 2) || cnt1 > (k / 2)) flag = false;

flag ? puts("YES") : puts("NO");

D. Tree Tag

容易发现初始位置看似是无用的,那么把树的直径找出来判断即可。

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
const int CN = 1e5 + 5;
int T, n, a, b, da, db;

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}
void hinit() {for(int i = 0; i <= n; i++) hd[i] = 0;}

int d[CN], dm;
void dinit() {for(int i = 0; i <= n; i++) d[i] = 0;}
void dfs(int u, int p){
for(int k = hd[u]; k; k = E[k].nxt) {int v = E[k].to; if(v ^ p) d[v] = d[u] + 1, dfs(v, u);}
}

int fa[CN][21], dep[CN];
void finit(){
for(int i = 0; i <= 20; i++) for(int j = 0; j <= n; j++) fa[j][i] = 0;
for(int i = 0; i <= n; i++) dep[i] = 0;
}
void pc(int u, int p){
fa[u][0] = p, dep[u] = dep[p] + 1;
for(int k = hd[u]; k; k = E[k].nxt) {int v = E[k].to; if(v ^ p) pc(v, u);}
}
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
for(int k = 20; k + 1; k--) if(dep[ fa[u][k] ] >= dep[v]) u = fa[u][k];
if(u ^ v) {for(int k = 20; k + 1; k--) if(fa[u][k] ^ fa[v][k]) u = fa[u][k], v = fa[v][k]; u = fa[u][0];}
return u;
}
int dis(int u, int v) {return dep[u] + dep[v] - 2 * dep[lca(u, v)];}

int main() { T = read(); while(T--){
hinit(), ecnt = 0;
n = read(), a = read(), b = read(), da = read(), db = read();
for(int i = 1; i < n; i++) {int u = read(), v = read(); add(u, v), add(v, u);}

finit(), pc(1, 0);
for(int k = 1; k <= 20; k++) for(int i = 1; i <= n; i++) fa[i][k] = fa[ fa[i][k - 1] ][k - 1];
if(dis(a, b) <= da) {puts("Alice"); continue;}

dinit(), dfs(1, 0); int mx = 0, p;
for(int i = 1; i <= n; i++) mx = mx < d[i] ? p = i, mx = d[i] : mx;

dinit(), dfs(p, 0), dm = 0;
for(int i = 1; i <= n; i++) dm = max(dm, d[i]);

if(2 * da >= dm) puts("Alice");
else if(db >= 2 * da + 1) puts("Bob");
else puts("Alice");
}}

E. Fixed Point Removal

容易发现一个点能否被消除仅与询问的左边界 $l$ 有关,设 $p_i$ 为可以令 $a_i$ 消除的最大的 $l$,则答案是 $\sum\limits_{i=l}^r[p_i\ge l]$,这是一个愉快的二维数点。
考虑 $p_i$ 如何求出,容易观察到如下性质:

  1. 若 $a_i > i$,则可以定义 $p_i = 0$;
  2. 若 $a_i = i$,显然 $p_i=i$;
  3. 若 $a_i < i$,则 $p_i=\max m, \text{s.t.} \left( \sum\limits_{j=m}^{i-1}[p_j\ge m]\right) \ge i - a_i$

前两条都好处理,最后一条二分即可,套一个静态主席树解决二维数点,时间复杂度 $O(n\log^2 n+q\log n)$。

代码:

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
const int CN = 3e5 + 5;

class SGT {
public: int d[CN * 50], ch[CN * 50][2], rt[CN], idx; SGT(){idx = 0;}
#define lc ch[u][0]
#define rc ch[u][1]
void md(int &u, int v, int l, int r, int p){
if(!u) u = ++idx;
if(l == r) return (void)(d[u] = d[v] + 1);
int m = (l + r) >> 1;
if(p <= m) rc = ch[v][1], md(lc, ch[v][0], l, m, p);
else lc = ch[v][0], md(rc, ch[v][1], m + 1, r, p);
d[u] = d[lc] + d[rc];
}
int qu(int u, int v, int l, int r, int p){
if(l == r) return d[u] - d[v];
int m = (l + r) >> 1;
if(p <= m) return d[rc] - d[ch[v][1]] + qu(lc, ch[v][0], l, m, p);
else return qu(rc, ch[v][1], m + 1, r, p);
}
} D;

int n, q, p[CN];

int main()
{
n = read(), q = read();
for(int i = 1; i <= n; i++){
int ai = read();
if(ai > i) p[i] = 0;
else if(ai == i) p[i] = i;
else{
int l = 0, r = i - 1, m, minus = i - ai;
while(l < r){
m = (l + r + 1) >> 1;
int cur = D.qu(D.rt[i - 1], D.rt[m - 1], 0, n, m);
if(cur >= minus) l = m;
else r = m - 1;
}
p[i] = l;
}
D.md(D.rt[i], D.rt[i - 1], 0, n, p[i]);
}

while(q--){
int l = read(), r = read(); l++, r = n - r;
printf("%d", D.qu(D.rt[r], D.rt[l - 1], 0, n, l)), puts("");
}
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×