文章目录

A - Required Remainder [思维]B - Multiply by 2, divide by 6 [思维]C - Move Brackets [思维]D - Zero Remainder Array [思维]E1 - Reading Books (easy version) [排序]E2 - Reading Books (hard version) [三分]F - Cyclic Shifts Sorting [找规律]

---

---

比赛首页 标准题解

A - Required Remainder [思维]

目录 题目传送门

Time Limit Per TestMemory Limit Per Testinputoutput1 seconds256 megabytesstandard inputstandard output

题意

求数 $k$ 满足 $k=t\ast x+y$ $\&\&$ $0<=k<=n$，满足条件的最大 $k$ 保证这样的 $k$ 都存在

分析

令 $k=n/x\ast x+y$，可以得到最接近的所求数 但如果大于 $n$ 则需再 $-y$，否则即为答案

Code

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100 + 5; int main() { int T; scanf("%d", &T); while(T--) { ll x, y, n; scanf("%lld%lld%lld", &x, &y, &n); ll t = n / x * x + y; if(t > n) t -= x; printf("%lld\n", t); } return 0; }

---

B - Multiply by 2, divide by 6 [思维]

目录 题目传送门

Time Limit Per TestMemory Limit Per Testinputoutput1 seconds256 megabytesstandard inputstandard output

题意

给定数 $n$，每次的操作可以选择

$n$ 满足 $n\%6==0$ 时，$n=n÷6$$n=n\ast 2$

要用尽可能少的次数使得 $n$ 最终变为 $1$ 问至少需要几次，如果不可能输出 $-1$

分析

每次除以 $6$ 相当于 $÷3÷2$ 要使得最后得到 $1$，则 $n$ 应该只有因数 $2,3$；且 $2$ 的个数必须 $<=3$

Code

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100 + 5; int main() { int T; scanf("%d", &T); while(T--) { int n, n1 = 0, n2 = 0; scanf("%d", &n); while(n % 3 == 0) n1 += 1, n /= 3; while(n % 2 == 0) n2 += 1, n /= 2; if(n != 1 || n1 < n2) puts("-1"); else{ printf("%d\n", n1 * 2 - n2); } } return 0; }

---

C - Move Brackets [思维]

目录 题目传送门

Time Limit Per TestMemory Limit Per Testinputoutput1 seconds256 megabytesstandard inputstandard output

题意

一个串仅包含 ‘(’, ‘)’ 任意位置的字符可以调换到串首或者串尾，求得到合法字符串最少移动次数 合法字符串例如： ‘()’, ‘(())’, ‘()()’

分析

（这题出过好几次） 不合法的时候都会出现这样的情况 ‘))(’ 因此只要记录右括号剩余的个数即可

Code

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 50 + 5; char s[maxn]; int main() { int T; scanf("%d", &T); while(T--) { int n, l = 0, k = 0; scanf("%d%s", &n, s + 1); for(int i = 1; i <= n; ++i) { if(s[i] == '(') l += 1, s[++k] = '('; else if(l) l -= 1, k -= 1; else s[++k] = ')'; } printf("%d\n", k ? k / 2 : 0); } return 0; }

---

D - Zero Remainder Array [思维]

目录 题目传送门

Time Limit Per TestMemory Limit Per Testinputoutput2 seconds256 megabytesstandard inputstandard output

题意

一个长度为 $n$ 的数组 现在有一个 $x$，$x$ 每次可以增加 $1$ 现在要使这个长度为 $n$ 的数组每个元素 $\%k==0$ 每次的 $x$，可以选择一个位置上的元素进行相加或者不选择相加 每个位置上的元素最多仅能加一次 问至少 $x$ 为几时满足条件。

分析

统计 $k-a[i]\%k$ 的个数，如果 $a[i]\%k==0$ 则不需要统计。 最后需要计算的是 取模后的值的个数最多的，如果有同样多的就选择取模后的值最大的。 $cnt[pos]-1)\ast k+pos$ 即最终所要求的结果 这里统计个数需要用 $map$，因为 $k$ 的取值范围较大

