Codeforces Round #556 (Div. 2)

没想到平成年代最后一场cf居然是手速场，幸好拿了个小号娱乐不然掉分预定 (逃

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

 A：

傻题。

 1 /* basic header */
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <cstring>
 7 #include <cmath>
 8 #include <cstdint>
 9 #include <climits>
10 #include <float.h>
11 /* STL */
12 #include <vector>
13 #include <set>
14 #include <map>
15 #include <queue>
16 #include <stack>
17 #include <algorithm>
18 #include <array>
19 #include <iterator>
20 /* define */
21 #define ll long long
22 #define dou double
23 #define pb emplace_back
24 #define mp make_pair
25 #define fir first
26 #define sec second
27 #define sot(a,b) sort(a+1,a+1+b)
28 #define rep1(i,a,b) for(int i=a;i<=b;++i)
29 #define rep0(i,a,b) for(int i=a;i<b;++i)
30 #define repa(i,a) for(auto &i:a)
31 #define eps 1e-8
32 #define int_inf 0x3f3f3f3f
33 #define ll_inf 0x7f7f7f7f7f7f7f7f
34 #define lson curPos<<1
35 #define rson curPos<<1|1
36 /* namespace */
37 using namespace std;
38 /* header end */
39 
40 const int maxn = 1e2 + 10;
41 int n, m, r, minn = 2000, maxx = 0;
42 
43 int main()
44 {
45     scanf("%d%d%d", &n, &m, &r);
46     rep1(i, 1, n)
47     {
48         int x; scanf("%d", &x); minn = min(minn, x);
49     }
50     rep1(i, 1, m)
51     {
52         int x; scanf("%d", &x); maxx = max(maxx, x);
53     }
54     if (maxx > minn) printf("%d
", maxx * (r / minn) + r % minn);
55     else printf("%d
", r);
56     return 0;
57 }
View Code

B：

乍一看以为要搜，其实根本不需要，n^2填进去判断就完事了 (看通过人数就能猜到根本不用搜。

至于为什么可以这样，是因为跟紧密填充相关吗？

 1 /* basic header */
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <cstring>
 7 #include <cmath>
 8 #include <cstdint>
 9 #include <climits>
10 #include <float.h>
11 /* STL */
12 #include <vector>
13 #include <set>
14 #include <map>
15 #include <queue>
16 #include <stack>
17 #include <algorithm>
18 #include <array>
19 #include <iterator>
20 /* define */
21 #define ll long long
22 #define dou double
23 #define pb emplace_back
24 #define mp make_pair
25 #define fir first
26 #define sec second
27 #define sot(a,b) sort(a+1,a+1+b)
28 #define rep1(i,a,b) for(int i=a;i<=b;++i)
29 #define rep0(i,a,b) for(int i=a;i<b;++i)
30 #define repa(i,a) for(auto &i:a)
31 #define eps 1e-8
32 #define int_inf 0x3f3f3f3f
33 #define ll_inf 0x7f7f7f7f7f7f7f7f
34 #define lson curPos<<1
35 #define rson curPos<<1|1
36 /* namespace */
37 using namespace std;
38 /* header end */
39 
40 const int maxn = 55;
41 int a[maxn][maxn], n, solved = 0;
42 char s[maxn];
43 
44 int check()
45 {
46     rep1(i, 1, n)
47     rep1(j, 1, n)
48     if (!a[i][j]) return 0;
49     return 1;
50 }
51 
52 int putable(int x, int y)
53 {
54     if (x == 1 || x == n || y == 1 || y == n) return 0;
55     if (a[x - 1][y] || a[x + 1][y] || a[x][y - 1] || a[x][y + 1] || a[x][y]) return 0;
56     return 1;
57 }
58 
59 int main()
60 {
61     scanf("%d", &n);
62     rep1(i, 1, n)
63     {
64         scanf("%s", s + 1);
65         rep1(j, 1, n)
66         if (s[j] == '#') a[i][j] = 1; else a[i][j] = 0;
67     }
68     rep1(i, 2, n - 1)
69     {
70         rep1(j, 2, n - 1)
71         if (putable(i, j))
72         {
73             a[i - 1][j] = a[i + 1][j] = a[i][j - 1] = a[i][j + 1] = a[i][j] = 1;
74         }
75     }
76     if (check()) puts("YES");
77     else puts("NO");
78     return 0;
79 }
View Code

C：

2e5质数筛贪心就完事了，优先满足最近的质数，先塞2再塞1，也有大佬说不用筛。

 1 /* basic header */
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <cstring>
 7 #include <cmath>
 8 #include <cstdint>
 9 #include <climits>
10 #include <float.h>
11 /* STL */
12 #include <vector>
13 #include <set>
14 #include <map>
15 #include <queue>
16 #include <stack>
17 #include <algorithm>
18 #include <array>
19 #include <iterator>
20 /* define */
21 #define ll long long
22 #define dou double
23 #define pb emplace_back
24 #define mp make_pair
25 #define fir first
26 #define sec second
27 #define sot(a,b) sort(a+1,a+1+b)
28 #define rep1(i,a,b) for(int i=a;i<=b;++i)
29 #define rep0(i,a,b) for(int i=a;i<b;++i)
30 #define repa(i,a) for(auto &i:a)
31 #define eps 1e-8
32 #define int_inf 0x3f3f3f3f
33 #define ll_inf 0x7f7f7f7f7f7f7f7f
34 #define lson curPos<<1
35 #define rson curPos<<1|1
36 /* namespace */
37 using namespace std;
38 /* header end */
39 
40 const int maxn = 2e5 + 10;
41 int c1 = 0, c2 = 0, n, prime[maxn], p = 1, tot;
42 vector<int>ans;
43 
44 bool valid[maxn];
45 void getPrime(int n, int &tot, int ans[maxn])
46 {
47     tot = 0;
48     memset(valid, 1, sizeof(valid));
49     for (int i = 2; i <= n; i++)
50     {
51         if (valid[i]) ans[++tot] = i;
52         for (int j = 1; (j <= tot) && (i * ans[j] <= n); j++)
53         {
54             valid[i * ans[j]] = false;
55             if (i % ans[j] == 0) break;
56         }
57     }
58 }
59 
60 int main()
61 {
62     getPrime(2e5, tot, prime);
63     ans.clear();
64     scanf("%d", &n);
65     rep1(i, 1, n)
66     {
67         int x; scanf("%d", &x);
68         if (x & 1) c1++; else c2++;
69     }
70     int curr = 0;
71     while (c1 || c2)
72     {
73         if (prime[p] - curr > 2 && c2)
74         {
75             ans.pb(2); c2--; curr += 2;
76         }
77         else if (prime[p] - curr == 2 && c2)
78         {
79             ans.pb(2); c2--; p++; curr += 2;
80         }
81         else if (prime[p] - curr == 1 && c1)
82         {
83             ans.pb(1); c1--; p++; curr += 1;
84         }
85         else
86         {
87             if (c2)
88             {
89                 ans.pb(2); c2--; curr += 2;
90             }
91             else if (c1)
92             {
93                 ans.pb(1); c1--; curr += 1;
94             }
95         }
96     }
97     for (auto i : ans) printf("%d ", i);
98     return 0;
99 }
View Code

D：

把全场人卡死的dp，直到比赛结束都只有不到20个人过了.

设f[i][j][k]表示第1个串匹配到i，第2个串匹配到j，第3个串匹配到k所用的最小长度，然后每次添加一个字符可以O(250^2)转移另外两维的状态即可。

复杂度：O(q*250^2)

E：

给定一个括号序列，每个括号序列可以唯一生成一棵有根树。给出q次询问，每次询问交换上次得到的括号序列中某两个括号的位置（保证交换之后仍然可以生成一棵有根树）。输出交换之后得到的有根树的直径。

一看就是线段树可以做的题。

  1 /* basic header */
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <string>
  6 #include <cstring>
  7 #include <cmath>
  8 #include <cstdint>
  9 #include <climits>
 10 #include <float.h>
 11 /* STL */
 12 #include <vector>
 13 #include <set>
 14 #include <map>
 15 #include <queue>
 16 #include <stack>
 17 #include <algorithm>
 18 #include <array>
 19 #include <iterator>
 20 /* define */
 21 #define ll long long
 22 #define dou double
 23 #define pb emplace_back
 24 #define mp make_pair
 25 #define fir first
 26 #define sec second
 27 #define sot(a,b) sort(a+1,a+1+b)
 28 #define rep1(i,a,b) for(int i=a;i<=b;++i)
 29 #define rep0(i,a,b) for(int i=a;i<b;++i)
 30 #define repa(i,a) for(auto &i:a)
 31 #define eps 1e-8
 32 #define int_inf 0x3f3f3f3f
 33 #define ll_inf 0x7f7f7f7f7f7f7f7f
 34 #define lson curPos<<1
 35 #define rson curPos<<1|1
 36 /* namespace */
 37 using namespace std;
 38 /* header end */
 39 
 40 const int maxn = 2e5 + 10;
 41 char s[maxn];
 42 
 43 struct Node
 44 {
 45     int sum, pmx, lmx, minn, maxx, d;
 46     Node() {}
 47     Node(int a, int b, int c, int d, int e, int f)
 48     {
 49         sum = a; pmx = b; lmx = c; minn = d; maxx = e; d = f;
 50     }
 51 };
 52 
 53 //ostream &operator<<(ostream &os, const Node &rhs)
 54 //{
 55 //    os << rhs.sum << " " << rhs.pmx << " " << rhs.lmx << " " << rhs.minn << " " << rhs.maxx << " " << rhs.d;
 56 //    return os;
 57 //}
 58 
 59 Node segT[maxn << 2];
 60 
 61 void maintain(int curPos)
 62 {
 63     segT[curPos].sum = segT[lson].sum + segT[rson].sum;
 64     segT[curPos].pmx = max(segT[lson].pmx, max(segT[rson].maxx - 2 * segT[lson].minn + segT[lson].sum, segT[rson].pmx - segT[lson].sum));
 65     segT[curPos].lmx = max(segT[lson].lmx, max(segT[rson].lmx - segT[lson].sum, segT[lson].maxx - 2 * segT[rson].minn - 2 * segT[lson].sum));
 66     segT[curPos].minn = min(segT[lson].minn, segT[rson].minn + segT[lson].sum);
 67     segT[curPos].maxx = max(segT[lson].maxx, segT[rson].maxx + segT[lson].sum);
 68     segT[curPos].d = max(max(segT[lson].d, segT[rson].d), max(segT[lson].maxx + segT[rson].pmx - segT[lson].sum, segT[lson].lmx + segT[lson].sum + segT[rson].maxx));
 69 }
 70 
 71 void build(int curPos, int curL, int curR)
 72 {
 73     if (curL == curR)
 74     {
 75         int x = s[curL] == '(' ? 1 : -1;
 76         segT[curPos] = Node(x, -x, -x, x, x, 0);
 77         // cout << segT[curPos] << endl;
 78         return;
 79     }
 80     int mid = curL + curR >> 1;
 81     build(lson, curL, mid); build(rson, mid + 1, curR);
 82     maintain(curPos);
 83 }
 84 
 85 void update(int pos, int curPos, int curL, int curR)
 86 {
 87     if (curL == curR)
 88         return build(curPos, curL, curR);
 89     int mid = curL + curR >> 1;
 90     if (pos <= mid)
 91         update(pos, lson, curL, mid);
 92     else
 93         update(pos, rson, mid + 1, curR);
 94     maintain(curPos);
 95 }
 96 
 97 int main()
 98 {
 99     int n, m; scanf("%d%d", &n, &m);
100     scanf("%s", s + 1);
101     n = n * 2 - 2;
102     build(1, 1, n);
103     printf("%d
", segT[1].d);
104     while (m--)
105     {
106         int x, y; scanf("%d%d", &x, &y);
107         swap(s[x], s[y]);
108         update(x, 1, 1, n); update(y, 1, 1, n);
109         printf("%d
", segT[1].d);
110     }
111     return 0;
112 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/JHSeng/p/10795255.html