Xueyang Liu

CodeForces 1606C Banknotes

Banknotes 转化为求最小的 $s$，使得 $f(s) = k + 1$，也就是用 $k + 1$ 个硬币组合成尽量小的值 $s$，同时满足 $s$ 不能用更少的硬币组成。考虑贪心，为了让 $s$ 尽量小，需要尽量多地使用小面值的硬币，但是又不能全部使用小面值（因为这会让求得的 $s$ 可以用比 $k + 1$ 还少的硬币组成），考虑小面值的硬币最多可以使用多少个，对于面值为 $a_i$ 的硬币，它最多能够使用的次数是 $\frac{a_{i+1}}{a_i}-1$，特殊情况 $a_n$ 可以使用任意多次。 // Date: Fri Jan 19 22:18:45 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 20; ll a[N], b[N]; void solve() { ll n, k; cin >> n >> k; For1(i, 1, n) { int x; cin >> x; ll t = 1; while (x--) t *= 10; a[i] = t; } For1(i, 1, n - 1) { b[i] = a[i + 1] / a[i] - 1; } ll ans = 0; ++k; For1(i, 1, n - 1) { if (k <= b[i]) { ans += k * a[i]; k = 0; break; } ans += b[i] * a[i]; k -= b[i]; } if (k) { ans += k * a[n]; } cout << ans << '\n'; } int main(void) { #ifdef _DEBUG freopen("1606c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

CodeForces 1605C Dominant Character

Dominant Character 挺有意思的一道贪心题目。官方题解就挺好的，具体就是观察得到有限的符合题意的字符串，发现长度不超过 $7$，所以检查所有长度不大于 $7$ 的子字符串即可。 // Date: Wed Jan 17 22:44:56 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif int n; string s; void solve() { cin >> n >> s; int ca{}, cb{}, cc{}, res = INF; For(i, 0, n) { int k = min(n, i + 7); ca = cb = cc = 0; For(j, i, k) { if (s[j] == 'a') ca++; else if (s[j] == 'b') cb++; else cc++; if (ca >= 2 && ca > cb && ca > cc) { int tmp = j - i + 1; ckmin(res, tmp); } } } if (res == INF) res = -1; cout << res << '\n'; } int main(void) { #ifdef _DEBUG freopen("1605c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

CodeForces 1579D Productive Meeting

Productive Meeting 经典的贪心问题，和电池例题一样。唯一的区别是需要输出方案。证明方法见 CF1649B，按照证明中的步骤模拟输出方案即可。简单说就是当 $mx < sum - mx$ 的时候，先在 $sum - mx$ 内部构造方案，一直到 $mx \ge sum - mx$，此时就是简单情况了。 // Date: Wed Jan 17 22:07:09 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 200100; using PLL = pair<ll, ll>; ll n, a[N]; void solve() { cin >> n; ll sum = 0, mx = -1; For1(i, 1, n) { cin >> a[i]; sum += a[i]; ckmax(mx, a[i]); } vector<PLL> b; PLL mxp{-1, -1}; For1(i, 1, n) { if (a[i]) { if (a[i] == mx && mxp.f1 == -1) { mxp = {a[i], i}; } else { b.pb({a[i], i}); } } } sort(all(b)); vector<PII> res; if (mx < sum - mx) { ll rem = sum - mx; while (rem > mx) { int len = SZ(b); for (int i = 0, j = len - 1; rem > mx && i <= j;) { while (i <= j && b[i].f1 == 0) { ++i; } while (i <= j && b[j].f1 == 0) j--; if (i > j) break; while (rem > mx && b[i].f1 > 0 && b[j].f1 > 0) { res.pb({b[i].f2, b[j].f2}); rem -= 2; b[i].f1--; b[j].f1--; } } } } for (auto &[cnt, i] : b) { while (cnt--) { res.pb({i, mxp.f2}); } } cout << SZ(res) << '\n'; for (auto &[x, y] : res) { cout << x << ' ' << y << '\n'; } } int main(void) { #ifdef _DEBUG freopen("1579d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

CodeForces 1559D1 Mocha and Diana (Easy Version)

