Xueyang Liu

CodeForces 1710A Color the Picture

Color the Picture 观察可以发现，最终答案中连续的相同颜色的列的数量一定大于等于 $2$。按照行染色同理。设颜色 $a_i$ 能够染色的列数是 $b_i = \lfloor \frac{a_i}{m} \rfloor$，需要构造 $b_1 + b_2 + \ldots + b_j = n, b_i \ge 2$。考虑分解的思想，如果 $n$ 是偶数，设 $b_1 + b_2 + \ldots + b_k = sum$，如果有解，那么要求 $sum \ge n$。如果 $sum$ 是偶数，这意味着，奇数 $b_j$ 的个数为偶数个，如果 $sum > n$，那么把偶数 $b_j$ 拆分成 $2$，奇数 $b_j$ 拆分成若干个 $2$ 和一个 $1$，最后 $1$ 的个数是偶数个，先去掉偶数个 $1$，然后再考虑去掉 $2$，直到 $sum = n$。用类似的方法可以解决 $n$ 和 $sum$ 的奇偶性的其它三种情况，最终得到答案。这种奇偶性转换和分解的构造思想很常见。 // 2024/1/30 #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 << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 100100; ll n, m, a[N], k, b[N]; void solve() { cin >> n >> m >> k; For1(i, 1, k) { cin >> a[i]; } sort(a + 1, a + 1 + k); ll tot = n * m; if (a[k] >= tot) { cout << "Yes\n"; return; } auto check = [&](ll n, ll m) -> bool { ll cnt = 0; bool found = false; For1(i, 1, k) { b[i] = a[i] / n; if (b[i] >= 2) cnt += b[i]; if (b[i] >= 3) found = true; } if (cnt < m) return false; if (m % 2 == 0) return true; return found; }; if (check(n, m) || check(m, n)) { cout << "Yes\n"; } else cout << "No\n"; } int main(void) { #ifdef _DEBUG freopen("input.txt", "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 1933C Turtle Fingers: Count the Values of k

Turtle Fingers: Count the Values of k 枚举 $a^i$ 中的 $i$，然后枚举 $b^j$，求出对应的 $k$ 即可，由于 $l$ 的范围只有 $10^6$，暴力即可。 #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; typedef pair<ll, ll> PLL; 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; } using lll = __int128; istream &operator>>(istream &is, lll &v) { string s; is >> s; v = 0; for (auto &it : s) if (isdigit(it)) v = v * 10 + it - '0'; if (s[0] == '-') v *= -1; return is; } ostream &operator<<(ostream &os, const lll &v) { if (v == 0) return (os << "0"); lll num = v; if (v < 0) os << '-', num = -num; string s; for (; num > 0; num /= 10) s.pb((char)(num % 10) + '0'); reverse(all(s)); return (os << s); } 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 << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif void solve() { ll a, b, l; cin >> a >> b >> l; set<int> s; int a1 = 1; while (a1 <= l) { if (l % a1 != 0) { a1 *= a; continue; } int l1 = l / a1, b1 = 1; while (l1 % b1 == 0) { s.insert(l1 / b1); b1 *= b; } a1 *= a; } cout << SZ(s) << '\n'; } int main(void) { std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T = 1; cin >> T; while (T--) { solve(); } return 0; }

CodeForces 1706C Qpwoeirut And The City

