这里介绍几种非常有意思的技巧，比如剥洋葱法。

Image is Everything

剥洋葱，k from 1 to 6, means k view

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 <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

#define REP(i,n)    for(int i = 0; i < (n); i++)

const int maxn = 10;
int n;
char pos[maxn][maxn][maxn];
char view[maxn][maxn][maxn];


char read_char(){
    char ch;
    for(;;){
        ch = getchar();
        if( (ch >= 'A' && ch <= 'Z') || ch == '.' )
            return ch;
    }
}

void getxyz(int k, int i, int j, int depth, int& x, int& y, int& z){
    if(k == 0){
        x = depth; y = j; z = i;
    }
    if(k == 1){
        x = n-1-j; y = depth; z = i;
    }
    if(k == 2){
        x = n-1-depth; y = n-1-j; z = i;
    }
    if(k == 3){
        x = j; y = n-1-depth; z = i;
    }
    if(k == 4){
        x = n-1-i; y = j; z = depth;
    }
    if(k == 5){
        x = i; y = j; z = n-1-depth;
    }
}

void init(int n){
    REP(i,n) REP(k,6) REP(j,n){
        view[k][i][j] = read_char();
    }
    //k视图
    REP(i,n) REP(j,n) REP(l,n){
        pos[i][j][l] = '#';
    }
}

int cntempty(){
    int ans = 0;
    REP(i,n) REP(j,n) REP(k,n){
        if(pos[i][j][k] != '.')
            ans++;
    }
    return ans;
}

int cal() {
    REP(k,6) REP(i,n) REP(j,n){
        if(view[k][i][j] == '.'){
            REP(dep,n){
                int x,y,z;
                getxyz(k,i,j,dep,x,y,z);
                pos[x][y][z] = '.';
            }
        }
    }
    // finished clean position
    //
    //循环一层一层删除，到最后不能删除为止
    //每次删除一层，就得到一个新的立方体
    //新的立方体作为start，继续执行删除，直到不能删除为止

    for(;;){
        bool finished = true;
        REP(k,6) REP(i,n) REP(j,n){
            if(view[k][i][j] != '.'){
                REP(dep,n){
                    //一层一层检查，一层一层剥开你的心
                    int x,y,z;
                    getxyz(k,i,j,dep,x,y,z);

                    if(pos[x][y][z] == '.')
                        continue;
                    if(pos[x][y][z] == '#'){
                        pos[x][y][z] = view[k][i][j];
                        break;
                    }
                    if(pos[x][y][z] == view[k][i][j])
                        break;

                    pos[x][y][z] = '.';
                    finished = false;

                    //所有视图删除完之后，作为一个新的立方体
                    //重新进入循环
                    //删除！一直删到不能删为止
                }
            }
        }

        if(finished)
            break;
    }
    return cntempty();

}



int main(){
    while(scanf("%d",&n) == 1  && n){
        memset(pos,0, sizeof(pos));
        memset(view,0, sizeof(view));

        init(n);
        int ans = cal();
        printf("Maximum weight: %d gram(s)\n",ans);
    }
}

graveyard

graveyard

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m) == 2){
        double ans = 0.0;

        for(int i = 0; i < n; i++){
            double pos = (double) i / n * (n+m);
            ans += fabs(pos-floor(pos+0.5)) / (n+m);
        }

        printf("%.4lf\n",ans*10000);
    }
}

even-parity

算法分析：
even-parity
even-parity2

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 20;
int data[maxn][maxn], buffer[maxn][maxn];
int n;

int check(int val){
    memset(buffer,0, sizeof(buffer));

    for(int c = 0; c < n; c++){
        if(val & (1<<c))
            buffer[0][c] = 1;
        //enumerate
        else{
            // the number in high bits is 0
            if(data[0][c] == 1)
                // not 0，contradict with default
                // enumerate default --> binary bits
                return INF;
        }
    }

    for(int r = 1; r < n; r++){
        for(int c = 0; c < n; c++){
            int sum = 0;
            if(r > 1) sum += buffer[r-2][c];
            if(c > 0) sum += buffer[r-1][c-1];
            if(c+1 < n) sum += buffer[r-1][c+1];

            buffer[r][c] = sum % 2;

            if(data[r][c] == 1 && buffer[r][c] == 0)
                return INF;
        }
    }

    int cnt = 0;
    for(int r = 0; r < n; r++){
        for(int c = 0; c < n; c++){
            if(data[r][c] != buffer[r][c])
                cnt++;
        }
    }
    return cnt;
}