Mocha and Diana (Easy Version) 一个连通块中的两个点之间不能添加边，所以想到使用并查集维护集合。设第一个人为 $A$，第二个人是 $B$，那么 $A$ 中的两个点 $x, y$ 能够相连的条件是 $B$ 中的 $x, y$ 不在一个连通块中。如果在 $x, y$ 之间添加边，此时 $A, B$ 中的连通块数量都减少 $1$，当 $B$ 的连通块数量是 $1$ 的时候，就不能再添加边了。对于 $x, y$ 来说，其实换成对应的连通块中的其它符合条件的两个点都可以，它们是等价的，最终效果都一样。最终局面是 $B$ 只有一个连通块，$A$ 的连通块至少有一个。因此检查 $A$ 中的所有点对，能连的就放到答案中即可。 // Date: Wed Jan 17 19:55:47 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 1100; int f[2][N], sz[2][N], n, m1, m2; void Init() { For1(i, 1, n) { f[0][i] = f[1][i] = i; sz[0][i] = sz[1][i] = 1; } } int Find(int i, int x) { if (f[i][x] == x) return x; return f[i][x] = Find(i, f[i][x]); } void Union(int i, int x, int y) { int rx = Find(i, x), ry = Find(i, y); if (rx == ry) return; f[i][ry] = rx; } void solve() { while (cin >> n >> m1 >> m2) { int u, v; Init(); For(i, 0, m1) { cin >> u >> v; Union(0, u, v); } For(i, 0, m2) { cin >> u >> v; Union(1, u, v); } vector<PII> res; For1(i, 1, n) { For1(j, i + 1, n) { int ri = Find(0, i), rj = Find(0, j); if (ri != rj) { int ri1 = Find(1, i), rj1 = Find(1, j); if (ri1 != rj1) { res.pb({i, j}); Union(1, i, j); Union(0, i, j); } } } } int len = SZ(res); cout << len << '\n'; if (len) { for (auto &[x, y] : res) { cout << x << ' ' << y << '\n'; } } } } int main(void) { #ifdef _DEBUG freopen("1559d1.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; while (T--) { solve(); } return 0; }

CodeForces 1553D Backspace

Backspace 观察到一次删除操作需要从原字符串中删除连续的两个字符，如果 $s_i$ 在 $t$ 中不存在，那么删除的可能是 $s_i, s_{i + 1}$ 或者 $s_{i - 1}, s_i$。其实如果从后往前考虑会更简单，如果 $s_n \ne t_m$，只能删除 $s_{n - 1}, s_{n}$；如果 $s_n$ 恰好等于$t_{m - 1}$，那么让它们两个匹配不会让结果更差。 // Date: Wed Jan 17 19:13:03 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif void solve() { string s, t; cin >> s >> t; int n = SZ(s), m = SZ(t); int j = m - 1; Rof(i, 0, n) { if (s[i] == t[j]) { --j; if (j == -1) break; } else { --i; } } if (j == -1) cout << "YES"; else cout << "NO"; cout << '\n'; } int main(void) { #ifdef _DEBUG freopen("1553d.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

CodeForces 1552B Running for Gold

Running for Gold 注意到题目给定的关系的性质：只有两种情况 $a > b$ 或者 $b > a$。所有人中只有一个人强于所有人，假设最终答案是 $cur$，当前比较的人是 $i$，如果 $cur > i$，那么 $i$ 不可能是答案；如果 $cur < i$，那么 $cur$ 不可能是答案，把 $cur$ 更新成 $i$，最终得到的 $cur$ 可能是答案，再到原数组中验证一遍。 // Date: Tue Jan 16 23:35:27 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 50100; int a[N][7], n; bool check(int i, int j) { int cnt{}; For1(k, 1, 5) { if (a[i][k] < a[j][k]) cnt++; } return (cnt >= 3); } void solve() { cin >> n; For1(i, 1, n) { For1(j, 1, 5) { cin >> a[i][j]; } } int cur = 1; For1(i, 2, n) { if (!check(cur, i)) cur = i; } bool flag = true; For1(i, 1, n) { if (i == cur) continue; if (!check(cur, i)) { flag = false; break; } } cout << (flag ? cur : -1) << '\n'; } int main(void) { #ifdef _DEBUG freopen("1552b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

CodeForces 1551B2 Wonderful Coloring - 2

Wonderful Coloring - 2 考虑用 $k$ 个颜色去染色同一个数字，最多使用 $k$ 个数字。对于个数不够 $k$ 个的数字，可以把它们分到一组里面，每 $k$ 个数字染 $[1, k]$ 颜色即可。其实这两种情况可以合并成一种：从多于 $k$ 个的数字中取出 $k$ 个，与剩下个数不够 $k$ 个的数字合并在一起，按照值排序，这样可以保证连续的 $k$ 个数字不会含有相同的颜色。 // Date: Tue Jan 16 20:03:51 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 200100; int n, k, a[N], b[N]; void solve() { cin >> n >> k; map<int, VI> m; memset(b, 0, sizeof b); For1(i, 1, n) { cin >> a[i]; m[a[i]].pb(i); } vector<PII> d; int sum{}; for (auto &[x, v] : m) { For(i, 0, min(SZ(v), k)) { d.pb({x, v[i]}); } } sort(all(d)); sum = SZ(d) / k * k; For(i, 0, sum) { int idx = d[i].f2; b[idx] = i % k + 1; } For1(i, 1, n) { cout << b[i] << ' '; } cout << '\n'; } int main(void) { #ifdef _DEBUG freopen("1551b2.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

