这是我正规打的第一场比赛啊。！cf神奇的时区导致每次都在半夜开场，这次遇到个八点半的，终于可以试试了。
现场a了三题，终于变绿了，0.o，1500-2，还能接受，其实还能再a一题的，但是由于两个小时六道题真的来不及，所以看到E的时候着急了，看错题了，后来看到题解才反应过来，果断试了一下，虽然还有些波折，但还是过了。
A. Hotelier
签到题 枚举
L就从左开始，R就从右开始枚举
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
| #include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include <functional>
#include<string>
#include<set>
#include<queue>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
int n;
set<int>room;
bool ans[maxn];
int main() {
cin.sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) {
char c;
cin >> c;
if (c == 'L') {
for (int i = 0; i <= 9; i++) {
if (ans[i] == 0) {
ans[i] = 1;
break;
}
}
}
else if (c == 'R') {
for (int i = 9; i >= 0; i--) {
if (ans[i] == 0) {
ans[i] = 1;
break;
}
}
}
else {
int t = c - '0';
ans[t] = 0;
}
}
for (int i = 0; i <= 9; i++) {
cout << ans[i];
}
return 0;
}
|
B. Block Adventure
贪心
每次走之前尽可能多地拿砖块。
注意如果地上的砖块已经是0了，就不能再拿了。
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
| #include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include <functional>
#include<string>
#include<set>
#include<queue>
using namespace std;
#define ll long long
const int maxn = 1e6 + 5;
int t;
int a[105];
int main() {
cin.sync_with_stdio(false);
cin >> t;
while (t--) {
bool win = 1;
int n, k;
ll m;
cin >> n >> m >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n - 1; i++) {
if (a[i] + k >= a[i + 1]) {
m += min(a[i], a[i] + k - a[i + 1]);
}
else if (a[i + 1] - k - a[i] <= m) {
m -= (a[i + 1] - k - a[i]);
}
else {
win = 0;
break;
}
}
if (win)cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
|
C. Round Corridor
数学，最小公倍数
观察发现，在两个数的公倍数处会有墙，因此最小公倍数把圆分成几个block，只要计算两个房间是否在同一个block里就能判断能否达到。
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
| #include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include <functional>
#include<string>
#include<set>
#include<queue>
using namespace std;
#define ll long long
const int maxn = 1e6 + 5;
ll gcd(ll a, ll b) {
if (a < b)
swap(a, b);
if (b == 0) {
return a;
}
return gcd(b, a%b);
}
ll n, m;
int q;
int main() {
cin.sync_with_stdio(false);
cin >> n >> m >> q;
ll t = gcd(m, n);
n /= t; m /= t;
while (q--) {
int sx, ex;
ll sy, ey;
cin >> sx >> sy >> ex >> ey;
sy--; ey--;
if (sx == 1 && ex == 1) {
if ((sy / n) == (ey / n))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
else if (sx == 2 && ex == 2) {
if ((sy / m) == (ey / m))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
else if (sx == 1 && ex == 2) {
if ((sy / n) == (ey / m))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
else {
if ((sy / m) == (ey / n))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}
return 0;
}
|
E. Compress Words
就是这道题了，刚开始理解成判断第二个串的字符是否在第一个串中，写的当然也是错的了。
实际上是要找到满足第二个串的前缀等于第一个串的后缀的最大串。
那么把第二个串拼在第一个串前面，然后kmp确定next数组。
不过如果在拼接的时候用substr的话，是会超时的！！
**用push_back！！**这一点也是刚学到了，以前都不知道string还有个push_back函数。实验证明，push_back拼接字符串比substr快的不知道到哪里去了，差了一百多倍。
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
| #include<iostream>
#include<stdio.h>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
using namespace std;
#define ll long long
const int maxn = 1e6 + 5;
int n;
int nxt[maxn];
void getNextVal(const string& p) {
int plen = p.length();
nxt[0] = -1;
int k = -1;
int j = 0;
while (j < plen) {
if (k == -1 || p[j] == p[k]) {
j++;
k++;
if (p[j] != p[k]) {
nxt[j] = k;
}
else {
nxt[j] = nxt[k];
}
}
else {
k = nxt[k];
}
}
}
string s, t, c;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
cin >> s;
string tmp;
for (int i = 0; i < n - 1; i++) {
tmp.clear();
cin >> t;
int x = s.length(), y = t.length();
if (x > y) {
for (int j = 0; j < y; j++) {
tmp.push_back(t[j]);
}
tmp.push_back('$');
for (int j = x - y; j < x; j++) {
tmp.push_back(s[j]);
}
}
else {
for (int j = 0; j < x; j++) {
tmp.push_back(t[j]);
}
tmp.push_back('$');
for (int j = 0; j < x; j++) {
tmp.push_back(s[j]);
}
}
int z = tmp.length();
getNextVal(tmp);
int len = nxt[z];
for (int j = len; j < y; j++) {
s.push_back(t[j]);
}
}
cout << s << endl;
return 0;
}
|