int main(){
    int kase;
    int k = 0;
    scanf("%d",&kase);
    while(kase--){
        scanf("%d",&n);

        for(int r = 0; r < n; r++){
            for(int c = 0; c < n; c++)
                scanf("%d",&data[r][c]);
        }

        int ans = INF;
        for(int v = 0; v < (1 << n); v++){
            ans = min(ans,check(v));
        }

        if(ans == INF)  ans = -1;

        printf("Case %d: %d\n",++k,ans);
    }
}

RAID

算法分析图解：

RAID1
RAID2

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 6500;
char data[8][maxn];
bool parity;
int d,s,b,w;
char type;


bool fix(){
    w = s*b;

    for(int i = 0; i < w; i++){
        int sum = 0;
        int bro_cnt = 0, bro_id = 0;

        for(int j = 0; j < d; j++){
            if(data[j][i] == '1'){
                sum++;
            }
            if(data[j][i] == 'x'){
                bro_cnt++;
                bro_id = j;
            }
        }

        sum %= 2;

        if(bro_cnt >= 2)
            return false;
        else if(bro_cnt == 1){
            if(sum){
                if(parity)
                    data[bro_id][i] = '0';
                else
                    data[bro_id][i] = '1';
            }else{
                if(parity)
                    data[bro_id][i] = '1';
                else
                    data[bro_id][i] = '0';
            }
        }else if(bro_cnt == 0){
            if(parity == 0 && sum == 1)
                return false;
            if(parity == 1 && sum == 0)
                return false;
        }
    }
    return true;
}

void printdata(){
    int sum = 0;
    int bit_cnt = 0;
    for(int i = 0; i < b; i++){
        int except = i % d;
        for(int j = 0; j < d; j++){
            if(j == except)
                continue;

            for(int k = i*s; k < i*s+s; k++){
                bit_cnt = (bit_cnt+1) % 4;

                if(data[j][k] == '0')
                    sum = sum << 1;
                if(data[j][k] == '1')
                    sum = (sum << 1)  + 1;

                if(bit_cnt == 0){
                    // bit finish!
                    printf("%X",sum);
                    sum = 0;
                }

            }
        }
    }
    if(bit_cnt){
        // complete 0
        int add_0 = 4 - bit_cnt;
        sum = sum << add_0;
        printf("%X",sum);
    }
    printf("\n");
}

int main(){
    int kase = 0;
    while(cin >> d && d){
        memset(data, 0, sizeof(data));
        cin >> s >> b >> type;
        parity = type == 'O';

        for(int i = 0; i < d; i++)
            cin >> data[i];

        if(!fix())
            printf("Disk set %d is invalid.\n",++kase);
        else{
            printf("Disk set %d is valid, contents are: ",++kase);
            printdata();
        }

    }


    return 0;
}

非常重要的一种枚举思想: Colored Cubes

枚举的核心，在于相对位置的变化：

colored-cubes01

colored-cubes02

colored-cubes03

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
//
//  main.cpp
//  coloredCubes
//
//  Created by zhangmin chen on 2019/4/11.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>

using namespace std;
typedef long long llong;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)


/*
int Left[6] = {4, 0, 2, 3, 5, 1};
int Up[6] = {2, 1, 5, 0, 4, 3};

void rot(int* trans, int* pos) {
    int q[6];
    memcpy(q, pos, sizeof(q));
    for(int i = 0; i < 6; i++) {
        pos[i] = trans[q[i]];
    }
}

void enumerate() {
    int p0[6] = {0, 1, 2, 3, 4, 5};
    printf("dice24[24][6]: \n");
    
    for(int i = 0; i < 6; i++) {
        int q[6];
        memcpy(q, p0, sizeof(q));
        
        if(i == 0) rot(Up, q);
        if(i == 1) {
            rot(Left, q); rot(Up, q);
        }
        if(i == 3) {
            rot(Up, q); rot(Up, q);
        }
        if(i == 4) {
            rot(Left, q); rot(Left, q); rot(Left, q); rot(Up, q);
        }
        if(i == 5) {
            rot(Left, q); rot(Left, q); rot(Up, q);
        }
        
        for(int k = 0; k < 4; k++) {
            printf("{%d, %d, %d, %d, %d, %d},\n", q[0], q[1], q[2], q[3], q[4], q[5]);
            rot(Left, q);
        }
    }
    cout << endl;
}

int main() {
    enumerate();
}
 */

