Codeforces Round #560 (Div. 3)

传送门

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 2e5+5;
 4 int main() {
 5     int n, x, y; cin >> n >> x >> y;
 6     string s; cin >> s;
 7     reverse(s.begin(),s.end());
 8     int ans = 0;
 9     for (int i = 0; i < s.size(); ++i) {
10         if (i >= x) break;
11         if (i == y) {
12             if (s[i] == '0') ans++;
13         }
14         else {
15             if (s[i] == '1') ans++;
16         }
17     }
18     cout << ans << endl;
19     return 0;
20 }

A. Remainder

 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; cin >> n;
 7     for (int i = 1; i <= n; ++i) cin >> a[i];
 8     sort(a+1,a+1+n);
 9     int k = 1;
10     for (int i = 1; i <= n; ++i) {
11         if (a[i] >= k) k++;
12     }
13     cout << k-1 << endl;
14     return 0;
15 }

B. Polycarp Training

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main() {
 4     int n; cin >> n;
 5     string s; cin >> s;
 6     int len = s.size();
 7     string ans;
 8     for (int i = 0; i < len-1; i+=2) {
 9         if (s[i] == s[i+1]) {
10             int pos = i;
11             while (i < len-1 && s[pos] == s[i+1]) {
12                 s[i+1] = ' ';
13                 ++i;
14             }
15         }
16     }
17     for (int i = 0; i < len; ++i) {
18         if (s[i] == ' ') continue;
19         ans += s[i];
20     }
21     len = ans.size();
22     if (ans.size() % 2 == 1) len--;
23     cout << n-len << endl;
24     for (int i = 0; i < len; ++i) putchar(ans[i]);
25     putchar('\n');
26     return 0;
27 }

C. Good String

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 305;
 5 ll a[maxn];
 6 int main() {
 7     int t; cin >> t;
 8     while (t--) {
 9         int n; cin >> n;
10         for (int i = 1; i <= n; ++i) cin >> a[i];
11
12         sort(a+1,a+1+n);
13         ll ans = a[1]*a[n];
14         bool flag = true;
15         for (int i = 1; i <= n; ++i) {
16             if (ans % a[i] != 0) {
17                 flag = false;
18                 break;
19             }
20         }
21         if (flag == false) {
22             cout << -1 << endl;
23             continue;
24         }
25         ll cnt = 0; ll t = sqrt(ans);
26         for (int i = 2; i <= t; ++i) {
27             if (ans % i == 0) cnt++;
28         }
29         cnt *= 2;
30         if (t*t == ans) cnt--;
31         if (cnt != n) cout << -1 << endl;
32         else cout << ans << endl;
33     }
34     return 0;
35 }

D. Almost All Divisors

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 2e5+5;
 5 const int mod = 998244353;
 6 ll a[maxn], b[maxn];
 7 int main() {
 8     int n; cin >> n;
 9     for (int i = 1; i <= n; ++i) cin >> a[i];
10     for (int i = 1; i <= n; ++i) cin >> b[i];
11     for (int i = 1; i <= n; ++i) a[i] = (ll)(n-i+1)*i*a[i];
12     sort(a+1,a+1+n,greater<ll>() );
13     sort(b+1,b+1+n,less<ll>() );
14     ll ans = 0;
15     for (int i = 1; i <= n; ++i) {
16         ans = (ans + ((a[i]%mod) * (b[i]%mod))%mod)%mod;
17     }
18     cout << ans << endl;
19     return 0;
20 }

E. Two Arrays and Sum of Functions

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 2e5+5;
 5 const int inf = 0x3f3f3f3f;
 6 struct node {
 7     int d, t;
 8 }nds[maxn];
 9 int a[maxn], b[maxn];
10 int n, m, sum;
11 bool cmp(node x, node y) {
12     return x.d == y.d ? x.t < y.t : x.d < y.d;
13 }
14 bool check(int x) {
15     int res = sum;
16     int now = x;
17     int unused = 0;
18     for (int i = 0; i < n; ++i) b[i] = 0;
19     int i;
20     for (i = m-1; i >= 0; --i) {
21         if (now >= nds[i].d) break;
22     }
23     for (; i >= 0; --i) {
24         if (now == 0) break;
25         int d = min(now,nds[i].d);
26         unused += now-d;
27         now = d;
28         if (b[nds[i].t-1] != a[nds[i].t-1]) {
29             int consump = min(d,a[nds[i].t-1]-b[nds[i].t-1]);
30             res -= consump;
31             b[nds[i].t-1] += consump;
32             now -= consump;
33         }
34     }
35     if (now != 0) {
36         unused += now;
37     }
38     return res-unused/2 <= 0;
39 }
40 int main() {
41     cin >> n >> m;
42     for (int i = 0; i < n; ++i) {
43         cin >> a[i];
44         sum += a[i];
45     }
46     for (int i = 0; i < m; ++i) {
47         cin >> nds[i].d >> nds[i].t;
48     }
49     sort(nds,nds+m,cmp);
50     int l = 1, r = inf;
51     while (l <= r) {
52         int mid = (l+r)/2;
53         if (check(mid)) r = mid-1;
54         else l = mid+1;
55     }
56     if (!check(r)) r++;
57     cout << r << endl;
58     return 0;
59 }

F1. Microtransactions (easy version)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 2e5+5;
 5 const int inf = 0x3f3f3f3f;
 6 struct node {
 7     int d, t;
 8 }nds[maxn];
 9 int a[maxn], b[maxn];
10 int n, m, sum;
11 bool cmp(node x, node y) {
12     return x.d == y.d ? x.t < y.t : x.d < y.d;
13 }
14 bool check(int x) {
15     int res = sum;
16     int now = x;
17     int unused = 0;
18     for (int i = 0; i < n; ++i) b[i] = 0;
19     int i;
20     for (i = m-1; i >= 0; --i) {
21         if (now >= nds[i].d) break;
22     }
23     for (; i >= 0; --i) {
24         if (now == 0) break;
25         int d = min(now,nds[i].d);
26         unused += now-d;
27         now = d;
28         if (b[nds[i].t-1] != a[nds[i].t-1]) {
29             int consump = min(d,a[nds[i].t-1]-b[nds[i].t-1]);
30             res -= consump;
31             b[nds[i].t-1] += consump;
32             now -= consump;
33         }
34     }
35     if (now != 0) {
36         unused += now;
37     }
38     return res-unused/2 <= 0;
39 }
40 int main() {
41     cin >> n >> m;
42     for (int i = 0; i < n; ++i) {
43         cin >> a[i];
44         sum += a[i];
45     }
46     for (int i = 0; i < m; ++i) {
47         cin >> nds[i].d >> nds[i].t;
48     }
49     sort(nds,nds+m,cmp);
50     int l = 1, r = inf;
51     while (l <= r) {
52         int mid = (l+r)/2;
53         if (check(mid)) r = mid-1;
54         else l = mid+1;
55     }
56     if (!check(r)) r++;
57     cout << r << endl;
58     return 0;
59 }

F2. Microtransactions (hard version)