Qpwoeirut And The City 对于奇数长度的数组，为了让合法的元素最多，只有一种情况。对于偶数长度的数组，如果把合法的点标记为 $1$，其它点标记为 $0$，可以发现 $0$ 和 $1$ 的排列规律，首先不能出现连续的 $1$，并且最多出现一次连续的两个 $0$，连续的两个 $0$ 出现的位置决定了最终的结果。从 $a_2$ 开始，假设 $a_2 = 1, a_3 = 0, \ldots$ 这是一种情况。从 $a_{n - 1}$ 开始，假设 $a_{n - 1} = 1, a_{n - 2} = 0, \ldots$ 这是对称的另外一种情况。对这两种情况分别求出前缀和与后缀和，然后枚举 $i$，就可以求出答案。 // 2024/1/29 #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 << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 300100; int n; ll a[N], p[N], p1[N]; void solve() { cin >> n; For1(i, 1, n) { cin >> a[i]; } ll ans{}; auto check = [](int start) { ll ans = 0; for (int i = start; i <= n - 1; i += 2) { if (a[i] > a[i - 1] && a[i] > a[i + 1]) continue; ll top = max(a[i - 1], a[i + 1]) + 1; ans += top - a[i]; } return ans; }; if (n & 1) { ans = check(2); cout << ans << '\n'; return; } p[1] = 0; for (int i = 2; i <= n; i += 2) { ll top = max(a[i - 1], a[i + 1]) + 1, delta = max(top - a[i], 0LL); p[i] = p[i + 1] = delta + p[i - 1]; } p1[n] = 0; for (int i = n - 1; i >= 1; i -= 2) { ll top = max(a[i - 1], a[i + 1]) + 1, delta = max(top - a[i], 0LL); p1[i] = p1[i - 1] = delta + p1[i + 1]; } ans = -1; for (int i = 2; i <= n; i += 2) { ll tmp = p[i - 1] + p1[i]; if (ans == -1) ans = tmp; else ckmin(ans, tmp); } cout << ans << '\n'; } int main(void) { #ifdef _DEBUG // freopen("1706c.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 1701C Schedule Management

Schedule Management 如果一个任务不能由最擅长它的员工完成，那么其他任何一个员工都是可以的，花费的时间都是 $2$，为了让总时间最小，应该让剩余时间多的员工优先完成，对于给定的总时间，尽量让每个员工的工作量是饱和的。可以发现判定某个总时间是否合法是可以通过上面的贪心思想 $O(n)$ 完成，因此可以二分答案。 // 2024/1/29 #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 << __func__ << ":" << __LINE__ << " [" << #x << "] = ["; \ _print(x); \ cerr << endl; #else #define debug1 #define debug2 #define debug3 #define dbg(x...) #endif const int N = 200100; int n, m, a[N], b[N]; bool check(int top) { int cnt {}; For1(i, 1, n) { if (b[i] > top) { cnt += (b[i] - top); } else if (cnt) { int rem = top - b[i]; rem /= 2; if (rem >= cnt) cnt = 0; else cnt -= rem; } } return !cnt; } void solve() { cin >> n >> m; fill(b, b + 1 + n, 0); For1(i, 1, m) { cin >> a[i]; b[a[i]]++; } sort(b + 1, b + 1 + n, greater<int>()); int l = 1, r = m, mid; while (l < r) { mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid + 1; } cout << r << '\n'; } int main(void) { #ifdef _DEBUG freopen("input.txt", "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 1697C awoos Favorite Problem

awoo’s Favorite Problem 通过观察可以发现对于任何一个位置满足 $s(a) \ge t(a), s(c) \le t(c)$，这是因为字符 $a$ 可以通过任意次操作跨过字符 $b$ 往右移动，字符 $c$ 可以通过任意次操作跨过字符 $b$ 往左移动，同时字符 $a, c$ 的相对顺序并不会改变。因此，当把两个字符串中的 $b$ 字符全部去掉之后，两个字符串相等。 // Date: Wed Jan 24 23:26: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}, {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() { int n; string s, t, s1, t1; cin >> n >> s >> t; bool flag = true; int a1{}, a2{}, c1{}, c2{}; For(i, 0, n) { if (s[i] != 'b') s1 += s[i]; if (t[i] != 'b') t1 += t[i]; } if (s1 != t1) flag = false; For(i, 0, n) { if (s[i] == 'a') a1++; else if (s[i] == 'c') c1++; if (t[i] == 'a') a2++; else if (t[i] == 'c') c2++; if (a1 < a2 || c1 > c2) { flag = false; break; } if (a1 && a1 == a2) a1 = a2 = 0; if (c1 && c1 == c2) c1 = c2 = 0; } if (c1 || c2 || a1 || a2) flag = false; cout << (flag ? "YES" : "NO") << '\n'; } int main(void) { #ifdef _DEBUG freopen("1697c.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 1696C Fishingprince Plays With Array