/*
 *
 dice24[24][6]:
 {2, 1, 5, 0, 4, 3},
 {2, 0, 1, 4, 5, 3},
 {2, 4, 0, 5, 1, 3},
 {2, 5, 4, 1, 0, 3},
 {4, 2, 5, 0, 3, 1},
 {5, 2, 1, 4, 3, 0},
 {1, 2, 0, 5, 3, 4},
 {0, 2, 4, 1, 3, 5},
 {0, 1, 2, 3, 4, 5},
 {4, 0, 2, 3, 5, 1},
 {5, 4, 2, 3, 1, 0},
 {1, 5, 2, 3, 0, 4},
 {5, 1, 3, 2, 4, 0},
 {1, 0, 3, 2, 5, 4},
 {0, 4, 3, 2, 1, 5},
 {4, 5, 3, 2, 0, 1},
 {1, 3, 5, 0, 2, 4},
 {0, 3, 1, 4, 2, 5},
 {4, 3, 0, 5, 2, 1},
 {5, 3, 4, 1, 2, 0},
 {3, 4, 5, 0, 1, 2},
 {3, 5, 1, 4, 0, 2},
 {3, 1, 0, 5, 4, 2},
 {3, 0, 4, 1, 5, 2},

 
 */

const int dice24[24][6] = {
    //
    {2, 1, 5, 0, 4, 3},
    {2, 0, 1, 4, 5, 3},
    {2, 4, 0, 5, 1, 3},
    {2, 5, 4, 1, 0, 3},
    {4, 2, 5, 0, 3, 1},
    {5, 2, 1, 4, 3, 0},
    {1, 2, 0, 5, 3, 4},
    {0, 2, 4, 1, 3, 5},
    {0, 1, 2, 3, 4, 5},
    {4, 0, 2, 3, 5, 1},
    {5, 4, 2, 3, 1, 0},
    {1, 5, 2, 3, 0, 4},
    {5, 1, 3, 2, 4, 0},
    {1, 0, 3, 2, 5, 4},
    {0, 4, 3, 2, 1, 5},
    {4, 5, 3, 2, 0, 1},
    {1, 3, 5, 0, 2, 4},
    {0, 3, 1, 4, 2, 5},
    {4, 3, 0, 5, 2, 1},
    {5, 3, 4, 1, 2, 0},
    {3, 4, 5, 0, 1, 2},
    {3, 5, 1, 4, 0, 2},
    {3, 1, 0, 5, 4, 2},
    {3, 0, 4, 1, 5, 2}
};

const int maxn = 4;
int colors[maxn][6];
int n;
int dice[maxn][6];
int posD[maxn];

int ans;

// posD[i] = val,  means No.i dice choose posture
// dice24[val][...]

void painting(int colors[][6], int dice[][6]) {
    // posD[i] = val, means No.i dice choose posture
    // dice24[val][..]
    
    for(int i = 0; i < n; i++) for(int j = 0; j < 6; j++) {
        // No.i dice surface j
        // dice[i][j] changed to position p = posD[i][j];
        // subscript is postion p
        // color[i][p] = dice[i][j]
        
        int p = dice24[posD[i]][j];
        colors[i][p] = dice[i][j];
    }
}


void solve() {
    // posD[i] = val, means No.i dice choose posture
    // dice24[val][..]
    
    painting(colors, dice);
    int tot = 0;
    for(int k = 0; k < 6; k++) {
        int cnt[maxn * 6];
        memset(cnt, 0, sizeof(cnt));
        
        int maxface = 0;
        for(int i = 0; i < n; i++) {
            maxface = max(maxface, ++cnt[colors[i][k]]);
            //debug(maxface);
        }
        
        tot += n-maxface;
    }
    
    ans = min(ans, tot);
    //debug(ans);
}

vector<string> nColor;
int getID(const char* name) {
    //
    string str(name);
    int id = (int)nColor.size();
    
    for(int i = 0; i < nColor.size(); i++) {
        if(nColor[i] == str) return i;
    }
    nColor.push_back(str);
    return id;
}



