首页 > 其他分享 >Atcoder ABC 342 全题解

Atcoder ABC 342 全题解

时间：2024-02-25 12:11:09浏览次数：20  
标签：Atcoder ABC return min int 题解 ll max size

闲话

当我还是一个只会 AB 的小蒟蒻时，由于不会 C 又看不懂官方题解，只好看网上的题解。

结果：

ABC

签到题不讲

AB

对着题意模拟即可。

A 有个好玩的做法，先看前两个，如果不同跟第三个比较，如果相同看后面哪个字母跟第一个不一样。

C

由于是将所有的 $ c_i $ 替换，所以可得同一个字母最后替换成的字母都一样。

于是可以考虑 abcdefghijklmnopqrstuvwxyz 最后会变成什么。时间复杂度 $ O(26Q + N) $。

// Problem: C - Many Replacement
// Contest: AtCoder - HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）
// URL: https://atcoder.jp/contests/abc342/tasks/abc342_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#ifdef LOCAL
#include "debugger.h"
#define debug(x) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::print(x), cerr << endl)
#define debug_arr(x, n) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::printarr(x, n), cerr << endl)
#else
#include <bits/stdc++.h>
#define debug(x) 114514
#define debug_arr(x, n) 1919810
#endif

using namespace std;

#define ll long long
ll max(int a, ll b) { return max((ll)a, b); }
ll min(int a, ll b) { return min((ll)a, b); }
ll max(ll a, int b) { return max(a, (ll)b); }
ll min(ll a, int b) { return min(a, (ll)b); }
int max(int a, size_t b) { return max(a, (int)b); }
int min(int a, size_t b) { return min(a, (int)b); }
int max(size_t a, int b) { return max((int)a, b); }
int min(size_t a, int b) { return min((int)a, b); }

// Your code goes here...

char to[128];

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
	for (char i = 'a'; i <= 'z'; i++) {
		to[i] = i;
	}
	int q;
	scanf("%d", &q);
	while (q--) {
		char x, y;
		cin >> x >> y;
		for (char i = 'a'; i <= 'z'; i++) {
			if (to[i] == x) {
				to[i] = y;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		putchar(to[s[i]]);
	}
}

D

首先是一个重要的性质，平方数的只质因数分解：

\[x^2 = p_1^{2e_1} \times p_2^{2e_2} \times \cdots \times p_k^{2e_k} \]

那么对于 $ x^2 = ab $ 里面每个质因子，要么 $ a $ 和 $ b $ 里面都有奇数个，要么都有偶数个。

于是可以将 $ a, b $ 都除以最大能整除的平方，然后开个桶计数就可以了。

// Problem: D - Square Pair
// Contest: AtCoder - HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）
// URL: https://atcoder.jp/contests/abc342/tasks/abc342_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#ifdef LOCAL
#include "debugger.h"
#define debug(x) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::print(x), cerr << endl)
#define debug_arr(x, n) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::printarr(x, n), cerr << endl)
#else
#include <bits/stdc++.h>
#define debug(x) 114514
#define debug_arr(x, n) 1919810
#endif

using namespace std;

#define ll long long
ll max(int a, ll b) { return max((ll)a, b); }
ll min(int a, ll b) { return min((ll)a, b); }
ll max(ll a, int b) { return max(a, (ll)b); }
ll min(ll a, int b) { return min(a, (ll)b); }
int max(int a, size_t b) { return max(a, (int)b); }
int min(int a, size_t b) { return min(a, (int)b); }
int max(size_t a, int b) { return max((int)a, b); }
int min(size_t a, int b) { return min((int)a, b); }

// Your code goes here...

int a[200005], cnt[200005];

int main() {
	int m;
	scanf("%d", &m);
	ll ans = 0;
	int n = 0, zero = 0;
	for (int i = 0; i < m; i++) {
		int x;
		scanf("%d", &x);
		if (x == 0) {
			ans += m - 1;
			zero++;
		} else {
			a[n++] = x;
		}
	}
	ans -= 1ll * zero * (zero - 1) / 2;
	for (int i = 0; i < n; 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 < n; i++) {
		ans += cnt[a[i]];
		cnt[a[i]]++;
	}
	printf("%lld", ans);
}

E

这场我先做的 F 再做的 E，幸好我 F 写的是树状数组，不然我就没时间调 E 了。

image

好的那么正向很难搞，那我们能不能时光倒流呢？

答案是可以的。然后改改 dij 就可以了。

具体做法就是建反图，经过一条边时考虑能赶上的最晚的火车（时光倒流了所以选最晚的），没有就当这条边不存在，否则就用这班火车过去。

// Problem: E - Last Train
// Contest: AtCoder - HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）
// URL: https://atcoder.jp/contests/abc342/tasks/abc342_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#ifdef LOCAL
#include "debugger.h"
#define debug(x) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::print(x), cerr << endl)
#define debug_arr(x, n) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::printarr(x, n), cerr << endl)
#else
#include <bits/stdc++.h>
#define debug(x) 114514
#define debug_arr(x, n) 1919810
#endif

using namespace std;

#define ll long long
ll max(int a, ll b) { return max((ll)a, b); }
ll min(int a, ll b) { return min((ll)a, b); }
ll max(ll a, int b) { return max(a, (ll)b); }
ll min(ll a, int b) { return min(a, (ll)b); }
int max(int a, size_t b) { return max(a, (int)b); }
int min(int a, size_t b) { return min(a, (int)b); }
int max(size_t a, int b) { return max((int)a, b); }
int min(size_t a, int b) { return min((int)a, b); }

// Your code goes here...

struct train {
	ll l, d, k, c;
	int v;
	train(ll _l, ll _d, ll _k, ll _c, int _v) {
		l = _l, d = _d, k = _k, c = _c, v = _v;
	}
};

vector<train> graph[200005];
ll f[200005];
priority_queue<pair<ll, int> > que;

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		ll l, d, k, c;
		int a, b;
		scanf("%lld %lld %lld %lld %d %d", &l, &d, &k, &c, &a, &b);
		graph[b].push_back(train(l + (k - 1) * d + c, d, k, c, a));
	}
	memset(f, -1, sizeof f);
	f[n] = 1e18 + 1e9;
	que.emplace(1e18 + 1e9, n);
	while (que.size()) {
		ll now = que.top().first;
		int u = que.top().second;
		que.pop();
		if (f[u] < now) {
			continue;
		}
		for (auto eg : graph[u]) {
			int v = eg.v;
			ll tim = now / eg.d * eg.d + eg.l % eg.d;
			if (tim > now) {
				tim -= eg.d;
			}
			tim = min(tim, eg.l);
			if (tim >= eg.l - (eg.k - 1) * eg.d && tim - eg.c > f[v]) {
				f[v] = tim - eg.c;
				que.emplace(f[v], v);
			}
		}
	}
	for (int i = 1; i < n; i++) {
		if (f[i] == -1) {
			puts("Unreachable");
		} else {
			printf("%lld\n", f[i]);
		}
	}
}

