Codeforces Round 533 (Div. 2) 题解

发表于 | 分类于 |
字数统计: 1,685 字

感觉这次比较简单…?

A

题目链接

一个简单的贪心。对每一个棍子，设其长度为$k$，分别选取$k+1,k,k-1$作为$t$，然后求出总代价，选总代价最小的方案即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int n, a[1005], ans = 2000000000, t = 0;
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    for(int i = 0; i < n; ++i){
        for(int j = max(1, a[i] - 1); j <= a[i] + 1; ++j){
            int s = 0;
            for(int k = 0; k < n; ++k){
                if(abs(a[k] - j) <= 1) continue;
                if(a[k] > j) s += a[k] - j - 1;
                else s += j - a[k] - 1;
            }
            if(s < ans) ans = s, t = j;
        }
    }
    printf("%d %d\n", t, ans);
    return 0;
}

B

题目链接

先用类似滑动窗口的方法找到这些子串并在相应子串的末尾处打上标记，然后DP即可。
设$f(i, j)$表示到第$i$位为止，所有已选择的子串均包含字母$j$+'a'的情况下，不相交子串的最大数目，则：

其中$a(i, j)$表示以下标为$i$的字符为结尾的子串是否存在，存在为$1$，不存在为$0$。

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
#include <bits/stdc++.h>
using namespace std;
char s[200005];
int n, k, f[200005][27] = {0};
int cnt[27] = {0};
int main(){
    scanf("%d%d%s", &n, &k, s);
    for(int i = 0; i < k; ++i)
        cnt[s[i] - 'a']++;
    if(cnt[s[0] - 'a'] == k)
        f[k - 1][s[0] - 'a']++;
    for(int i = k; i < n; ++i){
        cnt[s[i - k] - 'a']--,
        cnt[s[i] - 'a']++;
        if(cnt[s[i] - 'a'] == k)
            f[i][s[i] - 'a']++;
    }
    int ans = 0;
    for(int i = 0; i < 26; ++i)
        ans = max(ans, f[k - 1][i]);
    for(int i = k; i < n; ++i)
        for(int j = 0; j < 26; ++j)
            f[i][j] = max(f[i][j] + f[i - k][j], f[i - 1][j]), ans = max(ans, f[i][j]);
    printf("%d\n", ans);
    return 0;
}

C

题目链接

分别算出$l$和$r$之间有多少模$3$余$0, 1, 2$的数，然后按数列的每一位，根据到这一位为止的数列之和的模$3$余数DP。具体见代码。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, l, r, c1, c2, c3;
ll f[200005][4] = {0}, M = 1000000007;
int main(){
    scanf("%d%d%d", &n, &l, &r);
    int t1, t2;
    t1 = (l - 2) / 3, t2 = (r - 1) / 3;
    c1 = t2 - t1;
    if(l == 1) c1++;//特判1
    f[0][1] = c1;
    t1 = (l - 3) / 3, t2 = (r - 2) / 3;
    c2 = t2 - t1;
    if(l <= 2 && r >= 2) c2++;//特判2
    f[0][2] = c2;
    t1 = (l - 1) / 3, t2 = r / 3;
    c3 = t2 - t1, f[0][0] = c3;
    //printf("%d %d %d\n", c1, c2, c3);
    for(int i = 1; i < n; ++i){
        f[i][0] = ((f[i - 1][1] * c2) % M + (f[i - 1][2] * c1) % M + (f[i - 1][0] * c3) % M) % M;
        f[i][1] = ((f[i - 1][2] * c2) % M + (f[i - 1][0] * c1) % M + (f[i - 1][1] * c3) % M) % M;
        f[i][2] = ((f[i - 1][0] * c2) % M + (f[i - 1][1] * c1) % M + (f[i - 1][2] * c3) % M) % M;
    }
    printf("%I64d\n", f[n - 1][0]);
    return 0;
}

D

题目链接

