发表更新ICPC/CCPC / Contests / Codeforces10 分钟读完 (大约1441个字)

Codeforces Global Round 7

比赛链接 / 官方题解链接

A. Bad Ugly Numbers

Solution

输出 $999\cdots98$ 或者$233\cdots3$ 之类的都行。

Code

>folded
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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int T, n;

int main(){
    read(T);
    while(T--){
        read(n);
        if(n == 1)  puts("-1");
        else{
            for(int i = 1; i < n; i++)  putchar('9');
            puts("8");
        }
    }
    return 0;
}

B. Maximums

Solution

从左到右依次恢复即可。

Code

>folded
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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 200005;

int a[N], b[N], n;

int main(){
    read(n);
    for(int i = 1; i <= n; i++) read(b[i]);
    int mx = 0;
    for(int i = 1; i <= n; i++){
        a[i] = b[i] + mx;
        mx = max(mx, a[i]);
    }
    for(int i = 1; i <= n; i++) printf("%d ", a[i]);
    return 0;
}

C. Permutation Partitions

Solution

最大值就是最大的 $k$ 个数之和。统计方案数时考虑在两个选出的数中插一个隔板，乘法原理即可。

Code

>folded
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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 200005;
const LL MOD = 998244353;

LL n, k;
LL p[N], ans, cnt = 1;

int main(){
    read(n, k);
    for(int i = 1; i <= n; i++) read(p[i]);
    ans = (2 * n + 1 - k) * k / 2;
    int pre = 0;
    for(int i = 1; i <= n; i++){
       if(p[i] >= n - k + 1){
           if(!pre) pre = i;
           else{
               (cnt *= i - pre) %= MOD;
               pre = i;
           }
       }
    }
    printf("%lld %lld\n", ans, cnt);
    return 0;
}

D1&D2. Prefix-Suffix Palindrome

Solution

先把头尾对称的字符加入答案并去掉，问题转化为寻找最大前缀/后缀回文串。为方便处理，字符两两之间插入 # 使长度为奇数。然后枚举中间点，通过正反哈希值判断能否形成回文串。

复杂度：$O(|s|)$

Code

>folded
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<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 2000005;
const LL MOD = 998244353;

LL h[N], invh[N], power[N], base = 233; // hash value of string s[1...i] is stored in h[i]
void Hash(char s[], int len){
    h[1] = s[1]; h[0] = 0;
    for(int i = 2; i <= len; i++)
        h[i] = (h[i-1] * base % MOD + s[i]) % MOD;
}
void invHash(char s[], int len){
    invh[len] = s[len]; invh[len+1] = 0;
    for(int i = len - 1; i >= 1; i--)
        invh[i] = (invh[i+1] * base % MOD + s[i]) % MOD;
}
LL getSubstring(int l, int r){ // get hash value of s[l...r]
    return ((h[r] - h[l-1] * power[r - l + 1] % MOD) % MOD + MOD) % MOD;
}
LL getSubstringinv(int l, int r){
    return ((invh[l] - invh[r+1] * power[r - l + 1] % MOD) % MOD + MOD) % MOD;
}

int T, n;
char s[N], ans[N], t[N];

int main(){
    power[0] = 1;
    for(int i = 1; i <= 1000000; i++)   power[i] = power[i-1] * base % MOD;
    read(T);
    while(T--){
        scanf("%s", s+1);
        n = strlen(s+1);
        if(n == 1){ printf("%s\n", s+1); continue; }
        int id = 0, l = 0, r = n + 1;
        for(int i = 1; i <= n / 2; i++){
            if(s[i] == s[n - i + 1])
                ans[++id] = s[i], l = i, r = n - i + 1;
            else    break;
        }
        if(l == r - 1){
            for(int i = 1; i <= id; i++)    putchar(ans[i]);
            for(int i = id; i >= 1; i--)    putchar(ans[i]);
            puts(""); continue;
        }

        int tid = 0;
        for(int i = l + 1; i < r; i++)  t[++tid] = s[i], t[++tid] = '#'; tid--;
        Hash(t, tid); invHash(t, tid);
        int mark = 0, mx = 0;
        for(int i = 1; i <= tid; i++){
            if(i <= tid - i + 1){
                if(getSubstring(1, i) == getSubstringinv(i, i + i - 1)){
                    if(mx < i){
                        mx = i;
                        mark = i;
                    }
                }
            }
            else{
                if(getSubstring(i - (tid - i + 1) + 1, i) == getSubstringinv(i, tid)){
                    if(mx < tid - i + 1){
                        mx = tid - i + 1;
                        mark = i;
                    }
                }
            }
        }
        if(mark <= tid - mark + 1) for(int i = 1; i <= mark; i++) ans[++id] = t[i];
        else for(int i = tid; i >= mark; i--) ans[++id] = t[i];
        for(int i = 1; i <= id; i++) if(ans[i] != '#') putchar(ans[i]);
        for(int i = id - 1; i >= 1; i--) if(ans[i] != '#') putchar(ans[i]);
        puts("");
    }
    return 0;
}