F

据说 Black Jack 是扑克牌 21 点加上一些奇奇怪怪的规则，这也解释了为什么 $ x > N $ 你就输了（笑）

称你的敌人为庄家。

首先，由于庄家的策略固定，所以你可以先处理出庄家停在每一个点上的概率。有了这个概率，你就可以用前缀和 $ O(1) $ 计算当 $ x = i $ 时你赢的概率，把这个算你赢的概率的函数叫做 $ \operatorname{solve} $。

接下来考虑你赢的概率，设 $ f_i $ 为假如你当前点数为 $ i $，在最优策略下你赢的概率。

假如你扔骰子，那么赢的概率就是 $ \cfrac{\sum_{k=1}^{D} f_{i+k}}{D} $。

假如你不扔，那么赢的概率就是 $ g(i) $。

所以可得出状态转移方程（注意需要倒着转移）：

\[f_i = \max(\cfrac{\sum_{k=1}^{D} f_{i+k}}{D}, \operatorname{solve}(i)) \]

最终的答案就是 $ f_0 $。

那么庄家的点数概率该怎么算呢？

设这个数组为 $ g $。

接下来，将 $ i $ 从 $ 1 $ 循环到 $ L - 1 $，将 $ g_i $ 的概率平均分配到 $ g_{i + 1} \sim g_{i + D} $。

然后就可以了。别问我为什么？

问题来了，显然我们不能 $ O(LD) $ 搞这个，那我们怎么做呢？

其实这个就是区间修改单点查询，差分版树状数组维护一下就可以了。

最后一个小问题：$ \operatorname{solve} $ 怎么求呢？

很简单，考虑是 $ y > N $ 赢的还是 $ x > y $ 赢的，将 $ g $ 数组前缀和就可以了。

友情提醒：数组要开到 $ 400000 $。

// Problem: F - Black Jack
// Contest: AtCoder - HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）
// URL: https://atcoder.jp/contests/abc342/tasks/abc342_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#ifdef LOCAL
#include "debugger.h"
#define debug(x) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::print(x), cerr << endl)
#define debug_arr(x, n) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::printarr(x, n), cerr << endl)
#else
#include <bits/stdc++.h>
#define debug(x) 114514
#define debug_arr(x, n) 1919810
#endif

using namespace std;

