A - Yay! (abc342 A)
题目大意
给定一个字符串，两个字符，其中一个只出现一次，找出它的下标。
解题思路
看第一个字符出现次数，如果是\(1\)则就是它，否则就是不是它的字符。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
if (s.find(s[0], 1) == string::npos) {
cout << 1 << '\n';
} else {
cout << s.find_first_not_of(s[0], 1) + 1 << '\n';
}
return 0;
}
B - Which is ahead? (abc342 B)
题目大意
一排人。
\(m\)个询问，每个询问问两个人，谁在左边。
解题思路
记录一下每个人的下标，然后对于每个询问比较下标大小即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> pos(n);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
--x;
pos[x] = i;
}
int q;
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
--x, --y;
cout << (pos[x] < pos[y] ? x + 1 : y + 1) << '\n';
}
return 0;
}
C - Many Replacement (abc342 C)
题目大意
给定一个长度为\(n\)的字符串，进行\(m\)次操作。
每次操作， 将所有的字符 \(a\)替换成字符 \(b\)。
输出最后的字符串。
解题思路
朴素做法的复杂度是\(O(nm)\)，但考虑到字母只有\(26\)个，可以维护一个字母的映射： \(op[a]\)表示字符a替换成了op[a]。
这样每次操作就修改这个映射表即可，注意是将所有的\(op[i] == a\)的修改成 \(op[i] = b\)
最后根据映射表还原最终的字符串即可。时间复杂度为\(O(n + 26m)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
string s;
cin >> n >> s;
array<int, 26> op;
iota(op.begin(), op.end(), 0);
int q;
cin >> q;
while (q--) {
string a, b;
cin >> a >> b;
for (auto& i : op)
if (i == a[0] - 'a')
i = b[0] - 'a';
}
for (auto& i : s)
cout << char('a' + op[i - 'a']);
cout << '\n';
return 0;
}
D - Square Pair (abc342 D)
题目大意
给定\(n\)个数\(a_i\)，问有多少对 \((i, j), i < j\)，满足 \(a_i a_j\)是完全平方数。
解题思路
考虑怎样的两个数相乘是完全平方数。
对一个数质因数分解，如果每个质数的幂都是偶数，那么这个数就是完全平方数。
而如果\(a_i\)不是完全平方数，那么肯定有质数的幂是奇数，如果\(a_ia_j\)是完全平方数，\(a_j\) 中，质数的幂是奇数的那些质数一定得和\(a_i\)相同。即取质数的幂为奇数的那些质数的乘积，它们是相同的。
因此，对每个数\(a_i\)求出质数的幂是奇数的质数乘积，记为\(b_i\)，剩下的问题就是统计\((i,j)\)的数量，满足 \(b_i==b_j\)，这就是个经典的问题，维护每个数出现的次数即可。
注意特殊情况 \(0\)的处理。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
const int N = 2e5 + 10;
vector<int> cnt(N);
LL ans = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (x == 0) {
ans += i;
cnt[0]++;
continue;
}
int up = sqrt(x);
int odd = 1;
for (int j = 2; j <= up; j++) {
int num = 0;
while (x % j == 0) {
x /= j;
num++;
}
if (num & 1)
odd *= j;
}
if (x != 1)
odd *= x;
ans += cnt[odd];
ans += cnt[0];
cnt[odd]++;
}
cout << ans << '\n';
return 0;
}
E - Last Train (abc342 E)
题目大意
\(n\)个车站，给定 \(m\)条信息，每条信息给定 \((l,d,k,c,a,b)\)，表示从第\(l\)时刻开始，每隔 \(d\)时刻会发一辆车，一共会发 \(k\)辆车，每辆车从车站 \(a \to b\)，耗时 \(c\)时刻。
问从每一个车站出发，能到达第\(n\)个车站的最晚出发时刻。忽略换乘时间。
解题思路
直接考虑从第\(i\)个车站出发的话，会发现比较难做，题问最晚时刻，那我自然是搭乘越晚的班车越好，但是晚的话可能就错过了下一个站点的班车，导致最终不可达，即早到的话可以选择的余地多点，但晚到的话就很少选择，甚至没有。即我当前做决策的可行性难以判断。并且如果考虑每一个站点，时间上也不够。
题意问的是多起点单终点的情况，不妨反过来考虑，将边反向，从终点第 \(n\)个车站考虑，这样就是单起点多终点的情况，跟最短路考虑的情况是一致的。
既然是反过来考虑，时间也是倒流的，我们从最晚的时刻，从第\(n\)个车站出发，搭班车。
题目求最晚时刻，那我肯定是搭的班车越晚越好（正向考虑的），而这个越晚越好相对于现在考虑的时光倒流来说，就是越早越好。
所以就从第\(n\)个车站开始，搭乘当前可搭乘的最晚的一个班车（一个数学公式就可以得到，也可以二分），到达下一个车站。维护\(dis[i]\)表示到达第 \(i\)个车站的最晚时刻，为保证正确性和复杂度的正确性（道理和\(dijkstra\)一样），接着考虑最晚到达时刻的车站，依次搭乘班车即可，就像\(dijkstra\)一样，用一个优先队列维护出队顺序即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<vector<array<int, 5>>> edge(n);
for (int i = 0; i < m; ++i) {
int l, d, k, c, a, b;
cin >> l >> d >> k >> c >> a >> b;
--a, --b;
edge[b].push_back({a, l, d, k, c});
}
vector<LL> dis(n, -1);
priority_queue<pair<LL, int>> q;
dis[n - 1] = 3e18;
q.push({3e18, n - 1});
while (!q.empty()) {
auto [d, u] = q.top();
q.pop();
if (dis[u] != d)
continue;
for (auto [v, l, dd, k, c] : edge[u]) {
LL t = dis[u] - c;
t = (t - l) / dd;
if (t >= k)
t = k - 1;
if (t < 0)
continue;
t = l + t * dd;
if (dis[v] < t) {
q.push({dis[v] = t, v});
}
}
}
for (int i = 0; i < n - 1; ++i) {
if (dis[i] == -1)
cout << "Unreachable" << endl;
else
cout << dis[i] << endl;
}
return 0;
}
F - Black Jack (abc342 F)
题目大意
扔骰子。骰子\(D\)面，均等概率。扔若干次，分数为这几次的骰子数的和。
对手会一直扔，直到分数 \(y \geq L\)。
问你的策略，使得获胜的概率最大。
获胜的条件为，假设你的分数为\(x\)，要求 \(x \leq N\)，且(\(x > y\) 或 \(y > N\))
解题思路
首先可以求出对手的分数分布。设\(dp[i]\)表示结果为 \(i\)的概率，那 \(dp[i] = \sum_{1 \leq j \leq D \& i-j < L} \frac{dp[i - j]}{D}\)，
考虑我的策略，由样例的启发，可以和对手类似，即设定一个 \(R\)，表示我会一直扔，直到分数 \(x \geq R\)。
假设我枚举了 \(R\)， 那我同样也可以得到一个概率分布，根据这两个概率分布，根据规则用前缀和可以\(O(n)\)计算出我获胜的概率。
不同的\(R\)对应了一个获胜概率，遍历所有的 \(R\)取最大值就是答案。
但这样的复杂度是 \(O(n^2)\)。考虑优化枚举 \(R\)。
注意到当 \(R\)很小时，我的分数可能都低于对手分数，使得我获胜的概率很低。而当 \(R\)很大时，我的分数可能都大于 \(N\)，同样使得我获胜的概率很低，中间就有获胜概率高的。于是猜测 获胜概率关于\(R\)是一个 凸函数，因此三分\(R\)，发现过了。
后来测了下貌似确实是个凸函数，但要 注意一下三分初始边界。\(R\)很小的一部分范围，其获胜概率都相同的，这会影响到三分边界。根据规则，我的分数肯定是越高越好，但不超过 \(N\)，因此下界应该是 \(N - D + 1\)，这样我的分数分布在 \([N - D + 1, N]\)，是最好的。剩下三分的就是超过\(N\)的和不超过 \(N\)之间的一个权衡。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, l, d;
cin >> n >> l >> d;
auto solve = [&](int up) {
vector<double> dp(up + d, 0);
dp[0] = 1;
double sum = 0;
if (0 < up)
sum += dp[0];
for (int i = 1; i < up + d; i++) {
dp[i] = sum / d;
if (i < up)
sum += dp[i];
if (i - d >= 0)
sum -= dp[i - d];
}
return dp;
};
auto dp1 = solve(l);
double large = 0;
for (int i = n + 1; i < dp1.size(); ++i)
large += dp1[i];
int L = n - d + 1, R = n;
auto calc = [&](int x) {
auto dp2 = solve(x);
double sum = 0;
double ret = 0;
int pos = l;
for (int i = x; i < x + d; ++i) {
if (i > n)
break;
while (pos < i && pos < dp1.size()) {
sum += dp1[pos];
pos++;
}
ret += (sum + large) * dp2[i];
}
return ret;
};
while (L < R) {
int lmid = L + (R - L) / 3;
int rmid = R - (R - L) / 3;
if (calc(lmid) < calc(rmid))
L = lmid + 1;
else
R = rmid - 1;
}
cout << fixed << setprecision(10) << max(calc(L), calc(R)) << '\n';
return 0;
}
还有一种更简洁的求法，直接设\(dp[i]\)表示当前分数为 \(i\)，我以最优策略下获胜的概率。
策略无非就两种：
- 停止投掷，那根据当前分数 \(i\)和对手的概率分布，就可以算出自己的获胜概率。
- 继续投掷，那获胜概率就是 \(\sum_{d=1}^{D}\frac{dp[i + d]}{D}\)
两者取最大值即可。
但感觉第二种的转移方式有点奇特。
G - Retroactive Range Chmax (abc342 G)
题目大意
给定一个数组\(a\)，维护下列三种操作：
- 区间取最大值
- 撤销之前的操作
- 输出第 \(x\)个数
解题思路
朴素的想法就是记录所有的区间操作，那第一和第二的操作都可以\(O(1)\)完成，但对于第三的操作，我需要遍历所有的操作，耗时 \(O(q)\)。
想着有什么办法可以优化第三种操作，睡梦中一个霓虹人指点了我，一醒来猛然会了（？
区间操作一般可以通过线段树分成$\log $段的区间操作，对于同一区间的若干次操作，注意到操作顺序不会影响最终结果，因为要撤销，所以用 multiset记录对这个区间取最大值的所有数，这样撤销时直接删去那个数即可。
查询时就从根到叶子一路往下，对中途节点的multiset里的值取个最大值即为答案。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 8;
class segment {
#define lson (root << 1)
#define rson (root << 1 | 1)
public:
multiset<int> maxx[N << 2];
void build(int root, int l, int r, vector<int>& a) {
if (l == r) {
maxx[root].insert(a[l - 1]);
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid, a);
build(rson, mid + 1, r, a);
}
void update(int root, int l, int r, int L, int R, int val, int remove = 0) {
if (L <= l && r <= R) {
if (remove) {
maxx[root].extract(val);
} else
maxx[root].insert(val);
return;
}
int mid = (l + r) >> 1;
if (L <= mid)
update(lson, l, mid, L, R, val, remove);
if (R > mid)
update(rson, mid + 1, r, L, R, val, remove);
}
int query(int root, int l, int r, int pos) {
if (l == r) {
return *maxx[root].rbegin();
}
int fa = maxx[root].empty() ? 0 : *maxx[root].rbegin();
int mid = (l + r) >> 1;
if (pos <= mid)
return max(fa, query(lson, l, mid, pos));
else
return max(fa, query(rson, mid + 1, r, pos));
}
} sg;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a)
cin >> x;
sg.build(1, 1, n, a);
int q;
cin >> q;
vector<array<int, 3>> ope(q);
for (int i = 0; i < q; i++) {
int op;
cin >> op;
if (op == 1) {
int l, r, x;
cin >> l >> r >> x;
sg.update(1, 1, n, l, r, x);
ope[i] = {l, r, x};
} else if (op == 2) {
int pos;
cin >> pos;
--pos;
auto& [l, r, x] = ope[pos];
sg.update(1, 1, n, l, r, x, 1);
} else {
int pos;
cin >> pos;
cout << sg.query(1, 1, n, pos) << '\n';
}
}
return 0;
}