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

Atcoder ABC 360 全题解

时间：2024-07-01 21:54:27浏览次数：19  
标签：Atcoder ABC int 题解 ll tree ans mx mod

致歉

对不起，我不应该在全题解的编写上咕咕咕两个月，导致流量大量流失。

我知错了，下次还犯。

AB

无

C

考虑一个箱子里的所有球，我们需要把这些球放进互不相同的一些箱子里。然而我们可以留一个球在箱子里，显然留重量最大的最好，所以答案就是 $ \sum_{i=1}^{N} W_i $ 减去每个箱子里的最重的球的重量（没球的为 0）。

// Problem: C - Move It
// Contest: AtCoder - AtCoder Beginner Contest 360
// URL: https://atcoder.jp/contests/abc360/tasks/abc360_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

int a[100005], w[100005];
int sum[100005], mx[100005];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		a[i]--;
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &w[i]);
		sum[a[i]] += w[i];
		mx[a[i]] = max(mx[a[i]], w[i]);
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans += sum[i] - mx[i];
	}
	printf("%d", ans);
}

D

显然只有相对的两只蚂蚁可能相遇，所以我们可以先记录向右的蚂蚁坐标，然后对向左的蚂蚁使用二分。

假如两只蚂蚁各走了 $ K $ 个单位的长度，我们可以相对运动（bushi，把一只蚂蚁固定住，这时候另一只蚂蚁为了追上摆烂的蚂蚁（），就会以两倍的速度怒气冲冲的赶过去（）（）（）

所以对于一只位于 $ X $ 的，向左的蚂蚁，她（？）能遇到的向右的蚂蚁坐标就处在 $ X - 2T \sim X $ 中，然后就可以愉快的使用二分了。

// Problem: D - Ghost Ants
// Contest: AtCoder - AtCoder Beginner Contest 360
// URL: https://atcoder.jp/contests/abc360/tasks/abc360_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define ll long long
ll a[200005], b[200005];

int main() {
	int n;
	ll t;
	cin >> n >> t;
	string s;
	cin >> s;
	int p = 0, q = 0;
	for (int i = 0; i < n; i++) {
		ll x;
		scanf("%lld", &x);
		if (s[i] == '1') {
			a[p++] = x;
		} else {
			b[q++] = x;
		}
	}
	sort(a, a + p);
	ll ans = 0;
	for (int i = 0; i < q; i++) {
		ans += upper_bound(a, a + p, b[i]) - lower_bound(a, a + p, b[i] - t - t);
		// upper_bound(a, a + p, b[i]) 查询第一个 > b[i] 的，即太右的蚂蚁
		// lower_bound(a, a + p, b[i] - t - t) 查询第一个 >= b[i] - 2t 的，即可以在 t 时间内遇到的蚂蚁
	}
	printf("%lld", ans);
}

E

神仙期望。

期望是这样的，出题人只需要写标程得到一个半 rng 不 rand 的东西就可以了，而我们写各种程序凑到 $ \frac{1}{998244353} $ 的概率可就难了。

首先 1 和其它位置肯定要分开考虑，毕竟要是运气那么不好，一直没有交换，那么黑球就一直留在 1 上了。

考虑（某种意义上的）DP，设 $ f $ 和 $ g $ 为黑球在 1 上的概率和黑球不在 1 上的概率。

转移的概率：

  • $ f \to g : \cfrac{2}{N} - \cfrac{2}{N^2} $

  • $ g \to f : \cfrac{2}{N^2} $

  • $ f \to f : 1 - \cfrac{2}{N} + \cfrac{2}{N^2} $

  • $ g \to g : 1 - \cfrac{2}{N^2} $

然后进行转移。

易证如果不是 1 那么概率均等，所以最后的答案就是 $ f + (\cfrac{N}{2} + 1)g $。

// Problem: E - Random Swaps of Balls
// Contest: AtCoder - AtCoder Beginner Contest 360
// URL: https://atcoder.jp/contests/abc360/tasks/abc360_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mod 998244353

ll qpow(ll a, ll x, ll m) {
	ll ans = 1;
	while (x) {
		if (x & 1) {
			ans = ans * a % m;
		}
		x >>= 1;
		a = a * a % m;
	}
	return ans;
}

int main() {
	ll n, m;
	scanf("%lld %lld", &n, &m);
	ll on1 = 1, other = 0;
	ll other_1 = 2 * qpow(n, 2 * mod - 4, mod) % mod; // f -> g
	ll swapp = (2 * qpow(n, mod - 2, mod) % mod + 2 * (mod - qpow(n, 2 * mod - 4, mod)) % mod) % mod; // g -> f
	// 注 mod - x 在模 mod 意义下就相当于 -x
	for (int i = 0; i < m; i++) {
		ll n1 = 0, no = 0;
		// other + (1 other / other 1)
		n1 += other * other_1 % mod;
		// 1 + no swap
		n1 += on1 * (mod + 1 - swapp) % mod;
		// other + (bushi 1
		no += other * (mod + 1 - other_1) % mod;
		// 1 + swap
		no += on1 * swapp % mod;
		on1 = n1 % mod;
		other = no % mod;
	}
	printf("%lld", (on1 + (n * 499122177 + 1) % mod * other % mod) % mod); // 499122177 * 2 = 998244354
}