#define ll long long
ll max(int a, ll b) { return max((ll)a, b); }
ll min(int a, ll b) { return min((ll)a, b); }
ll max(ll a, int b) { return max(a, (ll)b); }
ll min(ll a, int b) { return min(a, (ll)b); }
int max(int a, size_t b) { return max(a, (int)b); }
int min(int a, size_t b) { return min(a, (int)b); }
int max(size_t a, int b) { return max((int)a, b); }
int min(size_t a, int b) { return min((int)a, b); }

// Your code goes here...

namespace bit {
	double c[400005];
	void _update(int i, double x) {
		i++;
		while (i < 400003) {
			c[i] += x;
			i += (i & -i);
		}
	}
	void update(int l, int r, double x) {
		_update(l, x);
		_update(r + 1, -x);
	}
	double query(int x) {
		x++;
		double ans = 0;
		while (x) {
			ans += c[x];
			x -= (x & -x);
		}
		return ans;
	}
};

int n, l, d;
double g[400005];

void calc_g() {
	// g[i]: 庄家点数为 i 的概率，前缀和
	bit::update(0, 0, 1);
	for (int i = 0; i <= 400000; i++) {
		g[i] = bit::query(i);
		if (i < l) {
			bit::update(i + 1, i + d, g[i] / d);
			g[i] = 0;
		}
	}
	for (int i = 1; i <= 400000; i++) {
		g[i] += g[i - 1];
	}
}

double f[400005];

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 calc_f() {
	// f[i]: 你当前为 i，赢的概率
	// solve(i): x = i 赢的概率
	// f[i] = max((f[i + 1] + f[i + 2] + ... + f[i + d]) / d, solve(i))
	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);
	calc_g();
	calc_f();
	printf("%.15f", f[0]);
}

G

赛后补的。

假如没有 2 操作，那么可以用线段树，配合标记永久化实现。

那么 2 操作怎么搞呢？

这时候，我们就要用到一个高大上的东西：erasable_priority_queue！

???：说的这么好听，不就是 multiset 吗？

这个有什么用呢？

在更新的时候，我们不再是直接更新 $ \max $，而是插入一个 multiset，询问的时候取 multiset 最后一个元素。

这样，2 操作直接从 multiset 里删除就可以了。

好像也可以用分块。

// Problem: G - Retroactive Range Chmax
// Contest: AtCoder - HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）
// URL: https://atcoder.jp/contests/abc342/tasks/abc342_g
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#ifdef LOCAL
#include "debugger.h"
#define debug(x) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::print(x), cerr << endl)
#define debug_arr(x, n) (cerr << "LINE " << __LINE__ << ", " << #x << " = ", __HARVEY_DEBUG__::printarr(x, n), cerr << endl)
#else
#include <bits/stdc++.h>
#define debug(x) 114514
#define debug_arr(x, n) 1919810
#endif

using namespace std;

#define ll long long
ll max(int a, ll b) { return max((ll)a, b); }
ll min(int a, ll b) { return min((ll)a, b); }
ll max(ll a, int b) { return max(a, (ll)b); }
ll min(ll a, int b) { return min(a, (ll)b); }
int max(int a, size_t b) { return max(a, (int)b); }
int min(int a, size_t b) { return min(a, (int)b); }
int max(size_t a, int b) { return max((int)a, b); }
int min(size_t a, int b) { return min((int)a, b); }

// Your code goes here...

multiset<int> tree[800005];

void update(int L, int R, int x, int l, int r, int p) {
	if (L <= l && r <= R) {
		tree[p].insert(x);
		return;
	}
	int mid = (l + r) / 2;
	if (mid >= L) {
		update(L, R, x, l, mid, p * 2);
	}
	if (mid < R) {
		update(L, R, x, mid + 1, r, p * 2 + 1);
	}
}

void cancel(int L, int R, int x, int l, int r, int p) {
	if (L <= l && r <= R) {
		tree[p].erase(tree[p].find(x));
		return;
	}
	int mid = (l + r) / 2;
	if (mid >= L) {
		cancel(L, R, x, l, mid, p * 2);
	}
	if (mid < R) {
		cancel(L, R, x, mid + 1, r, p * 2 + 1);
	}
}

int query(int x, int l, int r, int p) {
	int ans = (tree[p].size() ? (*tree[p].rbegin()) : 0);
	if (l != r) {
		int mid = (l + r) / 2;
		if (x <= mid) {
			ans = max(ans, query(x, l, mid, p * 2));
		} else {
			ans = max(ans, query(x, mid + 1, r, p * 2 + 1));
		}
	}
	return ans;
}

struct qry {
	int l = -1, r = -1, x = 0;
} a[200005];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		update(i, i, x, 1, n, 1);
	}
	int q;
	scanf("%d", &q);
	for (int i = 1; i <= q; i++) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d %d %d", &a[i].l, &a[i].r, &a[i].x);
			update(a[i].l, a[i].r, a[i].x, 1, n, 1);
		} else if (op == 2) {
			int x;
			scanf("%d", &x);
			cancel(a[x].l, a[x].r, a[x].x, 1, n, 1);
		} else {
			int x;
			scanf("%d", &x);
			printf("%d\n", query(x, 1, n, 1));
		}
	}
}

