Educational Codeforces Round 31 题解

2017/10/28

A. Book Reading

签到题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

int N, T;

int main() {
    scanf("%d %d", &N, &T);
    
    int c;
    for(int i=1;i<=N;i++) {
        scanf("%d", &c);
        
        T -= (86400 - c);
        
        if(T <= 0) return printf("%d\n", i), 0;
    }
    
    printf("%d\n", N);
}

B. Japanese Crosswords Strike Back

继续签到

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

int N, X;

int main() {
    scanf("%d %d", &N, &X);
    
    int p = 0;
    int c;
    for(int i=1;i<=N;i++) {
        scanf("%d", &c);
        p += c;
    }
    
    p += N - 1;
    
    puts(p == X ? "YES" : "NO");
}

C. Bertown Subway

少看条件签到失败。

给一个图,每个点入度出度均为 1 ,定义一个图的权值为存在多少对 (u, v) 存在路径 u -> v

现在可以更新两个点的出边,求图上的最大权值。

两眼昏花少看了入度为 1 的条件,以为是 基环树 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int SIZ = int(2e5) + 2007;
typedef long long LL;
int nxt[SIZ];
int N;

int vis[SIZ];
int c[SIZ], cpos;

void dfs(int u) {
    int v = u;
    while(!vis[v]) {
        c[cpos]++;
        vis[v] = 1;
        v = nxt[v];
    }
    cpos++;
}

int main() {
    scanf("%d", &N);
    
    for(int i=1;i<=N;i++) {
        scanf("%d", &nxt[i]);
    }
    
    for(int i=1;i<=N;i++) {
        if(!vis[i]) dfs(i);
    }
    
    LL ans = 0;
    if(cpos == 1) {
        ans = (1LL * c[0] * c[0]);
    } else {
        sort(c, c + cpos);
        c[cpos-2] += c[cpos-1]; cpos--;
        for(int i=0;i<cpos;i++) ans += (1LL * c[i] * c[i]);
    }
    
    printf("%lld\n", ans);
}

D. Boxes And Balls

有一些盒子和一些不同颜色的球,初始的时候都在第一个盒子里。

输入给定目标状态,使得第 i 个盒子中恰有所有颜色为 i 的球(共 Bi 个)。

定义每次操作可以取出一个盒子中的全部球,分成 2 份或 3 份,放到任意空的盒子里。 每次操作的代价是取出球的个数,总代价是各次操作代价的和。

求最小化操作代价。

反过来考虑如何把目标状态变成其实状态,每次合并 2 个或者 3 个节点, 合并代价为节点和,因此仿照荷马史诗写一个 3叉霍夫曼。

 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
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int SIZ = int(2e5) + 2007;
typedef long long LL;

int N;

priority_queue<LL, vector<LL>, greater<LL> > pq;
int main() {
    scanf("%d", &N);
    
    int c;
    for(int i=1;i<=N;i++) {
        scanf("%d", &c);
        pq.push(c);
    }
    
    if((N & 1) == 0) N++, pq.push(0);

    LL ans = 0;
    for(int i=N;i>1;i-=2) {
        LL n = 0;
        n += pq.top(); pq.pop();
        n += pq.top(); pq.pop();
        n += pq.top(); pq.pop();
        
        ans += n; pq.push(n);
    }
    
    printf("%lld\n", ans);
}

E. Binary Matrix

求一个大小为 的 0-1 矩阵上的 1 联通块数目。

内存限制 16 M。

答案变动只用考虑相邻两行,于是用滚动 bitset 存储信息,并查集维护行内的连通性信息。

 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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <vector>
using namespace std;
const int SIZ = 2<<16;

int LUT[256];
bitset<SIZ> cur, tmp;
char buf[SIZ];
int N, M;

struct seg {
    int l, r, num;
    bool flag;
}; int npos;
vector<seg> vlst, vcur;

int fa[SIZ<<1];

int find(int x) {
    return fa[x] == x ? x : (fa[x] = find(fa[x]));
}

void unite(int x, int y) {
    x = find(x), y = find(y);
    fa[x] = y;
}

