【赛题整理】CodeForces Round#625

大概是赛时整理?但是赛时发挥的一点也不好…第二天早上一起来就A掉了赛时没A的两个题…

总结:还是太菜。

没整理1E和1F。顺序按照Div2的顺序写的——

A

给定两个 $01$ 串。设给每个位置一个正整数权 $p_i$ ,权被算到贡献里当且仅当对应位置为 true 。要求第一个串的权和要严格大于第二串。构造这样的 $p_i$ ,求 $\min\{\max_{i=1}^n\{p_i\}\}$ ,或者输出不可能。

签到题。感觉可能直接放代码比嘴巴更好用?

1
2
3
4
5
6
7
8
9
10
int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i) cin >> b[i] ;
for (int i = 1 ; i <= n ; ++ i) cin >> c[i] ;
for (int i = 1 ; i <= n ; ++ i)
if (c[i] > b[i]) ++ t1 ;
else if (c[i] < b[i]) ++ t2 ;
if (!t2 || t1 == n) return puts("-1"), 0 ;
t1 ++ ; cout << (int)ceil(1.0 * t1 / (1.0 * t2)) << endl ;
}

B

给定一个序列 $\{a_n\}$ ,要求选出来一个下标序列 $\{s_m\} ~ s.t. \forall i < n,s_{i+1}-s_{i}=a_{s_{i+1}}-a_{s_i}$。

最大化选出来的 $a_i$ 的数值和。

$\{a_n\}>0$

大概是和差分那种题差不多的思路。令 $b_i=a_i-i$ ,那么发现 $b_i$ 同样的位置产生同一组贡献。由于每个位置的 $a_i$ 都 $>0$ ,所以拿一个桶记一下即可。

C

给定一个小写字母串 $s$,对于一个位置 $c$,如果相邻位置有音序掐好比它小 $1$ 的字母就可以删。问最多删多少个。

$1\leq |s|\leq 100$

nmd,这题真是十分sb。给了个 $|s|=100$ 的范围这是在坑鬼?于是我就写了个 while(1) 无限删除,感觉这个复杂度应该很对。但是一直 WA on 11 ,期间编了编感觉很对…冷静了一会儿发现,dcbcd 这种就可以卡掉,只有从大到小删才是好的。所以就是个贪心。

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
int n ;
int ans ;
int a[N] ;
char S[N] ;
int pd[N] ;
int sd[N] ;
int pre[N] ;
int nxt[N] ;
bool vis[N] ;
//int f[N][N][27][27] ;

int main(){
int flag = 1 ;
cin >> n >> (S + 1) ;
for (int i = 1 ; i <= n ; ++ i)
a[i] = S[i] - 'a' ; nxt[0] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
pre[i] = i - 1, nxt[i] = i + 1 ;
a[0] = a[n + 1] = 23333333 ; nxt[n] = 0 ;
for (int c = 'z' ; c >= 'a' ; -- c){
flag = 1 ;
while (flag){
flag = 0 ;// cout << nxt[1] << endl ;
for (int i = nxt[0] ; i ; i = nxt[i])
if (a[i] == c - 'a'){
if (a[pre[i]] + 1 == a[i] || a[nxt[i]] + 1 == a[i])
ans ++, flag = 1, pre[nxt[i]] = pre[i], nxt[pre[i]] = nxt[i] ;
}
/*for (int i = 1 ; i <= n ; ++ i){
if (!vis[i]){
pd[i] = a[i] - a[pre[i]] ;
sd[i] = a[i] - a[nxt[i]] ;
}
else pd[i] = sd[i] = -1 ;
}
int ret = 0 ;
for (int i = 1 ; i <= n ; ++ i){
//for (in i = 1 ; i <= n ; ++ i) cout << pre[i] << " " ; puts("") ;
if (vis[i]) continue ;
if (a[nxt[i]] != a[i]){
for (int j = nxt[i] ; j ; j = nxt[j])
if (j && pd[j] <= 1 && pd[j] >= 0)
++ ret, pre[nxt[j]] = pre[j], nxt[pre[j]] = nxt[j], vis[j] = 1 ; else break ;
}
ans += ret ; //cout << i << " " << ret << endl ;
if (ret) flag = 1 ; ret = 0 ;
if (a[pre[i]] != a[i]){
for (int j = pre[i] ; j ; j = pre[j])
if (j && sd[j] <= 1 && sd[j] >= 0)
++ ret, pre[nxt[j]] = pre[j], nxt[pre[j]] = nxt[j], vis[j] = 1 ; else break ;
}
ans += ret ; //cout << i << " " << ret << endl ;
if (ret) flag = 1 ; ret = 0 ;*/
}
}
cout << ans << endl ;
}

