Codeforces Round #653 (Div. 3)
A.Required Remainder
题意:
给定,要求找到最大的,使得
题解:
先算出的值,如果,就减去
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { ll x, y, n; scanf("%lld%lld%lld", &x, &y, &n); ll ans = n / x * x + y; if (ans > n) ans -= x; printf("%lld\n", ans); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
B.Multiply by 2, divide by 6
题意:
给定一个,询问能否通过不断地乘或除得到。
题解:
对每次判断能否除,能则答案,再判断能否除,能则答案,直到两者都不能发生,判断最终能否等于即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { ll n; scanf("%lld", &n); int cnt = 0; while (n % 3 == 0) { if (n % 6 == 0) { n /= 6; cnt++; } else { n /= 3; cnt += 2; } } printf("%d\n", n == 1 ? cnt : -1); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
C.Move Brackets
题意:
给定一个长度为的括号序列,保证为偶数,且左括号与右括号数量相等。每次操作可以将任意一个括号移至首部和尾部,询问最少通过几次操作可以使得真个序列合法。
题解:
将左括号计为,右括号计为,遍历序列,当遇到时,答案加上即可,相当于每次把多出来的右括号都放到最后,最终最能构成合法序列
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; void solve() { int n; scanf("%d", &n); string s; cin >> s; int cnt = 0, ans = 0; for (int i = 0; i < n; i++) { if (s[i] == '(' && cnt < 0) { ans -= cnt; cnt = 1; continue; } if (s[i] == '(') cnt++; else cnt--; } printf("%d\n", ans); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
D.Zero Remainder Array
题意:
给定一个长度为的数组与一个数,有一个数,初始为。有两种操作:
- ,其中
询问最少操作次数使得
题解:
遍历序列,对每个数都,并分成份,最终答案就是,其中为出现次数最多的那个数出现次数,就是出现次数最多的那个最大的数。要特判均为的情况即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e5 + 5; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; map<ll, int> mp; void solve() { mp.clear(); ll n, k; scanf("%lld%lld", &n, &k); ll mx = 0, idx = -1; int flag = 0; for (ll i = 0, x; i < n; i++) { scanf("%lld", &x); x %= k; mp[x]++; if (x) flag = 1; else continue; if (mx < mp[x]) mx = mp[x], idx = k - x; else if (mx == mp[x] && k - x > idx) idx = k - x; } if (flag) printf("%lld\n", (mx - 1) * k + idx + 1); else puts("0"); } int main() { int t; for (scanf("%d", &t); t >= 1; t--) solve(); }
E1.Reading Books (easy version)
题意:
给本书,阅读第本数需要花费的时间,表示Alice是否喜欢该书,表示Bob是否喜欢该书。询问两个人都至少要读本自己喜欢的书所要花费的最短时间,如果选定的书两人都喜欢,那么只会花费的时间,两人读的书数均加一
题解:
将书分为Alice和Bob都喜欢,只有Alice喜欢和只有Bob喜欢三类,先将只有Alice喜欢和只有Bob喜欢的分别排序,将它们两两组合加入到Alice和Bob都喜欢的那组中,整体排序,如果不满个则无解,否则前个相加即为答案
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 10; int A[maxn], B[maxn], sum[maxn]; int main() { int k, n; scanf("%d%d", &n, &k); int cnt = 0, cnta = 0, cntb = 0; for (int i = 0; i < n; ++i) { int t, a, b; scanf("%d%d%d", &t, &a, &b); if (a && b) sum[cnt++] = t; else if (a) A[cnta++] = t; else if (b) B[cntb++] = t; } sort(A, A + cnta); sort(B, B + cntb); for (int i = 0; i < min(cnta, cntb); ++i) sum[cnt++] = (A[i] + B[i]); if (cnt < k) { puts("-1"); return 0; } sort(sum, sum + cnt); ll ans = 0; for (int i = 0; i < k; ++i) ans += sum[i]; printf("%lld\n", ans); }