首页 > 其他分享 >Codeforces Round 869 (Div.1 & Div.2) 题解

Codeforces Round 869 (Div.1 & Div.2) 题解

时间：2023-04-30 18:45:39浏览次数：43  
标签：869 __ gnu int 题解 tree Codeforces pbds include

2A. Politics

因为编号为 \(1\) 的人一定不会离开，那么最后留下的人一定要和编号为 \(1\) 的人的所有参数都一致，所以计数即可。

#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;}
//#define int long long
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;
inline int read () {
	int 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);
	return !f ? x : -x;
}
char s[105][105];
int n, k;
signed main () {
	int _ = read ();
	while (_ --) {
		n = read (), k = read ();
		for (int i = 1;i <= n; ++ i) scanf ("%s", s[i] + 1);
		int ans = 1;
		for (int i = 2;i <= n; ++ i) {
			int ok = 1;
			for (int j = 1;j <= k; ++ j) {
				if (s[i][j] != s[1][j]) ok = 0;
			}
			ans += ok;
		} 
		printf ("%d\n", ans);
	}
	return 0;
}

2B. Indivisible

我们可以写一个 \(O(n!)\) 的暴力打出表来，然后就发现无解条件是 \(n > 1\) 且 \(n \bmod 2 = 1\)。

然后分成两种情况：

  • 如果 \(n = 1\)，那么答案为 \([1]\)。

  • 否则答案为 \([2, 1, 4, 3, \dots, 2n, 2n - 1]\)。

#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;}
//#define int long long
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;
inline int read () {
	int 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);
	return !f ? x : -x;
}
int a[105], _, n, sum[105];
signed main () {
	_ = read ();
	while (_ --) {
		n = read ();
		if (n == 1) {
			printf ("1\n");
			continue;
		}
		if (n & 1) {
			printf ("-1\n");
			continue;
		}
		for (int i = 1, j = 2;i <= n; i += 2, j += 2) a[i] = j;
		for (int i = 2;i <= n; i += 2) a[i] = a[i - 1] - 1;
		for (int i = 1;i <= n; ++ i) printf ("%d ", a[i]);
		printf ("\n");
	}
	return 0;
}

2C/1A. Almost Increasing Subsequence

我们首先考虑长度为 \(r - l + 1\) 不合法在哪里。

我们要把满足 \(a_{i} \geq a_{i + 1} \geq a_{i + 2}\) 全部删掉，只需要将把 \(l \leq i \leq r - 2\) 并且 \(a_{i} \geq a_{i + 1} \geq a_{i + 2}\) 的 \(i\) 全部删掉。

直接前缀和即可。

#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;}
//#define int long long
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;
inline int read () {
	int 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);
	return !f ? x : -x;
}
int n, q, a[200005], s[200005];
signed main () {
	n = read (), q = read ();
	for (int i = 1;i <= n; ++ i) a[i] = read ();
	for (int i = 1;i <= n; ++ i) {
		s[i] = s[i - 1];
		if (a[i] >= a[i + 1] && a[i + 1] >= a[i + 2] && i + 2 <= n) s[i] ++;
	}
	while (q --) {
		int l = read (), r = read (), ans = r - l + 1;
		int L = l, R = r - 2;
		if (L <= R) {
			int d = s[R] - s[L - 1];
			ans -= d;
		}
		printf ("%d\n", ans);
	}
	return 0;
}

2D/1B. Fish Graph

我们考虑将每一个连通块分开处理，对于每一个连通块，取出其中任意一个生成树，拎出来每一个返祖边，然后就构成了一个环，枚举每一个点（是点 \(u\)），判断是不是一个 Fish Garph 即可。

代码非常难写，有 114514 个细节，需要注意。