CodeForces 1548A Web of Lies

Web of Lies 观察发现如果一个点能够存活下来，那么它的值比它周围的点都大，也就是一个连通块中，只有最大的点会留下来。因此一个点能够留下来的充要条件是它的度数等于和它相邻的点中比它小的点的个数。对每个点维护这两个值，添加边和删除边的时候可以 $O(1)$ 更新，同时 $O(1)$ 维护答案。 // Date: Mon Jan 15 20:44:12 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 200100; int n, m, q, u, v, a[N], b[N]; void solve() { while (cin >> n >> m) { memset(a, 0, sizeof a); memset(b, 0, sizeof b); For1(i, 1, m) { cin >> u >> v; b[u]++; b[v]++; if (u > v) a[u]++; else a[v]++; } int cur = 0; For1(i, 1, n) { if (a[i] == b[i]) cur++; } int op; cin >> q; For1(i, 1, q) { cin >> op; if (op == 3) { cout << cur << '\n'; } else if (op == 1) { cin >> u >> v; b[u]++; b[v]++; if (u > v) { a[u]++; if (a[v] == b[v]) cur++; if (b[v] - 1 == a[v]) cur--; } else { a[v]++; if (a[u] == b[u]) cur++; if (b[u] - 1 == a[u]) cur--; } } else if (op == 2) { cin >> u >> v; b[u]--; b[v]--; if (u > v) { a[u]--; if (a[v] == b[v]) cur++; if (a[v] == b[v] + 1) cur--; } else { a[v]--; if (a[u] == b[u]) cur++; if (a[u] == b[u] + 1) cur--; } } } } } int main(void) { #ifdef _DEBUG freopen("1548a.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; while (T--) { solve(); } return 0; }

CodeForces 1540A Great Graphs

Great Graphs 要使得所有边的和最小，就要让正权边尽量少并且尽量小，可以想到相邻的两个点之间的距离应该互为相反数，也就是它们对答案的贡献是 $0$。为了让边权为正的边尽量小，可以把所有点到原点的距离从小到大排序，这样每个正权边的大小就是相邻两个正数的增量。接下来考虑不相邻两个点的情况，考虑每条边对最终答案的贡献，对于相邻的 $a, b$，设 $a, b$ 之间的边权是 $d$，这条边对答案的贡献分成两部分，一部分是以 $b$ 为起点，以 $a$ 左边的点的个数为终点；另一部分是横跨 $b$ 点，起点在 $b$ 的右侧，终点在 $a$ 以及它的左侧。这两部分的个数相加再乘 $-d$ 就是这条边对答案的总贡献。 // Date: Mon Jan 15 19:30:47 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 100100; int n, a[N]; void solve() { cin >> n; For1(i, 1, n) { cin >> a[i]; } sort(a + 1, a + 1 + n); ll ans = 0; For(i, 1, n) { ll t = a[i + 1] - a[i]; ll cnt1 = i - 1, cnt2 = n - (i + 1); ans += -(i * cnt2 + cnt1) * t; } cout << ans << '\n'; } int main(void) { #ifdef _DEBUG freopen("1540a.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

CodeForces 1535C Unstable String

Unstable String 有意思的 $DP$ 题目。如果 $s_i$ 是 $?$，它是 $1$ 还是 $0$ 取决于 $s_{i - 1}$，因此想到 $dp$，设 $d_{0, i}$ 表示以 $s_i$ 为结尾，并且 $s_i = 0$ 的合法的最长连续子字符串的个数，$d_{1, i}$ 同理。最终答案就是 $\sum max(d_{0, i}, d_{1, i})$ // Date: Sun Jan 14 23:57:50 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 200100; string s; int n, d[2][N]; void solve() { cin >> s; memset(d, 0, sizeof d); n = SZ(s); if (s[0] == '?') d[0][0] = d[1][0] = 1; else if (s[0] == '1') d[1][0] = 1; else d[0][0] = 1; For(i, 1, n) { if (s[i] == '?') { d[0][i] = 1 + d[1][i - 1]; d[1][i] = 1 + d[0][i - 1]; } else if (s[i] == '1') { d[0][i] = 0; d[1][i] = d[0][i - 1] + 1; } else { d[1][i] = 0; d[0][i] = d[1][i - 1] + 1; } } ll ans = 0; For(i, 0, n) { ans = ans + max(d[0][i], d[1][i]); } cout << ans << '\n'; } int main(void) { #ifdef _DEBUG freopen("1535c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

