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

Atcoder ABC 350 全题解

时间：2024-04-21 17:35:18浏览次数：91  
标签：Atcoder cnt ABC int 题解 ++ color isbig white

题外话

别以为博主之前几场 ABC 都咕咕咕了，最近状态不好，这次 ABC 终于回来了（也有可能是题目变容易了，有图为证）
图片加载失败，但是Never gOnna gIve you uP

P.S. 请耐心看到最后！！否则后果自负！！！

AB

这年头谁不会 AB 啊

当然有。不学 OI 的人。

C

考虑选择排序，依次将 $ 1, 2, 3 \cdots $ 与它们应该在的位置进行交换。

那如果真的“选择”排序会 TLE。

把下标存起来，交换数的时候同时交换下标就可以了。

C 
// Problem: C - Sort
// Contest: AtCoder - AtCoder Beginner Contest 350
// URL: https://atcoder.jp/contests/abc350/tasks/abc350_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

int ansa[200005], ansb[200005];
int cnt = 0;

void print_swap(int u, int v) {
	if (u != v) {
		if (u < v) {
			ansa[cnt] = u, ansb[cnt] = v;
			cnt++;
		} else {
			ansa[cnt] = v, ansb[cnt] = u;
			cnt++;
		}
	}
}

int a[200005], b[200005];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		x--;
		a[i] = x;
		b[x] = i;
	}
	for (int i = 0; i < n; i++) {
		print_swap(i + 1, b[i] + 1);
		int x = a[i];
		swap(a[i], a[b[i]]);
		swap(b[x], b[i]);
	}
	printf("%d\n", cnt);
	for (int i = 0; i < cnt; i++) {
		printf("%d %d\n", ansa[i], ansb[i]);
	}
}

D

假如我们的图连通，那我们可以连距离为 $ 2 $ 的，距离为 $ 3 $ 的，以此类推，连成一张完全图。

那如果不联通，我们就把图视为一些连通图，统计最后有多少对好友，再减去 $ M $ 就可以了。

可以 dsu，可以 dfs。

D 
// Problem: D - New Friends
// Contest: AtCoder - AtCoder Beginner Contest 350
// URL: https://atcoder.jp/contests/abc350/tasks/abc350_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

int color[200005];
vector<int> graph[200005];

void dfs(int u, int co) { // 我用的是 dfs
	if (color[u] != -1) {
		return;
	}
	color[u] = co;
	for (int v : graph[u]) {
		dfs(v, co);
	}
}

int cnt[200005]; // 全 dfs 完了统一统计各颜色出现次数

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		u--, v--;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	memset(color, -1, sizeof color);
	for (int i = 0; i < n; i++) {
		dfs(i, i); // 染色
	}
	for (int i = 0; i < n; i++) {
		cnt[color[i]]++; // 统计
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		// cerr << cnt[i] << " ";
		ans += (1ll * cnt[i] * (cnt[i] - 1)); // 好友对数*2
	}
	printf("%lld", ans / 2 - m); // /2-m
}

E

期望 DP。

为了方便，接下来用 $ x / a $ 代表 $ \lfloor \cfrac{x}{a} \rfloor $。

先考虑一个最简单的柿子

\[f(n) = \min(f(n / A) + X, \cfrac{\sum_{i = 1}^{6} f(n / i)}{6} + Y) \]

那么这个式子是有后效性的。那怎么办捏。

很简单，一元一次方程谁不会解哪！设 $ f(n) $ 等于原先 $ \min $ 里右边的东西，解一下就行了。

可得

\[f(n) = \min(f(n / A) + X, \cfrac{\sum_{i = 1}^{5} f(n / i)}{5} + \frac{6}{5}Y) \]

一看数据范围……天哪！$ 10^{18} $ 怎么办？

其实想想就能知道状态数很少，因此 map + 记忆化搜索就行了。

