目录
写在前面
比赛地址：https://codeforces.com/contest/1937。
被交互杀死的一集。
赛时卡 C 明天有早八就直接睡大觉了，第二天看看 D 一眼秒了，最困的一集。
A
签到
发现 1 会被先后交换到 2，4，8，16……
输出 \(2^{\left\lfloor\log n \right\rfloor}\) 即可。
//
/*
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 a; std::cin >> a;
std::cout << (1ll << ((int) log2(a))) << "\n";
}
return 0;
}
B
贪心。
只有两行。构造字典序最小的字符串 \(t\) 时贪心即可，考虑在当前位置是往右走更优还是转移到第二行更优。
输出方案即考虑找到所有的位置 \(i\)，满足 \(a_1[1:i]\) 与 \(t[1:i]\) 相同，\(a_2[i:n]\) 与 \(t[i + 1:n + 1]\) 相同，于是预处理第一行每个位置可以匹配到 \(t\) 的前几位，第二行每个位置可以匹配到 \(t\) 的后几位，然后枚举 \(i\) 检查即可。
//贪心。
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
int n, yes[2][kN];
std::string s[2], t;
//=============================================================
//=============================================================
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::cin >> s[0];
std::cin >> s[1];
t.clear();
t.push_back(s[0][0]);
int now = 0;
for (int i = 0; i < n; ++ i) {
if (now == 1 || i == n - 1) t.push_back(s[1][i]);
else {
if (s[1][i] < s[0][i + 1]) now = 1, t.push_back(s[1][i]);
else t.push_back(s[0][i + 1]);
}
}
std::cout << t << "\n";
int ans = 0;
for (int i = 0; i < n; ++ i) yes[0][i] = yes[1][i] = 0;
for (int i = 0; i < n; ++ i) {
if (s[0][i] != t[i]) break;
yes[0][i] = 1;
}
for (int i = n - 1, j = n; i >= 0; -- i, -- j) {
if (s[1][i] != t[j]) break;
yes[1][i] = 1;
}
for (int i = 0; i < n; ++ i) {
if (yes[0][i] && yes[1][i]) ++ ans;
}
std::cout << ans << "\n";
}
return 0;
}
C
交互，位运算
妈的我没脑子
暴力打个表发现两个数异或的最大值为 \(2^{\left\lfloor\log n - 1 \right\rfloor + 1} - 1\)，可以且仅可以由一对和为 \(2^{\left\lfloor\log n - 1 \right\rfloor + 1} - 1\) 的数异或得到。
找到最大和最小值的位置是很容易的。以最大值为例，仅需记录当前最大值位置 \(x\)，对 \(i(1\le i< n)\) 进行询问 ? x x i i 并更新 \(x\) 即可。
于是考虑先求得最大值 \(n-1\) 的位置 \(x\)，再找到 \(2^{\left\lfloor\log n - 1 \right\rfloor + 1} - 1 - (n - 1)\) 来凑出最大值。发现这个数满足如下特征：
- 由异或的性质可知该数与 \(n-1\) 各二进制位上的值是互补的。
- 该数与 \(n-1\) 的或也为 \(2^{\left\lfloor\log n - 1 \right\rfloor + 1} - 1\)。
- 在所有与 \(n-1\) 的或为 \(2^{\left\lfloor\log n - 1 \right\rfloor + 1} - 1\) 的数中，该数是最小的（二进制位上的 0 最多）。
又所有数与 \(n-1\) 的或的最大值为 \(2^{\left\lfloor\log n - 1 \right\rfloor + 1} - 1\)，于是记当前与 \(n-1\) 或最大的位置集合为 \(s\)，考虑对 \(i(1\le i< n)\) 进行询问 ? x i x s[0]，若大于则令 \(s= \{ i \}\)，若等于则将 \(i\) 加入 \(s\)，即可得到所有与 \(n-1\) 的或的最大值为 \(2^{\left\lfloor\log n - 1 \right\rfloor + 1} - 1\) 的数。
然后对集合 \(s\) 中的位置运行上述求最小值的算法，即可得到要求的数的位置 \(y\)，输出 ! x y 即可。
上述三个过程均仅需要 \(n-1\) 次询问，总询问次数合法。
//交互，位运算
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
int n, ans1, ans2;
//=============================================================
char query(int a_, int b_, int c_, int d_) {
std::cout << "? " << a_ << " " << b_ << " " << c_ << " " << d_ << "\n";
fflush(stdout);
char ret;
std::cin >> ret;
return ret;
}
void Solve() {
std::cin >> n;
ans1 = ans2 = 0;
for (int i = 1; i < n; ++ i) {
char ret = query(i, i, ans1, ans1);
if (ret == '>') ans1 = i;
}
int maxp = 0;
std::vector <int> pos;
pos.push_back(0);
for (int i = 1; i < n; ++ i) {
if (i == ans1) continue;
char ret = query(ans1, i, ans1, maxp);
if (ret == '>') {
maxp = i;
pos.clear(), pos.push_back(maxp);
} else if (ret == '=') {
pos.push_back(i);
}
}
ans2 = maxp;
for (auto x: pos) {
int ret = query(x, x, ans2, ans2);
if (ret == '<') ans2 = x;
}
std::cout << "! " << ans1 << " " << ans2 << "\n";
}
//=============================================================
int main() {
//freopen("1.txt", "r", stdin);
// std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
Solve();
}
return 0;
}
D
前缀和，二分
甚至没什么好说的题呃呃。
先手玩，发现对于一段长为 \(d\) 的 >>...>><，若小球从左侧进入，则会先运动到最右侧且字符串变为 <<...<<<，然后小球将在转向后重新回到起点，字符串变为 >>...>>>。相当于消去了与初始方向相反的第一个位置，移动了 \(2\times d\) 的距离。
则对于某个起点，小球的运动路径是左右反复横跳，仅需考虑左侧的 > 与右侧的 < 的贡献，且每个符号的贡献为它们与起点的距离。于是考虑前缀和维护各个符号的数量与坐标之和，然后枚举起点，先分别求得两侧 > 和 < 的数量并比较确定在哪侧移出平面，则答案可以分成三份：
- 这一侧所有符号，它们的贡献都可以取到，前缀和统计即可。
- 另一侧的前若干的符号，数量大于这一侧符号数量，可以通过二分得到其位置，前缀和可得到其区间贡献。
- 在这一侧最后一次移出平面的移动，贡献即为起点与端点的距离。
实现时需要注意端点。我的写法中求两侧的符号数量时左侧范围是 \(1\sim i-1\)，右侧是 \(i\sim n\)（相当于钦定了小球初始向右移动，即不考虑第 \(i\) 个位置为 > 的影响），则当右侧大于左侧时终点为左侧，否则为右侧。
总时间复杂度 \(O(n\log n)\) 级别。
//前缀和，二分
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
//=============================================================
int n;
std::string s;
LL cnt[2][kN], sum[2][kN];
//=============================================================
void Init() {
std::cin >> n;
std::cin >> s;
for (int i = 1; i <= n; ++ i) {
int t = (s[i - 1] == '>');
cnt[t][i] = cnt[t][i - 1] + 1, cnt[t ^ 1][i] = cnt[t ^ 1][i - 1];
sum[t][i] = sum[t][i - 1] + i, sum[t ^ 1][i] = sum[t ^ 1][i - 1];
}
}
void Solve() {
for (int i = 1; i <= n; ++ i) {
LL ans = 0;
int cl = cnt[1][i - 1], cr = cnt[0][n] - cnt[0][i - 1];
if (cr > cl) {
int p = i;
for (int l = i, r = n; l <= r; ) {
int mid = (l + r) >> 1;
if (cnt[0][mid] - cnt[0][i - 1] > cl) {
p = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
ans = 2ll * (1ll * cl * i - sum[1][i - 1])
+ 2ll * (1ll * sum[0][p] - sum[0][i - 1] - 1ll * (cnt[0][p] - cnt[0][i - 1]) * i) + i;
} else {
int p = i;
for (int l = 1, r = i; l <= r; ) {
int mid = (l + r) >> 1;
if (cnt[1][i - 1] - cnt[1][mid - 1] >= cr) {
p = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
ans = 2ll * (1ll * (cnt[1][i - 1] - cnt[1][p - 1]) * i
- (sum[1][i - 1] - sum[1][p - 1]))
+ 2ll * (1ll * sum[0][n] - sum[0][i - 1] - 1ll * cr * i) + n - i + 1;
}
std::cout << ans << " ";
}
std::cout << "\n";
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
std::ios::sync_with_stdio(0), std::cin.tie(0);
int T; std::cin >> T;
while (T --) {
Init();
Solve();
}
return 0;
}
E
建图，最短路
居然是牛逼建图最短路，而且这个图建得有一种自动机的味儿，学到了。
首先对于某属性强化操作的终点是离散的，一定是某个宝可梦该属性值，
经过强化后宝可梦的属性是递增的，且召唤完之后还需要把它打败，则所有宝可梦至多只会召唤一次，若出现召唤多次的情况说明有一段操作是冗余甚至有害的（使当前被召唤多次的宝可梦的属性上升从而不好打败了）。
考虑最优的操作序列的形态：（加强 \(a_1\) 直至能打败 1，召唤 \(a_1\) 打败 1） \(\longrightarrow\) （加强 \(a_2\) 直至能打败 \(a_1\)，召唤 \(a_2\) 打败 \(a_1\)） \(\longrightarrow \cdots \longrightarrow\) （加强 \(a_n\) 直至能打败 \(a_k\)，召唤 \(n\) 打败 \(a_k\)）。
考虑把这个操作序列倒过来考虑，如果把当前在道馆的宝可梦看做结点，问题好像变为找到一条 \(n\rightarrow 1\) 的最短的有向路径，有向边代表前一个宝可梦打败后一个，于是考虑建图跑最短路：
- 对于每个宝可梦 \(i\) 的属性 \(j\)，建立节点 \(X_{i, j}\)，代表召唤该宝可梦后准备使用其属性 \(j\)；建立 \(Y_{i, j}\) 表示可以打败该宝可梦。
- 连有向边 \((i, X_{i, j}, c_i)\) 表示召唤，\((X_{i, j}, Y_{i, j}, 0)\) 表示召唤自身，\((Y_{i, j}, i, 0)\) 表示打败该宝可梦后使该宝可梦可用来召唤。
- 对于每种属性，将所有宝可梦按照该属性值升序排序，设该属性为 \(j\) 且排序后顺序为 \(b_{1}\sim b_n\)，则连边 \((X_{b_{i-1}, j}, X_{b_{i}, j}, a_{b_{i}, j} - a_{b_{i - 1}, j})\) 表示强化操作至第一个大于的宝可梦，连边 \((Y_{b_{i}, j}, Y_{b_{i - 1}, j}, 0)\) 表示可以打败更弱的宝可梦。
然后跑出 \(n\rightarrow 1\) 的最短路即为答案。
节点与边数均为 \(O(nm)\) 级别，总时间复杂度 \(O(nm\log {nm})\) 级别。
//知识点：建图，最短路
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kN = 2e6 + 10;
const LL kInf = 1e18 + 2077;
//=============================================================
int n, m, nodenum;
int edgenum, head[kN], v[kN << 1], w[kN << 1], ne[kN << 1];
int c[kN];
std::vector <std::vector <pr <int, int> > > a;
LL dis[kN];
bool vis[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;
}
void Add(int u_, int v_, int w_) {
v[++ edgenum] = v_;
w[edgenum] = w_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void Dijkstra() {
std::priority_queue <pr <LL, int> > q;
for (int i = 1; i <= nodenum; ++ i) dis[i] = kInf, vis[i] = 0;
q.push(mp(0, n));
dis[n] = 0;
while (!q.empty()) {
int u_ = q.top().second; q.pop();
if (vis[u_]) continue;
vis[u_] = true;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i], w_ = w[i];
if (dis[u_] + w_ < dis[v_]) {
dis[v_] = dis[u_] + w_;
q.push(mp(-dis[v_], v_));
}
}
}
}
void Init() {
for (int i = 1; i <= nodenum; ++ i) {
head[i] = 0;
}
nodenum = edgenum = 0;
nodenum = n = read(), m = read();
for (int i = 1; i <= n; ++ i) c[i] = read();
a.clear(), a.push_back(std::vector <pr <int, int> >());
for (int i = 1; i <= m; ++ i) {
a.push_back(std::vector <pr <int, int> >(1, mp(0, 0)));
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) {
a[j].push_back(mp(read(), i));
}
}
for (int i = 1; i <= m; ++ i) {
std::sort(a[i].begin(), a[i].end());
for (int j = 1; j <= n; ++ j) {
int x = ++ nodenum;
int y = ++ nodenum;
Add(x, y, 0);
Add(a[i][j].second, x, c[a[i][j].second]);
Add(y, a[i][j].second, 0);
if (j != 1) Add(x - 2, x, a[i][j].first - a[i][j - 1].first);
if (j != 1) Add(y, y - 2, 0);
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
int T = read();
while (T --) {
Init();
// for (int i = 1; i <= nodenum; ++ i) {
// for (int j = head[i]; j; j = ne[j]) {
// printf("%d %d %d\n", i, v[j], w[j]);
// }
// }
Dijkstra();
printf("%lld\n", dis[1]);
}
return 0;
}
/*
1
3 1
2
6
1
*/
F
看着像数据结构，咕咕
写在最后
学到了什么：
- C：有点感觉但也不知道具体学到了啥。
- D：注意边界。
- E：有操作序列的最小化问题考虑用结点表示状态，往自动机方向思考，可能在自动机上跑贪心或者最短路。