Educational Codeforces Round 34 题解

2017/12/16

我(文化课)更菜了。

A. Hungry Student Problem

NOIP2017 Day1 T1 + 打表 = 签到题

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

int lut[] = {1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0};

int main() {
    int N, X;
    scanf("%d", &N);
    
    while(N--) {
        scanf("%d", &X);
        if(X > 11) {
            puts("YES");
        } else {
            puts(lut[X] ? "YES" : "NO");
        }
    }
}

B. The Modcrab

注意到只要不死随时都能嗑药,所以说先一次性磕足够多的药,再打死对方。

细节处理。

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

int h1, a1, c1, h2, a2;

int main() {
    scanf("%d %d %d %d %d", &h1, &a1, &c1, &h2, &a2);
    
    int cnt = ((h2 + a1 - 1) / a1);
    int ned = 0;
    
    if(cnt > 1 && h1 <= cnt * a2 - a2) {
        int mn = cnt * a2 - a2 + 1 - h1;
        ned = (mn + c1 - a2 - 1) / (c1 - a2);
    }
    
    printf("%d\n", ned + cnt);
    for(int i=1;i<=ned;i++) puts("HEAL");
    for(int i=1;i<=cnt;i++) puts("STRIKE");
}

C. Boxes Packing

排序贪心,倒序考虑每个大箱子装了哪个小箱子(保证最优性)。

 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;
const int SIZ = 5000 + 1007;

int A[SIZ];
int M[SIZ];

int main() {
    int N, x;
    scanf("%d", &N);
    
    for(int i=1;i<=N;i++) {
        scanf("%d", &A[i]);
    }
    
    sort(A + 1, A + N + 1, greater<int>());
    
    for(int i=1;i<=N;i++) {
        for(int j=i+1;j<=N;j++) {
            if(A[j] < A[i] && !M[j]) {
                M[j] = 1; break;
            }
        }
    }
    
    int ans = N - accumulate(M + 1, M + N + 1, 0);
    printf("%d\n", ans);
}

D. Almost Difference

离散化 + 倒序统计

看题解发现需要 long double 保平安(应该算高精度基本操作……)

 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
#include <deque>
#include <unordered_map>
#include <functional>
using namespace std;
const int SIZ = 4E5 + 1007;
typedef long double LL;

int N;
int A[SIZ]; deque<LL> B;
set<int> SS;
unordered_map<LL, int> LUT;
int Cnt[SIZ];
LL Sum;

LL solve() {
    LL ret = 0;
    
    for(int i=N;i;i--) {
        LL ans = 0;
        int pos = LUT[A[i]];
        
        ans += Sum - LL(N - i) * A[i];
        
        if(B[pos-1] == A[i] - 1) {
            ans += Cnt[pos-1];
        }
        
        if(B[pos+1] == A[i] + 1) {
            ans -= Cnt[pos+1];
        }
        
        Sum += A[i];
        Cnt[pos]++;
        ret += ans;
    }
    
    return ret;
}

int main() {
    scanf("%d", &N);

    for(int i=1;i<=N;i++) {
        scanf("%d", &A[i]);
        SS.insert(A[i]);
    }
    
    B = deque<LL>(SS.begin(), SS.end());
    B.push_front(numeric_limits<LL>::min());
    B.push_back(numeric_limits<LL>::max());
    
    int c = 0;
    for(int x : B) {
        LUT[x] = c++;
    }
    
    printf("%.0Lf\n", solve());
}

E. Swapping Characters

随便找两个不同的串,统计不同的位置,如果多于四个证明无解。

取一个之前找到不同的位置,再枚举另一个位置,交换之后构成模板串,然后 check 一下这个模板串是否可行。

枚举模板串 O(N) 检查可行 O(NK)

总体复杂度 O(N^2 K) ,非常稳。

 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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <functional>
#include <vector>
#include <algorithm>
using namespace std;
const int SIZ = 5000 + 1007;

int K, N;
bool can_ident;
char S[SIZ][SIZ];
size_t Hs[SIZ];

