AtCoder Beginner Contest 342 A~G
A.Yay!(模拟)
题意:
给定字符串 s s s,该字符串中只有一个字符与其他字符不同,找出这个字符。
分析:
遍历一遍字符串即可。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int num[N], ans[N];
string s;
int main() {
cin >> s;
int n = s.size();
for (int i = 0; i < n; i++) {
num[s[i] - 'a']++;
if (num[s[i] - 'a'] == 1)
ans[s[i] - 'a'] = i;
}
for (int i = 0; i < 26; i++) {
if (num[i] == 1) {
cout << ans[i] + 1 << endl;
}
}
return 0;
}
B.Which is ahead?(模拟)
题意:
有 n n n个人站成一排,站在第 i i i个位置的人是 p i p_i pi,给出 a i , b i a_i,b_i ai,bi,询问 a i , b i a_i,b_i ai,bi站的更靠前的人的编号。
分析:
用 m a p map map直接记录每个人站的位置,直接比较即可。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int p[N];
int main() {
int n;
cin >> n;
map<int, int> s;
for (int i = 1; i <= n; i++) {
cin >> p[i];
s[p[i]] = i;
}
int q;
cin >> q;
for (int i = 1; i <= q; i++) {
int a, b;
cin >> a >> b;
if (s[a] > s[b])
cout << b << endl;
else
cout << a << endl;
}
return 0;
}
C.Many Replacement(思维)
题意:
给定一个长度为 n n n的字符串 s s s,进行 q q q次修改,每次修改将 s s s中的所有字符 c i c_i ci修改为 d i d_i di,输出最后的字符串。
分析:
t o [ i ] to[i] to[i]表示每个字符最后会变成的字符,动态维护即可。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int to[N];
int main() {
int n;
cin >> n;
string s;
cin >> s;
int q;
cin >> q;
for (int i = 0; i < 26; i++)
to[i] = i;
while (q--) {
char c1, d1;
cin >> c1 >> d1;
int c = c1 - 'a';
int d = d1 - '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 n n的序列 a a a,询问满足 a i × a j a_i \times a_j ai×aj为平方数的无序数对 ( i , j ) (i,j) (i,j)的数量。
分析:
对平方数进行质因数分解,可以想到平方数的质因数一定是偶数个出现,那么假设 x = a b x=ab x=ab, x x x是平方数,那么其中每一个质因子都要有相同的奇数个或者偶数个。可以先对 a i a_i ai除以平方数进行缩小,之后就可以进行计数。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 5;
LL a[N];
LL cnt[N];
int main() {
int n;
cin >> n;
LL ans = 0;
LL num = 0, num0 = 0;
for (int i = 0; i < n; i++) {
LL x;
cin >> x;
if (x == 0) {
ans += n - 1;
num0++;
} else {
a[num++] = x;
}
}
ans -= 1ll * num0 * (num0 - 1) / 2;
for (int i = 0; i < num; i++) {
for (int j = sqrt(a[i]); j >= 1; j--) {
if (a[i] % (j * j) == 0) {
a[i] /= (j * j);
}
}
}
for (int i = 0; i < num; i++) {
ans += cnt[a[i]];
cnt[a[i]]++;
}
cout << ans << endl;
return 0;
}
E Last Train(最短路)
题意:
有 n n n个站台, m m m班列车,第 i i i班列车有 k i k_i ki次单程车,第 i i i班列车的第一班单程车在 l i l_i li时刻在 a i a_i ai站台发车,开到 b i b_i bi站台,每班车需要花费 c i c_i ci的时间从 a i a_i ai到达 b i b_i bi,之后每间隔 d i d_i di发一班车。对于每个 i i i求出从 i i i号站出发到达 n n n站台的最晚时间。
分析:
建反图,求单源最短路,经过一条边时考虑能赶上的最晚的火车,通过松弛操作选择合适的边,如果错过了最晚的车就不能够松弛。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
const int N = 2e5 + 5;
const LL INF = 1e18 + 1e9;
struct Node {
LL l, d, k, c, to;
};
vector<Node> g[N];
LL f[N];
LL n, m;
void dijkstra() {
for (int i = 0; i < N; i++) f[i] = -INF;
f[n] = INF;
set<pair<LL, LL>, greater<>> tmp;
tmp.insert(mp(INF, n));
while (!tmp.empty()) {
LL u = tmp.begin()->second;
tmp.erase(tmp.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) {
tmp.erase(mp(f[v], v));
f[v] = l + min((f[u] - c - l) / d, k - 1) * d;
tmp.insert(mp(f[v], v));
}
}
}
}
int main() {
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] == -INF)
cout << "Unreachable" << endl;
else
cout << f[i] << endl;
}
return 0;
}
F Black Jack(概率 dp)
题意:
有一个 d d d面的色子,会等概率摇出 1 − d 1-d 1−d的整数,你和一个人进行游戏,你先摇色子,每一次摇出的结果加到 x x x上,你可以摇任意次色子。之后轮到另一个人摇色子,如果摇出来的点数小于 l l l,他就继续摇色子,每一次摇出的结果加到 y y y上,如果最后 x > n x>n x>n或者 x ≤ y ≤ n x \le y \le n x≤y≤n 那么你就输了,询问获胜的概率最大是多少。
分析:
假设 f [ i ] f[i] f[i]为当前点数为 i i i,最优策略下获胜的概率, g [ i ] g[i] g[i]表示另一个人最后摇到了 x x x点数的概率。如果扔色子,那么赢的概率为 ∑ k = 1 D f i + k D \frac{\sum\limits_{k=1}^{D}f_{i+k}}{D} Dk=1∑Dfi+k,如果不扔色子那么获胜概率为 g [ i ] g[i] g[i],转移方程为 f [ i ] = m a x ( ∑ k = 1 D f i + k D , s o l v e ( i ) ) 。 s o l v e ( i ) f[i]=max(\frac{\sum\limits_{k=1}^{D}f_{i+k}}{D},solve(i))。solve(i) f[i]=max(Dk=1∑Dfi+k,solve(i))。solve(i)是计算赢的概率的函数, s o l v e solve solve的计算有两种情况: y > n , x > y y>n, x>y y>n,x>y ,将 g g g 数组前缀和即可。 g [ i ] g[i] g[i]可以将 i i i从 1 1 1枚举到 l − 1 l-1 l−1,将 g i g_i gi的概率平均分配到 g i + 1 − g D g_{i+1}-g_D gi+1−gD。这部分操作用差分版树状数组进行维护。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int lowbit(int x) {
return x & -x;
}
struct Fenwick {
double c[N];
void upd(int l, int r, double x) {
for (int i = l + 1; i < N; i += lowbit(i))
c[i] += x;
for (int i = r + 2; i < N; 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 g[N];
void solve1() {
fenwick.upd(0, 0, 1);
for (int i = 0; i <= 400000; 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 <= 400000; i++) {
g[i] += g[i - 1];
}
}
double f[N];
double solve(int x) {
if (x > n) {
return 0;
} else {
double ans = 1 - g[n];
if (x > l) {
ans += g[x - 1];
}
return ans;
}
}
void solve2() {
double sum = 0;
for (int i = 400000; i >= 0; i--) {
if (i > n) {
f[i] = 0;
} else {
f[i] = max(sum / d, solve(i));
}
sum += f[i];
if (i + d <= 400000) {
sum -= f[i + d];
}
}
}
int main() {
scanf("%d %d %d", &n, &l, &d);
solve1();
solve2();
printf("%.15f", f[0]);
return 0;
}
G Retroactive Range Chmax(树上启发式合并)
题意:
给一个长度为 n n n的序列 a a a,进行 q q q次操作:
- l ≤ i ≤ r , a i = m a x ( a i , x ) l \le i \le r,a_i=max(a_i,x) l≤i≤r,ai=max(ai,x)
- 取消第 i i i次操作,即新的状态为从前往后执行除了 i i i操作外的所有操作得到的状态
- 询问 a i a_i ai的值。
分析:
用线段树记录每个点所有可能的值,某个时刻查询的时候,只要给出最大的即可。维护的时候不需要用 p u s h u p , p u s h d o w n pushup, pushdown pushup,pushdown来维护前后影响,只需要返回到达 a i a_i ai时线段树路径上的最大值即可。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
#define ls p << 1
#define rs p << 1 | 1
int q;
int a[N];
struct Node {
map<int, int> val;
} t[N << 2];
void build(int p, int l, int r) {
if (l == r) {
t[p].val[a[l]]++;
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
}
void change(int p, int l, int r, int L, int R, int d, bool x) {
if (L <= l && r <= R) {
if (x) {
t[p].val[d]++;
} else {
if (--t[p].val[d] == 0)
t[p].val.erase(d);
}
return;
}
int mid = (l + r) >> 1;
if (L <= mid)
change(ls, l, mid, L, R, d, x);
if (R > mid)
change(rs, mid + 1, r, L, R, d, x);
}
int ask(int p, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return t[p].val.rbegin()->first;
}
int mid = (l + r) >> 1, ans = 0;
if (!t[p].val.empty())
ans = t[p].val.rbegin()->first;
if (L <= mid)
ans = max(ans, ask(ls, l, mid, L, R));
if (R > mid)
ans = max(ans, ask(rs, mid + 1, r, L, R));
return ans;
}
struct tmper {
int l, r, d;
} tmp[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
cin >> q;
for (int i = 1; i <= q; i++) {
int op;
cin >> op;
if (op == 1) {
cin >> tmp[i].l >> tmp[i].r >> tmp[i].d;
change(1, 1, n, tmp[i].l, tmp[i].r, tmp[i].d, 1);
} else if (op == 2) {
cin >> tmp[i].d;
change(1, 1, n, tmp[tmp[i].d].l, tmp[tmp[i].d].r, tmp[tmp[i].d].d, 0);
} else {
cin >> tmp[i].d;
cout << ask(1, 1, n, tmp[i].d, tmp[i].d) << endl;
}
}
return 0;
}
赛后交流
在比赛结束后,会在交流群中给出比赛题解,同学们可以在赛后查看题解进行补题。
群号: 704572101,赛后大家可以一起交流做题思路,分享做题技巧,欢迎大家的加入。
原文地址:https://blog.csdn.net/Code_Shark/article/details/136388754
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!