int lut[SIZ];
int ans = 0;
int main() {
    for(int i=0;i<10;i++) LUT[i + '0'] = i;
    for(int i=0;i<6;i++) LUT[i + 'A'] = 10 + i;
    
    scanf("%d %d", &N, &M);
    for(int i=1;i<=N;i++) {
        scanf("%s", buf);
        
        for(int j=0;j<M;j+=4) {
            int c = LUT[int(buf[j>>2])];
            cur[j | 3] = c & 1; c >>= 1;
            cur[j | 2] = c & 1; c >>= 1;
            cur[j | 1] = c & 1; c >>= 1;
            cur[j | 0] = c & 1; c >>= 1;
        }
        cur[M] = 0;
        
        for(int i=0;i<=M;i++) fa[i] = i;
        for(int i=0;i<=M;i++) lut[i] = -1;
        
        int l;
        bool flag = false; int num = 0;
        int pos = 0, ppos = vlst.size();
        for(int i=0;i<=M;i++) {
            if(pos < ppos && i > vlst[pos].r) {
                pos++;
            }
            
            if(cur[i]) {
                if(flag == false) l = i, flag = true;
                if(pos < ppos && vlst[pos].l <= i && i <= vlst[pos].r) {
                    if(num == 0) num = find(vlst[pos].num);
                    else if(find(num) != find(vlst[pos].num))
                        ans--, unite(vlst[pos].num, num);
                }
            } else {
                if(flag) {
                    if(!num) ans++, num = ++npos;
                    vcur.push_back(seg{l, i-1, num});
                    flag = false, num = 0;
                }
            }
        }
        
        npos = 0;
        for(seg &s : vcur) {
            int x = find(s.num);
            if(lut[x] == -1) lut[x] = ++npos;
            s.num = lut[x];
        }
        
//      for(seg s : vcur) {
//          printf("(%d, %d, %d)\n", s.l, s.r, s.num);
//      }
        
        vlst = vcur;
        vcur.clear();
//      printf("%d\n", ans);
    }
    
    printf("%d\n", ans);
}

F. Anti-Palindromize

定义反回文串是一种长度为偶数且任意对称位置字符不相同的串。

输入一个字符串,求这个字符串的一个反回文排列,如果该反回文排列中第 i 项与原串相同, 那么获得一个 Bi 的权值。求最大化的权值和。

因为是求一个带优化目标的匹配,所以考虑最大费用最大流。

建图非常玄学。

  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
//#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cassert>
using namespace std;
const int SIZ = 10000;

int N;
char buf[SIZ];
int val[SIZ];
int cnt[26];
int gpos, letter[26], _pair[SIZ];

struct tgno {
    int u, v, c, w, f;
    tgno *n;
    tgno *r;
} POOL[SIZ<<1], *Head[SIZ]; int ppos;

void addEdge(int u, int v, int c, int w) {
    int a = ppos, b = ppos+1; ppos += 2;
    POOL[a] = tgno{u, v, c, w, 0, NULL, NULL};
    POOL[b] = tgno{v, u, 0,-w, 0, NULL, NULL};
    
    POOL[a].n = Head[u];
    Head[u] = &POOL[a];
    
    POOL[b].n = Head[v];
    Head[v] = &POOL[b];
    
    POOL[a].r = &POOL[b];
    POOL[b].r = &POOL[a];
}

const int _inf = 0x3f3f3f3f;
int Flow, Cost;
int vis[SIZ], dis[SIZ], adv[SIZ];
tgno* pre[SIZ];

bool SPFA(int s, int t) {
    fill(dis, dis + SIZ, _inf);
    fill(pre, pre + SIZ, (tgno*)NULL);
    fill(vis, vis + SIZ, 0x00);
    
    queue<int> q; q.push(s);
    dis[s] = 0;
    vis[s] = true;
    adv[s] = _inf;
    
    while(!q.empty()) {
        int u = q.front(); q.pop();
        vis[u] = false;
        
        for(tgno* i=Head[u];i;i=i->n) {
            if(i->c > i->f && dis[i->v] > dis[u] + i->w) {
                dis[i->v] = dis[u] + i->w;
                adv[i->v] = min(adv[u], i->c - i->f);
                pre[i->v] = i;
                
                if(!vis[i->v]) {
                    q.push(i->v);
                    vis[i->v] = true;
                }
            }
        }
    }
    
    if(dis[t] == _inf) return false;
    else {
        Flow += adv[t];
        Cost += dis[t] * adv[t];
        
        int u = t;
        while(u != s) {
            pre[u]->f += adv[t];
            pre[u]->r->f -= adv[t];
            
            u = pre[u]->u;
        }
        return true;
    }
}

void MaxFlow(int s, int t) {
    Flow = Cost = 0;
    while(SPFA(s, t));
}

int main() {
    scanf("%d", &N);
    scanf("%s", buf);
    for(int i=0;i<N;i++) scanf("%d", &val[i]);
    
    for(int i=0;i<N;i++) cnt[buf[i] - 'a'] ++;
    
    int S = ++gpos;
    int T = ++gpos;
    for(int i=0;i<26;i++) letter[i] = ++gpos;
    
    for(int i=0;i<26;i++) {
        addEdge(S, letter[i], cnt[i], 0);
    }
    
    int _ = N>>1;
    for(int i=0;i<_;i++) {
        _pair[i] = ++gpos;
        int c1 = buf[i] - 'a';
        int c2 = buf[N-i-1] - 'a';
        int v1 = val[i];
        int v2 = val[N-i-1];
        
        for(int j=0;j<26;j++) {
            int vv = 0;
            if(j == c1) vv = -v1;
            if(j == c2) vv = min(vv, -v2);
            addEdge(letter[j], _pair[i], 1, vv);
        }
        
        addEdge(_pair[i], T, 2, 0);
    }
    
    MaxFlow(S, T);
    
    printf("%d\n", -Cost);
}