首页 > 其他分享 >AtCoder Beginner Contest 305 题解

AtCoder Beginner Contest 305 题解

时间:2023-06-11 21:44:26浏览次数:48  
标签:__ AtCoder gnu int 题解 tree 305 pbds include

https://atcoder.jp/contests/abc305/tasks_print

E - Art Gallery on Graph

冷知识:md 这题赛时没做出来 /cy

刚看到题:这是什么题啊,\(K, h\) 都 \(1e5\) 能做吗 /fn

确实能做。

考虑类似 SPFA 的操作。

设 \(a_x\) 表示 \(x\) 还可以对距离最多为 \(a_x\) 的点产生贡献,然后就直接 BFS 即可,用一个队列维护。

那么问题来了,它 WA 了。

发现这个过程类似于最短路,所以这不能单纯的用 queue 做。

类似 Dijkstra,要用大的更新小的,可能就有一个特别大的点去更新了队内的点,所以要用 priority_queue 维护,赛时太单纯了,没有想到。/ll

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
	Z x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	tmp = !f ? x : -x;
}
int n, m, k;
int cnt, head[200005], rem[200005], ans[200005];
struct edge {
	int to, nxt;
} ed[400005];
inline void add_edge (int u, int v) {
	cnt ++;
	ed[cnt] = (edge) {v, head[u]};
	head[u] = cnt;
}
priority_queue < pair < int, int > > q;
signed main () {
	read (n), read (m), read (k);
	while (!q.empty ()) q.pop ();
	for (int i = 1;i <= m; ++ i) {
		int u, v;
		read (u), read (v);
		add_edge (u, v);
		add_edge (v, u);
	}
	for (int i = 1;i <= n; ++ i) rem[i] = -1;
	for (int i = 1;i <= k; ++ i) {
		int x, y;
		read (x), read (y);
		rem[x] = y;
		q.push (make_pair (y, x));
	}
	while (!q.empty ()) {
		int u = q.top ().second, w = q.top ().first;
		q.pop ();
		ans[u] = 1;
		if (rem[u] != w) continue;
		for (int i = head[u]; i ; i = ed[i].nxt) {
			int v = ed[i].to;
			if (rem[v] < rem[u] - 1) {
				rem[v] = rem[u] - 1;
				q.push (make_pair (rem[v], v));
			}
		} 
	}
	int qwq = 0;
	for (int i = 1;i <= n; ++ i) {
		qwq += ans[i];
	}
	printf ("%d\n", qwq);
	for (int i = 1;i <= n; ++ i) {
		if (ans[i]) printf ("%d ", i);
	}
	printf ("\n");
	return 0;
}
// Always keep it simple and stupid

F - Dungeon Explore

差点没做出来。

如果是一个图,我们会发现这很烦人。

如果是一棵树,那就会很好做。

因为一个图总是可以删掉一些边当成一棵树做,所以我们考虑 \(m = n - 1\) 的情况。

那么我们就以 \(1\) 为根开始遍历,类似于回溯那种,遍历完 \(u\) 的子树就回溯。

每个节点都会被遍历一次,每个节点都会被回溯一次。

所以操作次数最多为 \(2n\)。

就做完了。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
	Z x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	tmp = !f ? x : -x;
}
int mp[105], n, m, no;
inline void dfs (int u, int fa) {
	if (no) cout << u << endl;
	no = 1;
	mp[u] = 1;
	if (u == n) {
		string s;
		cin >> s;
		exit (0);
	}
	vector < int > st; st.clear ();
	int x;
	read (x);
	for (int i = 1;i <= x; ++ i) {
		int v; read (v);
		st.push_back (v);
	}
	for (int i = 1;i <= x; ++ i) {
		int v = st[i - 1];
		if (!mp[v] && v != fa) dfs (v, u); 
	}
	cout << fa << endl;
	read (x);
	for (int i = 1;i <= x; ++ i) {
		int v; read (v);
	}
}
signed main () {
	read (n), read (m);
	dfs (1, 0);
	return 0;
}
// Always keep it simple and stupid