一个大模拟，每一回合对每一个人做一次BFS即可。
注意可能有格子被障碍围了起来，无法接触！

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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pp;
int n, m, p, s[11], cur[11] = {0};
int grid[1005][1005] = {0}, cnt = 0;
vector<pp> inte[11];
char ss[1005];
int que[2000005][3], hd = 0, ra = 0;
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
void expand(int id){
    for(int &i = cur[id]; i < inte[id].size(); ++i)
        que[ra][0] = inte[id][i].first, que[ra][1] = inte[id][i].second,
        que[ra++][2] = 0;
    while(ra > hd){
        int xx, yy, step;
        xx = que[hd][0], yy = que[hd][1], step = que[hd++][2];
        if(step == s[id]) continue;
        for(int i = 0; i < 4; ++i){
            int cx = xx + dx[i], cy = yy + dy[i];
            if(cx < 0 || cx >= n || cy < 0 || cy >= m)
                continue;
            if(grid[cx][cy] == 0)
                grid[cx][cy] = id + 1, 
                cnt++, 
                que[ra][0] = cx, que[ra][1] = cy, que[ra++][2] = step + 1, 
                inte[id].push_back(make_pair(cx, cy));
        }
    }
}
int main(){
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 0; i < p; ++i)
        scanf("%d", &s[i]), s[i] = min(s[i], n + m);
    for(int i = 0; i < n; ++i){
        scanf("%s", ss);
        for(int j = 0; j < m; ++j)
            if(isdigit(ss[j])){
                int id = ss[j] - '0' - 1;
                inte[id].push_back(make_pair(i, j));
                grid[i][j] = id + 1;
                cnt++;
            }else if(ss[j] == '#')
                grid[i][j] = -1, cnt++;
    }
    while(cnt != n * m){
        int flag = 0;
        for(int i = 0; i < p; ++i){
            int ori = inte[i].size();
            expand(i);
            if(ori < inte[i].size())
                flag = 1;
        }
        if(!flag) break;
    }
    for(int i = 0; i < p - 1; ++i)
        printf("%d ", inte[i].size());
    printf("%d\n", inte[p - 1].size());
    return 0;
}

E

题目链接

可以发现多个1事件连在一起时效果和只有一个1事件是一样的，所以在读入时可以做处理。
考虑每一个1事件后跟着的一连串2事件。在这一连串2事件中，如果有两个不同的人，那么就出现“有我没他”的局面，选了一个人另一个人就不能选。
因此可以考虑向图论问题转化，把人视作点，如果出现了上述局面就在两个人之间连一条边，然后问题变为求该图的最大独立集。用求补图最大团的方法解决。
顺带一提，这题时限很紧，要用各种压位。。。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, tot = 0, lis[45], cnt = 0, ans = 0;
map<string, int> mp;
ll conn[45] = {0};
int count1(ll x){
    int res = 0;
    while(x){
        if(x & 1) res++;
        x >>= 1;
    }
    return res;
}
void bron_kerbosch(ll R, ll P, ll X){
    if(!P && !X){
        ans = max(ans, count1(R));
        return ;
    }
    ll pv = P | X, P_ = P;
    int id = 0;
    while(((1ll << id) & pv) == 0)
        id++;
    P_ -= (P_ & conn[id]);
    for(ll i = 1, j = 0; i <= P_; i <<= 1, ++j){
        if(!(i & P)) continue;
        bron_kerbosch(R | i, P & conn[j], X & conn[j]);
        P ^= i, X |= i;
    }
}
int main(){
    scanf("%d%d", &n, &m);
    char name[45];
    int d;
    scanf("%d", &d);
    for(int i = 1; i < n; ){
        int j = i, d;
        for(; j < n; ){
            scanf("%d", &d);
            if(d == 1) j++;
            else break;
        }
        if(j == n) break;
        cnt = 0;
        ll in = 0;
        for(; j < n; ){
            scanf("%s", name);
            string st(name);
            if(!mp.count(st))
                mp[st] = ++tot;
            int id = mp[st] - 1;
            if(!((1ll << id) & in)){
                in += (1ll << id), lis[cnt] = id;
                for(int k = 0; k < cnt; ++k)
                    conn[id] |= (1ll << lis[k]), 
                    conn[lis[k]] |= (1ll << id);
                cnt++;
            }
            if(j < n - 1) scanf("%d", &d);
            if(d == 2) j++;
            else break;
        }
        i = j + 2;
    }
    ll mask = (1ll << m) - 1ll;
    for(int i = 0; i < m; ++i)
        conn[i] ^= mask, conn[i] ^= (1ll << i);
    bron_kerbosch(0, (1ll << m) - 1, 0);
    printf("%d\n", ans);
    return 0;
}

小结

时隔很长时间的一次CF，因为题目比较容易没有看起来太菜，但是E还是没有写出来。。。
知识漏洞补全刻不容缓。

Powered By Valine
v1.5.2