Codeforces Round #555 (Div. 3)

传送门

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 set<int> se;
 4 int f(int x) {
 5     x += 1;
 6     while (x % 10 == 0 && x) x /= 10;
 7     return x;
 8 }
 9 int main() {
10     int n; scanf("%d",&n);
11
12     int x = n;
13     while (!se.count(x)) {
14         se.insert(x);
15         x = f(x);
16     }
17     printf("%d\n",se.size());
18     return 0;
19 }

A. Reachable Numbers

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int f[10], s[200005];
 4 char a[200005];
 5 int main() {
 6     int n; scanf("%d",&n);
 7     scanf("%s",a+1);
 8     for (int i = 1; i <= n; ++i) s[i] = a[i] - '0';
 9     for (int i = 1; i <= 9; ++i) scanf("%d",&f[i]);
10
11     bool flag = false;
12     for (int i = 1; i <= n; ++i) {
13         if (f[s[i]] > s[i]) {
14             s[i] = f[s[i]];
15             flag = true;
16         }
17         else if (f[s[i]] < s[i]) {
18             if (flag == true) break;
19         }
20     }
21     for (int i = 1; i <= n; ++i) printf("%d",s[i]);
22     printf("\n");
23     return 0;
24 }

B. Long Number

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 2e5+5;
 4 int a[maxn];
 5 int main() {
 6     int n; scanf("%d",&n);
 7     for (int i = 1; i <= n; ++i) scanf("%d",&a[i]);
 8     int i = 1, j = n;
 9
10     string ans;
11     int now = min(a[i],a[j]);
12     if (a[i] == now) ans += 'L', i++;
13     else ans += 'R', j--;
14     while (i <= j) {
15         if (now < a[i] && now < a[j]) {
16             if (a[i] < a[j]) now = a[i], ans += 'L', i++;
17             else now = a[j], ans += 'R', j--;
18         }
19         else if (a[j] < now && now < a[i]) {
20             now = a[i], ans += 'L', i++;
21         }
22         else if (a[i] < now && now < a[j]) {
23             now = a[j], ans += 'R', j--;
24         }
25         else break;
26     }
27     printf("%d\n",ans.size());
28     printf("%s\n",ans.c_str());
29     return 0;
30 }

C1. Increasing Subsequence (easy version)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 2e5+5;
 4 int a[maxn];
 5 int main() {
 6     int n; scanf("%d",&n);
 7     for (int i = 1; i <= n; ++i) scanf("%d",&a[i]);
 8
 9     int i = 1, j = n;
10     string ans;
11     int now = -1;
12     while (i <= j) {
13         if (now < a[i] && now < a[j]) {
14             if (a[i] < a[j]) now = a[i], ans += 'L', i++;
15             else if (a[i] > a[j]) now = a[j], ans += 'R', j--;
16             else {
17                 string temp1; temp1 += 'L';
18                 for (int x = i+1; x <= j; x++) {
19                     if (a[x-1] >= a[x]) break;
20                     temp1 += 'L';
21                 }
22                 string temp2; temp2 += 'R';
23                 for (int x = j-1; x >= i; x--) {
24                     if (a[x+1] >= a[x]) break;
25                     temp2 += 'R';
26                 }
27                 if (temp1.size() > temp2.size()) ans += temp1;
28                 else ans += temp2;
29                 break;
30             }
31         }
32         else if (a[j] <= now && now < a[i]) {
33             now = a[i], ans += 'L', i++;
34         }
35         else if (a[i] <= now && now < a[j]) {
36             now = a[j], ans += 'R', j--;
37         }
38         else break;
39     }
40     printf("%d\n",ans.size());
41     printf("%s\n",ans.c_str());
42     return 0;
43 }

C2. Increasing Subsequence (hard version)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1e5+5;
 5 ll a[maxn];
 6 int main() {
 7     ll n, k; scanf("%lld%lld",&n,&k);
 8     ll mi = (k+1)*k/2;
 9     if (n < mi) {
10         puts("NO");
11         return 0;
12     }
13     n -= mi;
14     ll temp = n/k;
15     for (int i = 1; i <= k; ++i) {
16         a[i] = i+temp;
17     }
18     n %= k;
19     for (int i = k; i >= 1 && n; --i) {
20         temp = min(n,a[i-1]*2-a[i]);
21         if (temp<0) temp = 0;
22         a[i] += temp;
23         n -= temp;
24     }
25     if (n > 0) puts("NO");
26     else {
27         puts("YES");
28         printf("%d",a[1]);
29         for (int i = 2; i <= k; ++i) {
30             printf(" %d",a[i]);
31         }
32         printf("\n");
33     }
34     return 0;
35 }