#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;}
//#define int long long
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;
inline int read () {
	int 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);
	return !f ? x : -x;
}
const int N = 2005;
struct LCAns {
	struct edge {int to, nxt;} e[N << 1];
	int head[N], eid;
	inline void add_edge (int u, int v) {e[eid] = {v, head[u]}; head[u] = eid ++;}
	int dp[N][17], d[N], lg[N];
	int n, root;
	inline void dfs (int u) {
		for (int i = head[u]; ~i ; i = e[i].nxt) {
			int v = e[i].to;
			if (v == dp[u][0]) continue; 
			dp[v][0] = u; d[v] = d[u] + 1; dfs (v);
		}
	}
	inline int LCA (int u, int v) {
		if (d[u] < d[v]) swap (u, v);
		for (int j = lg[d[u] - d[v]];j >= 0; -- j) {if (d[dp[u][j]] >= d[v]) u = dp[u][j];}
		if (u == v) return u;
		for (int j = lg[d[u]];j >= 0; -- j) {if (dp[u][j] != dp[v][j]) {u = dp[u][j], v = dp[v][j];}}
		return dp[u][0];
	}
	inline void perf () {
		for (int i = 0;i < N; ++ i) head[i] = -1;
		eid = 0;
	}
	inline void pre () {
		lg[0] = -1;
		for (int i = 1;i <= n; ++ i) dp[i][0] = 0, d[i] = 0;
		for (int i = 1;i <= n; ++ i) lg[i] = lg[i / 2] + 1;
		d[root] = 1; dfs (root);
		for (int j = 1; (1 << j) < n; ++ j) for (int i = 1;i <= n; ++ i) {
			dp[i][j] = dp[dp[i][j - 1]][j - 1];
		}
	}
} tr; 
int ed[N][2], n, m, vis[N], vis2[N], fl[N];
struct DSU {
	int fa[N];
	inline void init (int X) {
		for (int i = 1;i <= X; ++ i) fa[i] = i;
	}
	inline int find (int x) {
		return fa[x] == x ? x : fa[x] = find (fa[x]);
	}
	inline void merge (int x, int y) {
		fa[find (x)] = find (y);
	}
	inline int query (int x, int y) {
		return find (x) == find (y);
	}
} awa, qwq;
vector < pair < int, int > > th;
vector < int > G2[N], G[N];
signed main () {
	int _ = read ();
	while (_ --) {
		n = read (), m = read ();
		for (int i = 1;i <= n; ++ i) vis[i] = 0;
		for (int i = 1;i <= m; ++ i) vis2[i] = 0;
		awa.init (n);
		for (int i = 1;i <= m; ++ i) {
			ed[i][0] = read (), ed[i][1] = read ();
			awa.merge (ed[i][0], ed[i][1]);
			G[ed[i][0]].push_back (ed[i][1]);
			G[ed[i][1]].push_back (ed[i][0]);
		}
		int ok = 0;
		for (int i = 1;i <= n; ++ i) {
			if (vis[i]) continue;
			tr.n = n, tr.root = i;
			tr.perf ();
			vector < int > _edge, ex;
			_edge.clear ();
			ex.clear ();
			qwq.init (n);
			for (int j = 1;j <= m; ++ j) {
				if (!awa.query (i, ed[j][0]) || !awa.query (i, ed[j][1])) continue;
				if (qwq.query (ed[j][0], ed[j][1])) {
					ex.push_back (j);
					continue;
				}
				tr.add_edge (ed[j][0], ed[j][1]);
				tr.add_edge (ed[j][1], ed[j][0]);
				G2[ed[j][0]].push_back (ed[j][1]);
				G2[ed[j][1]].push_back (ed[j][0]);
				vis2[j] = 1;
				vis[ed[j][0]] = vis[ed[j][1]] = 1;
				_edge.push_back (j);
				qwq.merge (ed[j][0], ed[j][1]);
			}
			tr.pre ();
			for (int E : ex) {
				int U = ed[E][0], V = ed[E][1];
				int Z = tr.LCA (U, V);
				for (int j = 1;j <= n; ++ j) fl[j] = 1;
				vector < int > vertex;
				vertex.clear ();
				int tot = 1;
				for (int j = U; j != Z; j = tr.dp[j][0]) vertex.push_back (j), tot ++;
				for (int j = V; j != Z; j = tr.dp[j][0]) vertex.push_back (j), tot ++;
				vertex.push_back (Z);
				for (int u : vertex) fl[u] = 0;
				for (int u : vertex) {
					th.clear ();
					for (int v : G[u]) {
						if (fl[v]) th.push_back (make_pair (u, v));
					}
					if (th.size () >= 2) {
						tot += 2;
						printf ("YES\n");
						ok = 1;
						printf ("%d\n", tot);
						for (int j = U; j != Z; j = tr.dp[j][0]) printf ("%d %d\n", j, tr.dp[j][0]);
						for (int j = V; j != Z; j = tr.dp[j][0]) printf ("%d %d\n", j, tr.dp[j][0]);
						printf ("%d %d\n", U, V);
						printf ("%d %d\n", th[0].first, th[0].second);
						printf ("%d %d\n", th[1].first, th[1].second);
						break;
					}
				}
				if (ok) break;
			}
			for (int j = 1;j <= n; ++ j) G2[j].clear ();
			if (ok) break;
		}
		if (!ok) printf ("NO\n");
		for (int i = 1;i <= n; ++ i) G[i].clear ();
	}
	return 0;
}