E. Bombs

Solution

【参考博客】答案是单调不增的。我们只需递减枚举答案上界 $x$，判断答案是否小于 $x$.

若答案小于 $x$，那么所有 $\geq x$ 的点都会被炸掉，于是乎：

  • 最靠右的 $\geq x$ 的点的右侧（包括自己）必须要有至少 $1$ 个炸弹
  • 次靠右的 $\geq x$ 的点的右侧必须要有至少 $2$ 个炸弹
  • $\cdots$
  • 第 $k$ 靠右的 $\geq x$ 的点的右侧必须要有至少 $k$ 个炸弹

我们维护一个序列 $a_i=其右的炸弹数-其右 \geq x 的数的数量$，若所有 $a_i$ 都 $\geq0$，则答案小于 $x$.

于是我们对这个序列的操作有：

  • 加入一个炸弹，将加入位置及其以前的所有 $a_i$ 加 $1$；
  • $x$ 变成 $x-1$，将数 $x-1$ 所在位置及其以前的所有 $a_i$ 减 $1$；
  • 询问所有 $a_i$ 的最小值。

线段树即可。

复杂度：$O(n\lg n)$

Code

>folded
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
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 300005;

struct segTree{
    int l, r, mn, lazy;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
inline void pushup(int id){
    tr[id].mn = min(tr[lid].mn, tr[rid].mn);
}
inline void pushdown(int id){
    if(tr[id].l == tr[id].r)    return;
    if(tr[id].lazy){
        tr[lid].lazy += tr[id].lazy;
        tr[lid].mn += tr[id].lazy;
        tr[rid].lazy += tr[id].lazy;
        tr[rid].mn += tr[id].lazy;
        tr[id].lazy = 0;
    }
}
void build(int id, int l, int r){
    tr[id].l = l, tr[id].r = r;
    if(tr[id].l == tr[id].r)    return;
    build(lid, l, mid);
    build(rid, mid+1, r);
    pushup(id);
}
void add(int id, int l, int r, int val){
    pushdown(id);
    if(tr[id].l == l && tr[id].r == r){
        tr[id].lazy += val;
        tr[id].mn += val;
        return;
    }
    if(r <= mid)    add(lid, l, r, val);
    else if(l > mid)    add(rid, l, r, val);
    else    add(lid, l, mid, val), add(rid, mid+1, r, val);
    pushup(id);
}

int n, p[N], q[N], pos[N];

int main(){
    read(n);
    for(int i = 1; i <= n; i++){
        read(p[i]);
        pos[p[i]] = i;
    }
    build(1, 1, n);
    printf("%d ", n);
    int x = n + 1;
    for(int i = 1; i <= n; i++){
        read(q[i]);
        if(i == n)  break;
        add(1, 1, q[i], 1);
        pushdown(1);
        while(tr[1].mn >= 0){
            x--;
            add(1, 1, pos[x], -1);
            pushdown(1);
        }
        printf("%d ", x);
    }
    return 0;
}

Codeforces Global Round 7

http://xyfjason.github.io/blog-xcpc/2020/03/20/Codeforces-Global-Round-7/

作者

xyfJASON

发布于

2020-03-20

更新于

2020-12-20

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×