D

弱智题。是真的没有一点意思的弱智题。甚至比不上A。

E

给定一系列有代价的装备,第一种提供 $x$ 值,第二种提供 $y$ 值。给出一些怪兽,如果怪兽的 $x_i$ 和 $y_i$ 都小于选定的 $x$ 和 $y$ ,那么会有 $z_i$ 的奖励。最大化收益。

$1\leq n\leq 2\times 10^5$ 。

一个比较自然的想法是排序之后枚举一维坐标,然后去算另一维。然而另一维并不具备单调性。考虑对于一个确切的 $x$ ,如何选择一个最优的 $y$ 取到最大值。考虑快速查找一个 $y$ 的最优值,需要快速计算当前 $y$ 可以提供击败哪些怪兽的贡献。

考虑将询问按照 $x$ 排序,就转化和成了一个二维扫描线问题。考虑用线段树维护每个 $y$ 值处的最大值。枚举第一种装备,每次用双指针扫到当前的 $x_i$,提前用线段树进行 $y$ 坐标的后缀加计算贡献。最后答案就是所有 $y$ 的最大值减去使用当前 $x$ 的代价。

感觉现在语言越来越苍白无力,还是代码比较容易说明道理。

感觉自己没做过太多这种类似的题,可能见多了就是套路了吧233

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
#define LL long long
#define lowb lower_bound
#define uppb upper_bound

const int N = 200010 ;
const int S = 1000000101 ;

LL ans ;
int len ;
int tmp[N] ;
int n, m, k ;
struct arm{
int x ;
int c ;
bool operator < (const arm & t)
const { return t.x == x ? t.c > c : t.x > x ; }
}a[N], b[N] ;
struct monster{
int x, y, v ;
bool operator < (const monster & t)
const { return t.y == y ? t.x > x : t.y > y ; }
}base[N] ;
LL s[N * 3] ;
LL tag[N * 3] ;

void _up(int x){
s[x] = max(s[x << 1], s[x << 1 | 1]) ;
}
void _down(int x){
if (tag[x]){
s[x << 1] += tag[x] ;
s[x << 1 | 1] += tag[x] ;
tag[x << 1] += tag[x] ;
tag[x << 1 | 1] += tag[x] ;
}
tag[x] = 0 ;
}
void chkmax(LL& a, int b){
a = b > a ? b : a ; return ;
}
void update(int rt, int l, int r, int v, int p){
if (l == r)
return chkmax(s[rt], v) ;
int mid = (l + r) >> 1 ;
if (p <= mid) update(rt << 1, l, mid, v, p) ;
else update (rt << 1 | 1, mid + 1, r, v, p) ;
}
void update(int rt, int l, int r, int v, int ul, int ur){
if (ul <= l && r <= ur){
return s[rt] += v, tag[rt] += v, void() ;
}
int mid = (l + r) >> 1 ; _down(rt) ;
if (ul <= mid) update(rt << 1, l, mid, v, ul, ur) ;
if (ur > mid) update(rt << 1 | 1, mid + 1, r, v, ul, ur) ;
_up(rt) ;
}
int main(){
cin >> n >> m >> k ;
memset(s, -63, sizeof(s)) ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d%d", &a[i].x, &a[i].c) ;
for (int i = 1 ; i <= m ; ++ i)
scanf("%d%d", &b[i].x, &b[i].c) ;
sort(b + 1, b + m + 1) ;
for (int i = 1 ; i <= k ; ++ i)
scanf("%d%d%d", &base[i].x, &base[i].y, &base[i].v) ;
sort(base + 1, base + k + 1) ;
for (int i = 1 ; i <= n ; ++ i) tmp[i] = a[i].x ;
sort(tmp + 1, tmp + n + 1) ;
len = unique(tmp + 1, tmp + n + 1) - (tmp + 1) ;
for (int i = 1 ; i <= k ; ++ i)
base[i].x = uppb(tmp + 1, tmp + len + 1, base[i].x) - tmp ;
for (int i = 1 ; i <= n ; ++ i){
a[i].x = lowb(tmp + 1, tmp + len + 1, a[i].x) - tmp ;
update(1, 1, len, - a[i].c, a[i].x) ;
}
//cout <<s[1]<<endl;//, cout << base[i].y<<endl;
int now = 1 ; ans = - (S + S) ;
for (int i = 1 ; i <= m ; ++ i){
//cout << b[i].x << endl ;
while (now <= k && base[now].y < b[i].x)
update(1, 1, len, base[now].v, base[now].x, len), ++ now ;
//cout << now << endl, cout << s[1] << " ---------- " << endl ;
ans = max(ans, s[1] - b[i].c) ;
}
cout << ans << endl ; return 0 ;
}

