这个比赛没有找到题解，有点难绷，所以来写篇。（实际上是无聊时写的就是了）
题面：https://codeforces.com/gym/105125/。目测难度是 绿绿黄紫紫。
A
有点诈骗。其实策略是只保留 \(\le 3\) 个数，然后就随便维护一下。\(O(n\log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, y) for (int i = (x); i <= (y); i++)
#define per(i, x, y) for (int i = (x); i >= (y); i--)
// #define int long long
using ll = long long; using ull = unsigned long long;
inline int read() {
char ch = getchar(); int s = 0, f = 1;
while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * f;
}
constexpr int N = 1e5 + 5;
int n, m, a[N];
map<array<int, 3>, int> mp;
map<pair<int, int>, int> m2;
map<int, int> m1;
inline void sol() {
n = read(), m = read(); mp.clear(), m1.clear(), m2.clear();
rep (i, 1, n) a[i] = 0;
while (m--) {
int v[3];
v[0] = read(), v[1] = read(), v[2] = read();
sort(v, v + 3);
int q = unique(v, v + 3) - v;
if (q == 1) m1[v[0]]++;
else if (q == 2) m2[{v[0], v[1]}]++;
else mp[{v[0], v[1], v[2]}]++;
}
for (auto [x, v] : m1) {
if (v & 1) {
cout << "YES\n";
a[x] = 1;
rep (i, 1, n) cout << a[i] << ' ';
cout << '\n';
return ;
}
}
for (auto [x, v] : m2) {
int b1 = m1[x.first] + m1[x.second];
if ((v + b1) & 1) {
cout << "YES\n";
a[x.first] = a[x.second] = 1;
rep (i, 1, n) cout << a[i] << ' ';
cout << '\n';
return ;
}
}
for (auto [x, v] : mp) {
int b1 = m1[x[0]] + m1[x[1]] + m1[x[2]];
int b2 = m2[{x[0], x[1]}] + m2[{x[0], x[2]}] + m2[{x[1], x[2]}];
if ((v + b1 + b2) & 1) {
cout << "YES\n";
a[x[0]] = a[x[1]] = a[x[2]] = 1;
rep (i, 1, n) cout << a[i] << ' ';
cout << '\n';
return ;
}
}
cout << "NO\n";
return ;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int Mako = read(); while (Mako--) sol();
return 0;
}
B
有点诈骗。注意到值域较小，所以我们贪心一个一个确定每次打哪个点。如果是打点内第二个目标，策略是打最小的目标数 \(\ge 2\) 的点。如果打点内第一个目标，有目标数 \(=1\) 的点就打，没有就打最大的。\(O(V\log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, y) for (int i = (x); i <= (y); i++)
#define per(i, x, y) for (int i = (x); i >= (y); i--)
// #define int long long
using ll = long long; using ull = unsigned long long;
inline int read() {
char ch = getchar(); int s = 0, f = 1;
while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * f;
}
constexpr int N = 3e5 + 5;
int n, a[N];
set<pair<int, int>> s;
inline void sol() {
n = read(); int su = 0; s.clear();
rep (i, 1, n) {
a[i] = read();
su += a[i];
s.insert({a[i], i});
}
if (!(su & 1)) return (void)(cout << "NO\n");
vector<int> ans;
rep (i, 1, su) {
if (i & 1) {
auto it = s.lower_bound({1, 0});
if (it -> first == 1) ans.push_back(it -> second), s.erase(it);
else {
it = prev(s.end());
ans.push_back(it -> second);
s.insert({it -> first - 1, it -> second});
s.erase(it);
}
} else {
auto it = s.lower_bound({2, 0});
if (it == s.end()) return (void)(cout << "NO\n");
ans.push_back(it -> second);
s.insert({it -> first - 1, it -> second});
s.erase(it);
}
}
cout << "YES\n";
for (auto to : ans) cout << to << ' '; cout << '\n';
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int Mako = read(); while (Mako--) sol();
return 0;
}
C
贪心确定每一位，然后按照题意模拟。\(O(nm\log (nm))\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, y) for (int i = (x); i <= (y); i++)
#define per(i, x, y) for (int i = (x); i >= (y); i--)
// #define int long long
using ll = long long; using ull = unsigned long long;
inline int read() {
char ch = getchar(); int s = 0, f = 1;
while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
while (isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * f;
}
constexpr int N = 1e6 + 5;
int n, m, a[N], sum[N], buc[N];
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
n = read(), m = read();
rep (i, 1, n * m) a[i] = read(), sum[a[i]]++;
rep (i, 1, n * m) {
buc[i] = sum[i];
sum[i] += sum[i - 1];
}
sort(a + 1, a + n * m + 1);
rep (i, 0, n - 1) {
vector<int> ans;
ans.push_back(a[i + 1]);
int s = sum[a[i + 1]] - 1 - i, ss = buc[a[i + 1]] - s - 1, lst = a[i + 1];
// ss 左，s 右
while (ans.size() < m) {
int p = lower_bound(sum + 1, sum + n * m + 1, sum[lst] + ss - s + 1) - sum;
if (ss - s + 1 < 0) p = lst;
if (p == lst) {
s -= ss + 1;
} else {
int x = sum[lst] + ss - s + 1;
s = sum[p] - x, ss = buc[p] - s - 1;
}
ans.push_back(p);
lst = p;
}
for (auto to : ans) cout << to << ' '; cout << '\n';
}
return 0;
}
D
这个题非常神秘，一开始还不太会做。但是只要先往 dp 想，再想想细节，就能发现 key observation。
key observation：当一个区间内 \(1,2,3\) 都出现时，无论它怎么扩张，它的绝对众数不变或没有绝对众数。
同理，发现只出现两个数时，绝对众数一定存在。转化一下题面，后面就好做了，随便 dp 容斥一下，不过我写了一坨 100 多行的答辩。大常数 \(O(n^3)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define rep(i, x, y) for (int i = (x); i <= (y); i++)
#define per(i, x, y) for (int i = (x); i >= (y); i--)
#define fi first
#define se second
// #define int long long
using ll = long long;
constexpr int N = 205, B = 200, mod = 1e9 + 7;
int n, n2; string s;
int dp[2][N][N << 1][4];
inline void MOD(int &x) { if (x >= mod) x -= mod; }
inline int sol(int p) {
memset(dp, 0, sizeof(dp));
int p0, p1;
rep (i, 1, 3) if (p ^ i) p0 = i;
per (i, 3, 1) if (p ^ i) p1 = i;
bool bl = 1;
auto upp0 = [&](bool i, bool j) {
rep (k, 0, n) rep (l, 1, n2) {
if (k > 0) {
MOD(dp[i][k - 1][min(l - 1, n - 1)][p0] += dp[j][k][l][0]);
MOD(dp[i][k - 1][min(l - 1, n - 1)][p0] += dp[j][k][l][p0]);
}
if (l - n > 0) MOD(dp[i][l - n - 1][n - 1][p0] += dp[j][k][l][p]);
}
if (bl) MOD(++dp[i][n][n - 1][p0]);
};
auto upp1 = [&](bool i, bool j) {
rep (k, 0, n) rep (l, 1, n2) {
if (k > 0) {
MOD(dp[i][k - 1][min(l - 1, n - 1)][p1] += dp[j][k][l][p]);
MOD(dp[i][k - 1][min(l - 1, n - 1)][p1] += dp[j][k][l][p1]);
}
if (l - n > 0) MOD(dp[i][l - n - 1][n - 1][p1] += dp[j][k][l][0]);
}
if (bl) MOD(++dp[i][n][n - 1][p1]);
};
auto up0 = [&](bool i, bool j) {
rep (k, 0, n - 1) rep (l, 1, n2) {
MOD(dp[i][k + 1][l + 1][0] += dp[j][k][l][0]);
MOD(dp[i][k + 1][l + 1][0] += dp[j][k][l][p0]);
}
rep (l, 1, n2) {
MOD(dp[i][n][l + 1][0] += dp[j][n][l][0]);
MOD(dp[i][n][l + 1][0] += dp[j][n][l][p0]);
}
};
auto up1 = [&](bool i, bool j) {
rep (k, 0, n - 1) rep (l, 1, n2) {
MOD(dp[i][k + 1][l + 1][p] += dp[j][k][l][p]);
MOD(dp[i][k + 1][l + 1][p] += dp[j][k][l][p1]);
}
rep (l, 1, n2) {
MOD(dp[i][n][l + 1][p] += dp[j][n][l][p]);
MOD(dp[i][n][l + 1][p] += dp[j][n][l][p1]);
}
};
if (s[1] - '0' == p0 || s[1] == '?') dp[1][n][n - 1][p0] = 1;
if (s[1] - '0' == p1 || s[1] == '?') dp[1][n][n - 1][p1] = 1;
if ((s[1] != '?') && (s[1] - '0' != p)) bl = 0;
rep (i, 2, n) {
bool o = i & 1, w = i & 1 ^ 1;
memset(dp[o], 0, sizeof(dp[o]));
if (s[i] == '?') {
upp0(o, w), upp1(o, w);
up0(o, w), up1(o, w);
} else {
if (s[i] - '0' == p0) upp0(o, w);
else if (s[i] - '0' == p1) upp1(o, w);
else up0(o, w), up1(o, w);
}
if ((s[i] != '?') && (s[i] - '0' != p)) bl = 0;
}
int res = 0;
if (bl) res = -1;
rep (i, 0, n) rep (j, 0, n2 + 1) rep (k, 0, 3) {
MOD(res += dp[n & 1][i][j][k]);
}
return res;
}
inline ll sol2(int x, int y) {
int res = 1; bool bl = 0, bl1 = 0, bl2 = 0;
rep (i, 1, n) {
if (s[i] != '?' && s[i] - '0' != x && s[i] - '0' != y) return 0;
if (s[i] == '?') MOD(res += res), bl = 1;
if (s[i] - '0' == x) bl1 = 1;
if (s[i] - '0' == y) bl2 = 1;
}
if (bl1 && bl2) return res;
if (!bl1 && !bl2) return (res - 2 + mod) % mod;
return (res - 1 + mod) % mod;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> s; n2 = n << 1, n2--;
s = ' ' + s;
int ans = ((sol(1) + sol(2)) % mod + sol(3)) % mod;
int x = (sol2(1, 2) + sol2(2, 3) + sol2(1, 3)) % mod;
ans -= x;
if (ans < 0) ans += mod;
cout << ans;
return 0;
}
E
CF 炸了，还没做。
标签：Invitational,ch,MITIT,题解,rep,long,int,dp,MOD From： https://www.cnblogs.com/kxwenorz/p/18222753