【赛题整理】Codeforces[Global Round 7] $\rm A\to E$

这一场相对来说还是比较简单的,至少 $A\to E$ 都是比较传统的题目。

因为F对我来说不是很general,于是单开了一篇文章整理F了。

不知道为什么,感觉所有Global Round里面,最喜欢的还是第一场。

唉,过去的事情,也就只能让它过去了吧。

A

构造一个 $n$ 位十进制数,保证不被该数的任意一位整除。

$1\leq n\leq 100000$

感觉就是一个考反应能力的??大概就是瞎构造。正确性似乎不是那么显然?唯一的不确定性就是这种做法可能出现末尾接上 $ 3\sim 9$ 都不合法的情况,然而似乎数据卡不了这一点。

仔细想一想的话,需要满足以下的条件:

好的,我刚刚写完关于 $3$ 的就发现了,只要是 $77777…7774$ 就一定合法。我太弟弟了。

1
2
3
4
5
6
7
8
9
int main(){ 
cin >> T ;
while (T --){
cin >> n ;
if (n == 1) puts("-1") ;
for (int i = 1 ; i <= n - 1 ; ++ i) printf("7") ;
cout << 4 << endl ;
}
}

B

对于一个序列 $\{a_n\}$,定义序列 $\{c_n\}$ :$c_i=\max\{0,a_1,\cdots,a_{i-1}\}$ 。同时定义序列 $\{b_n\} :b_i=a_i-c_i$ 。

给定 $\{b_n\}$ ,求 $\{a_n\}$ 。

$1\leq n\leq 200,000$

谔谔,完全就是一道模拟题,不知道这种题是怎么当B的,一点技术含量也没有啊??

1
2
3
4
5
6
7
8
9
10
11
12
13
14
long long n, m ;
long long ans[500010] ;
long long base[500010] ;

int main(){
cin >> n ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%lld", &base[i]) ;
ans[1] = base[1] ; m = ans[1] ;
for (int i = 2 ; i <= n ; ++ i)
ans[i] = base[i] + m, m = max(ans[i], m) ;
for (int i = 1 ; i <= n ; ++ i)
printf("%lld ", ans[i]) ; return 0 ;
}

C

给定一个长度为 $n$ 的排列 $\{a_n\}$。要求将这个序列分成互不相交的 $k$ 段。记第 $p$ 段的左端点和右端点分别为 $l_p,r_p$ 。要求最大化

同时输出最大化该值的方案数。对 $998,244,353$ 取模。

发现显然 $n-k+1\sim n$ 这几个数是一定能取到的。乘法原理算一算区间怎么拆即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main(){
cin >> n >> k ; res = 1ll ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]) ;
for (int i = 1 ; i <= k ; ++ i)
ans += (ll)(n - i + 1) ;
for (int i = 1 ; i <= n ; ++ i){
if (base[i] > n - k){
if (lst)
(res *= (ll)(i - lst)) %= P ;
lst = i ;
}
}
cout << ans << " " << res << endl ;
}

D1

给定一个字符串。要求选取他的一个前缀(可以为空)和与该前缀不相交的一个后缀(可以为空)拼接成回文串,且该回文串长度最大。求该最大长度。

多组数据。保证 $\sum n\leq 5000$ 。

草,我做这题的时候就是nm离谱。感觉自己完全没带脑子。一开始读错题了,以为是个构造题,只要构造一个用了非空前缀和非空后缀拼出来回文串就好了,然后写完之后看完样例就蒙了。思考了半天才发现是最优化问题。然后此时还有大概2h左右,我就觉得大概不用仔细思考可以瞎写写。于是我就成功地用KMP很麻烦地求了这个串「最长的、拼在一起可以回文的前缀和后缀」,然后发现就是个Manacher板子题,然后又很麻烦地去判边界(不得不说这个manacher判边界的麻烦程度也是一绝)。

然后在我WA了好几发之后才发现「最长的、拼在一起可以回文的前缀和后缀」只要枚举一下就好了…惨惨…

