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

Atcoder ABC 360 全题解

时间:2024-07-01 21:54:27浏览次数:18  
标签: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\)个盒子,最小化......