A - Yay!
题意
-
给定字符串 \(s\)
-
已知该字符串中只有一个字符与其他字符不同
-
求这个字符
思想
开一个数组 \(cnt_i\) 来记录 \(s\) 中每个字符出现的次数，一个数组 \(first_i\) 来记录 \(s\) 中每个字符第一次出现的下标。
选择 \(cnt_i = 1\) 的 \(i\) 输出 \(first_i\) 即可。
代码
#include <bits/stdc++.h>
using namespace std;
int cnt[26], f[26];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
int n = s.size();
for (int i = 0; i < n; i++) {
cnt[s[i] - 'a']++;
if (cnt[s[i] - 'a'] == 1)
f[s[i] - 'a'] = i;
}
for (int i = 0; i < 26; i++) {
if (cnt[i] == 1) {
cout << f[i] + 1 << endl;
}
}
return 0;
}
B - Which is ahead?
题意
-
有 \(n\) 个人站成一排，从前往后第 \(i\) 个人是 \(P_i\)
-
处理 \(q\) 次询问
-
每次询问 \(a_i\) 与 \(b_i\) 哪个更靠前，输出人的编号。
思想
每次询问从前向后扫描，先扫描到 \(a_i\) 就输出 \(a_i\)，否则输出 \(b_i\)。
代码
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 105;
int n, q;
int p[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i];
cin >> q;
for (int i = 1; i <= q; i++) {
int a, b;
cin >> a >> b;
int x, y;
bool flag = false;
for (int j = 1; j <= n; j++) {
if (p[j] == a) {
if (!flag) {
cout << a << endl;
}
flag = true;
}
if (p[j] == b) {
if (!flag) {
cout << b << endl;
}
flag = true;
}
}
}
return 0;
}
C - Many Replacement
题意
-
给你一个长度为 \(n\) 的字符串 \(s\)
-
有 \(q\) 次修改
-
每次修改将 \(s\) 中的所有字符 \(c_i\) 更改为 \(d_i\)
-
输出最后的字符串
思想
如果直接按照题目要求模拟的话，时间复杂度为 \(\mathcal{O}(n^2)\)，在 \(n \le 2 \times 10 ^ 5\) 的情况下会 \(\tt{TLE}\)。
考虑记录每个字符 \(c\) 最终会变字符 \(to_c\)。
动态维护 \(to_c\)。
每次更改将所有会更改为 \(c_i\) 的字符的 \(to_a\) 改为 \(d_i\)。
即对于所有 \(to_a = c_i\) 的 \(a\) 令 \(to_a=d_i\)。
最后将 \(s\) 的每个字符变为相应的 \(to\) 就行了。
时间复杂度 \(\mathcal{O}(Cn)\)，其中 \(C\) 为字符集大小。
代码
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 2e5 + 5;
int n, q;
string s;
int to[26], ans[26];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
cin >> s;
cin >> q;
for (int i = 0; i < 26; i++)
to[i] = i;
while (q--) {
string c1, d1;
cin >> c1 >> d1;
int c = c1[0] - 'a';
int d = d1[0] - 'a';
for (int i = 0; i < 26; i++) {
if (to[i] == c) {
to[i] = d;
}
}
}
for (int i = 0; i < n; i++) {
s[i] = to[s[i] - 'a'] + 'a';
}
cout << s << endl;
return 0;
}
D - Square Pair
题意
-
给你一长度为 \(n\) 的序列 \(\left\{a_i\right\}\)
-
求 \(a_i \times a_j\) 为平方数的无序数对 \((i, j)\) 的个数
思想
如果直接按照题意模拟复杂度高达 \(\mathcal{O}(n^2\sqrt{a})\)，会 \(\tt{TLE}\)。
根据算数基本定理，我们将 \(a_i\) 分解。
\[a=p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot p_2^{\alpha_2} \cdots p_k^{\alpha_k} \]考虑什么时候 \(a_i \times a_j\) 为平方数。
若 \(t\) 为平方数，则:
\[\alpha_1 \equiv 0 \mod 2 \\ \alpha_2 \equiv 0 \mod 2 \\ \vdots \\ \alpha_k \equiv 0 \mod 2 \]此时要让他为平方数则要求：
\[\alpha_1 \equiv \alpha'_1 \mod 2 \\ \alpha_2 \equiv \alpha'_2 \mod 2 \\ \vdots \\ \alpha_k \equiv \alpha'_k \mod 2 \]我们可以给 \(a_i\) 记录下序列 \(\left\{x_i\right\}\) 为 \(\alpha_j \equiv 1 \mod 2\) 的 \(p_j\)。
这样只需要 \(a_i\) 与 \(a_j\) 的 \(x\) 相同相乘即为平方数。
但是这里有个特例：\(0\) 乘任何数都等于 \(0\)，为平方数。
所以我们先把 \(0\) 处理掉，设 \(0\) 的个数为 \(cnt\)。
则 \(0\) 乘非 \(0\) 的个数为 \(cnt \times (n - cnt)\)。
\(0\) 乘 \(0\) 的个数为 \(\cfrac{cnt \times (cnt - 1)}{2}\)。
所以答案的贡献先算上 \(cnt \times (n - cnt) + \cfrac{cnt \times (cnt - 1)}{2}\)。
我们接着把每一个 \(a_i\) 都计算出他们的 \(x\)，放到 \(map\) 里统计同一个 \(x\) 的有多少个。
若这一种的数量为 \(j\) 则对答案的贡献为 \(\cfrac{j \times (j - 1)}{2}\)。
按照此方法计算即可。
此处 \(x\) 用 \(vector\) 记录，因为 \(vector\) 可以方便的用 \(map\) 统计。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int MAXN = 2e5 + 5;
int n;
int a[MAXN];
map<vector<int>, int> mp;
void build(int x) {
vector<int> ans;
map<int, int> tmp;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0) {
while (x % i == 0) {
x /= i;
tmp[i]++;
}
}
}
if (x > 1) {
tmp[x]++;
}
for (auto [i, j] : tmp) {
if ((j & 1) == 0)
continue;
ans.push_back(i);
}
mp[ans]++;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
long long ans = 0;
long long cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (a[i] == 0)
cnt++;
else build(a[i]);
}
ans += cnt * (n - cnt) + cnt * (cnt - 1) / 2;
for (auto [i, j] : mp) {
ans += 1ll * j * (j - 1) / 2;
}
cout << ans << endl;
return 0;
}
E - Last Train
题意
-
有 \(n\) 个站台，\(m\) 种列车
-
第 \(i\) 种列车有 \(k_i\) 次单程车
-
第一次单程车发车于 \(l_i\)
-
每次单程车都需要花 \(c_i\) 单位的时间来到达终点
-
每相邻两次单程车发车时间相距 \(d_i\) 单位时间
-
出发站为 \(a_i\)
-
结束站为 \(b_i\)
-
求对于每个点 \(i \in [1,n-1]\) 求出 \(f(i)\) 即从 \(i\) 号站出发要能到达 \(n\) 号站的最晚时间
思想
由题面可知这是一道图论题。
感性理解一下这是一个类似最短路的问题。
题中的列车网络是一个有向图，但不一定无环。
这样拓扑排序就被 pass 了。
如果是 BFS 它又有边权。
观察一下，不可能其他都一样只是多坐了一班车还更优。
所以我们选用堆优化 \(\tt{Dijkstra}\)。
注意要反向建图，本题是单终最短路。
我们可以按照最优顺序来排序 \(Dijkstra\) 的松弛顺序，在本题中为按照 \(f(i)\) 从大到小访问。
如何松弛呢？
考虑计算要在 \(f(u)\) 之前从 \(v\) 到达 \(u\) 的最晚距离。
\[f(u) \ge l + td + c \\ f(v) \le l + td \]其中 \(t\) 为我们坐哪一次车。
我们选择最大的 \(t\)。
\[t = \lfloor \cfrac{f(u) - l - c}{d} \rfloor \]我们注意到 \(0 \le t < k\)
如果错过了这班车就不能松弛，但是如果太早了可以等。
错过这班车即 \(l + c > f(u)\)。
太早了等即
\[t = \min\left\{\lfloor \cfrac{f(u) - l - c}{d} \rfloor,\space k - 1 \right\} \]我们把 \(t\) 带入 \(f(v)\) 的式子。
\[f(v) \le l + \min\left\{\lfloor \cfrac{f(u) - l - c}{d} \rfloor,\space k - 1 \right\}d \]我们只要发现 $f(v) < $ 这个值，就可以来更新它。
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int MAXN = 2e5 + 5;
int n, m;
struct Node {
int l, d, k, c, to;
};
vector<Node> G[MAXN];
int f[MAXN];
void Dijkstra() {
memset(f, 0xc0, sizeof f);
f[n] = 0x3f3f3f3f3f3f3f3f;
set<pair<int, int>, greater<>> st;
st.insert(make_pair(0x3f3f3f3f3f3f3f3f, n));
while (st.size()) {
int u = st.begin()->second;
st.erase(st.begin());
for (auto [l, d, k, c, v] : G[u]) {
if (l + c > f[u])
continue;
if (f[v] < l + min((f[u] - c - l) / d, k - 1) * d) {
st.erase(make_pair(f[v], v));
f[v] = l + min((f[u] - c - l) / d, k - 1) * d;
st.insert(make_pair(f[v], v));
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int l, d, k, c, a, b;
cin >> l >> d >> k >> c >> a >> b;
G[b].push_back({ l, d, k, c, a });
}
Dijkstra();
for (int i = 1; i < n; i++) {
if (f[i] == 0xc0c0c0c0c0c0c0c0)
cout << "Unreachable" << endl;
else
cout << f[i] << endl;
}
return 0;
}
F - Black Jack
题意
-
你在跟一个叫庄稼的人玩游戏
-
有一个有 \(d\) 面的色子，它会等概率地摇出 \(1\) 到 \(d\) 的整数
-
你先摇，每一次都把摇出来的结果加到 \(x\) 上去，你可以选择摇几次
-
庄稼后摇，只要它摇出来的点数 \(< l\)，就会继续摇，同样地，它会把每次摇出来的数加到 \(y\) 上
-
如果 \(x > n\) 或 \(x \le y \le n\) 你就输了，否则你就赢了
-
求你获胜的概率最大是多少
思想
因为庄稼的策略是固定的，所以我们计算 \(g'(i)\) 即庄稼最后摇到了 \(x\) 的点数的概率
注意到每次 \(i < l\) 再摇时会把概率平均分到 \(i + 1\) 到 \(i + d\)。
我们就从小往大向后贡献。
但是这样会 \(\tt{TLE}\)。
区间加和单点查询。
我们用差分树状数组来维护它。
我们为了计算小于等于的贡献就直接前缀和一下得到 \(g(i)\)。
我们计算出 \(g(i)\) 了之后开始计算答案。
我们先计算在 \(i\) 处我们停止摇色子的获胜概率。
若 \(i > l\) 则概率为 \(g(x - 1) + 1 - g(n)\)。
若 \(i < l\) 则概率为 \(1 - g(n)\)。
我们令这个函数为 \(calc(i)\)。
然后我们令 \(f(i)\) 为我们从 \(x=i\) 开始摇色子最多的获胜概率。
如果继续摇答案就是 \(\cfrac{\sum^d_{j=1}f(i + j)}{d}\)。
停下答案就是 \(calc(i)\)。
所以:
\[f_i=\max\left\{calc(i), \cfrac{\sum^d_{j=1}f(i + j)}{d}\right\} \]我们从后往前扫描，用 \(sum\) 来维护 \(\sum^d_{j=1}f(i + j)\)。
代码
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 4e5 + 5;
int lowbit(int x) {
return x & -x;
}
struct Fenwick {
double c[MAXN];
void upd(int l, int r, double x) {
for (int i = l + 1; i < MAXN; i += lowbit(i))
c[i] += x;
for (int i = r + 2; i < MAXN; i += lowbit(i))
c[i] -= x;
}
double ask(int x) {
double ans = 0;
for (int i = x + 1; i > 0; i -= lowbit(i))
ans += c[i];
return ans;
}
} fenwick;
int n, l, d;
double f[MAXN], g[MAXN];
double calc(int x) {
if (x > n)
return 0;
double ans = 1 - g[n];
if (x > l)
ans += g[x - 1];
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> l >> d;
fenwick.upd(0, 0, 1);
for (int i = 0; i <= 4e5; i++) {
g[i] = fenwick.ask(i);
if (i < l) {
fenwick.upd(i + 1, i + d, g[i] / d);
g[i] = 0;
}
}
for (int i = 1; i <= 4e5; i++)
g[i] += g[i - 1];
double sum = 0;
for (int i = 4e5; i >= 0; i--) {
if (i > n)
f[i] = 0;
else
f[i] = max(sum / d, calc(i));
sum += f[i];
if (i + d <= 4e5)
sum -= f[i + d];
}
cout << fixed << setprecision(15) << f[0] << endl;
return 0;
}