然后就没有然后了。不过好在还是抢救回来了。中间很无奈D1写了个暴力,不过还是最后绝杀了D2…

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
char S[N] ;
char I[N] ;
int Len[N] ;
int len[N], st ;
int T, L, n, res ;
int ns[N], base[N] ;

int main(){
cin >> T ;
while (T --){
scanf("%s", S + 1) ;
n = strlen(S + 1) ;
res = 0 ; st = 0 ;
for (int i = 1 ; i <= n ; ++ i)
if (S[i] != S[n - i + 1]) break ; else st = i ;
int p = n - st ; int db = 0 ; int q = 0 ;
for (int i = st + 1 ; i <= p ; ++ i){
for (int j = st + 1 ; j <= i ; ++ j)
I[j - st] = S[j] ; int k = i - st ;
reverse(I + 1, I + k + 1) ; bool fg = 0 ;
for (int j = 1 ; j <= k ; ++ j)
if (I[j] != S[j + st]) { fg = 1 ; break ;}
if (!fg && k > res) res = i - st, db = 1 ;
}
for (int i = p ; i >= st + 1 ; -- i){
for (int j = i ; j <= p ; ++ j)
I[j - i + 1] = S[j] ; int k = p - i + 1 ;
reverse(I + 1, I + k + 1) ; bool fg = 0 ;
for (int j = 1 ; j <= k ; ++ j)
if (I[j] != S[j + i - 1]) { fg = 1 ; break ;}
if (!fg && k > res) res = k, db = 2 ;
}
if (!db){
cout << (S + 1) << endl ;
continue ;
}
if (db == 1){
for (int i = 1 ; i <= st + res ; ++ i) printf("%c", S[i]) ;
for (int i = n - st + 1 ; i <= n ; ++ i) printf("%c", S[i]) ;
}
else if (db == 2){
for (int i = 1 ; i <= st ; ++ i) printf("%c", S[i]) ;
for (int i = n - st - res + 1 ; i <= n ; ++ i) printf("%c", S[i]) ;
}
puts("") ;
}
}

D2

给定一个字符串。要求选取他的一个前缀(可以为空)和与该前缀不相交的一个后缀(可以为空)拼接成回文串,且该回文串长度最大。求该最大长度。

多组数据。保证 $\sum n\leq 10^6$ 。

嗯,jiangly确实是神仙。代码写的又快又整洁又有条理,比我高到不知道哪里去了…

感觉还是很难在做题的时候让自己保持清醒的头脑。还需要多加练习。

哦对,有个小细节需要说一下。就是用Manacher枚举每个位置,判断左界和右界能不能拼起来的时候,是需要取 $min$ 的。这也属于细节吧??

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
const int N = 3000010 ;

char S[N] ;
int ns[N], base[N] ;
int T, L, n, res, st ;