标签：Atcoder,ABC,return,min,int,题解,ll,max,size
From： https://www.cnblogs.com/AProblemSolver/p/18032209

相关文章

  • CF1930E 2..3...4.... Wonderful! Wonderful! 题解
    DescriptionStackhasanarray$a$oflength$n$suchthat$a_i=i$forall$i$($1\leqi\leqn$).Hewillselectapositiveinteger$k$($1\leqk\leq\lfloor\frac{n-1}{2}\rfloor$)anddothefollowingoperationon$a$an......
  • [ARC155D] Avoid Coprime Game 题解
    Description非负整数\(x,y\)的最大公约数记为\(\gcd(x,y)\)，规定\(\gcd(x,0)=\gcd(0,x)=x\)。黑板上写了\(N\)个整数\(A_1,A_2,...,A_N\)，这\(N\)个数的最大公约数是\(1\)。Takahashi和Aoki在玩游戏，有一个变量\(G\)初值为\(0\)，他们轮流进行以下操作：从黑板上选择......
  • 2024牛客寒假算法基础集训营4个人补题题解（B、E）
    B、左右互博不能操作的情况有且仅有所有石子堆的石子个数只有1的时候，因此不管途中怎么操作，让所有石子堆都变成1的总操作次数是确定的。即假设一共有\(n\)堆石子，石子总数为\(sum\)，总操作次数为\((sum-n)\)次。因此当\((sum-n)\)%\(2=0\)时一定在sweet操作完（或没有操作）后gui无法......
  • CF1832B Maximum Sum 题解
    【题目描述】给定一个长度为\(n\)的数列，其中每个元素互不相同，进行\(k\)次操作，每次可以选择删除序列中最小的两个数或最大的一个数。求操作后剩余数的和的最大值。【思路】我们构造一组数据：首先我们看到题目中的一句话：每次可以选择删除序列中最小的两个数或最大的一个数。......
  • CF1857B Maximum Rounding 题解
    题目描述给定一个自然数\(n\)，可以对任意一位进行四舍五入，可以进行任意次，求能得到的最大数。（这里的\(n\)没有前导零）思路首先我们发现，如果我们将其中一位进位了，那后面的所有位都会变成\(0\)，因此，如果我们进位了两次，那么位置靠后的那次进位，其实是没有用的。所以我们要从高位往......
  • CF1857G Counting Graphs 题解
    题目描述给定一棵最小生成树，求有多少张图的最小生成树是给定的树，并且这张图的所有边边权不超过\(S\)。思路考虑在最小生成树中加边。我们回顾一下Kruskal的过程：找到没被用过的，最小的边判断这条边的两端是否在一个联通块中加入这条边，将两端的联通块连在一起根据第三条......
  • P9562 [SDCPC2023] G-Matching 题解
    题目描述给定长度为\(n\)的整数序列\(a_1,a_2,\cdots,a_n\)，我们将从该序列中构造出一张无向图\(G\)。具体来说，对于所有\(1\lei<j\len\)，若\(i-j=a_i-a_j\)，则\(G\)中将存在一条连接节点\(i\)与\(j\)的无向边，其边权为\((a_i+a_j)\)。求\(G\)的一个......
  • CF1832B Maximum Sum 题解
    【题目描述】给定一个长度为\(n\)的数列，其中每个元素互不相同，进行\(k\)次操作，每次可以选择删除序列中最小的两个数或最大的一个数。求操作后剩余数的和的最大值。【思路】我们构造一组数据：首先我们看到题目中的一句话：每次可以选择删除序列中最小的两个数或最大的一个数。......
  • P4569 [BJWC2011] 禁忌 题解
    题目传送门前置知识AC自动机|矩阵加速递推解法对于一段固定的文本串，由于重叠的模式串不对伤害产生贡献，故考虑贪心，每碰到出现一个模式串将其分为一段，最终这个文本串的伤害就是划分次数。类似luoguP3193[HNOI2008]GT考试，令\(f_{i,j}\)表示前\(i\)个字符，当前运行到......
  • AT_abc341_g [ABC341G] Highest Ratio 题解
    题目传送门前置知识单调栈简化题意给定一个长度为\(n\)的序列\(a\)。对于所有的\(l(1\lel\len)\)，均求出\(\max\limits_{r=l}^{n}\{\frac{\sum\limits_{i=l}^{r}a_{i}}{r-l+1}\}\)。解法令\(sum_{i}=\sum\limits_{j=1}^{i}a_{j},P_{i}=(i,sum_{i})\)，则有\(\beg......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99