bool check() {
    for(int i=2;i<=K;i++) {
        vector<int> pos;
        for(int j=1;j<=N;j++) {
            if(S[1][j] != S[i][j]) pos.push_back(j);
        }
        
        if(pos.size() == 2) {
            if(S[1][pos[0]] != S[i][pos[1]] || S[1][pos[1]] != S[i][pos[0]])
                return false;
        } else if(!can_ident || pos.size() != 0) {
            return false;
        }
    }
    
    return true;
}

void solve(int b) {
    vector<int> pos;
    
    for(int i=1;i<=N;i++) {
        if(S[1][i] != S[b][i]) pos.push_back(i);
    }
    
    if(pos.size() > 4) { puts("-1"); return; } 

    for(int dp : pos) {
        for(int i=1;i<=N;i++) {
            if(i == dp) continue;
            swap(S[1][i], S[1][dp]);
            if(check()) {
                puts(S[1] + 1);
                return;
            }
            swap(S[1][i], S[1][dp]);
        }
    }
    
    puts("-1");
}

int main() {
    scanf("%d %d", &K, &N);
    
    hash<string> hs_fun;
    
    for(int i=1;i<=K;i++) {
        scanf("%s", S[i] + 1);
        Hs[i] = hs_fun(string(S[i] + 1));
    }
    
    char buf[SIZ]; memcpy(buf, S[1], sizeof(buf));
    sort(buf + 1, buf + N + 1);
    can_ident = unique(buf + 1, buf + N + 1) != (buf + N + 1);
    
    int pos = -1;
    for(int i=2;i<=K;i++) {
        if(Hs[1] != Hs[i] && strcmp(S[1]+1, S[i]+1) != 0) {
            pos = i; break;
        }
    }
    
    if(pos == -1) {
        swap(S[1][1], S[1][2]);
        puts(S[1] + 1);
    } else {
        solve(pos);
    }
}

F. Clear The Matrix

状压的题做太少……

因为整个矩阵只有四行,所以说可以把 4x4 的区域状态压缩。

然后转移具备单调性,类似完全背包。

 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 <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int SIZ = 1007;
const int STA = (1 << 16) - 1;

int N, A[5];
unsigned char S[4][SIZ];
int DP[SIZ][STA + 7], C[SIZ];
vector<int> msk[5];

int trans_msk(int ofs, int len) { 
    int msk = 0;
    
    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
            msk |= 1 << ((j << 2) + ofs + i);
    
    return msk;
}

int col_msk(int ofs) {
    int msk = 0;
    
    for(int j=0;j<4;j++)
        msk |= S[j][ofs] << j;
    
    return msk;
}

void init() {
    for(int i=1;i<=4;i++) {
        for(int j=0;j+i<=4;j++) {
            msk[i].push_back(STA ^ trans_msk(j, i));
        }
    }
    
    for(int i=0;i<N;i++) C[i] = col_msk(i);
}

int main() {
    scanf("%d", &N);
    
    for(int i=1;i<=4;i++) scanf("%d", &A[i]);

    char buf[SIZ];
    for(int i=0;i<4;i++) {
        scanf("%s", buf);
        for(int j=0;j<N;j++) S[i][j] = (buf[j] == '*');
    }
    
    init();
    memset(DP, 0x3f, sizeof(DP));
    
    int S = 0;
    for(int i=0;i<min(4, N);i++) S |= C[i] << (i<<2);
    DP[0][S] = 0;
    
    for(int i=0;i<N;i++) {
        for(int S=STA;S>=0;S--) {
            if(DP[i][S] == 0x3f3f3f3f) continue;
            if((S & 15) == 0) {
                int SS = S >> 4 | (C[i+4] << 12);
                DP[i+1][SS] = min(DP[i+1][SS], DP[i][S]);
            }
            
            for(int j=1;j<=4&&i+j<=N;j++) {
                for(auto SS : msk[j]) {
                    DP[i][S & SS] = min(DP[i][S & SS], DP[i][S] + A[j]);
                }
            }
        }
    }
    
    printf("%d\n", DP[N][0]);
}