CodeForces 1579C Ticks

Ticks 数据范围很小，暴力做：依次把每个点当作最低点，模拟一遍。最终检查是否每个 * 都在某次尝试中访问过了。 // Date: Sun Jan 14 23:20:38 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 30; char a[N][N]; int n, m, k; void solve() { cin >> n >> m >> k; For(i, 0, n) { cin >> a[i]; } set<PII> s; For(i, 0, n) { For(j, 0, m) { if (a[i][j] == '*') { vector<PII> l, r; int len1{}, len2{}, i1{}, j1{}; i1 = i - 1, j1 = j - 1; while (i1 >= 0 && j1 >= 0 && a[i1][j1] == '*') { l.pb({i1, j1}); i1--; j1--; } len1 = SZ(l); i1 = i - 1; j1 = j + 1; while (i1 >= 0 && j1 < m && a[i1][j1] == '*') { r.pb({i1, j1}); i1--; j1++; } len2 = SZ(r); int len = min(len1, len2); if (len >= k) { s.insert(PII(i, j)); For(k, 0, len) { s.insert(l[k]); s.insert(r[k]); } } } } } bool flag = true; For(i, 0, n) { For(j, 0, m) { if (a[i][j] == '*' && !has(s, PII(i, j))) { flag = false; break; } } if (!flag) break; } cout << (flag ? "YES" : "NO") << '\n'; } int main(void) { #ifdef _DEBUG freopen("1579c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

CodeForces 1519C Berland Regional

Berland Regional tutorial 对每个学校的学生从小到达排序，设第 $i$ 个学校的人数是 $len_i$，那么这个学校对答案有贡献的 $k$ 的范围是 $[1, min(n, len_i)]$，对这其中的每个 $k$，可以找到应该从这个学校中去除的人数 $len_i \mod k$，进而求出这个学校的贡献。 // Date: Sat Jan 13 22:17:27 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 200100; int n, u[N], s[N]; VI a[N]; ll p[N]; void solve() { cin >> n; For1(i, 1, n) { a[i].clear(); cin >> u[i]; } For1(i, 1, n) { cin >> s[i]; a[u[i]].pb(s[i]); } map<int, ll> m; For1(i, 1, n) { if (nemp(a[i])) { ll sum = 0; sort(all(a[i])); int len = SZ(a[i]); p[0] = 0; For(j, 0, len) { sum += a[i][j]; p[j + 1] = a[i][j] + p[j]; } For1(i, 1, len) { int rem = len % i; m[i] += sum - p[rem]; } } } For1(i, 1, n) { cout << m[i] << ' '; } NL; } int main(void) { #ifdef _DEBUG freopen("1519c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

CodeForces 1517C Fillomino 2

Fillomino 2 tutorial 从第一行开始考虑，最优策略是先往左填，否则往下，这样可以保证下一行至少有一个「出口」。画图直观体会一下，$DFS$ 一直填就可以了。 // Date: Sat Jan 13 21:45:41 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, -1}, {1, 0}, {0, 1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 600; int n, a[N][N], p[N]; bool vis[N][N]; bool check(int x, int y) { return x > 1 && x <= n && y < x && y >= 1; } void dfs(int x, int y, int &cnt, int val) { int x1, y1; if (cnt == 0) return; vis[x][y] = true; a[x][y] = val; cnt--; For(i, 0, 2) { x1 = x + dir[i][0], y1 = y + dir[i][1]; if (check(x1, y1) && !vis[x1][y1]) { dfs(x1, y1, cnt, val); } } } void solve() { while (cin >> n) { memset(vis, false, sizeof vis); For1(i, 1, n) { cin >> p[i]; int x = p[i]; a[i][i] = x; vis[i][i] = true; } For1(i, 1, n) { int cnt = a[i][i]; dfs(i, i, cnt, a[i][i]); } For1(i, 1, n) { For1(j, 1, i) { cout << a[i][j] << ' '; } NL; } } } int main(void) { #ifdef _DEBUG freopen("1517c.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; while (T--) { solve(); } return 0; }

CodeForces 1516B AGAGA XOOORRR