Fishingprince Plays With Array 挺好的一道题目。像这种分久必合，合久必分的题目，我们可以考虑把能分解的都分解。把 $a$ 中的每个元素都分解到不能分解，对 $b$ 中的每个元素，考虑是否可以由分解后 $a$ 的前缀元素组成。有一个更加好写的方法：把 $b$ 中的每个元素也分解到不能分解，然后比较两个分解后的数组是否相等。有一个陷阱：如果对分解后的 $a$ 数组合并同类项，可能会出现整数溢出，需要使用 long long 类型。 // Date: Sat Feb 10 17:00:44 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 n, m, k, a[N], b[N]; PII split(int x) { int cnt = 1; while (x % m == 0) { cnt *= m; x /= m; } return {x, cnt}; } using PLL = pair<ll, ll>; void solve() { cin >> n >> m; For1(i, 1, n) { cin >> a[i]; } cin >> k; For1(i, 1, k) { cin >> b[i]; } vector<PII> d, d1; For1(i, 1, n) { d.pb(split(a[i])); } For1(i, 1, k) { d1.pb(split(b[i])); } auto shrink = [](vector<PII> &d) { vector<PLL> da; ll pre = -1, cnt = 0; for (auto &[x, c] : d) { if (x == pre) { cnt += c; } else if (pre == -1) { pre = x; cnt = c; } else { da.pb({pre, cnt}); pre = x, cnt = c; } } da.pb({pre, cnt}); return da; }; vector<PLL> da = shrink(d), db = shrink(d1); bool flag = true; if (SZ(da) != SZ(db)) flag = false; else { int len = SZ(da); For(i, 0, len) { if (da[i] != db[i]) { flag = false; break; } } } cout << (flag ? "YES" : "NO") << '\n'; } int main(void) { #ifdef _DEBUG freopen("1696c.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 1691C Sum of Substrings

Sum of Substrings 很有意思的一道题目，可以发现，中间的 $1$ 对答案的贡献总是 $11$，不管他们之间的顺序是怎样的，唯一对答案有影响的是最右边和最左边的 $1$，如果最右边的是 $0$，那么把中间的 $1$ 移动到最右边可以使得它对答案的贡献变为 $1$，如果最左边的是 $0$，那么把中间的 $1$ 移动到最左边可以使得它对答案的贡献变为 $1$，所以我们可以贪心的把中间的 $1$ 移动到最左边或者最右边，然后计算答案即可。 // Date: Wed Jan 24 22:52:04 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() { int n, k; string s; cin >> n >> k >> s; int cnt2 = -1; Rof(i, 0, n) { if (s[i] == '1') { cnt2 = n - 1 - i; break; } } if (cnt2 == -1) { cout << "0\n"; return; } int cnt1 = -1; For(i, 0, n) { if (s[i] == '1') { cnt1 = i; break; } } if (cnt2 <= k) { k -= cnt2; swap(s[n - 1], s[n - cnt2 - 1]); } if (cnt1 <= k && cnt1 != n - 1) { swap(s[0], s[cnt1]); } int ans = 0; For(i, 0, n - 1) { ans += (s[i] - '0') * 10 + (s[i + 1] - '0'); } cout << ans << '\n'; } int main(void) { #ifdef _DEBUG freopen("1691c.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 1690E Price Maximization

Price Maximization 对于简单的情况，如果 $a_i \mod k = r$，那么尽量取 $a_j \mod k = k - r$ 和 $a_i$ 配对，如果不存在这样的 $a_j$，那么就取 $a_j \mod k = k - r + s, (0 \lt s \lt k)$ // Date: Sat Feb 10 21:46:55 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; ll n, k, a[N]; vector<int> b[N]; void solve() { cin >> n >> k; For1(i, 1, n) { b[i].clear(); cin >> a[i]; } For1(i, 1, n) { int x = a[i] % k; b[x].pb(i); } ll ans = 0; For(i, 0, k) { while (nemp(b[i])) { int ta = (k - i) % k; int i1 = b[i].back(); b[i].pop_back(); int j = ta; while (b[j].empty()) { j = (j + 1) % k; } int j1 = b[j].back(); b[j].pop_back(); ans += (a[i1] + a[j1]) / k; } } cout << ans; NL; } int main(void) { #ifdef _DEBUG freopen("1690e.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 1684C Column Swapping