F

扫描线。

考虑将 $ (l, r) $ 表示成一个点。

那么，跟 $ (l, r) $ 相交的区间就会是两个长方形：$ 0 \le x \le l - 1, l + 1 \le y \le f - 1 $ 和 $ l + 1 \le x \le r - 1, r + 1 \le y \le 1e9 $，而我们要做的就是找到被长方形覆盖次数最多的一个点。

这个问题可以用扫描线解决，但是这里的线段树就简单很多了：区间修改，区间查询最大值，以及最大值中最前面的下标。

注意需要特判一下答案为 $ (0, 1) $ 的情况。

// Problem: F - InterSections
// Contest: AtCoder - AtCoder Beginner Contest 360
// URL: https://atcoder.jp/contests/abc360/tasks/abc360_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

// bool _st;

struct line { // 扫描“线”，使用一种差分
	int y, l, r, d;
	line(int _y = -1, int _l = -1, int _r = -1, int _d = 0) {
		y = _y, l = _l, r = _r, d = _d;
	}
} a[400005];

bool cmp(line a, line b) {
	// 优先比坐标，同坐标先加后减（因为我的代码是这么写的）
	if (a.y != b.y) {
		return a.y < b.y;
	} else {
		return a.d > b.d;
	}
}

namespace seg { // 线段树部分
	// 我选择动态开点
	int tot = 1, rt = 1;
	struct node {
		int idx, mx, l, r, tag;
		node() {
			idx = mx = l = r = tag = 0;
		}
	} tree[400005 << 5];
	void pushdown(int L, int R, int p) {
		int mid = (L + R) / 2;
		if (!tree[p].l) {
			tree[p].l = ++tot;
			tree[tree[p].l].idx = L;
		}
		tree[tree[p].l].mx += tree[p].tag;
		tree[tree[p].l].tag += tree[p].tag;
		if (!tree[p].r) {
			tree[p].r = ++tot;
			tree[tree[p].r].idx = mid + 1;
		}
		tree[tree[p].r].mx += tree[p].tag;
		tree[tree[p].r].tag += tree[p].tag;
		tree[p].tag = 0;
	}
	void update(int l, int r, int x, int L = 0, int R = 1e9, int &p = rt) {
		if (!p) {
			p = ++tot;
			tree[p].idx = L;
		}
		if (l <= L && R <= r) {
			tree[p].mx += x;
			tree[p].tag += x;
			return;
		}
		pushdown(L, R, p);
		int mid = (L + R) / 2;
		if (mid >= l) {
			update(l, r, x, L, mid, tree[p].l);
		}
		if (mid < r) {
			update(l, r, x, mid + 1, R, tree[p].r);
		}
		if (tree[tree[p].l].mx >= tree[tree[p].r].mx) {
			tree[p].idx = tree[tree[p].l].idx;
		} else {
			tree[p].idx = tree[tree[p].r].idx;
		}
		tree[p].mx = max(tree[tree[p].l].mx, tree[tree[p].r].mx);
	}
}

// bool _ed;

int main() {
	// cerr << (&_ed - &_st) / 1024.0 / 1024.0 << endl;
	int n;
	scanf("%d", &n);
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		int l, r;
		scanf("%d %d", &l, &r);
		// 将四条线按照差分的方式（我写的左闭右闭所以更新先加后减）
		a[cnt++] = line(0, l + 1, r - 1, 1);
		a[cnt++] = line(l - 1, l + 1, r - 1, -1);
		a[cnt++] = line(l + 1, r + 1, 1e9, 1);
		a[cnt++] = line(r - 1, r + 1, 1e9, -1);
	}
	sort(a, a + cnt, cmp);
	int l = 0, r = 1, mx = 0;
	for (int i = 0; i < cnt; i++) {
		seg::update(a[i].l, a[i].r, a[i].d);
		if (a[i].y >= 0 && seg::tree[1].mx > mx) { // a[i].y >= 0 就是所谓的特判
			mx = seg::tree[1].mx;
			l = a[i].y, r = seg::tree[1].idx;
		}
	}
	printf("%d %d", l, r);
}

G

震惊！某博主竟然自己 hack 了自己的 AC 做法！这究竟是 Atcoder 的不重视，还是博主的自虐？（）（）（）（）（）（）

先讲一下被我 hack 的做法。

（此处省略 ? 字）

那么正解是什么呢，其实正解是一个类 LIS 的 DP：

设 $ f_{i, j, 0/1} $ 为前 $ i $ 个，当前 LIS 的最后一个为 $ j $，现在用过/没用过超能力（）能得到的最大 LIS 是多长。

有两种转移方式：

  • $ 0 \to 0 $ ，$ 1 \to 1 $，正常转移即可。

  • $ 0 \to 1 $。

在 $ 0 \to 1 $ 的时候，必然是设成当前最大的 + 1 最好，不好也有个地方好（）

