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

Educational Codeforces Round 82

比赛链接 / 官方题解链接

A. Erasing Zero

Solution

删去第一个 $1$ 和最后一个 $1$ 之间的 $0$.

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

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...);}

int T;
char s[105];

int main(){
    read(T);
    while(T--){
        int fir = 105, lst = 0, cnt = 0;
        scanf("%s", s+1);
        int n = strlen(s+1);
        for(int i = 1; i <= n; i++){
            if(s[i] == '1'){
                fir = min(fir, i);
                lst = max(lst, i);
            }
        }
        for(int i = fir; i <= lst; i++)
            if(s[i] == '0')
                cnt++;
        printf("%d\n", cnt);
    }
    return 0;
}

B. National Project

Solution

找到达到要求的 “good day” 在第几块（一个连续 $g$ 天算一“块”），计算此时够不够 $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
#include<algorithm>
#include<cstdio>

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;
LL n, g, b;

int main(){
    read(T);
    while(T--){
        read(n, g, b);
        LL m = (n + 1) / 2;
        LL x = m / g;
        LL remain = m - x * g;
        if(m % g != 0)   x++;
        if(m % g == 0)  remain += g;
        if((x - 1) * (b + g) + remain >= n)    printf("%lld\n", (x - 1) * (b + g) + remain);
        else    printf("%lld\n", n);
    }
    return 0;
}

C. Perfect Keyboard

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
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<cstring>
#include<cstdio>
#include<vector>

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 = 205;

int T;
char s[N];
bool vis[N], g[N][N];
vector<int> v[N];
vector<char> ans;

void dfs(int x){
    vis[x] = 1;
    ans.push_back(x+'a'-1);
    for(int i = 0; i < v[x].size(); i++){
        if(vis[v[x][i]])  continue;
        dfs(v[x][i]);
    }
}

int main(){
    read(T);
    while(T--){
        scanf("%s", s+1);
        int n = strlen(s+1);
        if(n == 1){
            puts("YES");
            for(int i = 1; i <= 26; i++)
                putchar(i+'a'-1);
            puts("");
            continue;
        }
        ans.clear();
        for(int i = 1; i <= 26; i++)    v[i].clear();
        memset(vis, 0, sizeof vis);
        memset(g, 0, sizeof g);
        for(int i = 1; i < n; i++){
            if(!g[s[i]-'a'+1][s[i+1]-'a'+1]){
                g[s[i]-'a'+1][s[i+1]-'a'+1] = g[s[i+1]-'a'+1][s[i]-'a'+1] = true;
                v[s[i]-'a'+1].push_back(s[i+1]-'a'+1);
                v[s[i+1]-'a'+1].push_back(s[i]-'a'+1);
            }
        }
        bool cntbigger2 = false;
        int cnt1 = 0, mark = 0;
        for(int i = 1; i <= 26; i++){
            if(v[i].size() > 2){
                cntbigger2 = true;
                break;
            }
            if(v[i].size() == 1){
                cnt1++;
                if(!mark)   mark = i;
            }
        }
        if(cntbigger2 || cnt1 != 2){
            puts("NO");
            continue;
        }
        dfs(mark);
        puts("YES");
        for(int i = 0; i < ans.size(); i++)
            printf("%c", ans[i]);
        for(int i = 1; i <= 26; i++)
            if(!vis[i])
                putchar(i+'a'-1);
        puts("");
    }
    return 0;
}

D. Fill The Bag

Solution

显然 $n>\sum a_i$ 时无解，否则一定有解。

设 $bn$ 是 $n$ 的二进制表示，$bt$ 每一位是对应 $a_i$ 的出现次数，那么题述操作可转化为：

  • $bt$ 低位 $2$ 变高位 $1$，花费 $0$. 例如：$105020\rightarrow121100$
  • $bt$ 高位 $1$ 拆成低位 $2$，花费 $1$. 例如：$101000\rightarrow100200$

从低到高依次考虑 $bn$ 中的 $1$，先尝试用 $bt$ 的低位合成高位消去它（花费 $0$），不行的话就用 $bt$ 的高位拆成低位消去它（花费 $=$ 高位与低位的差）。

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
#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 = 100005;

int T, m, pt1, pt2;
LL n, a[N], ans;
int bt[100], bn[100];