E 
// Problem: E - Toward 0
// Contest: AtCoder - AtCoder Beginner Contest 350
// URL: https://atcoder.jp/contests/abc350/tasks/abc350_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

ll n, a, x, y;
double small[3000005]; // 为了保险我预处理了 <= 3000000 的答案
map<ll, double> f; // 记忆化搜索

double dfs(ll n) {
	if (n <= 3000000) {
		return small[n];
	} else if (f.count(n)) {
		return f[n];
	}
	return f[n] = min(dfs(n / a) + x, (dfs(n / 2) + dfs(n / 3) + dfs(n / 4) + dfs(n / 5) + dfs(n / 6)) / 5 + 6.0 / 5.0 * y); // 题解中给出的式子
}

int main() {
	scanf("%lld %lld %lld %lld", &n, &a, &x, &y);
	f[0] = 0;
	for (int i = 1; i <= 3000000; i++) { // 预处理部分
		// f[i] = min(f[i / a] + x, (f[i / 1] + f[i / 2] + f[i / 3] + f[i / 4] + f[i / 5] + f[i / 6]) / 6 + y);
		small[i] = min(small[i / a] + x, (small[i / 2] + small[i / 3] + small[i / 4] + small[i / 5] + small[i / 6]) / 5 + 6.0 / 5.0 * y);
	}
	printf("%.15f", dfs(n)); // 暴力搜
}

F

赛后补的。

假如是偶数层括号就正着处理，奇数层反着处理。那我们怎么快速做切换呢？

从头开始遍历，如果遇到括号，就跳到与之配对的括号并翻转方向（切换处理方向）即可。

F 

// Problem: F - Transpose
// Contest: AtCoder - AtCoder Beginner Contest 350
// URL: https://atcoder.jp/contests/abc350/tasks/abc350_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

stack<int> lbs;
int to[500005];

int main() {
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '(') {
			lbs.push(i);
		} else if (s[i] == ')') {
			to[lbs.top()] = i;
			to[i] = lbs.top();
			lbs.pop();
		}
	}
	int step = 1; // 方向
	string ans = "";
	for (int i = 0; i < s.size(); i += step) {
		if (s[i] == '(' || s[i] == ')') {
			step ^= -2; // step = -step
			i = to[i];
		} else {
			ans.push_back(s[i] ^ (step == 1 ? 0 : 32)); // 'a' ^ 'A' = 32
		}
	}
	cout << ans;
}

G

<++>

$ \color{white}{} $

$ \color{white}{} $

$ \color{white}{} $

$ \color{white}{} $

$ \color{white}{} $

$ \color{white}{} $

$ \color{white}{} $

$ \color{white}{} $

$ \color{white}{} $

$ \color{white}{} $

$ \color{white}{} $

$ \color{white}{} $

想必你是看了粗体字的人吧^_^

有三种思路，提供其中两种的思路，其中一种的代码。

sol1

根号分治。

众所不周知，根号分治大致就是把两种暴力拼起来。

暴力1：

考虑用 unordered_set 存图。
当查询 u,v 的时候，直接看 u 的邻居里有没有跟 v 相邻的。
时间复杂度 O(nq)，空间复杂度 O(n)。

暴力2：

将所有的答案存在一个二维数组里。
当加边的时候，就从两个点分别向邻居更新答案。
时间复杂度也是 O(nq)，空间复杂度 O(n^2)。

拼起来：

设邻居数 >= sqrt(N) 的为大点，其它的为小点。
将 <= sqrt(N) 个大点的答案放在二维数组里，空间复杂度 O(n)。
对于小点用 unordered_set 处理。接着考虑加边时。
如果一个点被提拔为大点了，那么把它加进大点群里。
在更新大点对大点时，用另一个点去更新大点到大点的答案。
由于有大点群所以时间复杂度（一次）是 O(sqrt n)。
查询的时候，如果有小点，那么用小点去暴力搜，时间复杂度是 O(sqrt n)。
否则直接查询二维数组。
总体时间复杂度为 $ O(n sqrt n) $。
G 
// Problem: G - Mediator
// Contest: AtCoder - AtCoder Beginner Contest 350
// URL: https://atcoder.jp/contests/abc350/tasks/abc350_g
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

#define ll long long
#define mod 998244353

int bigans[505][505], big[505], bigcnt;
int isbig[100005];
unordered_set<int> graph[100005];

int main() {
	int n, q;
	scanf("%d %d", &n, &q);
	int S = sqrt(n);
	int lastans = 0;
	while (q--) {
		ll a, b, c;
		scanf("%lld %lld %lld", &a, &b, &c);
		a = 1 + ((a * (1 + lastans) % mod) % 2);
		b = 1 + ((b * (1 + lastans) % mod) % n);
		c = 1 + ((c * (1 + lastans) % mod) % n);
		// cerr << a << " " << b << " " << c << endl;
		if (a == 1) {
			graph[b].insert(c);
			graph[c].insert(b);
			if (!isbig[b] && graph[b].size() >= S) {
				big[isbig[b] = ++bigcnt] = b;
				for (int i = 1; i <= bigcnt - 1; i++) {
					for (int d : graph[b]) {
						if (graph[d].count(big[i])) {
							bigans[i][isbig[b]] = d;
							bigans[isbig[b]][i] = d;
							break;
						}
					}
				}
			}
			if (!isbig[c] && graph[c].size() >= S) {
				big[isbig[c] = ++bigcnt] = c;
				for (int i = 1; i <= bigcnt - 1; i++) {
					for (int d : graph[c]) {
						if (graph[d].count(big[i])) {
							bigans[i][isbig[c]] = d;
							bigans[isbig[c]][i] = d;
							break;
						}
					}
				}
			}
			// if (bigcnt >= 500) {
				// puts("WArning");
				// return 0;
			// }
			if (isbig[b]) {
				for (int d : graph[c]) {
					if (isbig[d]) {
						bigans[isbig[b]][isbig[d]] = c;
						bigans[isbig[d]][isbig[b]] = c;
					}
				}
			}
			if (isbig[c]) {
				for (int d : graph[b]) {
					if (isbig[d]) {
						bigans[isbig[c]][isbig[d]] = b;
						bigans[isbig[d]][isbig[c]] = b;
					}
				}
			}
		} else {
			if (isbig[b] && isbig[c]) {
				printf("%d\n", lastans = bigans[isbig[b]][isbig[c]]);
				// cerr << lastans << endl;
				continue;
			}
			if (graph[b].size() > graph[c].size()) {
				swap(b, c);
			}
			bool flag = 0;
			for (int d : graph[b]) {
				if (graph[d].count(c)) {
					printf("%d\n", lastans = d);
					flag = 1;
					break;
				}
			}
			if (!flag) {
				printf("%d\n", lastans = 0);
			}
			// cerr << lastans << endl;
		}
	}
}

sol2

考虑并查集……里面的 fa。

查询 $ u, v $ 时，有三种可能答案不为 $ 0 $：

  • $ u = fa[fa[v]] $。

  • $ fa[u] = fa[v] $。

  • $ fa[fa[u]] = v $。

但是当连边的时候，并查集的整个结构可能要重构。（因此有了个离线的办法：提前先连一遍所有的边，固定结构，然后开搞，但这题强制在线）

放乐观点，重构就重构呗！启发式合并，重新计算 fa，照样能过。

点击查看代码 
不是我不是都说了只放一种思路的代码吗你怎么点进来了

标签：Atcoder,cnt,ABC,int,题解,++,color,isbig,white
From： https://www.cnblogs.com/AProblemSolver/p/18149138

相关文章

  • 题解：CF17D Notepad
    由于首位不能是\(0\)，因此首位有\(b-1\)种可能性。其他\(n-1\)位有\(b^{n-1}\)种可能。因此这些数总计\((b-1)b^{n-1}\)每页\(c\)个数，求最后一页有多少个数，即求\(\text{ans}=(b-1)b^{n-1}\quad\bmodc\)注意到题目中\(b,n\)都非常大，采用扩展欧拉定理进行降......
  • [ZJOI2019] 语言 题解
    不愧是\(ZJOI\)，《最可做的一道题》都让人一头雾水……首先将问题转化到链上。可以将总共的组数转化为每个点可以到达的城市。明显给每个点建一棵动态开点线段树，维护可以和他通商的点。很明显，可以通商的点的标号连续的一段。我们可以将可以将每一次传播语言的工作当作区间修改......
  • ABC-325
    D题目链接https://atcoder.jp/contests/abc325/tasks/abc325_d题目大意题目思路贪心，每一次优先选取最先出去的，优先队列！题目代码#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intn,ans;intmain(){ cin>>n; vector<array<ll,2>>a(n); for(......
  • ABC 287 B - Postal Card
    题目链接：由于是可以和\(T\)的多个字符串相同而仅计数一次，考虑把\(T\)中的字符串用\(\rmset\)存储已达到去重的目的。注：\(\rmset\)的\(\rmcount\)返回\(1\)表示找到了该元素，返回\(0\)则说明没找到。#include<bits/stdc++.h>usingi64=longlong;intmain......
  • 【题解】[NOIP2001 普及组] 装箱问题
    [NOIP2001普及组]装箱问题这是一道动态规划题。那就先定义状态吧（这里用的是一维滚动数组)。$f[j]$代表当我有$j$这么多容量可以用时，能装的最大重量是多少。好，状态定义好了再想状态转移方程。$f[j]$可以从哪里转移过来呢？想一想，当我们循环到第$i$个物品时，我们面临两个......
  • ABC 287 C - Path Graph?
    题目链接：首先根据条件$-对于所有i=1,2,…,N−1,有一条边连接顶点v_i$和\(v_{i+1}\)可以得到，路径图必须有\(N-1\)条边。其次，Ifintegers\(i\)and\(j\)satisfies\(1\leqi,j\leqN\)and\(|i-j|\geq2\),thenthereisnoedgethatconnectsvertices\(......
  • 简单的数学题 题解
    题意：解方程\[a^x\equivx\pmodm\]数据范围：\(a<m\le10^9\)Solution首先\(a^x\equiva^{x\bmod\varphi(m)+\varphi(m)}\pmodm\)我们设\(\text{solve}(\&x,y,m)\)表示解决\[a^{x\bmod\varphi(m)+y}\equivx\pmodm\]原题即\(\text{solve}(\&x,......
  • 数表 题解
    “当你想不出来一道题的时候就想一下排序”先不考虑\(a\)，求\[\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^m\sigma_1(\gcd(i,j))\\=&\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^{\min(n,m)}[d=\gcd(i,j)]\sigma_1(d)\\=&\sum_{d=1}^{\min(n,m)}\sigma_1(d)\sum_......
  • 最大幂指数 题解
    Statement\(f(x)\)表示\(x\)所含质因子的最大幂指数，对于\(T=10^4\)，\(a,b\le10^7\)，求\[\sum_{i=1}^a\sum_{j=1}^bf(\gcd(i,j))\]时限2sSolution\[\begin{aligned}&\sum_{i=1}^a\sum_{j=1}^bf(\gcd(i,j))\\=&\sum_{i=1}^a\sum_{j=1}^b\sum_{......
  • 一个人的数论 题解
    Solution令指数为\(k\)正常反演得到\[\sum_{d\midn}\mu(d)d^k\sum_{i=1}^{\fracnd}i^k\]设\(f(x)=\sum_{i=1}^xi^k\)，它是一个关于\(x\)的\(k+1\)次多项式求这个多项式可以插值\(\mathcalO(n^2)\)（推荐）高斯消元（待定系数法）\(\mathcalO(n^3)\)直接伯努利数\(\ma......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99