F

给定一个 $01$ 串。每次询问两个等长的子串,询问是否可以从一个变换到另一个。变换操作的定义是每次选定一个子段,让 $110\to 011$ 或者 $011\to110$ 。

$n,q\leq 2\times 10^5$

很有趣的一道观察性质题。考虑对于一次变换之后,位于 $p$ 位置的 $0$ 会变到 $p-2$ 或者 $p+2$ ,也就是 前缀 $1$ 的奇偶性没有发生改变。所以实质上每次是在查询,对于两个串,是否有相同数量的 $0$ ,且对应位置的 $0$ 之前 $1$ 的数量的奇偶性是否相同。这一部分可以用哈希实现。哈希时按奇偶性分类哈希,即可保证区间哈希的正确性。

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
const int N = 300010 ;
const int P = 998244353 ;

int len ;
int n, m ;
int a[N] ;
int sum[N] ;
LL base[N] ;
LL S[N], T[N] ;

const LL Base = 217ll ;
int sub(int a, int b){
return ((a - b) % P + P) % P ;
}
bool check(int p, int q, int L){
int p0 = p + L - 1 ;
int q0 = q + L - 1 ;
int e1 = p0 - sum[p0] ;
int e2 = q0 - sum[q0] ;
int s1 = p - 1 - sum[p - 1] ;
int s2 = q - 1 - sum[q - 1] ;
if (sum[p0] - sum[p - 1] != sum[q0] - sum[q - 1]) return 0 ;
if ((sum[p - 1] & 1) ^ (sum[q - 1] & 1))
return (bool)(sub(T[e1], T[s1] * base[e1 - s1] % P) == sub(S[e2], S[s2] * base[e2 - s2] % P)) ;
else
return (bool)(sub(S[e1], S[s1] * base[e1 - s1] % P) == sub(S[e2], S[s2] * base[e2 - s2] % P)) ;
}
int main(){
cin >> n ;
int x, y, l ; base[0] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%1d", &a[i]), sum[i] = sum[i - 1] + a[i] ;
for (int i = 1 ; i <= n ; ++ i){
if (!a[i]){
++ len ; base[len] = (base[len - 1] * Base) % P ;
S[len] = (S[len - 1] * Base % P + (sum[i] & 1)) % P ;
T[len] = (T[len - 1] * Base % P + ((sum[i] & 1) ^ 1)) % P ;
}
}
cin >> m ;
while (m --){
scanf("%d%d%d", &x, &y, &l) ;
if (check(x, y, l)) puts("Yes") ; else puts("No") ;
}
return 0 ;
}

总结

感觉这场CF办的就跟闹着玩一样.jpg