Codeforces Round 402 (Div. 1)

2017/03/02

本月第一篇!_(:з」∠)_

A. String Game

给两个个字符串 AB 和一个删除顺序,求最大的 N 使得串 A 按照顺序删除 N 个元素之 后,串 B 仍然是 A 的一个子序列。

做法就是 二分答案 + O(N) 暴力判断解。

 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
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200000 + 1000;
string A, B; int len;
int Seq[MAX_N];
int Msk[MAX_N];

bool check(int pos) {
    memset(Msk, 0, sizeof(Msk));

    for(int i=1;i<=pos;i++) {
        Msk[Seq[i]-1] = 1;
    }

    int pb = 0, lenb = B.size();
    for(int i=0;i<len;i++) {
        if(!Msk[i] && A[i] == B[pb]) {
            ++pb; if(pb == lenb) return true;
        }
    }

    return false;
}

int solve() {
    int L = 0, R = len+1; // [L, R)

    while(L + 1 < R) {
        int Mid = (L + R) >> 1;
        if(check(Mid)) L = Mid;
        else R = Mid;
    }

    return L;
}

int main() {
    cin >> A >> B; len = A.size();
    for(int i=1;i<=len;i++) {
        cin >> Seq[i];
    }

    cout << solve() << endl;
}

B. Bitwise Formula

a := 101
b := 011
c := ? XOR b

定义一些位宽相同的二进制常量和变量,求最小的 ? 的值,使得 Sum{ Var } 最小或 最大。

此题类似 UOJ2 - [NOI2014] 起床困难综合症,暴力统计,按位贪心。

 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
#include <bits/stdc++.h>
using namespace std;
const int MAX_M = 1000 + 100;
const int MAX_N = 5000 + 200;
typedef bitset<MAX_M> bts;

int N, M; // num of var, bit depth

struct var {
    bts t;
    int typ; // 0 constant, 1 AND, 2 OR, 3 XOR, 4 ?
    int op1, op2;
} POOL[MAX_N]; int ppos;
unordered_map<string, int> Var_LUT;

bool is01(const string& s) {
    int _ = s.size();
    for(int i=0;i<_;i++) {
        char c = s[i];
        if(c != '0' && c != '1') return false;
    }
    return true;
}

int cnt[2][MAX_M];
void eval(int sel, const bts& t) {
    POOL[MAX_N - 1].t = t;
    for(int i=0;i<N;i++) {
        if(POOL[i].typ) {
            if(POOL[i].typ == 1) POOL[i].t = POOL[POOL[i].op1].t & POOL[POOL[i].op2].t;
            if(POOL[i].typ == 2) POOL[i].t = POOL[POOL[i].op1].t | POOL[POOL[i].op2].t;
            if(POOL[i].typ == 3) POOL[i].t = POOL[POOL[i].op1].t ^ POOL[POOL[i].op2].t;

            for(int j=0;j<M;j++) {
                cnt[sel][j] += POOL[i].t[j];
            }
        }
    }
}

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

    Var_LUT["?"] = MAX_N - 1;
    POOL[MAX_N - 1].typ = 4;

    for(int i=0;i<N;i++) {
        string name; cin >> name;
        string op1; cin >> op1; cin >> op1;
        if(is01(op1)) {
            Var_LUT[name] = ppos;
            POOL[ppos].t = bts(op1);
            POOL[ppos].typ = 0;
            ++ppos;
        } else {
            string opd, op2; cin >> opd >> op2;
            Var_LUT[name] = ppos;
            if(opd[0] == 'A') POOL[ppos].typ = 1;
            else if(opd[0] == 'O') POOL[ppos].typ = 2;
            else POOL[ppos].typ = 3;
            POOL[ppos].op1 = Var_LUT[op1];
            POOL[ppos].op2 = Var_LUT[op2];
            ++ppos;
        }
    }

    bts tmp;
    eval(0, tmp); // all zero
    tmp.flip();
    eval(1, tmp); // all one
    tmp.reset();

    for(int i=0;i<M;i++) {
        if(cnt[0][i] <= cnt[1][i]) tmp[i] = false;
        else tmp[i] = true;
    }

    for(int i=M-1;i>=0;i--) {
        cout << int(tmp[i]);
    }
    cout << endl;

    for(int i=0;i<M;i++) {
        if(cnt[0][i] >= cnt[1][i]) tmp[i] = false;
        else tmp[i] = true;
    }

    for(int i=M-1;i>=0;i--) {
        cout << int(tmp[i]);
    }
    cout << endl;
}