Codeforces Round 444 (Div. 2) 题解

2017/11/07

听说这场比赛出锅了,还好没报名。

A. Div. 64

签到题。

1
2
a = raw_input().strip()
print('yes' if a.find('1') != -1 and a[a.find('1')+1:].count('0') >= 6 else 'no')

B. Cubes for Masha

搜索型签到

 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 <bits/stdc++.h>
using namespace std;

int N;
int LUT[4][11];
int mem[1001];
int used[4];
int cur[4];

void dfs(int dep = 0) {
    int base = 1;
    int ans = 0;
    for(int i=dep-1;i>=0;i--) {
        ans = ans + base * cur[i];
        base *= 10;
    }
    mem[ans] = 1;

    if(dep == N) return;

    for(int d=0;d<=9;d++) {
        cur[dep] = d;
        for(int i=1;i<=N;i++) {
            if(used[i] || LUT[i][d] == 0) continue;
            used[i] = 1;
            dfs(dep + 1);
            used[i] = 0;
        }
    }
}

int main() {
    cin >> N;
    int x;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=6;j++) {
            cin >> x; LUT[i][x] = 1;
        }

    dfs();

    int i;
    for(i=0;i<1000;i++) {
        if(mem[i] == 0) break;
    }
    cout << i-1 << endl;
}

C. Solution for Cube

类似之前的 某道置换群搜索

  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
#include <bits/stdc++.h>
using namespace std;

struct group {
    int C[25];
    group() {
        for(int i=1;i<=24;i++)
            C[i] = i;
    }

    group(const group &a) {
        memcpy(C, a.C, sizeof(C));
    }

    group(const int* sq) {
        for(int i=1;i<=24;i++)
            C[i] = sq[i];
    }

    bool check() {
        for(int i=1;i<=24;i+=4) {
            if(C[i] != C[i+1] || C[i] != C[i+2] || C[i] != C[i+3])
                return false;
        }
        return true;
    }
};

group operator *(const group &a, const group &b) {
    group ret;
    for(int i=1;i<=24;i++)
        ret.C[i] = b.C[a.C[i]];
    return ret;
}



group op[7];

void init() {
    int *ptr = op[1].C;
    ptr[1] = 3;
    ptr[2] = 1;
    ptr[3] = 4;
    ptr[4] = 2;
    ptr[13] = 5;
    ptr[14] = 6;
    ptr[5] = 17;
    ptr[6] = 18;
    ptr[17] = 21;
    ptr[18] = 22;
    ptr[21] = 13;
    ptr[22] = 14;
    op[2] = op[1] * op[1];
    op[2] = op[2] * op[1];

    ptr = op[3].C;
    ptr[5] = 9;
    ptr[7] = 11;
    ptr[11] = 22;
    ptr[9] = 24;
    ptr[22] = 3;
    ptr[24] = 1;
    ptr[1] = 5;
    ptr[3] = 7;
    op[4] = op[3] * op[3];
    op[4] = op[4] * op[3];

    ptr = op[5].C;
    ptr[5] = 7;
    ptr[6] = 5;
    ptr[8] = 6;
    ptr[7] = 8;
    ptr[4] = 14;
    ptr[3] = 16;
    ptr[14] = 9;
    ptr[16] = 10;
    ptr[9] = 19;
    ptr[10] = 17;
    ptr[19] = 4;
    ptr[17] = 3;
    op[6] = op[5] * op[5];
    op[6] = op[6] * op[5];
}

int main() {
    init();
    group s;
    for(int i=1;i<=24;i++)
        cin >> s.C[i];
    
    bool flag = false;
    for(int i=1;i<=6;i++) {
        if((op[i] * s).check()) {
            flag = true; break;
        }
    }

    puts(flag ? "YES" : "NO");
}

D. Ratings and Reality Shows

题面不好翻译

做法就是先对时间离散化,预处理出两种情况下事件权值的前缀和。

扫过去的时候在前面挂一个滑动窗口求最小值,可以用单调队列维护。

复杂度

 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
#include <bits/stdc++.h>
using namespace std;
const int SIZ = 3e5 + 2007;
typedef long long LL;

int N, A, B, C, D, St, Ln;
int T[SIZ], Q[SIZ];
LL Pre1[SIZ], Pre2[SIZ];
LL L[SIZ<<1]; int hd, ta;

void insert(int x) {
    while(hd < ta && Pre2[L[ta-1]] >= Pre2[x]) ta--;
    L[ta++] = x;
}

void erase(int x) {
    while(hd < ta && L[hd] == x) hd++;
}

LL query() {
    return hd < ta ? Pre2[L[hd]] : (numeric_limits<LL>::max()>>1);
}

int main() {
    cin >> N >> A >> B >> C >> D >> St >> Ln;
    
    for(int i=1;i<=N;i++)
        cin >> Q[i] >> T[i];

    Pre1[0] = Pre2[0] = St;
    for(int i=1;i<=N;i++) {
        Pre1[i] = Pre1[i-1] + (T[i] ? A : -B);
        Pre2[i] = Pre2[i-1] + (T[i] ? C : -D);
    }

    int r = 1;
    int ans = -1;
    Q[0] = -1;
    for(int i=0;i<=N;i++) {
        erase(i);
        while(r <= N && Q[r] <= Q[i] + Ln) insert(r++);
        LL p1 = Pre1[i], p2 = Pre2[i];
        if(p1 < 0) break;
        if(query() - p2 + p1 >= 0) {
            ans = Q[i] + 1;
            break;
        }
    }

    cout << ans << endl;
}