Educational Codeforces Round 59 Solution

A. Digits Sequence Dividing

签.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 1010
 5 char s[N]; int n; 
 6 
 7 void solve()
 8 {
 9     if (n == 2 && s[1] >= s[2]) 
10     {
11         puts("NO"); 
12         return;
13     }
14     else
15     {
16         puts("YES");
17         puts("2");
18         printf("%c %s
", s[1], s + 2);
19     }
20 }
21 
22 int main()
23 {
24     int t; scanf("%d", &t);
25     while (t--)
26     {
27         scanf("%d", &n);
28         scanf("%s", s + 1);
29         solve();
30     }
31     return 0;
32 }

View Code

B. Digital root

签.

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 int t;
 6 ll k, x;
 7 
 8 int main()
 9 {
10     scanf("%d", &t);
11     while (t--)
12     {
13         scanf("%lld%lld", &k, &x);
14         printf("%lld
", (k - 1) * 9 + x);
15     }
16     return 0;
17 }

View Code

C. Brutality

每次连续的一段中如果大于$k个，取最大的k个$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 200010
 6 int n, k;
 7 ll a[N];
 8 char s[N];
 9 
10 int main()
11 {
12     while (scanf("%d%d", &n, &k) != EOF)
13     {
14         for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
15         scanf("%s", s + 1); s[n + 1] = '#';
16         priority_queue <ll> pq; pq.push(a[1]);
17         ll res = 0;
18         for (int i = 2; i <= n + 1; ++i)
19         {
20             if (s[i] != s[i - 1]) 
21             {
22                 for (int j = k; !pq.empty() && j; --j)
23                 {
24                     res += pq.top(); pq.pop();
25                 }
26                 while (!pq.empty()) pq.pop();
27             }
28             pq.push(a[i]);
29         }
30         printf("%lld
", res);
31     }
32     return 0;
33 }

View Code

D. Compression

Solved.

题意：

有$n cdot n的01矩阵，把矩阵压缩，压缩后的大小为frac {n}{x}$

思路：

考虑$x | n, 枚举n的因数，在5200范围下，最多有60个$

$然后每次枚举因数n^2判断是否可以就可以喜提TLE一枚$

$我们考虑用bitset优化$

$我们先处理出b数组第一行，然后接下来x - 1行都可以直接位运算赋值$

$那么这个复杂度就是O(frac{n^2}{64} + (frac{n^2}{x}))$

我们发现$< x 的因数不会太多当因数 > x 的时候复杂度就接近O(frac{n^2}{64})$

$然后和a数字异或可以O(frac{n^2}{64}) 判断合法性$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define N 5510
 5 int n;
 6 bitset <N> a[N], b[N], tmp;  
 7 char s[N][N];
 8 char Hash[210]; 
 9 int res; 
10 
11 void change(int x)
12 {
13     a[x].reset();
14     for (int i = 1, j = 0; i <= n / 4; ++i)
15     {
16         int num = Hash[s[x][i]];
17         for (int k = 3; k >= 0; --k)
18             a[x][++j] = (num >> k) & 1;
19     }
20 }
21 
22 bool solve(int x)
23 {
24     for (int i = 1; i <= n; i += x)
25     {
26         tmp.reset();
27         for (int j = 1; j <= n; j += x)
28             for (int k = j; k < j + x; ++k)
29                 tmp[k] = a[i][j];
30         for (int j = i; j < i + x; ++j) 
31         {
32             b[j] &= 0; 
33             b[j] |= tmp;
34         }
35     } 
36     for (int i = 1; i <= n; ++i) if ((a[i] ^ b[i]) != 0)  
37     {
38         return false;
39     }
40     return true;
41 }
42 
43 int main()
44 {
45     for (int i = 0; i <= 9; ++i) Hash[i + '0'] = i;
46     Hash['A'] = 10;
47     Hash['B'] = 11;
48     Hash['C'] = 12;
49     Hash['D'] = 13; 
50     Hash['E'] = 14;
51     Hash['F'] = 15;
52     while (scanf("%d", &n) != EOF)
53     {
54         for (int i = 1; i <= n; ++i)
55             scanf("%s", s[i] + 1);    
56         for (int i = 1; i <= n; ++i) change(i); 
57         res = 1; 
58         vector <int> fac;
59         for (int i = 1; i * i <= n; ++i) if (n % i == 0) fac.push_back(i), fac.push_back(n / i);  
60         sort(fac.begin(), fac.end());
61         fac.erase(unique(fac.begin(), fac.end()), fac.end());
62         reverse(fac.begin(), fac.end()); 
63         for (auto it : fac) if (it > 1)
64         {
65             if (solve(it)) 
66             {
67                 res = it;
68                 break;
69             }
70         }
71         printf("%d
", res); 
72     }
73     return 0;
74 }

View Code

E. Vasya and Binary String

Upsolved.

题意：

有一个01串，每次可以取连续的一段相同的消除

消除后剩下的两段合并，给出连续消去$x个可以获得的价值$

求最大价值

思路：

$dp[l][r][k]表示区间[l, r]并且末尾接着k个与r相同的字符的最大价值$

$那么转移可以在[l, r]中找一个i使得s[i] = s[r] 那么答案就是 dp[l][i][k + 1] + dp[i + 1][r - 1][0]$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 110
 6 
 7 int n;
 8 char s[N];
 9 ll a[N];
10 ll dp[N][N][N];
11 
12 ll DFS(int l, int r, int k)
13 {
14     if (r < l) return 0;
15     if (l == r) return a[k + 1];
16     if (dp[l][r][k] != -1) return dp[l][r][k];
17     dp[l][r][k] = a[k + 1] + DFS(l, r - 1, 0);  
18     for (int i = l; i < r; ++i) if (s[i] == s[r]) 
19         dp[l][r][k] = max(dp[l][r][k], DFS(l, i, k + 1) + DFS(i + 1, r - 1, 0));
20     return dp[l][r][k];
21 }
22 
23 int main()
24 {
25     while (scanf("%d", &n) != EOF)
26     {
27         scanf("%s", s + 1);
28         for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
29         memset(dp, -1, sizeof dp);
30         printf("%lld
", DFS(1, n, 0));
31     }
32     return 0;
33 }

View Code

F. Vasya and Endless Credits

Upsolved.

题意：

有一个人可以向银行借款

$a_i, b_i, k_i$

$a_i表示借a_i元，b_i表示在接下来的k_i个月需要给银行b_i元钱$

求如何借款，使得其中某个月拥有最大的钱数

思路：

$dp[i]表示一共借款i个月的最大价值$

$假如我们有一个方案，那么这个方案得到的a_i的总和一样的情况下$

$我们希望将b_i大的借的月数较少，这样得到的钱数更多$

$可以先将b_i排序，再dp$

$每次可以将dp[i + 1] + dp[i] + 当前物品借i个月的价值$

$或者dp[i] 可以直接更新为加上当前月借满的状态$

$这样转移的时候就不用讨论i和k的大小关系$

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 #define ll long long
 5 #define N 510
 6 int n;
 7 struct node
 8 {
 9     ll a, b, k;
10     void scan() { scanf("%lld%lld%lld", &a, &b, &k); }
11     bool operator < (const node &other) const { return b > other.b; } 
12 }a[N];
13 ll dp[N];
14 
15 int main()
16 {
17     while (scanf("%d", &n) != EOF)
18     {
19         for (int i = 1; i <= n; ++i) a[i].scan();
20         sort(a + 1, a + 1 + n);
21         memset(dp, 0, sizeof dp);
22         for (int i = 1; i <= n; ++i) 
23         {
24             for (int j = n - 1; j >= 0; --j)
25             {
26                 dp[j + 1] = max(dp[j + 1], dp[j] + a[i].a - a[i].b * j);
27                 dp[j] = max(dp[j], dp[j] + a[i].a - a[i].b * a[i].k);
28             }
29         }
30         printf("%lld
", *max_element(dp, dp + 1 + n));
31     }
32     return 0;
33 }

View Code

G. Vasya and Maximum Profit

Upsolved.

题意：

有一些题目，可以选择连续的一段卖出去

设题目数为$x，则得到的利润为 a cdot x - sum c_i - max(d[i + 1] - d[i])^2$

思路：

用线段树维护右端点的答案，再从后往前移动左端点，在考虑在左边加入一个点的答案

对右端点的贡献的影响 $影响为 a - c[i]$

$max(d[i + 1] - d[i]) ^2 这部分的影响可以用单调栈维护某个区间的最大值是多少$

$因为每个值只会被操作两次，复杂度O(nlogn)$

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 
  4 #define ll long long
  5 #define N 300010
  6 #define INFLL 0x3f3f3f3f3f3f3f3f
  7 int n;
  8 ll a, c[N], d[N];
  9 ll val[N];
 10 struct node
 11 {
 12     ll v; int l, r;
 13     node () {}
 14     node (ll v, int l, int r) : v(v), l(l), r(r) {}
 15 };
 16 
 17 namespace SEG
 18 {
 19     struct node
 20     {
 21         ll lazy, Max;
 22         node () {}
 23         node (ll lazy, ll Max) : lazy(lazy), Max(Max) {}
 24         void init() { lazy = Max = 0; }
 25         void add(ll v)
 26         {
 27             lazy += v;
 28             Max += v;
 29         }
 30         node operator + (const node &other) const
 31         {
 32             node res; res.init();
 33             res.Max = max(Max, other.Max);
 34             return res;
 35         }
 36     }a[N << 2];
 37     void init() { memset(a, 0, sizeof a); }
 38     void pushdown(int id)
 39     {
 40         if (!a[id].lazy) return;
 41         a[id << 1].add(a[id].lazy);
 42         a[id << 1 | 1].add(a[id].lazy);
 43         a[id].lazy = 0;
 44     }
 45     void update(int id, int l, int r, int ql, int qr, ll v)
 46     {
 47         if (l >= ql && r <= qr)
 48         {
 49             a[id].add(v);
 50             return; 
 51         }
 52         int mid = (l + r) >> 1;
 53         pushdown(id);
 54         if (ql <= mid) update(id << 1, l, mid, ql, qr, v);
 55         if (qr > mid) update(id << 1 | 1, mid + 1, r, ql, qr, v);
 56         a[id] = a[id << 1] + a[id << 1 | 1];
 57     }
 58     ll query(int id, int l, int r, int ql, int qr)
 59     {
 60         if (l >= ql && r <= qr) return a[id].Max;
 61         int mid = (l + r) >> 1;
 62         pushdown(id);
 63         ll res = 0;
 64         if (ql <= mid) res = max(res, query(id << 1, l, mid, ql, qr));
 65         if (qr > mid) res = max(res, query(id << 1 | 1, mid + 1, r, ql, qr));
 66         return res;
 67     }
 68 }
 69 
 70 
 71 int main()
 72 {
 73     while (scanf("%d%lld", &n, &a) != EOF)
 74     {
 75         for (int i = 1; i <= n; ++i) scanf("%lld%lld", d + i, c + i); 
 76         for (int i = 2; i <= n; ++i) val[i] = (d[i] - d[i - 1]) * (d[i] - d[i - 1]); 
 77         SEG::init();
 78         stack <node> sta; 
 79         ll res = 0;
 80         for (int i = n; i >= 1; --i)
 81         {
 82             SEG::update(1, 1, n, i, n, a - c[i]); 
 83             if (i != n)
 84             {
 85                 node now = node(val[i + 1], i + 1, i + 1);     
 86                 while (!sta.empty())
 87                 {
 88                     node tmp = sta.top();
 89                     if (now.v >= tmp.v)
 90                     {
 91                         SEG::update(1, 1, n, tmp.l, tmp.r, tmp.v);
 92                         now.r = tmp.r;
 93                         sta.pop();
 94                     }
 95                     else
 96                         break;
 97                 }
 98                 SEG::update(1, 1, n, now.l, now.r, -now.v);
 99                 sta.push(now);
100             } 
101             res = max(res, SEG::query(1, 1, n, i, n));
102             sta.push(node(0, i, i));
103         }
104         printf("%lld
", res);
105     }
106     return 0;
107 }

View Code