注：这题在离散化（我的做法）时有个小坑，由于这里 LIS 是要严格递增的，所以要把每个数和这个数 +1 都放进去再离散化。

// Problem: G - Suitable Edit for LIS
// Contest: AtCoder - AtCoder Beginner Contest 360
// URL: https://atcoder.jp/contests/abc360/tasks/abc360_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

int a[200005], b[400005];
int c0[400005], c1[400005];

// c0 是 f[][][0] 的树状数组，c1 是 f[][][1] 的

void update(int *c, int u, int x) {
	while (u < 400003) {
		c[u] = max(c[u], x);
		u += (u & -u);
	}
}

int query(int *c, int u) {
	int ans = 0;
	while (u) {
		ans = max(ans, c[u]);
		u -= (u & -u);
	}
	return ans;
}

int main() {
	int n;
	scanf("%d", &n);
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		b[++cnt] = a[i];
		b[++cnt] = a[i] + 1;
	}
	sort(b + 1, b + 1 + cnt);
	cnt = unique(b + 1, b + 1 + cnt) - b;
	for (int i = 1; i <= n; i++) { // 离散化
		a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b + 1;
	}
	int mx0 = 0;
	for (int i = 1; i <= n; i++) {
		update(c0, a[i], query(c0, a[i] - 1) + 1);
		update(c1, a[i], query(c1, a[i] - 1) + 1);
		update(c1, mx0 + 1, query(c0, mx0) + 1);
		// 第三句务必写在最后！（不然会出现一个阶段多次转移）
		mx0 = max(mx0, a[i]);
	}
	printf("%d", max(query(c0, 400003), query(c1, 400003)));
}

标签：Atcoder,ABC,int,题解,ll,tree,ans,mx,mod
From： https://www.cnblogs.com/AProblemSolver/p/18278832

相关文章

  • ABC 360
    submissionsA,B直接暴力。C我们发现在多余\(1\)个东西的箱子一定会有多的一部分被移走，我们贪心地移走花费少的。D发现必须是面对面的蚂蚁才能相遇。并且距离小于等于\(2T\)。直接二分即可。E这一场最有思维量的题。我们记录一个目前的期望位置\(x\)，每一次操作有\(fra......
  • CF1987E 题解
    CF1987E题解题意给定一棵大小为\(n\)的有根树，各点各有一点权\(a_i\)。每次操作可以选定一节点使其点权加一，求最小的操作数，使得任一节点满足其点权不大于其所有儿子的点权之和。\(n\le5000,0\lea_i\le10^9\)题解麻了，赛后十五分钟调出来，可惜为时已晚。读懂题之后......
  • CF1375D Replace by MEX 题解
    题目大意令mexmexmex为序列中最小的没有出现的数。给你一个长度为......
  • GESP 202406 四级认证 T1 题解
    大意：一个只包含000和111的矩形，边长为......
  • ## BZOJ2720 [Violet 5] 列队春游 题解
    Problem对于一个数列\(S\)，\(S_0=\infty\)，设对于\(S_i\)，\(S_{a_i}\)是\(S_i\)之前第一个大于等于\(S_i\)的数。给定\(S\)中的元素，求\(\sum_{i=1}^{n}(i-a_i)\)的期望。Solution我们考虑对于每一种身高的学生，分别统计期望。显然，对于身高为\(h\)的学生，只有身高为\(......
  • ata1.00: exception Emask 0x0 SAct 0x8000000 SErr 0x0 action 0x6 frozen 问题解析
    ata1.00:exceptionEmask0x0SAct0x8000000SErr0x0action0x6frozen硬盘问题测试发现嵌入式linuxvfat文件系统的sata固态硬盘偶然启动时出现异常打印如下：ata1.00:exceptionEmask0x0SAct0x8000000SErr0x0action0x6frozenata1.00:failedcommand:READFPD......
  • 第24节 习题解析
    第24节习题解析24.1-数据类型、控制结构、函数1、数据类型与表达式1.类型修饰符不能修饰_____ A.charB.intC.longintD.float2.下列选项中，合法的整型常量的是_____A.60 B.01a C.986,012 D.2e53.字符串"\t\v\\\0which\n"的长度是_____A......
  • [oeasy]python0023_[趣味拓展]Guido的简历_从ABC到python
    Guido的简历......
  • 通信原理练习题解析(详细版)
    文章目录说明选择填空简答分析计算说明部分内容，仅为个人观点，如有错误之处，欢迎交流！选择属于数字信号的是(A)​A:PCM信号B:PAM信号C:PDM信号D:PPM信号PCM信号（PulseCodeModulation，脉冲编码调制）：P将模拟信号转换为数字信号的方法PDM信号（PulseDensityModula......
  • Public Round #13 题解
    旋转序列来源：IzbornePripreme2022(CroatianIOI/CEOITeamSelection)Day1,ProblemBhttps://qoj.ac/contest/956/problem/4326两个串之间\(1\)匹配的次数总和为\(k\timesl\)，并且共有\(n\)次匹配。于是答案的上界为\(k\timesl\)个球放进\(n\)个盒子，最小化......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99