递归和函数的秘密(二)

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

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

枚举得到相对位置的变化:

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
#include <iostream>
#include <cstdio>
#include <cstring>
int left[] = {4,0,2,3,5,1};
int up[] = {2,1,5,0,4,3};
int rot(int* way, int* cur){
int chan[6];
memcpy(chan,cur, sizeof(chan));
for(int i = 0; i < 6; i++)
cur[i] = way[chan[i]];
}
void enumerate(){
int start[6] = {0,1,2,3,4,5};
printf("int posture[24][6] = {\n");
for(int i = 0; i < 6; i++){
int cur[6];
memcpy(cur,start, sizeof(cur));
if(i == 0)
rot(up,cur);
if(i == 1){
rot(left,cur);
rot(up,cur);
}
if(i == 3){
rot(up,cur); rot(up,cur);
}
if(i == 4){
rot(left,cur); rot(left,cur); rot(left,cur);
rot(up,cur);
}
if(i == 5){
rot(left,cur); rot(left,cur);
rot(up,cur);
}
for(int k = 0; k < 4; k++){
printf("{%d, %d, %d, %d, %d, %d}\n",cur[0],cur[1],cur[2],cur[3],cur[4],cur[5]);
rot(left,cur);
}
}
printf("};\n");
}
int main(){
enumerate();
return 0;
}

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int posture[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 cubes[maxn][6], ans;
int n;
void check();
vector<string> cnames;
int getid(const char* name){
string cur(name);
int n = cnames.size();
for(int i = 0; i < n; i++){
if(cnames[i] == cur)
return i;
}
cnames.push_back(cur);
return n;
//返回的是颜色编号id-1,即vector数组下标
//有一个元素的时候,n=0,恰好cnames[0] = 这个元素
//n = 1, cnames[0] cnames[1]这两个元素 --> cnames[1]=name
}
//找到颜色不一样的
//如果颜色一样,返回第一次出现该颜色的id
//cnames中的各个颜色都不一样!
//该函数的作用相当于一个<set>
int rota[maxn], color[maxn][6];
void enumdfs(int curid){
if(curid == n)
check();
else{
for(int i = 0; i < 24; i++){
rota[curid] = i;
enumdfs(curid+1);
}
}
}
//实际上执行了24^3次
//按不同的姿态,分别染色,染入给定的颜色cubes[i][j]
void check(){
memset(color,0, sizeof(color));
for(int i = 0; i < n; i++){
for(int j = 0; j < 6; j++){
int p_face = posture[rota[i]][j];
color[i][p_face] = cubes[i][j];
//涂色
}
}
//finished painting
//以面作为标准
int tot = 0;
for(int k = 0; k < 6; k++){
int cnt[maxn*6];
memset(cnt,0, sizeof(cnt));
int maxface = 0;
//color[i][k]
for(int i = 0; i < n; i++){
maxface = max(maxface, ++cnt[color[i][k]]);
}
tot += n-maxface;
}
ans = min(ans,tot);
}
int main(){
while(scanf("%d",&n) == 1 && n){
cnames.clear();
for(int i = 0; i < n; i++){
for(int j = 0; j < 6; j++){
char name[30];
scanf("%s",name);
cubes[i][j] = getid(name);
}
}
ans = n*6;
rota[0] = 0;
enumdfs(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++;
}
}
原创技术分享,您的支持鼓励我继续创作