Educational Codeforces Round 56 (Rated for Div. 2)

唠嗑

这一场题目基本比较模板，所以就稍微写一下题解吧

题解

A. Dice Rolling

有一个色子，六个面为2到7，每一次给定一个数x，问可以掷多少次色子使得最上面的数的和为x。

解法

可以发现，尽量用7就可以了，答案显然为⌈7x​⌉。

代码

#include <bits/stdc++.h>
using namespace std;
template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x < y ? x : y;}
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == \'-\') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - \'0\', c = getchar(); x *= f;
}
int main() {
	int T; read(T);
	while (T--) {
		int x; read(x);
		int y = x % 7, z = x / 7;
		if (y == 0) {cout << z << \"\\n\"; continue;}
		cout << z + 1 << \"\\n\";
	}
	return 0;
}

B. Letters Rearranging

每一次给定一个字符串s，问能否构造一个顺序使得最后的字符串不是回文串。

解法

直接sort即可

代码

#include <bits/stdc++.h>
using namespace std;
template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x < y ? x : y;}
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == \'-\') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - \'0\', c = getchar(); x *= f;
}
int s[100];
int main() {
	int T; cin >> T;
	while (T--) {
		string st; cin >> st;
		memset(s, 0, sizeof(s));
		int l = st.size(), mx = 0;
		for (int i = 0; i < l; i++) s[st[i] - \'a\']++, chkmax(mx, s[st[i] - \'a\']);
		if (mx == l) {cout << \"-1\\n\"; continue;}
		for (int i = 0; i < 26; i++)
			for (int j = 1; j <= s[i]; j++)
				putchar(i + \'a\');
		cout << endl;
	}
	return 0;
}

D. Beautiful Graph

给定一个n个点，m条边的无向图，每一个点的点权可以为1,2,3，相邻的点权之和不能为偶数，问有多少种点权赋值方案。

解法

对于每一个联通块单独考虑，答案显然为所有联通块答案之积。
显然可以发现，相邻两个点的点权奇偶性不同，那么就可以变成一个二分图。假设白点有x个，黑点有y个，那么答案就为2x+2y。
时间复杂度：O(m)

代码

#include <bits/stdc++.h>
#define Mod 998244353
#define N 300010
using namespace std;
template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x < y ? x : y;}
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == \'-\') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - \'0\', c = getchar(); x *= f;
}
struct Edge {int next, num;} e[N * 10];
int s, cnt, tot, flag, vis[N], col[N];
void add(int x, int y) {
	e[++cnt] = (Edge) {e[x].next, y};
	e[x].next = cnt;
}
void dfs(int x, int c) {
	if (vis[x]) {if (col[x] != c) flag = false; return;}
	vis[x] = 1, col[x] = c, tot++; if (c) s++;
	for (int p = e[x].next; p; p = e[p].next) dfs(e[p].num, c ^ 1);
}
int Pow(int x, int y) {
	int ret = 1;
	while (y) {
		if (y & 1) ret = 1ll * ret * x % Mod;
		y >>= 1, x = 1ll * x * x % Mod;
	}
	return ret;
}
int main() {
	int T; read(T);
	while (T--) {
		int n, m; read(n), read(m); cnt = n;
		for (int i = 1; i <= n; i++) e[i].next = 0, vis[i] = 0, col[i] = 0;
		for (int i = 1; i <= m; i++) {
			int x, y; read(x), read(y);
			add(x, y), add(y, x);
		}
		int ans = 1;
		for (int i = 1; i <= n; i++)
			if (!vis[i]) {
				flag = true, s = tot = 0; dfs(i, 0);
				if (!flag) {ans = 0; continue;}
				ans = 1ll * ans * ((Pow(2, s) + Pow(2, tot - s)) % Mod) % Mod;
			}
		cout << ans << \"\\n\";
	}
	return 0;
}

E. Intersection of Permutations

给定1−n的排列a和b，有q组操作：1.交换b[x],b[y] 2.询问a[l],…,a[r]的数集与b[L],…,b[R]的数集的交集的大小。
n,q≤2×105

解法

考虑将b中的元素变成在a中出现的位置，那么就变成每一次询问b中的一段区间[L,R]中的元素大小在[l,r]的有多少个。
显然可以使用树套树实现，但是可能会出现空间不够的情况。
那么不妨考虑cdq分治，不过要将操作拆成多个。
时间复杂度：O(qlog2n)

代码

#include <bits/stdc++.h>
#define N 200010
using namespace std;
template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x < y ? x : y;}
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == \'-\') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - \'0\', c = getchar(); x *= f;
}
struct Node {
	int x, l, r, t, id;
	Node() {}
	Node(int _x, int _l, int _r, int _t, int _id) {x = _x; l = _l; r = _r; t = _t; id = _id;}
} q[N * 10], cur[N * 10]; 
int n, c[N], a[N], b[N], posa[N], posb[N], ans[N];
void add(int x, int v) {for (; x <= n

					

						
继续阅读与本文标签相同的文章
						

														无标签