计蒜客

71 阅读 0 评论 47 点赞

我是靠谱客的博主爱听歌鼠标，这篇文章主要介绍计蒜客，现在分享给大家，希望可以做个参考。

计蒜之道第一场：初赛

链接：https://www.jisuanke.com/contest/726

A. 阿里的新游戏

复制代码

1
思路：任意搜任意写（这个代码写的很挫）

复制代码

1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdio>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <algorithm>
 9
10 using namespace std;
11
12 int main()
13 {
14
int n, m;
15
int sum = 0;
16
int a, b;
17
set<pair<int, int>> s;
18
pair<int, int> p1 = {-3, 3};
19
pair<int, int> p2 = {0, 3};
20
pair<int, int> p3 = {3, 3};
21
pair<int, int> p4 = {-3, 0};
22
pair<int, int> p5 = {-2, 0};
23
pair<int, int> p6 = {-1, 0};
24
pair<int, int> p7 = {1, 0};
25
pair<int, int> p8 = {2, 0};
26
pair<int, int> p9 = {3, 0};
27
pair<int, int> p10 = {0, -1};
28
pair<int, int> p11 = {0, -2};
29
pair<int, int> p12 = {0, -3};
30
pair<int, int> p13 = {-3, -3};
31
pair<int, int> p14 = {3, -3};
32
pair<int, int> p15 = {0, 2};
33
pair<int, int> p16 = {0, 1};
34
pair<int, int> p17 = {-2, 2};
35
pair<int, int> p18 = {2, 2};
36
pair<int, int> p19 = {-1, 1};
37
pair<int, int> p20 = {1, 1};
38
pair<int, int> p21 = {-1, -1};
39
pair<int, int> p22 = {1, -1};
40
pair<int, int> p23 = {-2, -2};
41
pair<int, int> p24 = {2, -2};
42
43
44
cin >> n >> m;
45
for (int i = 0; i < n; i++)
46 
{
47
cin >> a >> b;
48 
s.insert(make_pair(a, b));
49 
}
50
for (int i = 0; i < m; i++)
51 
{
52
cin >> a >> b;
53 
}
54
if (s.count(p1) && s.count(p2) && s.count(p3))
55
sum++;
56
if (s.count(p1) && s.count(p4) && s.count(p13))
57
sum++;
58
if (s.count(p2) && s.count(p15) && s.count(p16))
59
sum++;
60
if (s.count(p4) && s.count(p5) && s.count(p6))
61
sum++;
62
if (s.count(p7) && s.count(p8) && s.count(p9))
63
sum++;
64
if (s.count(p12) && s.count(p11) && s.count(p10))
65
sum++;
66
if (s.count(p12) && s.count(p13) && s.count(p14))
67
sum++;
68
if (s.count(p3) && s.count(p9) && s.count(p14))
69
sum++;
70
if (s.count(p17) && s.count(p18) && s.count(p15))
71
sum++;
72
if (s.count(p23) && s.count(p24) && s.count(p11))
73
sum++;
74
if (s.count(p17) && s.count(p5) && s.count(p23))
75
sum++;
76
if (s.count(p8) && s.count(p18) && s.count(p24))
77
sum++;
78
if (s.count(p19) && s.count(p21) && s.count(p6))
79
sum++;
80
if (s.count(p19) && s.count(p16) && s.count(p20))
81
sum++;
82
if (s.count(p20) && s.count(p7) && s.count(p22))
83
sum++;
84
if (s.count(p21) && s.count(p10) && s.count(p22))
85
sum++;
86
cout << sum << endl;
87
88
return 0;
89 }

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
 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdio>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <algorithm>
 9