Column Swapping 暴力对每一行排序，检查需要交换的两列，找到两列之后，再对每一行的两列交换，检查是不是每一行都仍然保持有序。 // Date: Tue Jan 23 22:56:44 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() { int n, m; cin >> n >> m; vector<VI> a(n + 1, VI(m + 1, 0)); For1(i, 1, n) { For1(j, 1, m) { cin >> a[i][j]; } } vector<VI> b = a; int l = -1, r = -1; bool flag = true; VI di(2, -1); For1(i, 1, n) { sort(b[i].begin() + 1, b[i].begin() + 1 + m); VI d; For1(j, 1, m) { if (a[i][j] != b[i][j]) { d.pb(j); if (SZ(d) > 2) { flag = false; break; } } } if (!flag) break; if (d.empty()) continue; if (di[0] == -1) { di = d; } else { if (di != d) { flag = false; break; } } } l = di[0], r = di[1]; if (l == -1 && r == -1) l = r = 1; if (flag) { For1(i, 1, n) { swap(a[i][l], a[i][r]); auto check = [&](int j) { if (j > 1) { if (a[i][j] < a[i][j - 1]) flag = false; } if (j < m) { if (a[i][j] > a[i][j + 1]) flag = false; } return flag; }; flag = flag && check(l) && check(r); if (!flag) break; } } if (!flag) { cout << "-1\n"; } else { cout << l << ' ' << r << '\n'; } } int main(void) { #ifdef _DEBUG freopen("1684c.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 1682C LIS or Reverse LIS?

LIS or Reverse LIS? 如果 $a_i$ 出现过 2 次以上，那么只有其中的 2 个对答案有贡献，设这样的是数字个数有 $cnt$，那么它们对答案的贡献是 $cnt$。如果 $a_i$ 出现过 1 次，那么它必定可以出现在两个序列中的其中一个，并且其中的一个数字可以同时出现在两个子序列当中，设出现 1 次的数字个数有 $cnt_1$，那么它们对答案的贡献是 $\lfloor \frac{cnt_1 + 1}{2} \rfloor$ // Date: Mon Jan 22 23:16: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 = 200100; int n, a[N]; void solve() { cin >> n; map<int, int> m; For1(i, 1, n) { cin >> a[i]; m[a[i]]++; } int cnt{}; for (auto &[x, y] : m) { if (y >= 2) cnt += 2; else if (y == 1) cnt++; } int ans = (cnt + 1) / 2; cout << ans << '\n'; } int main(void) { #ifdef _DEBUG freopen("1682c.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 1675E Replace With the Previous, Minimize

Replace With the Previous, Minimize 从前往后扫描，记录能够转换到 $a$ 的最大的字符 $c_1$，直到某个字符 $c_i$ 不能转换到 $a$，此时它只能转换到 $c_2 > c_1$。也就是对于字符串中所有 $\le c_1$ 的都转换成 $a$，所有 $[c_2, c_i]$ 范围内的字符，都转换成 $c_2$，其余字符不变。 // Date: Mon Jan 22 22:35:54 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() { int n, k; string s; cin >> n >> k >> s; int delta = 0, c1 = -1, c2 = -1; For(i, 0, n) { int x = s[i] - 'a'; if (x <= delta) continue; if (k >= x - delta) { k -= (x - delta); delta = x; if (!k) break; } else { c1 = x, c2 = x - k; break; } } For(i, 0, n) { char c3 = 'a' + delta; if (delta && s[i] <= c3) s[i] = 'a'; else { int j = s[i] - 'a'; if (c1 != -1 && c2 != -1 && j >= c2 && j <= c1) { s[i] = 'a' + c2; } } } cout << s << '\n'; } int main(void) { #ifdef _DEBUG freopen("1675e.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 1659C Line Empire