Code

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e4 + 5; map<int, int> cnt; int main() { int T; scanf("%d", &T); while(T--) { int n, x, k; scanf("%d%d", &n, &k); int pos = 0; cnt.clear(); for(int i = 1; i <= n; ++i) { scanf("%d", &x); if(x % k == 0) continue; x = k - x % k; cnt[x] += 1; if(cnt[x] > cnt[pos] || cnt[x] == cnt[pos] && x > pos) { pos = x; } } printf("%lld\n", pos ? (cnt[pos] - 1) * 1ll * k * 1ll + pos * 1ll + 1ll : 0); } return 0; }

---

E1 - Reading Books (easy version) [排序]

目录 题目传送门

Time Limit Per TestMemory Limit Per Testinputoutput2 seconds256 megabytesstandard inputstandard output

题意

总共有 $n$ 本书，Alice 和 Bob 一起读书 第 $i$ 本书需要 $t_i$ 的时间读完； $a_i$ 为 $1$ 表示 Alice 对这本书有兴趣； $b_i$ 为 $1$ 表示 Bob 对这本书有兴趣； 选择其中几本书，使得 Alice 和 Bob 至少都有每个人都有 $k$ 本有兴趣的书且花费的阅读时间最少

分析

可以知道最终选的书应该是 $k$ 本 Alice 有兴趣的，$k$ 本Bob 有兴趣的。 可以将书进行分类，其中两人都有兴趣的书为一类 否则就将剩余的书分别进行排序（Alice和Bob的），二合一加入两人都有兴趣的数组中 选择前 $k$ 小的 $t_i$ 最后将总的进行排序 那么没有结果的情况是 两人都有兴趣的书 + min(Alice剩下有兴趣的书, Bob剩下有兴趣的书) < k 不存在结果输出-1

Code

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e5 + 5; int a[maxn], b[maxn], c[maxn]; int main() { int n, k, t, at, bt; scanf("%d%d", &n, &k); int an, bn, cn; an = bn = cn = 0; for(int i = 1; i <= n; ++i) { scanf("%d%d%d", &t, &at, &bt); if(at & bt == 1) c[cn++] = t; else if(at) a[an++] = t; else if(bt) b[bn++] = t; } if(cn + min(an, bn) < k) { puts("-1"); }else{ ll ans = 0; sort(a, a + an); sort(b, b + bn); for(int i = 0; i < an && i < bn; ++i) c[cn++] = a[i] + b[i]; sort(c, c + cn); while(k--) ans += c[k] * 1ll; printf("%lld\n", ans); } return 0; }

---

E2 - Reading Books (hard version) [三分]

目录 题目传送门 参考博客

Time Limit Per TestMemory Limit Per Testinputoutput2 seconds256 megabytesstandard inputstandard output

题意

与E1差不多，区别在于多了 $m$，表示一定要取 $m$ 本书，且满足上述条件

分析 错误解法

本来是沿用上一个的方式，选择完前 $k$ 小的后，这选择了 $cnt$ 本书 若 $cnt>k$，则将两本书两人各一个有兴趣的取出，在放一个两人都有兴趣的书 当然是前者是选择较大的 $t_i$，后者是选择较小的 $t_i$ 若 $cnt<=k$，则将没选择的书进行排序，选取 $t_i$ 较小的剩下的书 没有结果的情况是：(两人都有兴趣的书数目 > m || 两人都有兴趣的书数目 + 两人分别有兴趣的不同的书数目 < k) orz不行啊，我觉得挺正确的来着啊

正确解法

可以发现其决定性因素的是两人共同有兴趣的书选择的数目。 确定这个之后，其余的最优选择就可以决定。 首先选取满足每人有兴趣的书达到 $k$ 本，再选择全没选过的书（从小到大排序） 由于选择两人共同有兴趣的书选择的数目满足三分的性质（为什么呢小编也很疑惑，有知道的大佬可以跟我说一下吗 _(:з」∠)_） 所以可以采用三分的做法。 最后得到一段较小的区间，比较区间内每种情况的值。 翻了cf的AC代码，发现很多是用线段树和树状数组进行维护的 不太理解，_(:з」∠)_在线等大佬题解

Code