void dfs(int d) {
    if(d == n) solve();
    else {
        for(int i = 0; i < 24; i++) {
            // dice[24][..]
            // choose one posture of dice[24][..]
            // depth d cubes choose posture dice[i]
            
            posD[d] = i;
            //_for(i, 0, maxn) debug_(posD, i);
            dfs(d+1);
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    while(scanf("%d", &n) == 1 && n) {
        //
        nColor.clear();
        //memset(posD, 0, sizeof(posD));
        //memset(colors, 0, sizeof(colors));
        
        for(int i = 0; i < n; i++) for(int j = 0; j < 6; j++) {
            char name[30];
            scanf("%s", name);
            dice[i][j] = getID(name);
            //debug(dice[i][j]);
        }
        
        // solve()
        //posD[0] = 0;
        
        ans = n*6;
        dfs(1);
        printf("%d\n", ans);
    }
}


IP地址与二进制 IP Networks

具体涉及到二进制的处理：

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <assert.h>

using namespace std;

#define _for(i,a,b) for( int i = (a); i < (b); i++ )
#define _rep(i,a,b) for( int i = (a); i <= (b); i++ )

const int W = 8, IPW = 4*W;

bool inrange(int val, int a, int b){
    if(a > b)
        return inrange(val, b, a);
    return a <= val && val <= b;
}

void toBinary(int val, int* bin, int pos){
    assert(inrange(val,0,255));

    _for(i,0,W){
        bin[pos+W-1-i] = val % 2;
        val /= 2;
    }
}

void printip(const int* bin){

    bool first = true;

    for(int i = 0; i < 4; i++){
        int x = 0;
        for(int k = i*W; k < (i+1)*W; k++){
            x = (x << 1) | bin[k];
        }

        if(first)
            first = false;
        else
            printf(".");
        printf("%d",x);
    }
    puts("");
}

const int maxn = 1024;
int subip[maxn][IPW+5];

int main(){
    int subNet[IPW];
    int n, ip[4];

    while(scanf("%d",&n) == 1){
        _for(i,0,n){
            scanf("%d.%d.%d.%d",&ip[0],&ip[1],&ip[2],&ip[3]);
            _for(j,0,4){
                toBinary(ip[j],subip[i],j*W);
            }
        }
        //finished! Get ip binary presentation
        memset(subNet,0,sizeof(subNet));
        //enumerate
        int len;
        for(len = 0; len < IPW; len++){
            bool same = true;

            //erogodic
            for(int p = 1; p < n; p++){
                if(subip[p-1][len] != subip[p][len]){
                    same = false;
                    break;
                }
            }
            if(!same)
                break;
        }
        //len: position-> the first different element
        //len start from 0, it means the longest length

        fill_n(subNet,len,1);
        fill_n(subip[0]+len,IPW-len,0);

        printip(subip[0]);
        printip(subNet);

    }
}

Morse Mismatches

表的建立：

morse

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 <iostream>
#include <cstdio>
#include <map>
#include <unordered_map>
#include <vector>
#include <cstring>
#include <string.h>
#include <algorithm>

using namespace std;

unordered_map<char, string> morse;
unordered_map<string, vector<string> > context;

bool isprefix(const string& A, const string& B){
    return A.size() < B.size() && B.compare(0,A.size(),A) == 0;
}

void solve(const string& m){
    if(context.count(m)){
        const auto& word_v = context[m];
        cout << word_v.front();

        if(word_v.size() > 1){
            cout << "!";
        }
        cout << endl;
        return;
    }

    map<int, string> ans;

    for(const auto& it: context){
        const string& m_ext = it.first;

        if(isprefix(m, m_ext))
            ans[m_ext.size()-m.size()] = it.second.front();
        else if(isprefix(m_ext, m))
            ans[m.size()-m_ext.size()] = it.second.front();
    }
    cout << ans.begin() -> second << "?" << endl;
}


int main(){
    string alpha,M;

    while(cin >> alpha && alpha != "*"){
        cin >> M;
        morse[alpha[0]] = M;
    }
    while(cin >> alpha && alpha != "*"){
        M.clear();
        for(auto p : alpha){
            M += morse[p];
        }
        context[M].push_back(alpha);
    }
    while(cin >> M && M != "*"){
        solve(M);
    }
    return 0;
}

extraordinarily tired students

extraordinarily-tired

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 <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

struct stu{
    int a;
    int b;
    int c;
};

#define MAX_TIME 1000000
int n;
istream& operator>> (istream& is, stu& s) { return is >> s.a >> s.b >> s.c;}

stu stus[10+5];

bool action(int kase,int t){
    int wake = 0, sleep = 0;

    for(int i = 0; i < n; i++){
        if(stus[i].c <= stus[i].a)  wake++;
    }
    sleep = n-wake;

    if(sleep == 0){
        cout << "Case " << kase << ": " << t << endl;
        return true;
    }

    for(int i = 0; i < n; i++){
        stu& s = stus[i];
        s.c++;

        if(s.c == s.a + s.b + 1)    s.c = 1;
        if(s.c == s.a + 1 && wake >= sleep) s.c = 1;
    }
    return false;

}

int main(){
    int kase = 1;
    while(scanf("%d",&n) && n){
        for(int i = 0; i < n; i++){
            cin >> stus[i];
        }

        int t;
        for(t = 1; t < MAX_TIME; t++){
            if(action(kase, t))
                break;
        }

        if(t == MAX_TIME)
            cout << "Case " << kase << ": " << "-1" << endl;

        kase++;
    }
}