Line Empire 考虑基地的最终位置，如果最终的位置在 $x_i$，那么在把基地拉到 $x_i$ 之后，就再也不拉基地了，此时之后的代价可以计算出来。再考虑之前的拉基地的情况，可以发现攻打一个城市就拉一次基地的代价，总是比先攻打几个城市再拉基地的代价要小。因此在 $x_i$ 之前，每次攻打一个基地就拉一次基地，在 $x_i$ 之前的总代价也可以方便地计算出来。枚举基地最终的位置 $x_i$，使用 $O(1)$ 计算出总代价。 // Date: Mon Jan 22 22:01: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 = 200100; int n; ll x[N], a, b, p[N]; void solve() { cin >> n >> a >> b; x[0] = 0; For1(i, 1, n) { cin >> x[i]; } p[n + 1] = 0; Rof1(i, 1, n) { p[i] = x[i] + p[i + 1]; } ll ans = INFL; For1(i, 0, n) { ll left = (x[i] - x[0]) * (a + b); ll right = b * (p[i + 1] - x[i] * (n - i)); ckmin(ans, left + right); } cout << ans << '\n'; } int main(void) { #ifdef _DEBUG freopen("1659c.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 1654C Alice and the Cake

Alice and the Cake 这道题目考察逆向思维。如果使用数组 $a$ 两两组合成 $sum$，会发现不好组合，可能会有多种情况。可以反过来想，给定 $sum$，判定它是否可以经过一些操作之后得到数组 $a$，因为每次操作的结果是固定的，得到的数字顺序也不会影响答案，所以可以统计出 $a$ 中每个数字出现的次数。 // Date: Mon Jan 22 19:38:48 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; ll a[N], sum; void solve() { cin >> n; sum = 0; map<ll, int> m; For1(i, 1, n) { cin >> a[i]; sum += a[i]; m[a[i]]++; } queue<ll> q; bool flag = true; int cnt{}; q.push(sum); while (nemp(q)) { ll t = q.front(); q.pop(); if (m[t]) m[t]--; else { cnt++; ll x = (t + 1) / 2, y = t / 2; if (m[x]) m[x]--; else q.push(x); if (m[y]) m[y]--; else q.push(y); } if (cnt >= n) { flag = false; break; } } cout << (flag ? "yes" : "no") << '\n'; } int main(void) { #ifdef _DEBUG freopen("1654c.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 1644C Increase Subarray Sums

Increase Subarray Sums 先找到各种长度的连续子数组的最大的和，再加上 $min(len, k) * x$ // Date: Mon Jan 22 09:12:52 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 = 5100; int n, a[N], d[N], p[N], x; void solve() { cin >> n >> x; p[0] = 0; For1(i, 1, n) { cin >> a[i]; d[i] = -INF; p[i] = p[i - 1] + a[i]; } For1(i, 1, n) ckmax(d[1], a[i]); For1(k, 2, n) { For1(i, 1, n) { int j = i + k - 1; if (j > n) continue; int tmp = p[j] - p[i - 1]; ckmax(d[k], tmp); } } For1(k, 0, n) { int cur = 0; For1(i, 1, n) { int tmp; if (i <= k) tmp = d[i] + i * x; else tmp = d[i] + k * x; ckmax(cur, tmp); } cout << cur << ' '; } cout << '\n'; } int main(void) { #ifdef _DEBUG freopen("1644c.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 1628A Meximum Array

Meximum Array 首先整个序列的 $MEX$ 是可以求出来的，最终答案的第一个数字一定是整个数列的 $MEX$，为了让答案序列的字典序最大，要让答案数组的第二个数字尽可能大，也就是求剩余数组的 $MEX$。这里的「剩余数组」指的是，删除尽量短的前缀，使得前缀数组的 $MEX$ 等于整个数组的 $MEX$。重复这样做下去即可。 // Date: Sun Jan 21 23:19:59 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], m; deque<int> d[N]; void solve() { cin >> n; For1(i, 0, n) d[i].clear(); For1(i, 1, n) { cin >> a[i]; d[a[i]].pb(i); } m = 0; int idx = 1; while (idx <= n) { For1(i, 0, n) { if (d[i].empty()) { b[++m] = i; break; } ckmax(idx, d[i].front()); } For1(i, 0, b[m]) { while (nemp(d[i]) && d[i].front() <= idx) d[i].pop_front(); } ++idx; } cout << m << '\n'; if (m) { For1(i, 1, m) { cout << b[i] << ' '; } cout << '\n'; } } int main(void) { #ifdef _DEBUG freopen("1628a.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; }