#include <bits/stdc++.h> #define min(a, b) ((a) < (b) ? (a) : (b)) #define max(a, b) ((a) < (b) ? (b) : (a)) #define pii pair<int, int> #define fi first #define se second using namespace std; typedef long long ll; const ll INF = 1e18; const int inf = 2e9 + 1; const int maxn = 2e5 + 5; vector<pii> v[4]; vector<pii> vv; vector<int> ans; int n, m, k; int judge(int x) { if((int)v[1].size() + x < k) return inf; if((int)v[2].size() + x < k) return inf; if(max(0, k - x) * 2 + x > m) return inf; ans.clear(), vv.clear(); int res = 0, cnt = m - x; for(int i = 0; i < x; ++i) { res += v[3][i].fi; ans.push_back(v[3][i].se); } int y = max(0, k - x); for(int i = 0; i < y; ++i) { res += v[1][i].fi + v[2][i].fi, cnt -= 2; ans.push_back(v[1][i].se), ans.push_back(v[2][i].se); } for(int i = x; i < (int)v[3].size(); ++i) vv.push_back(v[3][i]); for(int i = 0; i < 3; ++i) { for(int j = i ? y : 0; j < (int)v[i].size(); ++j) vv.push_back(v[i][j]); } sort(vv.begin(), vv.end()); for(int i = 0; i < cnt; ++i) { res += vv[i].fi; ans.push_back(vv[i].se); } return res; } int solve() { for(int i = 0; i < 4; ++i) sort(v[i].begin(), v[i].end()); int l = 0, r = min(m, v[3].size()); while(r - l > 10) { int lmid = l + (r - l) / 3, rmid = r - (r - l) / 3; if(judge(lmid) >= judge(rmid)) l = lmid; else r = rmid; } int res = inf, y, t = -1; for(int i = l; i <= r; ++i) { y = judge(i); if(y < res) res = y, t = i; } return t; } int main() { int t, at, bt; scanf("%d%d%d", &n, &m, &k); for(int i = 0; i < 4; ++i) v[i].clear(); for(int i = 1; i <= n; ++i) { scanf("%d%d%d", &t, &at, &bt); v[(at << 1) | bt].push_back(make_pair(t, i)); } t = solve(); if(t == -1) puts("-1"); else{ int res = judge(t); printf("%d\n", res); for(int i = 0; i < m; ++i) printf("%d%c", ans[i], i + 1 == m ? '\n' : ' '); } return 0; }

---

F - Cyclic Shifts Sorting [找规律]

目录 题目传送门 参考博客

Time Limit Per TestMemory Limit Per Testinputoutput2 seconds256 megabytesstandard inputstandard output

题意 真要说大概是找规律题？ 详细见上述参考博客，感觉写的很详细了

Code

#include <bits/stdc++.h> #define min(a, b) ((a) < (b) ? (a) : (b)) #define max(a, b) ((a) < (b) ? (b) : (a)) #define pii pair<int, int> #define fi first #define se second using namespace std; typedef long long ll; const ll INF = 1e18; const int inf = 2e9 + 1; const int maxn = 2e5 + 5; int a[maxn], b[maxn]; void move(int i) { int a1 = a[i], a2 = a[i + 1], a3 = a[i + 2]; a[i] = a3, a[i + 1] = a1, a[i + 2] = a2; } int main() { int T; scanf("%d", &T); while(T--) { int n, k = 0; scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); for(int i = 0; i <= n - 2; ++i) { int minn = inf, pos = 0; for(int j = i; j <= n; ++j) { if(minn > a[j]) minn = a[j], pos = j; } // printf("\#1 %d %d\n", minn, pos); while(pos >= i + 2) pos -= 2, move(pos), b[k++] = pos; if(pos == i + 1) move(i), move(i), b[k++] = i, b[k++] = i; } // puts("test 1"); // for(int i = 1; i <= n; ++i) // printf("%d%c", a[i], i == n ? '\n' : ' '); for(int i = n; i >= 3; --i) { int maxx = 0, pos = 0; for(int j = i; j >= 1; --j) { if(maxx < a[j]) maxx = a[j], pos = j; } while(pos <= i - 2) move(pos), b[k++] = pos, pos += 2; if(pos == i - 1) move(pos - 1), b[k++] = pos - 1; } // puts("test 2"); // for(int i = 1; i <= n; ++i) // printf("%d%c", a[i], i == n ? '\n' : ' '); bool f = true; for(int i = 1; i < n; ++i) if(a[i] > a[i + 1]) f = false; if(f) { printf("%d\n", k); for(int i = 0; i < k; ++i) printf("%d%c", b[i], i + 1 == k ? '\n' : ' '); }else{ puts("-1"); } // puts(""); } return 0; }

---