标签:__,AtCoder,gnu,int,题解,tree,305,pbds,include
From: https://www.cnblogs.com/RB16B/p/17473669.html

相关文章

  • AtCoder Beginner Contest 258 F Main Street
    洛谷传送门AtCoder传送门发现这题有个远古的WA就来改了(发现走法很多种,不想分类讨论,考虑最短路。设起点编号为\(1\),终点为\(11\)。\(x=Bn\)和\(y=Bn\)把坐标系分成了若干块。考虑过起点作一条平行于\(Ox\)的直线,与左右两条\(x=Bn\)的线有两个交点,给它们编号......
  • Codeforces Round 876 Div2 A-D题解
    CodeforcesRound876Div2A-D题解A.TheGoodArray这个题就是问你对于\(i\leqn\),要求前面后面至少\(ceil(\frac{i}{k})\)个1那我们就贪心的每k个放一个1,或者直接用数学算一下就好了AC代码#include<bits/stdc++.h>usingnamespacestd;constexprintlimit=(......
  • Java8新特性Stream之list转map及问题解决
    List集合转Map,用到的是Stream中Collectors的toMap方法:Collectors.toMap具体用法实例如下://声明一个List集合Listlist=newArrayList();list.add(newPerson("1001","小A"));list.add(newPerson("1002","小B"));list.add(......
  • 杂题题解
    序列变化(exchange)只要第一位确定,后面的\(n-1\)位都是唯一确定的。因为具体是B还是C只取决于两侧字母是否一样,所以两种变化方案其中一种是另一种每一位取反,要么都合法,要么都不合法。但变化出的方案可能不能继续变化下去,比如CCC变化到BBB之后就不能再变化了,但变化到CCC......
  • permu题解(树上莫队)(非正解)
    题目传送门题意给出一个长度为$n$的排列$P(P1,P2,...Pn)$,以及$m$个询问。每次询问某个区间$[l,r]$中,最长的值域连续段长度。思路首先这道题事求连续段的长度,打个莫队先#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;namespaceTestify{ inlineint......
  • AtCoder Beginner Contest 305
    A-WaterStation(abc305a)题目大意给定一个数字\(x\),输出一个数字,它是最接近\(x\)的\(5\)的倍数。解题思路令\(y=x\%5\),如果\(y\leq2\),那答案就是\(x-y\),否则就是\(x+5-y\)。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=long......
  • mysql运行sql文件时,timestamp默认值出错问题解决
    出现了---Invaliddefaultvaluefor'reward_time' 直接打开sql文件,将字段reward_time类型值替换成NULL即可 ......
  • 和与积 题解 简单二分查找
    题目大意:给定两个整数\(a(2\lea\le2\times10^9)\)和\(b(1\leb\le10^{18})\)。判断是否存在两个正整数\(x\)和\(y\),同时满足如下两个条件:\(x+y=a\)\(x\timesy=b\)解题思路:用\(a-x\)表示\(y\),可以得到面积的表达式为\(x\times(a-x)\),然后......
  • 佳佳的 Fibonacci 题解
    佳佳的Fibonacci题解题目:题解:数据范围很大,暴力超时,考虑的是矩阵优化递推,关键是求出递推矩阵,然后结合矩阵快速幂求解如何求解递推矩阵?我们首先知道斐波那契的递推式:f[i]=f[i-1]+f[i-2]——>①然后题目中给我们了T(n)的递推式:T(n)=F[1]+2F[2]+3F[3]+...+nF[n]——>②考......
  • 题解 NOD2207C【不降序列】
    problem给出n个数组A1​到An​,数组中的元素为1到M之间的数字。数组之间也存在字典序,即从第一个数开始逐位比较,一旦某个数字大于另一个,则数组的字典序大于另一个,如果某一个是另一个的前缀,则前缀的字典序更小。你可以选择一些大于0的数字执行减法操作,一旦选中某个数......