Codeforces Round #578 (Div. 2)

比较简单暴力的一场。

题目链接：http://codeforces.com/contest/1200

A：

水题。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 const int maxn = 1e5 + 10;
21 int n, a[20];
22 char s[maxn];
23 
24 int main() {
25     scanf("%d", &n);
26     scanf("%s", s + 1);
27     for (int i = 1; i <= n; i++) {
28         if (s[i] == ‘L‘) {
29             for (int i = 0; i < 10; i++)
30                 if (!a[i]) {
31                     a[i] = 1; break;
32                 }
33         } else if (s[i] == ‘R‘) {
34             for (int i = 9; i >= 0; i--)
35                 if (!a[i]) {
36                     a[i] = 1; break;
37                 }
38         } else a[s[i] - ‘0‘] = 0;
39     }
40     for (int i = 0; i < 10; i++) printf("%d", a[i]);
41     puts("");
42     return 0;
43 }

B：

贪心，注意h[i]<h[i+1]时也可以攒石头。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 int main() {
21     int t; scanf("%d", &t);
22     while (t--) {
23         ll n, m, k; scanf("%lld%lld%lld", &n, &m, &k);
24         ll h[n + 1], solved = 1;
25         for (int i = 1; i <= n; i++) scanf("%lld", &h[i]);
26         for (int i = 1; i < n; i++) {
27             if (h[i] >= h[i + 1]) {
28                 m += h[i] - h[i + 1];
29                 h[i] = h[i + 1];
30                 m += min(h[i], k);
31             } else {
32                 if (h[i + 1] - h[i] - m > k) {
33                     solved = 0; break;
34                 } else {
35                     if (h[i + 1] - h[i] <= k)
36                         m += min(h[i], h[i] - (h[i + 1] - k));
37                     else
38                         m -= h[i + 1] - h[i] - k;
39                 }
40             }
41         }
42         if (solved) puts("YES"); else puts("NO");
43     }
44     return 0;
45 }

C：

求个gcd就看出来了。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 ll n, m;
21 int q;
22 
23 int main() {
24     scanf("%lld%lld%d", &n, &m, &q);
25     ll gcd = __gcd(n, m);
26     ll awall = n / gcd, bwall = m / gcd;
27     while (q--) {
28         ll x, y, p, q; scanf("%lld%lld%lld%lld", &x, &y, &p, &q);
29         ll tmpa, tmpb;
30         if (x == 1)
31             tmpa = y % awall ? y / awall : y / awall - 1;
32         else
33             tmpa = y % bwall ? y / bwall : y / bwall - 1;
34         if (p == 1)
35             tmpb = q % awall ? q / awall : q / awall - 1;
36         else
37             tmpb = q % bwall ? q / bwall : q / bwall - 1;
38         if (tmpa == tmpb) puts("YES"); else puts("NO");
39     }
40     return 0;
41 }

D：

O(n²)暴力可以过。

E：

kmp。

 1 /* basic header */
 2 #include <bits/stdc++.h>
 3 /* define */
 4 #define ll long long
 5 #define dou double
 6 #define pb emplace_back
 7 #define mp make_pair
 8 #define sot(a,b) sort(a+1,a+1+b)
 9 #define rep1(i,a,b) for(int i=a;i<=b;++i)
10 #define rep0(i,a,b) for(int i=a;i<b;++i)
11 #define eps 1e-8
12 #define int_inf 0x3f3f3f3f
13 #define ll_inf 0x7f7f7f7f7f7f7f7f
14 #define lson (curpos<<1)
15 #define rson (curpos<<1|1)
16 /* namespace */
17 using namespace std;
18 /* header end */
19 
20 const int maxn = 1e5 + 10;
21 int n;
22 string ans;
23 
24 int kmp(string s) {
25     vector<int> tmp(s.size());
26     for (int i = 1; i < s.size(); i++) {
27         int k = tmp[i - 1];
28         while (s[k] != s[i]) {
29             if (!k) {
30                 k = -1; break;
31             }
32             k = tmp[k - 1];
33         }
34         tmp[i] = k + 1;
35     }
36     return tmp.back();
37 }
38 
39 int main() {
40     cin >> n;
41     for (int i = 0; i < n; i++) {
42         if (!i) {
43             cin >> ans;
44             continue;
45         }
46         string s; cin >> s; string t = s + ‘#‘;
47         int a = min((int)ans.size(), (int)s.size());
48         t.insert(t.end(), ans.end() - a, ans.end());
49         int x = kmp(t);
50         while (x--) ans.pop_back();
51         ans.insert(ans.end(), s.begin(), s.end());
52     }
53     cout << ans << endl;
54     return 0;
55 }