10 using namespace std;
11
12 int main()
13 {
14
int n, m;
15
int sum = 0;
16
int a, b;
17
set<pair<int, int>> s;
18
pair<int, int> p1 = {-3, 3};
19
pair<int, int> p2 = {0, 3};
20
pair<int, int> p3 = {3, 3};
21
pair<int, int> p4 = {-3, 0};
22
pair<int, int> p5 = {-2, 0};
23
pair<int, int> p6 = {-1, 0};
24
pair<int, int> p7 = {1, 0};
25
pair<int, int> p8 = {2, 0};
26
pair<int, int> p9 = {3, 0};
27
pair<int, int> p10 = {0, -1};
28
pair<int, int> p11 = {0, -2};
29
pair<int, int> p12 = {0, -3};
30
pair<int, int> p13 = {-3, -3};
31
pair<int, int> p14 = {3, -3};
32
pair<int, int> p15 = {0, 2};
33
pair<int, int> p16 = {0, 1};
34
pair<int, int> p17 = {-2, 2};
35
pair<int, int> p18 = {2, 2};
36
pair<int, int> p19 = {-1, 1};
37
pair<int, int> p20 = {1, 1};
38
pair<int, int> p21 = {-1, -1};
39
pair<int, int> p22 = {1, -1};
40
pair<int, int> p23 = {-2, -2};
41
pair<int, int> p24 = {2, -2};
42
43
44
cin >> n >> m;
45
for (int i = 0; i < n; i++)
46 
{
47
cin >> a >> b;
48 
s.insert(make_pair(a, b));
49 
}
50
for (int i = 0; i < m; i++)
51 
{
52
cin >> a >> b;
53 
}
54
if (s.count(p1) && s.count(p2) && s.count(p3))
55
sum++;
56
if (s.count(p1) && s.count(p4) && s.count(p13))
57
sum++;
58
if (s.count(p2) && s.count(p15) && s.count(p16))
59
sum++;
60
if (s.count(p4) && s.count(p5) && s.count(p6))
61
sum++;
62
if (s.count(p7) && s.count(p8) && s.count(p9))
63
sum++;
64
if (s.count(p12) && s.count(p11) && s.count(p10))
65
sum++;
66
if (s.count(p12) && s.count(p13) && s.count(p14))
67
sum++;
68
if (s.count(p3) && s.count(p9) && s.count(p14))
69
sum++;
70
if (s.count(p17) && s.count(p18) && s.count(p15))
71
sum++;
72
if (s.count(p23) && s.count(p24) && s.count(p11))
73
sum++;
74
if (s.count(p17) && s.count(p5) && s.count(p23))
75
sum++;
76
if (s.count(p8) && s.count(p18) && s.count(p24))
77
sum++;
78
if (s.count(p19) && s.count(p21) && s.count(p6))
79
sum++;
80
if (s.count(p19) && s.count(p16) && s.count(p20))
81
sum++;
82
if (s.count(p20) && s.count(p7) && s.count(p22))
83
sum++;
84
if (s.count(p21) && s.count(p10) && s.count(p22))
85
sum++;
86
cout << sum << endl;
87
88
return 0;
89 }

View Code：

B. 阿里天池的新任务（简单）

复制代码

1
思路：先生成s然后再用kmp进行次数统计

复制代码

1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdio>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <algorithm>
 9
