目录
写在前面
比赛地址：https://codeforces.com/contest/1983
孩子们我回来了。
这场实在是太对胃口，vp 不到 1h 就 4 题了之后 EF 也口出来了，然而赛时睡大觉去了没打真是亏死。
感觉自己的文字能力已经很牛逼了，不需要再多练了，以后的题解都会写得简略些。
A
签到。
令 \(\forall 1\le i\le n, a_i = i\) 即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
int n; std::cin >> n;
for (int i = 1; i <= n; ++ i) std::cout << i << " ";
std::cout << "\n";
}
return 0;
}
B
模拟。
有点诈骗的题，让我跑去想牛逼结论。
发现对任意大于 \(2\times 2\) 的矩阵进行的一次操作，都可以等价于若干次对 \(2\times 2\) 矩阵进行的操作。
考虑逐行逐列枚举位置，检查两矩阵是否该位置此时是否相同，若不相同则直接修改以该位置为左上角的 \(2\times 2\) 矩阵，若需要改但无法修改则无解。
显然若有解，则这样直接改肯定能构造出来。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 510;
//=============================================================
int n, m;
std::vector<int> a[kN], b[kN];
//=============================================================
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n >> m;
for (int i = 0; i < n; ++ i) {
std::string s; std::cin >> s;
a[i].clear();
for (int j = 0; j < m; ++ j) a[i].push_back(s[j] - '0');
}
for (int i = 0; i < n; ++ i) {
std::string s; std::cin >> s;
b[i].clear();
for (int j = 0; j < m; ++ j) b[i].push_back(s[j] - '0');
}
int flag = 1;
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < m; ++ j) {
if (a[i][j] != b[i][j]) {
if (i + 1 >= n || j + 1 >= m) {
flag = 0;
} else {
int d = b[i][j] - a[i][j];
a[i][j] = (a[i][j] + d + 3) % 3;
a[i + 1][j + 1] = (a[i + 1][j + 1] + d + 3) % 3;
a[i + 1][j] = (a[i + 1][j] + 3 - d) % 3;
a[i][j + 1] = (a[i][j + 1] + 3 - d) % 3;
}
}
}
}
std::cout << (flag ? "YES" : "NO") << "\n";
}
return 0;
}
C
枚举。
套路题，首先 3! 地枚举三个人获得的段的顺序。所有数均大于零，则第一个人一定获得一段前缀，第三个人一定获得一段后缀，第二个人取中间所有的数。考虑枚举第一个人获得的前缀，在令其不小于 \(L = \left\fceil\frac{tot}{3}\right\rceil\) 的基础上，二分得到最短的第三个获得的后缀使其不小于 \(L\)，再检查中间一段是否不大于 \(L\) 即可。
复杂度 \(O(n\log n)\) 级别。
可以双指针枚举中间一段做到 \(O(n)\)。
写挺丑。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, a[kN], b[kN], c[kN], ans[7];
LL prea[kN], preb[kN], sufc[kN];
LL tot, lim;
//=============================================================
bool solve(std::vector<int> &a_, std::vector<int> &b_, std::vector<int> &c_) {
for (int i = 1; i <= n; ++ i) prea[i] = prea[i - 1] + a_[i - 1];
for (int i = 1; i <= n; ++ i) preb[i] = preb[i - 1] + b_[i - 1];
sufc[n + 1] = 0;
for (int i = n; i; -- i) sufc[i] = sufc[i + 1] + c_[i - 1];
for (int i = 1; i <= n; ++ i) {
if (prea[i] < lim) continue;
int l = i + 2, r = n, p = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (preb[mid - 1] - preb[i] < lim) {
l = mid + 1;
} else {
p = mid;
r = mid - 1;
}
}
if (p == -1) continue;
if (sufc[p] < lim) continue;
ans[1] = 1, ans[2] = i;
ans[3] = i + 1, ans[4] = p - 1;
ans[5] = p, ans[6] = n;
return true;
}
return false;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n;
std::vector<int> aa, bb, cc;
tot = lim = 0;
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
aa.push_back(a[i]);
tot += a[i];
}
lim = 1ll * ceil(tot / 3.0);
for (int i = 1; i <= n; ++ i) {
std::cin >> b[i];
bb.push_back(b[i]);
}
for (int i = 1; i <= n; ++ i) {
std::cin >> c[i];
cc.push_back(c[i]);
}
if (solve(aa, bb, cc)) {
std::cout << ans[1] << " " << ans[2] << " ";
std::cout << ans[3] << " " << ans[4] << " ";
std::cout << ans[5] << " " << ans[6] << " " << "\n";
} else if (solve(aa, cc, bb)) {
std::cout << ans[1] << " " << ans[2] << " ";
std::cout << ans[5] << " " << ans[6] << " ";
std::cout << ans[3] << " " << ans[4] << " " << "\n";
} else if (solve(bb, aa, cc)) {
std::cout << ans[3] << " " << ans[4] << " ";
std::cout << ans[1] << " " << ans[2] << " ";
std::cout << ans[5] << " " << ans[6] << " " << "\n";
} else if (solve(bb, cc, aa)) {
std::cout << ans[5] << " " << ans[6] << " ";
std::cout << ans[1] << " " << ans[2] << " ";
std::cout << ans[3] << " " << ans[4] << " " << "\n";
} else if (solve(cc, aa, bb)) {
std::cout << ans[3] << " " << ans[4] << " ";
std::cout << ans[5] << " " << ans[6] << " ";
std::cout << ans[1] << " " << ans[2] << " " << "\n";
} else if (solve(cc, bb, aa)) {
std::cout << ans[5] << " " << ans[6] << " ";
std::cout << ans[3] << " " << ans[4] << " ";
std::cout << ans[1] << " " << ans[2] << " " << "\n";
} else {
std::cout << -1 << "\n";
}
}
return 0;
}
D
结论，逆序对。
先判断两数列中各元素数量是否相同。
发现若存在方案使得两数列相同，则在此之后可任意操作使两数列相同前提下任意排列。一个显然的想法是使两数列均变为有序状态；又发现一次交换操作可以转换为若干次相邻的两个数交换，相邻两个数交换的结果是逆序对数加减 1，可以发现两数列能均变为有序状态的充要条件，是两数列的逆序对的奇偶性相同。
于是仅需分别求逆序对即可。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
const int kLim = 2e5;
//=============================================================
int n, a[kN], b[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
namespace BIT {
#define lowbit(x) ((x)&(-x))
const int kL = kN;
int lim, nowtime, tag[kN];
LL f[kN];
void Init(int n_) {
++ nowtime;
lim = n_;
}
void Insert(int pos_, int val_) {
for (int i = pos_; i <= lim; i += lowbit(i)) {
if (tag[i] != nowtime) f[i] = 0, tag[i] = nowtime;
f[i] += val_;
}
}
LL Sum(int pos_) {
LL ret = 0;
for (int i = pos_; i; i -= lowbit(i)) {
if (tag[i] != nowtime) f[i] = 0, tag[i] = nowtime;
ret += f[i];
}
return ret;
}
LL Query(int l_, int r_ = lim) {
return Sum(r_) - Sum(l_ - 1);
}
#undef lowbit
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
n = read();
LL s1 = 0, s2 = 0;
BIT::Init(kLim);
for (int i = 1; i <= n; ++ i) {
a[i] = read();
BIT::Insert(a[i], 1);
s1 += BIT::Query(a[i] + 1);
}
BIT::Init(kLim);
for (int i = 1; i <= n; ++ i) {
b[i] = read();
BIT::Insert(b[i], 1);
s2 += BIT::Query(b[i] + 1);
}
std::sort(a + 1, a + n + 1);
std::sort(b + 1, b + n + 1);
int flag = 1;
for (int i = 1; i <= n; ++ i) {
if (a[i] != b[i]) {
flag = 0;
break;
}
}
if (flag && s1 % 2 == s2 % 2) std::cout << "YES\n";
else std::cout << "NO\n";
}
return 0;
}
E
期望，组合数
因为是期望，于是仅需考虑两种球的期望获得个数，再分别乘上其平均价值即可。
一个显然的想法是考虑构造两个人按顺序拿球构成的排列。拿到普通球后换人，一个显然的想法是以普通球为间隔进行分段，然后在各段里插入特别球表示可连续获得的数量来构造。根据奇偶性即可得到每段分别属于哪个人。
在上述构造中，先手拿到的普通球期望数量显然为：
\[\left\lceil\frac{n - k}{2}\right\rceil \]共有 \(n - k + 1\) 段，先手会拿走其中 \(\left\lceil\frac{n - k + 1}{2}\right\rceil\) 段，而每个特殊球在每段中出现概率相同，则先手拿到的特殊球期望数量为：
\[\frac{k}{n - k + 1}\times \left\lceil\frac{n - k + 1}{2}\right\rceil \]上述两个数量分别乘上平均价值即为先手的期望得分。后手得分即为总价值和减去先手期望得分。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const LL p = 1e9 + 7;
//=============================================================
//=============================================================
LL qpow(LL x_, LL y_) {
LL ret = 1;
while (y_) {
if (y_ & 1ll) ret = ret * x_ % p;
x_ = x_ * x_ % p, y_ >>= 1ll;
}
return ret;
}
LL inv(LL x_) {
return qpow(x_, p - 2);
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
LL n, k, s1 = 0, s2 = 0;
std::cin >> n >> k;
for (int i = 1; i <= n; ++ i) {
int x; std::cin >> x;
if (i <= k) s1 += x, s1 %= p;
else s2 += x, s2 %= p;
}
LL ans = 1ll * (n - k + 1) / 2ll * s2 % p * inv(n - k) % p;
ans += 1ll * (n - k + 2) / 2ll * k % p * inv(n - k + 1) % p * s1 % p * inv(k) % p;
ans %= p;
std::cout << ans << " " << (s1 + s2 - ans + p) % p << "\n";
}
return 0;
}
F
01 Trie，贪心，二分答案
这题好几把眼熟——你是否在找 「十二省联考 2019」异或粽子 的另一数据范围版本 CF241B Friends？
和 CF241B 类似地，考虑二分答案 \(\operatorname{lim}\)，仅需检查是否有小于 \(k\) 个区间的价值小于 \(\operatorname{lim}\) 即可。
考虑枚举区间的右端点 \(r\)，并检查区间 \([1, r] \sim [r, r]\) 中有多少有贡献。一个显然的想法是对 \(a_1\sim a_{r - 1}\) 维护一棵 01 Trie，然后用 \(a_r\) 在上面贪心地逐位匹配令 \(a_l \oplus a_r\) 小于 \(\operatorname{lim}\) 即可，求得有哪些 \(l\) 可令 \(a_l \oplus a_r\) 的价值小于 \(\operatorname{lim}\)。记其中最大的为 \(L_r\)，则根据区间价值的定义，有贡献的区间左端点为：
\[1\sim \max_{1\le i\le r} L_i \]在上述过程中对有贡献的区间左端点计数即可完成检查。Trie 单次插入和贪心匹配均为 \(O(\log v)\) 级别，则总时间复杂度 \(O(n\log^2 v)\) 级别。
注意多次检查时 Trie 要懒惰清空，清空时注意必须将左右儿子也清空。
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 1e5 + 10;
//=============================================================
int n;
LL k, a[kN], ans;
//=============================================================
namespace Trie {
const int kNode = kN << 5;
int nodenum, nowtime, tr[kNode][2], tag[kNode], id[kNode];
void init() {
++ nowtime;
nodenum = 0;
}
void insert(LL val_, int id_) {
int now_ = 0;
for (LL i = 30; i >= 0; -- i) {
LL ch = val_ >> i & 1ll;
if (!tr[now_][ch] || tag[tr[now_][ch]] != nowtime) {
tr[now_][ch] = ++ nodenum;
tr[nodenum][0] = tr[nodenum][1] = 0;
}
now_ = tr[now_][ch];
tag[now_] = nowtime;
id[now_] = id_;
}
}
int query(LL val_, LL lim_) {
int now_ = 0, ret = 0;
for (LL i = 30; i >= 0; -- i) {
LL ch1 = val_ >> i & 1ll, ch2 = lim_ >> i & 1ll;
if (ch2 == 1 && tr[now_][ch1] && tag[tr[now_][ch1]] == nowtime) {
ret = std::max(ret, id[tr[now_][ch1]]);
}
if (tr[now_][ch1 ^ ch2] && tag[tr[now_][ch1 ^ ch2]] == nowtime) {
now_ = tr[now_][ch1 ^ ch2];
} else {
break;
}
}
return ret;
}
}
bool check(int lim_) {
LL maxp = 0, sum = 0;
Trie::init(), Trie::insert(a[1], 1);
for (int i = 2; i <= n; ++ i) {
maxp = std::max(maxp, 1ll * Trie::query(a[i], lim_));
sum += maxp;
Trie::insert(a[i], i);
}
return sum < k;
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
std::cin >> n >> k;
for (int i = 1; i <= n; ++ i) std::cin >> a[i];
for (LL l = 0, r = 2e9; l <= r; ) {
LL mid = (l + r) >> 1ll;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
std::cout << ans << "\n";
}
return 0;
}
写在最后
参考：
- Codeforces Round #956 (Div. 2) and ByteRace 2024 A - G - cup-pyy - 知乎
- Codeforces Round #956 (Div. 2) and ByteRace 2024 - 空気力学の詩 - 博客园
因为国服一周年了所以放一个 PV 在这里。PV 做得很有感觉啊但是歌和日服广播剧的 La La Run 还是有一定差距呃呃、、、