AGAGA XOOORRR 求出前缀 $XOR$ 和，$XOR$ 的简单性质，可以求出任意区间 $[l, r]$ 的 $XOR$ 和。考虑最终局面，有两种情况：1. 只剩下两个数字。2. 只剩下三个数字。其它情况都可以通过操作转化成这两种情况。因此可以考虑把原数组分成两个区间或者三个区间，而区间的 $XOR$ 和已经得到。 // Date: Sat Jan 13 20:56:11 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 2100; int n, a[N], b[N]; int check(int l, int r) { if (l > r) return 0; return b[r] ^ b[l - 1]; } void solve() { cin >> n; b[0] = 0; For1(i, 1, n) { cin >> a[i]; b[i] = b[i - 1] ^ a[i]; } bool flag = false; For1(j, 2, n) { if (flag) break; For(i, 1, j) { int c1 = check(1, i), c2 = check(i + 1, j - 1), c3 = check(j, n); if (i + 1 <= j - 1) { if (c1 == c2 && c2 == c3) { flag = true; break; } } else { if (c1 == c3) { flag = true; break; } } } } cout << (flag ? "YES" : "NO") << '\n'; } int main(void) { #ifdef _DEBUG freopen("1516b.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

CodeForces 1490F Equalize the Array

Equalize the Array tutorial 统计出每个数字出现的次数 $b_i$，问题转化为对数组 $b$ 进行操作，只能进行 $b_i = b_i - 1$ 操作，如果 $b_i = 0$ 就移除，求使得所有的 $b_i$ 都相等的最少的操作次数。设最终所有的 $b_i = C$，对于所有的 $b_i < C$，使用 $sum(b_i)$ 个操作移除，剩下的 $b_i \ge C$，一直操作到所有的数字等于 $C$。直接求操作次数不好求，可以反着求，因为操作次数最多是 $n$，剩下的 $b_i$ 的个数是原来 $b_i \ge C$ 的数字的个数 $k$，剩下的数字和是 $C * k$，因此操作次数是 $n - C * k$。求 $b_i \ge C$ 的个数可以二分，因此枚举 $C$，可以 $log(n)$ 求出操作次数。 // Date: Sat Jan 13 20:38:22 2024 #include <climits> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> VI; typedef pair<int, int> PII; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; const int INF = 0x3f3f3f3f, MOD = 1e9 + 7, MOD1 = 998'244'353; const ll INFL = 0x3f3f3f3f'3f3f3f3f; const double eps = 1e-8; const int dir[8][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}, }; const ull Pr = 131; #define For(i, a, b) for (int i = int(a); i < int(b); ++i) #define Rof(i, a, b) for (int i = int(b) - 1; i >= int(a); --i) #define For1(i, a, b) for (int i = int(a); i <= int(b); ++i) #define Rof1(i, a, b) for (int i = int(b); i >= int(a); --i) #define ForE(i, j) for (int i = h[j]; i != -1; i = ne[i]) #define f1 first #define f2 second #define pb push_back #define has(a, x) (a.find(x) != a.end()) #define nemp(a) (!a.empty()) #define all(a) (a).begin(), (a).end() #define SZ(a) int((a).size()) #define NL cout << '\n'; template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template <class T> bool ckmax(T &a, const T &b) { return a istream &operator>>(istream &in, vector<t> &vec) { for (t &x : vec) in >> x; return in; } template <typename t> ostream &operator<<(ostream &out, vector<t> &vec) { int n = SZ(vec); For(i, 0, n) { out << vec[i]; if (i < n - 1) out << ' '; } return out; } void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifdef _DEBUG #define debug1(x) cout << #x " = " << x << endl; #define debug2(x, y) cout << #x " = " << x << " " #y " = " << y << endl; #define debug3(x, y, z) \ cout << #x " = " << x << " " #y " = " << y << " " #z " = " << z << endl; #define dbg(x...) \ cerr << "\e[91m" << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << "\e[39m" << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 200100; int n, a[N], b[N], idx; void solve() { cin >> n; For1(i, 1, n) cin >> a[i]; map<int, int> m; For1(i, 1, n) { m[a[i]]++; } idx = 0; for (auto &[_, x] : m) { b[++idx] = x; } sort(b + 1, b + idx + 1); int ans = n; For1(i, 1, n) { int l = 1, r = idx, mid; while (l < r) { mid = (l + r) / 2; if (b[mid] >= i) r = mid; else l = mid + 1; } if (b[r] >= i) { int cnt = idx - r + 1, tmp = n - cnt * i; ckmin(ans, tmp); } } cout << ans << '\n'; } int main(void) { #ifdef _DEBUG freopen("1490f.in", "r", stdin); #endif std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }