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

Atcoder ABC 351 全题解

时间：2024-04-29 22:14:12浏览次数：17  
标签：Atcoder ABC 200005 int 题解 ll pos ++ ans

乾岩

我：G 题来咯！！！

大火：这 G 题，大家都不敢做，说是有人在里面放了毒瘤。

我：做，做，为什么不做！不做也别想活着！！！

（两天后）

我：我的 G 题完成辣！！！！！！

image

AB

不讲

C

显然 $ 2^a * 2 = 2^{a+1} $。

考虑用一个栈存球的大小是 $ 2 $ 的多少次方，每次插入球后，不断取出后面两个球，大小相同则合并，否则插入下一个球。

// Problem: C - Merge the balls
// Contest: AtCoder - AtCoder Beginner Contest 351
// URL: https://atcoder.jp/contests/abc351/tasks/abc351_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

// 简短的代码，qwq

int main() {
	int n;
	scanf("%d", &n);
	stack<int> stk;
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		while (stk.size() && stk.top() == x) { // 大小相同
			stk.pop();
			x++; // 则合并
		}
		stk.push(x);
	}
	printf("%d", stk.size());
}

D

首先，我们把 # 的上下左右的 . 都改成 ,。

众所周知，这道题可以 dfs $ O(NM) $ 遍，但是速度太慢，为 $ O(N^2 M^2) $。

考虑到一个 . 的 4-联通块里每个格子的答案都是一样的，所以就可以优化到 $ O(NM) $。

现在考虑如何统计个数。

如果每次 dfs 前都将 vis 数组清 0，那么时间复杂度又会退化到 $ O(N^2 M^2) $。

所以我们可以在 dfs 时携带一种颜色进行 dfs，遇到逗号都加上。


// Problem: D - Grid and Magnet
// Contest: AtCoder - AtCoder Beginner Contest 351
// URL: https://atcoder.jp/contests/abc351/tasks/abc351_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

int n, m;
char s[1005][1005];
int vis[1005][1005];

void dfs(int r, int c, int& ans, int color) { // dfs
	if (!(1 <= r && r <= n && 1 <= c && c <= m)) {
		return;
	} else if (vis[r][c] == color) { // 其它颜色也不返回，因为有逗号
		return;
	}
	vis[r][c] = color;
	ans++; // 先加再说
	if (s[r][c] == ',') {
		return;
	}
	// 为什么不考虑 '#' 呢，因为我们根本没法进入 '#'（都要先进入 ','）
	dfs(r + 1, c, ans, color);
	dfs(r - 1, c, ans, color);
	dfs(r, c + 1, ans, color);
	dfs(r, c - 1, ans, color);
}

int main() {
	scanf("%d %d", &n, &m);
	memset(s, '.', sizeof s);
	for (int i = 1; i <= n; i++) {
		scanf("%s", s[i] + 1);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (s[i][j] == '#') { // ASCII 码序：'.' > ',' > '#'
				s[i - 1][j] = min(s[i - 1][j], ',');
				s[i + 1][j] = min(s[i + 1][j], ',');
				s[i][j - 1] = min(s[i][j - 1], ',');
				s[i][j + 1] = min(s[i][j + 1], ',');
			}
		}
	}
	int ans = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!vis[i][j] && s[i][j] == '.') { // 进行 dfs
				int x = 0;
				dfs(i, j, x, i * n + j); // 直接用格子在一维上的编号作为颜色
				ans = max(ans, x);
			}
		}
	}
	printf("%d", ans);
}

E

首先，按照兔子的跳跃方式，我们可以把格子分成两类：$ x + y $ 是奇数和 $ x + y $ 是偶数。同类格子一定可以互相抵达，异类一定不行。

其次，只要你盯了这题足够长时间（？，你就会发现同类格子之间的距离是切比雪夫距离。

再次，你可以发现这个玩意改成曼哈顿距离很好算。

最后，你 bdfs，找到了切比雪夫转曼哈顿的办法。

转换上边说了，这里只说曼哈顿距离和的求法。

曼哈顿距离的两维是独立的，所以可以考虑一条直线上的情况。答案等于图中（请自行想象）所有的线段长度和。

那么，$ i \sim i + 1 $ 这条小线段就对答案贡献了 $ i \times (n - i) $ 次，即左边的点数乘右边的点数，请读者自行证明，易证，不难（（（

最后，伸手党们，我把链接丢给你们，行了吧！！！

// Problem: E - Jump Distance Sum
// Contest: AtCoder - AtCoder Beginner Contest 351
// URL: https://atcoder.jp/contests/abc351/tasks/abc351_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// oi.wiki/geometry/distance/#曼哈顿距离与切比雪夫距离的相互转化

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

#define ll long long

pair<int, int> odd[200005], even[200005];

bool cmpbyse(pair<int, int> a, pair<int, int> b) { // 默认以 x 排序，但我们还需要按 y 排一次
	return (a.second < b.second);
}

int main() {
	int n;
	scanf("%d", &n);
	int on = 0, en = 0; // 两种点的数量
	for (int i = 0; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		if ((x + y) & 1) {
			odd[on++] = make_pair(x + y, x - y); // 懒得用浮点，直接除以 2（计算时）
		} else {
			even[en++] = make_pair(x + y, x - y);
		}
	}
	ll ans = 0;
	sort(odd, odd + on); // 奇点 x
	for (int i = 0; i < on - 1; i++) {
		ans += 1ll * (i + 1) * (on - i - 1) * (odd[i + 1].first - odd[i].first) / 2; // 我是 0 下标的，所以还得 +1
	}
	sort(odd, odd + on, cmpbyse); // 奇点 y
	for (int i = 0; i < on - 1; i++) {
		ans += 1ll * (i + 1) * (on - i - 1) * (odd[i + 1].second - odd[i].second) / 2;
	}
	sort(even, even + en); // 偶点 x
	for (int i = 0; i < en - 1; i++) {
		ans += 1ll * (i + 1) * (en - i - 1) * (even[i + 1].first - even[i].first) / 2;
	}
	sort(even, even + en, cmpbyse); // 偶点 y
	for (int i = 0; i < en - 1; i++) {
		ans += 1ll * (i + 1) * (en - i - 1) * (even[i + 1].second - even[i].second) / 2;
	}
	printf("%lld", ans);
}

F

本次 F 题很水，至少比 E 水，有可能比 D 水，有人说比 C 水（那位哥们甚至打了三个大于号），这就太过分了吧（恼

一个数对答案造成的贡献来源于所有比它小的数，所以可以开一个树状数组。

假如数组是升序的，那么 $ i $ 对答案的贡献为：

\[C_i = \sum_{j = 1}^i A_i - A_j = iA_i - \sum_{j=1}^{i} A_j \]

所以可以开两个树状数组，一个记录和，一个记录个数。

数很大，要离散化。

// Problem: F - Double Sum
// Contest: AtCoder - AtCoder Beginner Contest 351
// URL: https://atcoder.jp/contests/abc351/tasks/abc351_f
// 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 cn[400005], cs[400005]; // cn 统计个数，cs 统计和

void update(ll* c, int pos, int val) { // 树状数组部分
	pos++;
	while (pos < 400003) {
		c[pos] += val;
		pos += (pos & -pos);
	}
}

ll query(ll* c, int pos) {
	pos++;
	ll ans = 0;
	while (pos) {
		ans += c[pos];
		pos -= (pos & -pos);
	}
	return ans;
}

ll num[400005]; // 离散化
ll a[400005];

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &a[i]);
		num[i] = a[i];
	}
	sort(num, num + n);
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		int pos = lower_bound(num, num + n, a[i]) - num;
		ans += query(cn, pos - 1) * a[i] - query(cs, pos - 1); // numA_i - sum
		update(cn, pos, 1), update(cs, pos, a[i]); // 更新
	}
	printf("%lld", ans);
}

G

曾经写过的代码最长的题。

对于这种树上修改的题就直接放一个树剖上去准没错。（）

考虑对于每个点 $ i $ 定义一个函数 $ g_i(x) $，代表如果它的重儿子的 hash 为 $ x $，那么这个点的 hash 是多少。很显然 $ g_i(x) = Sx + A_i $，其中 $ S $ 为 $ i $ 的轻儿子的 hash 积。

当我们查询一个点 $ i $ 的 hash 值 $ f(i) $ 时，就可以直接用 $ f(i) = g_i(f(hson_i)) $。当然 $ f(hson_i) $ 也可以这么展开，最后整个函数就变成了 $ f(i) = g_{p_1}(g_{p_2}(...g_{p_k}(0))) $，其中 $ p $ 是以 $ i $ 打头的重链。

那么考虑到 $ g $ 是一堆一元一次函数，所以可以用线段树维护。具体做法为 $ a(cx + d) + b = acx + ad + b $。

另外，在更新时我们也需要高效的更新 $ S $。考虑从 $ 1 $ 到 $ u $ 的路径上哪些点的 $ S $ 会发生变化。

观察可得，在这条路径上，$ x $ 的父节点的 $ g $ 被更新，说明 $ x $ 是轻儿子。再由树剖可得，轻儿子不会超过 $ O(log \ dep) $ 个。

所以不断往上跳重链，每次将链顶和链顶的 father 更新一下即可。求 $ S $ 可以用逆元，我学题解用了 bfs 序。

（下面的节点怎么办呢？直接烂尾，反正求最终答案用不着它们。）

// Problem: G - Hash on Tree
// Contest: AtCoder - AtCoder Beginner Contest 351
// URL: https://atcoder.jp/contests/abc351/tasks/abc351_g
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

#define mod 998244353
#define ll long long

int n;
ll nodeval[200005], initf[200005], initk[200005], initb[200005];

namespace hld {
	vector<int> graph[200005];
	int fa[200005], sz[200005], hson[200005];
	int dfn[200005], rnk[200005], top[200005]; // 树剖
	int bfnl[200005], bfnr[200005], rbfn[200005], allh[200005]; // bfs 序，最后一个儿子的 bfs 序，反 bfn（just like rnk），u 打头的重链
	// 树剖剖树
	void dfs1(int u) {
		sz[u] = 1;
		hson[u] = -1;
		for (int v : graph[u]) {
			dfs1(v);
			sz[u] += sz[v];
			if (hson[u] == -1 || sz[v] > sz[hson[u]]) {
				hson[u] = v;
			}
		}
	}
	int _tim = 0;
	int dfs2(int u, int tp) { // 树剖同时求出初始 hash 与函数
		initk[u] = 1, initb[u] = nodeval[u], initf[u] = nodeval[u];
		top[u] = tp;
		dfn[u] = _tim++;
		rnk[dfn[u]] = u;
		if (hson[u] == -1) {
			initk[u] = 0;
			return allh[u] = u;
		}
		int ans = dfs2(hson[u], tp);
		for (int v : graph[u]) {
			if (v != hson[u]) {
				dfs2(v, v);
				initk[u] = (initk[u] * initf[v]) % mod;
			}
		}
		initf[u] = (initk[u] * initf[hson[u]] + initb[u]) % mod;
		return allh[u] = ans; // 顺着重儿子找最重的节点
	}
	void bfs() { // bfs 序
		queue<int> que;
		que.push(0);
		int tim = 0;
		while (que.size()) {
			int u = que.front();
			que.pop();
			bfnl[u] = tim++;
			rbfn[bfnl[u]] = u;
			if (u) {
				bfnr[fa[u]] = max(bfnr[fa[u]], bfnl[u]);
			}
			if (hson[u] == -1) {
				continue;
			}
			que.push(hson[u]);
			for (int v : graph[u]) {
				if (v != hson[u]) {
					que.push(v);
				}
			}
		}
	}
};

using namespace hld;

namespace func_seg {
	// 一个用来记录一元一次函数的 segtree
	struct Node {
		ll k, b;
		Node(ll _k = -1, ll _b = -1) {
			k = _k, b = _b;
		}
	} tree[800005];
	Node merge(Node a, Node b) {
		return Node(a.k * b.k % mod, (a.k * b.b + a.b) % mod);
	}
	void build(int l, int r, int p) {
		if (l == r) {
			tree[p] = Node(initk[rnk[l]], initb[rnk[l]]);
		} else {
			int mid = (l + r) / 2;
			build(l, mid, p * 2);
			build(mid + 1, r, p * 2 + 1);
			tree[p] = merge(tree[p * 2], tree[p * 2 + 1]);
		}
	}
	void update(int pos, Node val, int l, int r, int p) {
		if (l == r) {
			tree[p] = val;
			return;
		}
		int mid = (l + r) / 2;
		if (pos <= mid) {
			update(pos, val, l, mid, p * 2);
		} else {
			update(pos, val, mid + 1, r, p * 2 + 1);
		}
		tree[p] = merge(tree[p * 2], tree[p * 2 + 1]);
	}
	Node query(int L, int R, int l, int r, int p) {
		if (L <= l && r <= R) {
			return tree[p];
		}
		int mid = (l + r) / 2;
		Node ans = Node(1, 0);
		if (L <= mid) {
			ans = merge(ans, query(L, R, l, mid, p * 2));
		}
		if (mid < R) {
			ans = merge(ans, query(L, R, mid + 1, r, p * 2 + 1));
		}
		return ans;
	}
};

using func_seg::Node;

namespace lp_seg {
	// 记录 light product 的 segtree，其实就是普通的乘法线段树
	ll prod[800005];
	void build(int l, int r, int p, ll* a) {
		if (l == r) {
			prod[p] = a[rbfn[l]];
		} else {
			int mid = (l + r) / 2;
			build(l, mid, p * 2, a);
			build(mid + 1, r, p * 2 + 1, a);
			prod[p] = prod[p * 2] * prod[p * 2 + 1] % mod;
		}
	}
	void update(int pos, ll val, int l, int r, int p) {
		if (l == r) {
			prod[p] = val;
			return;
		}
		int mid = (l + r) / 2;
		if (pos <= mid) {
			update(pos, val, l, mid, p * 2);
		} else {
			update(pos, val, mid + 1, r, p * 2 + 1);
		}
		prod[p] = prod[p * 2] * prod[p * 2 + 1] % mod;
	}
	ll query(int L, int R, int l, int r, int p) {
		if (L <= l && r <= R) {
			return prod[p];
		}
		int mid = (l + r) / 2;
		ll ans = 1;
		if (L <= mid) {
			ans = ans * query(L, R, l, mid, p * 2) % mod;
		}
		if (mid < R) {
			ans = ans * query(L, R, mid + 1, r, p * 2 + 1) % mod;
		}
		return ans;
	}
};

void link_update(int u) { // 林克专属的 update（bushi（其实是连接两棵线段树的 update）
	ll k = (graph[u].size() ? lp_seg::query(bfnl[hson[u]] + 1, bfnr[u], 0, n - 1, 1) : 0); // 重求倍数
	ll b = nodeval[u]; // 不必多说
	func_seg::update(dfn[u], Node(k, b), 0, n - 1, 1);
}

ll gethash(int u) { // hash
	return func_seg::query(dfn[u], dfn[allh[u]], 0, n - 1, 1).b;
}

int main() {
	int q;
	scanf("%d %d", &n, &q);
	fa[0] = -1;
	for (int i = 1; i < n; i++) {
		scanf("%d", &fa[i]);
		fa[i]--;
		graph[fa[i]].push_back(i);
	}
	for (int i = 0; i < n; i++) {
		scanf("%lld", &nodeval[i]);
	}
	dfs1(0);
	dfs2(0, 0);
	bfs();
	func_seg::build(0, n - 1, 1);
	lp_seg::build(0, n - 1, 1, initf);
	while (q--) {
		int u;
		ll val;
		scanf("%d %lld", &u, &val);
		u--;
		nodeval[u] = val;
		func_seg::update(dfn[u], Node(func_seg::query(dfn[u], dfn[u], 0, n - 1, 1).k, val), 0, n - 1, 1); // 只需要改常数就行了
		while (top[u]) { // 根节点不用更新
			// u ~ top[u]
			lp_seg::update(bfnl[top[u]], gethash(top[u]), 0, n - 1, 1); // 更新 hash 值
			u = fa[top[u]];
			link_update(u); // 更新
		}
		printf("%lld\n", gethash(0));
	}
}

标签：Atcoder,ABC,200005,int,题解,ll,pos,++,ans
From： https://www.cnblogs.com/AProblemSolver/p/18166619

相关文章

  • ABC351E 补题笔记
    批：赛时很快想到切比雪夫后就跳进主席树里出不来了。一个很妙的题。首先分\(x+y\)的奇偶性黑白染色后黑色和白色不可达。然后对于同一个颜色的点易得\(dis=\max(|x1-x2|,|y1-y2|)\)，即切比雪夫距离。这个时候就可以直接上主席树了，但太复杂不是正解。最简单的解法是：我们充分......
  • ABC351D
    [ABC351D]GridandMagnet题意简述给定一个\(h\timesw\)的网格，有些网格中有磁铁。你可以向上下左右移动\(1\)格。当这个格子上下左右有磁铁时你不能移动。对于每个没有磁铁的单元格，将其自由度定义为从该单元格重复移动所能到达的单元格数。求网格中所有没有磁铁的单元格......
  • XYCTF pwn部分题解 (部分题目详解)
    hello_world(签到)思路：✅这道题就是利用printf函数泄露libc的基地址，然后再次进行栈溢出通过system，/bin/sh来获取shellwp：invisible_flag思路：✅题目提示orw，那我们先看看是否开了沙盒那么是开了沙盒的，试试orw读取flag虽然保护全开但是程序会执行我们写的shellcdoe那么就可......
  • 二叉树笔试题解题思路
    数据结构二叉树笔试题：解题思路：1.判断是否为空树，若为空树，则返回0；2.定义两个指针备份根结点地址，定义两个整型变量a,b并初始化为0，记录左右子树的深度；先对根结点的左子树进行遍历，若根结点的左结点不为NULL，则a++，把根结点的左结点赋值为新的根结点，再进行上述操作，若根结点的左结点......
  • AtCoder-abc350_g 题解
    原题链接题意简述有一个无向图，初始时没有边。接下来有一些操作：将\(u,v\)连边。询问\(u,v\)的距离是否为\(2\)，如果是，则输出中间的那个点的编号，否则输出0。每次询问后，更新\(lastans\)为询问的答案，初始时为\(0\)。每次操作的\(opt,u,v\)使用\(lastans\)解码，......
  • AtCoder-abc350_f 题解
    原题链接题意简述给定一个字符串\(S\)，对于每个匹配的括号，将括号内的字符左右翻转并大小写反转，然后删除括号。输出最后的序列。思路本题为文艺平衡树的模板题。扫一遍字符串进行括号匹配，每次把最内层的括号进行操作。最后遍历一遍平衡树，将不为括号字符的字符输出。FHQ_Treap......
  • 【题解】 量化交易1
    题目描述applepi训练了一个可以自动在股票市场进行量化交易的模型。通常来说，applepi写出的模型，你懂得，就好比一架印钞机。不过为了谨慎起见，applepi还是想先检查一下模型的效果。applpie收集了“塞帕思股份(surpass)”在最近的连续N天内的价格。在每一天中，他可以做如下事情之一：......
  • 【题解】 量化交易2
    题目描述applepi训练了一个可以自动在股票市场进行量化交易的模型。通常来说，applepi写出的模型，你懂得，就好比一架印钞机。不过为了谨慎起见，applepi还是想先检查一下模型的效果。applpie收集了“塞帕思股份(surpass)”在最近的连续N天内的价格。在每一天中，他可以做如下事情之一：......
  • 问题解决：Failed to download metadata for repo ‘appstream‘: Cannot prepare inter
    大家都知道Centos8于2021年年底停止了服务，大家再在使用yum源安装时候，出现下面错误“错误：Failedtodownloadmetadataforrepo‘AppStream’:Cannotprepareinternalmirrorlist:NoURLsinmirrorlist”1、进入yum的repos目录代码语言：javascript复制cd/etc/yum......
  • git - git 问题解决方案汇总
    git命令行相关问题汇总记录如下：在本地创建git仓库并关联远程仓库后，无法正常拉取远程更新报错信息:fatal:refusingtomergeunrelatedhistories解决方案:gitpulloriginmaster--allow-unrelated-histories解决git使用ssh无法访问服务器的问题报错信息:Error:Unab......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99