标签：869,__,gnu,int,题解,tree,Codeforces,pbds,include
From： https://www.cnblogs.com/RB16B/p/17365603.html

相关文章

  • CF51F Caterpillar题解
    题目传送门题意：定义毛毛虫为一种特殊的树，形如一条链上挂着若干个叶子。特殊地，在本题中的毛毛虫允许自环但不允许重边。给定一个无向图，每次操作可以合并两个点以及两个点的出边（两个点有相同出边则出现重边，两个点之间有边则出现自环）。求将其变为毛毛虫的最小操作次数。容易发现，......
  • Windows下安装Docker详细过程及问题解决
    官方手册供参考：https://docs.docker.com/desktop/windows/一：什么是Docker？Docker是一个开放源代码软件，是一个开放平台，用于开发应用、交付（shipping）应用、运行应用。Docker允许用户将基础设施（Infrastructure）中的应用单独分割出来，形成更小的颗粒（容器），从而提高交付软件的速度。Dock......
  • Codeforces Round 825 (Div. 2)——B
      #include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#defineendl"\n"inlineintgcd(inta,intb){returnb>0?gcd(b,a%b):a;}inlineintlcm(inta,intb){returna/gcd(a,b)*b;}constint......
  • Codeforces Round 855 (Div. 3)--E
    题意：给定一个k，可以任意次交换满足|i-j|=k或|i-j|=k+1的两个位置的元素很容易发现有区间内的字符是可以任意交换的，但是一个个字符考虑太混乱了（就是这样子把脑袋搞晕了），从左考虑那么（1，n-k）这个区间可以任意交换，从右考虑（k+1，n）这个区间可以任意交换那......
  • Codeforces Round 863 (Div. 3)———E
    题意：给定一个k，问由012356789组成的数字第k大的是多少链接：Problem-E-Codeforces#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#defineendl"\n"/*思路：k代表在2没有出现4的数字中，第k大的数十进制表示由“0123456789”这九个数组......
  • Codeforces Round 855 (Div. 3)--D
    题意：给定一个字符串，删除其中连续两个字符，问有多少种不同字符串的情况#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#defineendl"\n"//开始时假设每个点都对答案有贡献，考虑什么时候没有贡献//假如字符串某处出现aba这种//删除ab或者ba最后都是......
  • 义中常规赛430题解
    T1二分一个删除的数字个数然后考虑删除的数字肯定是从大到小来的，所以预处理一个降序的数组，这样能知道二分的数字个数所对应的数字。在原数组上跑最大子段和，如果碰到大于二分位置的数字就删了。最终成绩26分，因为对于二分的个数mid，原数组中a[mid]不止1个的话，无法判断哪些该删，哪......
  • Android Bitmap内存溢出问题解释
    Android平台在图片处理方面经常会出现OOM的问题，在去年开发的一个项目中，我也一直被这个问题所困扰，在这方面也搜集了许多的资料，今天仅仅针对Android平台的Bitmap说事儿，今后再对内存的问题做详细的探讨，android平台对图片解码这块确实设置的有内存上限，在解码Bitmap的时候android平台会......
  • abc252_d Distinct Trio 题解
    这是数学题耶！题意给定一个整数\(n\)和一个长度为\(n\)的整数序列\(a\)，求满足以下要求的三元组个数：\(1\leqslanti<j<k\leqslantn\)。\(a_i\nea_j\)，\(a_j\nea_k\)，\(a_k\nea_i\)。思路先想正着做，好，不会。正着做不行就反着做，先算出所有情况，再去掉不合法。......
  • ABC G Ex 简要题解
    ABC212GPowerPair推柿子题\(\sum\limits_{x}^{P-1}\sum\limits_{y}^{P-1}\existsn\in\mathbb{N}\x^n\equivy(\bmodP)\)\(1+\sum\limits_{x=1}^{P-1}\sum\limits_{y=1}^{P-1}\existsn\in\mathbb{N}\x^n\equivy(\bmodP)\)考虑模\(P\)......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99