int main(){
    read(T);
    while(T--){
        memset(bt, 0, sizeof bt);
        memset(bn, 0, sizeof bn);
        read(n, m);
        LL sum = 0;
        for(int i = 1; i <= m; i++)
            read(a[i]), sum += a[i];
        if(n > sum){ puts("-1"); continue; }
        for(int i = 1; i <= m; i++)
            bt[(int)log2(a[i])]++;
        while(n){
            bn[(int)log2(n)]++;
            n -= (LL)pow(2, (LL)log2(n));
        }
        pt1 = pt2 = 0;
        ans = 0;
        while(1){
            while(pt1 <= 60 && bn[pt1] == 0)    pt1++;
            if(pt1 > 60)    break;
            for(int i = 0; i < pt1; i++){
                if(bt[i] >= 2){
                    bt[i+1] += bt[i] / 2;
                    bt[i] %= 2;
                }
            }
            if(bt[pt1]){
                bt[pt1] -= bn[pt1], bn[pt1] = 0;
                continue;
            }
            pt2 = pt1;
            while(pt2 <= 60 && bt[pt2] == 0)    bt[pt2]++, pt2++;
            bt[pt2]--;
            ans += pt2 - pt1;
            bt[pt1] -= bn[pt1], bn[pt1] = 0;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

E. Erase Subsequences

Solution

【参考官方题解】$t$ 是由两部分拼成的，自然可以想到枚举拼接点，把 $t$ 拆成 $a,b$ 两块。问题转化成：已知 $a,b$，判断 $s$ 能否通过题目操作生成 $a,b$.

考虑 $dp$：

  • $dp$ 状态：设 $dp[i][j]$ 表示能生成 $a$ 的前 $i$ 位和 $b$ 的前 $j$ 位的 $s$ 中最小位置。
  • 转移方程：设 $k=dp[i-1][j]$，则我们已经知道 $a$ 的前 $i-1$ 位和 $b$ 的前 $j$ 位至少需要从 $s_{1…k}$ 生成出来，现在在 $t$ 后面加上 $a_i$，则 $s$ 中的最小位置就是 $k$ 之后第一个出现 $a_i$ 的位置。为此，我们预处理一个 $nxt[pos][ch]$，用来表示 $s$ 中 $pos$ 位置之后第一个 $ch$ 的位置。于是乎，$dp[i][j] = nxt[k][a_i]$；同理，设 $l = dp[i][j-1]$，有 $dp[i][j]=nxt[l][b_j]$，二者取最小即可。
  • 转移顺序：由方程可知，循环 $i,j$ 即可。
  • 边界条件：$dp[0][0] = 0$

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

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...);}

const int N = 405;

int T;
char s[N], t[N];
int dp[N][N], nxt[N][200];

int main(){
    read(T);
    while(T--){
        scanf("%s", s+1);
        scanf("%s", t+1);
        memset(dp, 0, sizeof dp);
        int n = strlen(s+1), m = strlen(t+1);
        for(int k = 'a'; k <= 'z'; k++)
            nxt[n][k] = nxt[n+1][k] = n+1;
        for(int i = n-1; i >= 0; i--){
            for(int k = 'a'; k <= 'z'; k++){
                if(s[i+1] == k)   nxt[i][k] = i + 1;
                else    nxt[i][k] = nxt[i+1][k];
            }
        }
        bool ok = false;
        for(int k = 1; k <= m; k++){
            for(int i = 0; i < k; i++){
                for(int j = 0; j <= m - k + 1; j++){
                    dp[i][j] = 1e9;
                    if(!i && !j){ dp[i][j] = 0; continue; }
                    if(i)   dp[i][j] = min(dp[i][j], nxt[dp[i-1][j]][t[i]]);
                    if(j)   dp[i][j] = min(dp[i][j], nxt[dp[i][j-1]][t[j+k-1]]);
                }
            }
            if(dp[k-1][m-k+1] <= n && dp[k-1][m-k+1] > 0)   ok = true;
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}

F. Number of Components

Solution

【参考官方题解】我们单独考虑每个颜色。由于 $c_i\leq c_{i+1}$，所以对于每个颜色来说，一定是先加再删，不会在删之后有加入的情况。加的过程用并查集维护当前时间与上一时间的连通块改变量；删的过程是一个经典的删边并查集，即倒序加入，维护的倒序改变量即正序的负的改变量。

Tricks：为编程方便，我们可以增加在 $q+1$ 时间处删掉所有颜色的操作；然后并查集维护改变量，也就是说答案数组是一个差分数组。

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
#include<algorithm>
#include<cstdio>
#include<vector>

using namespace std;

typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

const int N = 305;
const int Q = 2000005;

int n, m, q, g[N][N], maxc;
bool b[N][N];
int ans[Q];

inline int num(int x, int y){ return (x - 1) * m + y; }

vector< pair<pii, int> > add[Q];
vector< pair<pii, int> > del[Q];

int fa[N*N];
int findfa(int x){ return fa[x] == x ? x : fa[x] = findfa(fa[x]); }
inline bool unionn(int x, int y){
    if(findfa(x) == findfa(y))  return false;
    fa[findfa(y)] = findfa(x);  return true;
}

inline void cal(vector< pair<pii, int> > &vec, int coeff){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            fa[num(i, j)] = num(i, j), b[i][j] = false;
    for(int k = 0; k < vec.size(); k++){
        int res = 1;
        int t = vec[k].second, x = vec[k].first.first, y = vec[k].first.second;
        b[x][y] = true;
        if(x > 1 && b[x-1][y])  res -= unionn(num(x, y), num(x-1, y));
        if(x < n && b[x+1][y])  res -= unionn(num(x, y), num(x+1, y));
        if(y > 1 && b[x][y-1])  res -= unionn(num(x, y), num(x, y-1));
        if(y < m && b[x][y+1])  res -= unionn(num(x, y), num(x, y+1));
        ans[t] += coeff * res;
    }
}

int main(){
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= q; i++) {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        if(g[x][y] == c)    continue;
        maxc = max(maxc, c);
        del[g[x][y]].pb(mp(mp(x, y), i));
        add[c].pb(mp(mp(x, y), i));
        g[x][y] = c;
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            del[g[i][j]].pb(mp(mp(i, j), q + 1));
    for(int i = 0; i <= maxc; i++){
        cal(add[i], 1);
        reverse(del[i].begin(), del[i].end());
        cal(del[i], -1);
    }
    ans[0] = 1;
    for(int i = 1; i <= q; i++)
        printf("%d\n", ans[i] += ans[i-1]);
    return 0;
}

G. Sum of Prefix Sums

Solution

【参考官方题解】树上路径问题，考虑点分治。

先思考一个简化版本：求 $s_1+s_2+\cdots+s_k$ 的最大值。那么我们在计算经过重心的路径时，只需要统计来自不同子树的权值最大路径即可，而且这些路径的一端一定是叶节点。

现在观察要求的式子：

其值与路径长度挂钩，我们只好无奈地对于每个叶节点都去考虑其他子树中的叶节点对它的答案。一对一考虑是 $O(n^2)$ 的，需要对上式进行一些调整：设分治点为 $c$，它的一个子树 $A$ 有叶节点 $x$，另一个子树 $B$ 有叶节点 $y$，从 $x$ 到 $c$ 的路径上的数字是 $a_1,a_2,\cdots,a_k$（包括 $c$），从 $c$ 到 $y$ 路径上的数字是 $b_1,b_2,\cdots,b_l$（不包括 $c$）。 设 $sum_A=\sum\limits_{i=1}^ka_i$，$psum_A=\sum\limits_{i=1}^k(k-i+1)a_i$，$psum_B=\sum\limits_{i=1}^l(l-i+1)b_i$，那么原式可写作：

上文提到，我们要枚举每个叶节点，计算它与其他子树的叶节点的答案。假设我们正在枚举一个叶节点 $y$，也就固定了 $l$ 和 $psum_B$，视 $sum_A$ 为斜率，$psum_A$ 为截距，那么上式是一条直线在 $x=l$ 处的值加上 $psum_B$. 要求所有这些直线在 $x=l$ 处的最大值，就是一个李超线段树的模板了。

枚举按照一下顺序：正着扫一遍子树，每扫到一个子树先在李超树中询问，然后将其加入李超树，然后再反过来扫一遍（因为路径答案与方向有关）。

注意：

  1. 特判只有一个子树的情况
  2. 清空李超树时用一个回收队列记录，不要直接全部清空（破坏复杂度）

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
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
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>

using namespace std;

typedef long long LL;

const int N = 150005;
const int INF = 1e9;

struct LiChaoTree{
    static inline LL getVal(int x, double k, double b){ return k * x + b; }
    struct segTree{
        int l, r;
        LL k, b;
    }tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((l + r) >> 1)
    queue<int> recycle;
    void clear(){
        while(!recycle.empty()){
            tr[recycle.front()].k = tr[recycle.front()].b = 0;
            recycle.pop();
        }
    }
    void insert(int id, int l, int r, double k, double b){
        if(l == r){
            if(getVal(mid, k, b) > getVal(mid, tr[id].k, tr[id].b))
                tr[id].k = k, tr[id].b = b, recycle.push(id);
            return;
        }
        if(k > tr[id].k){
            if(getVal(mid, k, b) > getVal(mid, tr[id].k, tr[id].b)){
                insert(lid, l, mid, tr[id].k, tr[id].b);
                tr[id].k = k, tr[id].b = b, recycle.push(id);
            }
            else  insert(rid, mid+1, r, k, b);
        }
        else{
            if(getVal(mid, k, b) > getVal(mid, tr[id].k, tr[id].b)){
                insert(rid, mid+1, r, tr[id].k, tr[id].b);
                tr[id].k = k, tr[id].b = b, recycle.push(id);
            }
            else    insert(lid, l, mid, k, b);
        }
    }
    LL query(int id, int l, int r, int x){
        if(l == r)    return getVal(x, tr[id].k, tr[id].b);
        if(x <= mid)    return max(getVal(x, tr[id].k, tr[id].b), query(lid, l, mid, x));
        else    return max(getVal(x, tr[id].k, tr[id].b), query(rid, mid+1, r, x));
    }
}lichao;

int n;
LL a[N], ans;

struct Edge{
    int nxt, to;
}edge[N<<1];
int head[N], edgeNum;
void addEdge(int from, int to){
    edge[++edgeNum] = (Edge){head[from], to};
    head[from] = edgeNum;
}

int root, sum, mxson[N], siz[N];
bool vis[N];
void getRoot(int x, int f){
    mxson[x] = 0, siz[x] = 1;
    for(int i = head[x]; i; i = edge[i].nxt){
        if(edge[i].to == f || vis[edge[i].to])	continue;
        getRoot(edge[i].to, x);
        siz[x] += siz[edge[i].to];
        mxson[x] = max(mxson[x], siz[edge[i].to]);
    }
    mxson[x] = max(mxson[x], sum - siz[x]);
    if(mxson[root] > mxson[x])	root = x;
}

LL sumA[N], psumA[N], psumB[N], lB[N];
vector<int> vec[N];
void getVal(int x, int f, int d, LL SumA, LL SumB){
    sumA[x] = SumA, psumA[x] = psumA[f] + d * a[x];
    lB[x] = d - 1, psumB[x] = psumB[f] + SumB;
    for(int i = head[x]; i; i = edge[i].nxt){
        if(edge[i].to == f || vis[edge[i].to])  continue;
        getVal(edge[i].to, x, d + 1, SumA + a[edge[i].to], SumB + a[edge[i].to]);
    }
}
void getVec(int k, int x, int f){
    bool isLeaf = true;
    for(int i = head[x]; i; i = edge[i].nxt){
        if(edge[i].to == f || vis[edge[i].to])  continue;
        isLeaf = false;
        getVec(k, edge[i].to, x);
    }
    if(isLeaf)  vec[k].push_back(x);
}
void solve(int x){
    int cnt = 0; // count the number of subtrees
    for(int i = head[x]; i; i = edge[i].nxt){
        if(vis[edge[i].to]) continue;
        cnt++;
    }
    if(cnt == 0){ // no subtree
        ans = max(ans, a[x]);
        return;
    }
    getVal(x, 0, 1, a[x], 0);
    vector<int> nxt;                            // store subtree
    for(int i = head[x]; i; i = edge[i].nxt){
        if(vis[edge[i].to]) continue;
        nxt.push_back(edge[i].to);
        vec[edge[i].to].clear();
        getVec(edge[i].to, edge[i].to, x);      // store the leaves
    }
    if(cnt == 1){ // only 1 subtree
        for(int k = 0; k < vec[edge[head[x]].to].size(); k++){
            int p = vec[edge[head[x]].to][k];
            ans = max(ans, psumA[p]);
            ans = max(ans, psumB[p] + a[x] * (lB[p] + 1));
        }
    }
    else{       // >= 2 subtrees --- use Li Chao Tree to update the answer
        lichao.clear();
        for(int j = 0; j < nxt.size(); j++){
            for(int k = 0; k < vec[nxt[j]].size(); k++){
                int p = vec[nxt[j]][k];
                ans = max(ans, lichao.query(1, 1, n, lB[p]) + psumB[p]);
            }
            for(int k = 0; k < vec[nxt[j]].size(); k++){
                int p = vec[nxt[j]][k];
                lichao.insert(1, 1, n, sumA[p], psumA[p]);
            }
        }
        lichao.clear();
        for(int j = nxt.size() - 1; j >= 0; j--){
            for(int k = 0; k < vec[nxt[j]].size(); k++){
                int p = vec[nxt[j]][k];
                ans = max(ans, lichao.query(1, 1, n, lB[p]) + psumB[p]);
            }
            for(int k = 0; k < vec[nxt[j]].size(); k++){
                int p = vec[nxt[j]][k];
                lichao.insert(1, 1, n, sumA[p], psumA[p]);
            }
        }
    }

    vis[x] = true;
    for(int i = head[x]; i; i = edge[i].nxt){
        if(vis[edge[i].to]) continue;
        root = 0, sum = siz[edge[i].to], mxson[0] = INF;
        getRoot(edge[i].to, 0);
        solve(root);
    }
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i < n; i++){
        int u, v; scanf("%d%d", &u, &v);
        addEdge(u, v), addEdge(v, u);
    }
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    root = 0, sum = n, mxson[0] = INF;
    getRoot(1, 0);
    solve(root);
    printf("%lld\n", ans);
    return 0;
}

Educational Codeforces Round 82

http://xyfjason.github.io/blog-xcpc/2020/02/13/Educational-Codeforces-Round-82/

作者

xyfJASON

发布于

2020-02-13

更新于

2020-12-20

许可协议

#

评论

关注我

分类

最新文章

标签

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