void Manacher(char *s){
int id, fars, i ;
id = 0, fars = 0 ; L = -1 ;
ns[++ L] = '$', ns[++ L] = '#' ;
//id : 最靠右的回文串的中心位置
//fars : 迄今为止最靠右的回文串的最右侧
for (i = 1 ; i <= n ; ++ i)
ns[++ L] = (int)s[i], ns[++ L] = '#' ;
for (i = 1 ; i <= L ; ++ i){
if (fars <= i) base[i] = 1 ;
else base[i] = min(fars - i + 1, base[id * 2 - i]) ;
while (ns[i + base[i]] == ns[i - base[i]]) base[i] ++ ;
if (i + base[i] > fars) id = i, fars = i + base[i] - 1 ;
}
}
int main(){
cin >> T ; int op = T ;
while (T --){
scanf("%s", S + 1) ;
n = strlen(S + 1) ; res = st = 0 ;
for (int i = 1 ; i <= n ; ++ i)
if (S[i] != S[n - i + 1]) break ; else st = i ;
int p = n - st ; int db = 0 ;
Manacher(S) ; //cout << st << endl ;
//for (int i = 1 ; i <= L ; ++ i) cout << base[i] << " " ; puts("") ;
for (int i = 1 ; i <= L ; ++ i){
int l = i / 2 - base[i] / 2 + 1 ;
int r = i / 2 + base[i] / 2 - 1 + (bool)(ns[i] == '#') ;
int p = base[i] - 1, q = base[i] - 1 ;
//cout << l << " " << r << " " << base[i] << " " << p << " " << q << endl ;
if (l <= st) p -= 2 * (st - l + 1) ;
if (r >= n - st + 1) p = min(p, q -= 2 * (r - n + st)) ;
//cout << base[i] << " " << p << " " << q << endl ;
l = i / 2 - (p + 1) / 2 + 1 ;
r = i / 2 + (p + 1) / 2 - 1 + (bool)(ns[i] == '#') ;
if (p > res && l <= st + 1) db = 1, res = p ;
if (p > res && r >= n - st) db = 2, res = p ;
}
//cout << db << endl ;
for (int i = 0 ; i <= L + 2 ; ++ i)
ns[i] = 0, base[i] = 0 ;
if (!db){
cout << (S + 1) << endl ;
continue ;
}
//cout << res << endl ;
if (db == 1){
for (int i = 1 ; i <= st + res ; ++ i) printf("%c", S[i]) ;
for (int i = n - st + 1 ; i <= n ; ++ i) printf("%c", S[i]) ;
}
else if (db == 2){
for (int i = 1 ; i <= st ; ++ i) printf("%c", S[i]) ;
for (int i = n - st - res + 1 ; i <= n ; ++ i) printf("%c", S[i]) ;
}
puts("") ;
}
}

E

给定两个长度均为 $n$ 的排列 $p,q$ 。对一个初始为空的集合 $s$ 进行如下操作:对于每个 $i$ ,将 $p_i$ 放入集合;如果 $i$ 被标记了,则此时再将集合中最大的数删除。求 $n$ 次操作后集合中最大的数。

排列 $q$ 的意义是,对于每个 $i$ ,询问将 $q_1,q_2\cdots q_{i-1}$ 都标记之后的上述操作的结果。

$1\leq n\leq 300,000$。

这是个神题。其实也不算严格意义上的神,只是我没注意到很多性质导致gg。

首先考虑答案最后一定是单调的。于是根据这个性质考虑何时应当把答案 $-1$ 。发现如果对于当前的一个答案 $x$ ,所有 $>x$ 的数右边均有一个炸弹,那么答案就需要 $-1$ 。所以拆分下来的话,每次只需要考虑 $x$ 的右边是否存才一个未被占的炸弹即可。

考虑如何实现这个过程。对于每个 $i$ 记录包括 $i $ 在内的右边有多少 $>x$ 的数,且有多少炸弹。如果前者减后者对于所有 $i$ 而言均 $\leq 0$ ,$ans$ 就 $-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
using namespace std ;

const int N = 600010 ;

int n ;
int ans ;
int pos[N] ;
int base[N] ;
int s[N * 3] ;
int tg[N * 3] ;

void _up(int x){
s[x] = max(s[x << 1], s[x << 1 | 1]) ;
}
void _down(int x){
if (tg[x]){
s[x << 1] += tg[x] ;
s[x << 1 | 1] += tg[x] ;
tg[x << 1] += tg[x] ;
tg[x << 1 | 1] += tg[x] ;
tg[x] = 0 ;
}
}
void update(int rt, int l, int r, int ul, int ur, int v){
if (ul <= l && r <= ur)
return s[rt] += v, tg[rt] += v, void() ;
int mid = (l + r) >> 1 ; _down(rt) ;
if (ul <= mid) update(rt << 1, l, mid, ul, ur, v) ;
if (ur > mid) update(rt << 1 | 1, mid + 1, r, ul, ur, v) ;
_up(rt) ;
}
int main(){
cin >> n ; int q ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]), pos[base[i]] = i ;
ans = n ; update(1, 1, n, 1, pos[ans], 1) ;
for (int i = 1 ; i <= n ; ++ i){
cout << ans << ' ' ; cin >> q ;
if (i == n) return 0 ; update(1, 1, n, 1, q, -1) ;
for ( ; s[1] <= 0 ; ) update(1, 1, n, 1, pos[-- ans], 1) ;
}
return 0 ;
}