10 using namespace std;
11
12 void get_next(string s, int* next)
13 
{
14
int n = s.size();
15
int j = 0;
16
int k = -1;
17
next[0] = -1;
18
while(j < n)
19 
{
20
if (k == -1 || s[j] == s[k])
21 
{
22
j++;
23
k++;
24
if (s[j] != s[k])
25
next[j] = k;
26
else
27
next[j] = next[k];
28 
}
29
else
30
k = next[k];
31 
}
32 
}
33
34 int main()
35 {
36
int n, a, b, l, r;
37
int sum = 0;
38
39
cin >> n >> a >> b >> l >> r;
40
vector<int> nums(n);
41
string s;
42
43
44
nums[0] = b;
45
for (int i = 1; i < n; i++)
46
nums[i] = (nums[i - 1] + a) % n;
47
for (int i = 0; i < n; i++)
48 
{
49
if (nums[i] >= l && nums[i] <= r)
50 
{
51
if (nums[i] & 1)
52
s += 'T';
53
else
54
s += 'A';
55 
}
56
else if (nums[i] < l || nums[i] > r)
57 
{
58
if (nums[i] & 1)
59
s += 'C';
60
else
61
s += 'G';
62 
}
63 
}
64
65
string t;
66
cin >> t;
67
int len = t.size();
68
if (len == 0 || len > s.size())
69
cout << 0 << endl;
70
else
71 
{
72
73
int next[len + 1] = {0};
74 
get_next(t, next);
75
76
int i = 0;
77
int j = 0;
78
while (i < s.size())
79 
{
80
if (j == -1 || s[i] == t[j])
81 
{
82
i++;
83
j++;
84 
}
85
else
86
j = next[j];
87
88
if (j >= len)
89 
{
90
j = next[j];
91
sum++;
92 
}
93 
}
94
cout << sum << endl;
95
96 
}
97
98
return 0;
99 }

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
 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <cstdio>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <algorithm>
 9
10 using namespace std;
11
12 void get_next(string s, int* next)
13 
{
14
int n = s.size();
15
int j = 0;
16
int k = -1;
17
next[0] = -1;
18
while(j < n)
19 
{
20
if (k == -1 || s[j] == s[k])
21 
{
22
j++;
23
k++;
24
if (s[j] != s[k])
25
next[j] = k;
26
else
27
next[j] = next[k];
28 
}
29
else
30
k = next[k];
31 
}
32 
}
33
34 int main()
35 {
36
int n, a, b, l, r;
37
int sum = 0;
38
39
cin >> n >> a >> b >> l >> r;
40
vector<int> nums(n);
41
string s;
42
43
44
nums[0] = b;
45
for (int i = 1; i < n; i++)
46
nums[i] = (nums[i - 1] + a) % n;
47
for (int i = 0; i < n; i++)
48 
{
49
if (nums[i] >= l && nums[i] <= r)
50 
{
51
if (nums[i] & 1)
52
s += 'T';
53
else
54
s += 'A';
55 
}
56
else if (nums[i] < l || nums[i] > r)
57 
{
58
if (nums[i] & 1)
59
s += 'C';
60
else
61
s += 'G';
62 
}
63 
}
64
65
string t;
66
cin >> t;
67
int len = t.size();
68
if (len == 0 || len > s.size())
69
cout << 0 << endl;
70
else
71 
{
72
73
int next[len + 1] = {0};
74 
get_next(t, next);
75
76
int i = 0;
77
int j = 0;
78
while (i < s.size())
79 
{
80
if (j == -1 || s[i] == t[j])
81 
{
82
i++;
83
j++;
84 
}
85
else
86
j = next[j];
87
88
if (j >= len)
89 
{
90
j = next[j];
91
sum++;
92 
}
93 
}
94
cout << sum << endl;
95
96 
}
97
98
return 0;
99 }

View Code：

（总结：调试过程输出结果然后把代码直接粘进去导致WA了好几次，下次得注意，细节方面还是得加强，加油！）

计蒜之道第三场：初赛

A. 腾讯课堂的物理实验

思路：碰撞理解为穿越，只是小球编号变化，位置可单独模拟（可参见《挑战程序设计》Ants那道题思路）

复制代码

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
 1 #include <iostream>
 2 #include <vector>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <algorithm>
 6
 7 using namespace std;
 8
 9 int main()
10 {
11
int l, t, T;
12
int res = 0;
13
int a = 0, b = 0, c = 0, d = 0;
14
int x, y;
15
16
cin >> l >> t >> T;
17
18
a = T / l;
19
b = T % l;
20
c = (T - t) / l;
21
d = (T - t) % l;
22
23
if (a % 2 == 0)
24
x = b;
25
else
26
x = l - b;
27
28
if (c % 2 == 0)
29
y = l - d;
30
else
31
y = d;
32
33
cout << abs(x - y) << endl;
34
35
return 0;
36 }