D. N Problems During K Days

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 2e5+5;
 5 int a[maxn];
 6 vector<int> b, c;
 7 char buf[70000000]; int cnt = 0;
 8 template<typename T> inline T read(T a) {
 9     T res = 0, f = 1;
10     char ch = buf[cnt++];
11     while (!isdigit(ch)) {
12         if (ch == '-') f = -1;
13         ch = buf[cnt++];
14     }
15     while (isdigit(ch)) {
16         res = (res<<3)+(res<<1) + ch - 48;
17         ch = buf[cnt++];
18     }
19     return res*f;
20 }
21 int main() {
22     fread(buf,1,70000000,stdin);
23     int n; n = read(n);
24     for (int i = 0; i < n; ++i) {
25         a[i] = read(a[i]);
26     }
27     for (int i = 0; i < n; ++i) {
28         int x; b.push_back(read(x));
29     }
30     sort(b.begin(),b.end());
31     for (int i = 0; i < n; ++i) {
32         int tmp = n-a[i];
33         auto iter = lower_bound(b.begin(),b.end(),tmp);
34         if (iter == b.end()) {
35             c.push_back((a[i]+b[0])%n);
36             b.erase(b.begin(),b.begin()+1);
37         }
38         else {
39             c.push_back((a[i]+(*iter))%n);
40             b.erase(iter,iter+1);
41         }
42     }
43     printf("%d",c[0]);
44     for (int i = 1; i < c.size(); ++i) {
45         printf(" %d",c[i]);
46     }
47     printf("\n");
48     return 0;
49 }

E. Minimum Array

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 2e5+5;
 4 int a[maxn];
 5 map<int,int> mp;
 6 int main() {
 7     int n; scanf("%d",&n);
 8     for (int i = 1; i <= n; ++i) {
 9         scanf("%d",&a[i]);
10         mp[a[i]]++;
11     }
12     sort(a+1,a+1+n);
13     int m = unique(a+1,a+1+n)-a-1;
14
15     int ans = mp[a[1]], l = 1, r = 1;
16     for (int i = 1, j; i <= m; i = j) {
17         j = i+1;
18         int sum = mp[a[i]];
19         while (j <= m && a[j]-a[j-1] == 1 && mp[a[j]] >= 2) sum += mp[a[j]], j++;
20         int tmp = j-1;
21         if (j <= m && a[j]-a[j-1] == 1) sum += mp[a[j]], tmp = j;
22         if (sum > ans) ans = sum, l = i, r = tmp;
23     }
24
25     printf("%d\n",ans);
26     for (int i = 1; i <= mp[a[l]]; ++i) printf("%d ",a[l]);
27     for (int i = l+1; i < r; ++i) for (int j = 1; j < mp[a[i]]; ++j) printf("%d ",a[i]);
28     if (l != r) for (int i = 1; i <= mp[a[r]]; ++i) printf("%d ",a[r]);
29     for (int i = r-1; i >= l+1; --i) printf("%d ",a[i]);
30     putchar('\n');
31     return 0;
32 }

F. Maximum Balanced Circle

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 205;
 4 int mat[maxn][maxn], tmp[maxn][maxn];
 5 int r[maxn], c[maxn];
 6 int n, m;
 7 void invRow(int row) {
 8     for (int j = 1; j <= m; ++j) {
 9         tmp[row][j] ^= 1;
10     }
11 }
12 void invCol(int col) {
13     for (int i = 1; i <= n; ++i) {
14         tmp[i][col] ^= 1;
15     }
16 }
17 bool solve(int x, int y) {
18     memset(tmp,0,sizeof(tmp));
19     memset(r,0,sizeof(r));
20     memset(c,0,sizeof(c));
21     for (int i = x; i <= n; ++i) {
22         for (int j = 1; j <= m; ++j) {
23             if (i == x && j < y) tmp[i][j] = 0;
24             else tmp[i][j] = 1;
25         }
26     }
27     for (int i = 1; i <= n; ++i)
28         r[i] = mat[i][1]^tmp[i][1]^c[1];
29     for (int j = 1; j <= m; ++j)
30         c[j] = mat[1][j]^tmp[1][j]^r[1];
31     for (int i = 1; i <= n; ++i) {
32         for (int j = 1; j <= m; ++j) {
33             if ((r[i]^c[j]) != (mat[i][j]^tmp[i][j])) return false;
34         }
35     }
36     return true;
37 }
38 int main() {
39     scanf("%d%d",&n,&m);
40     for (int i = 1; i <= n; ++i) {
41         for (int j = 1; j <= m; ++j) {
42             scanf("%d",&mat[i][j]);
43         }
44     }
45     for (int i = 1; i <= n; ++i) {
46         for (int j = 1; j <= m; ++j) {
47             if (solve(i,j)) {
48                 puts("YES");
49                 for (int i = 1; i <= n; ++i) printf("%d",r[i]);
50                 putchar('\n');
51                 for (int j = 1; j <= m; ++j) printf("%d",c[j]);
52                 putchar('\n');
53                 return 0;
54             }
55         }
56     }
57     puts("NO");
58     return 0;
59 }

G. Inverse of Rows and Columns