Codeforces Round #731 (Div. 3) 题解 (DEFG)

本文主要是介绍Codeforces Round #731 (Div. 3) 题解 (DEFG)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

• D. Co-growing Sequence
• E. Air Conditioners
• F. Array Stabilization (GCD version)
• G. How Many Paths?

免责说明：题解短是因为题目太裸（doge）

又好久没打 CF 了，而且代码风格大变，需要一段时间适应 qwq。

D. Co-growing Sequence

大意：自己看。

由于输出字典序最小的 y，因此先试着让 \(y_1\) 最小。显然，\(y_2\) 可以是任何数，也就意味着 \(x_2\oplus y_2\) 可以是任何数，那么 \(y_1\) 可以是 0（让 \(y_2\) 来适应 \(y_1\)）。

又由于 \(x_1\oplus y_1 \subseteq x_2\oplus y_2\)，前者已知，可以直接计算 \(y_2\) 最小值（最小值为 \(z\) 对 \(x_2\) 的差值，z - (z & x2)，其中 \(z=x_1\oplus y_1\)）。\(y_3,y_4,\ldots\) 也都可以这么求。

#include <bits/stdc++.h>
#define repeat(i, a, b) for (int i = (a), ib = (b); i < ib; i++)
#define repeat_back(i, a, b) for (int i = (b) - 1, ib = (a);i >= ib; i--)
#define mst(a, x) memset(a, x, sizeof(a))
#define fi first
#define se second
#define int ll
using namespace std;
namespace start {
	typedef long long ll; const int inf = INT_MAX >> 1; const ll INF = INT64_MAX >> 1;
		ll read() { ll x; if (scanf("%lld", &x) != 1) exit(0); return x; } // will detect EOF
		void print(ll x, bool e = 0) { printf("%lld%c", x, " \n"[e]); }
} using namespace start;
void Solve() {
	int n = read();
	int pre = 0;
	repeat (i, 0, n) {
		int x = read();
		print(pre - (x & pre), i == n - 1);
		pre |= x;
	}
}
signed main() {
	// freopen("data.txt", "r", stdin);
	int T = 1; T = read();
	repeat (ca, 1, T + 1) {
		Solve();
	}
	return 0;
}

E. Air Conditioners

大意：一些地方有一些空调。一个位置的温度为对每一空调，空调温度加空调到这里的距离，的最小值。求每一位置温度。

直接 for 两倍处理。没搞懂为什么放 D 题后面。（）

#include <bits/stdc++.h>
#define repeat(i, a, b) for (int i = (a), ib = (b); i < ib; i++)
#define repeat_back(i, a, b) for (int i = (b) - 1, ib = (a);i >= ib; i--)
#define mst(a, x) memset(a, x, sizeof(a))
#define fi first
#define se second
#define int ll
using namespace std;
namespace start {
	typedef long long ll; const int inf = INT_MAX >> 1; const ll INF = INT64_MAX >> 1;
	mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
		ll read() { ll x; if (scanf("%lld", &x) != 1) exit(0); return x; } // will detect EOF
		void print(ll x, bool e = 0) { printf("%lld%c", x, " \n"[e]); }
	const int N = 300010;
} using namespace start;
int a[N], x[N], t[N];
void Solve() {
	int n = read(), k = read();
	fill(a + 1, a + n + 1, inf);
	repeat (i, 0, k)
		x[i] = read();
	repeat (i, 0, k)
		t[i] = read();
	repeat (i, 0, k) {
		a[x[i]] = t[i];
	}
	repeat (i, 2, n + 1) a[i] = min(a[i], a[i - 1] + 1);
	repeat_back (i, 1, n) a[i] = min(a[i], a[i + 1] + 1);
	repeat (i, 1, n + 1) print(a[i], i == n);
}
signed main() {
	// freopen("data.txt", "r", stdin);
	int T = 1; T = read();
	repeat (ca, 1, T + 1) {
		Solve();
	}
	return 0;
}

F. Array Stabilization (GCD version)

大意：一个循环序列 a，令 b[i] = gcd(a[i], a[i + 1])，然后 b 将 a 替换，为一次操作。问至少多少次操作 a 只有一种元素。

想了好久，感觉朴素分解质因数复杂度不行，后来就换成线性筛优化了。

第一步，最后剩下的肯定是 n 个 gcd(a[1..n])。把初始 \(a[i]\) 都除以这个数，作为预处理。

然后将每一 \(a[i]\) 分解质因数，对于每一质因数单独讨论（显然可以独立计算）。答案就是有同一质因数的最大区间长度（要考虑循环）。比如 [2, 0, 4, 2]，[4, 2, 2] 就是一个合法区间，答案为 3。

#include <bits/stdc++.h>
#define repeat(i, a, b) for (int i = (a), ib = (b); i < ib; i++)
#define repeat_back(i, a, b) for (int i = (b) - 1, ib = (a);i >= ib; i--)
#define mst(a, x) memset(a, x, sizeof(a))
#define fi first
#define se second
#define int ll
using namespace std;
namespace start {
	typedef long long ll; const int inf = INT_MAX >> 1; const ll INF = INT64_MAX >> 1;
		ll read() { ll x; if (scanf("%lld", &x) != 1) exit(0); return x; } // will detect EOF
		void print(ll x, bool e = 0) { printf("%lld%c", x, " \n"[e]); }
	const int N = 1000010;
} using namespace start;
struct Sieve {
	static const int N = 1000010;
	bool vis[N]; int lpf[N]; vector<int> prime;
	Sieve() {
		vis[1] = 1;
		repeat (i, 2, N) {
			if (!vis[i]) prime.push_back(i), lpf[i] = i;
			for (auto j : prime) {
				if (i * j >= N) break;
				vis[i * j] = 1; lpf[i * j] = j;
				if (i % j == 0) break;
			}
		}
	}
} sieve;
int a[N];
bool f[N];
int ans, n;
void calc(vector<int> &v) {
	repeat (i, 0, v.size()) v.push_back(v[i] + n);
	int cnt = 1;
	repeat (i, 1, v.size()) {
		if (v[i] == v[i - 1] + 1) cnt++; else cnt = 1;
		ans = max(ans, cnt);
	}
}
vector<int> rec[N], appear;
void Solve() {
	n = read();
	int d = 1;
	repeat (i, 0, n) {
		a[i] = read();
		d = (i == 0 ? a[i] : __gcd(d, a[i]));
	}
	repeat (i, 0, n) a[i] /= d;
	repeat (i, 0, n) {
		while (a[i] != 1) {
			int t = sieve.lpf[a[i]];
			rec[t].push_back(i);
			appear.push_back(t);
			while (sieve.lpf[a[i]] == t) a[i] /= t;
		}
	}
	ans = 0;
	for (auto i : appear) {
		calc(rec[i]);
		rec[i].clear();
	}
	appear.clear();
	print(ans, 1);
}
signed main() {
	// freopen("data.txt", "r", stdin);
	int T = 1; T = read();
	repeat (ca, 1, T + 1) {
		Solve();
	}
	return 0;
}

G. How Many Paths?

大意：给一张有向图，可以有自环，问 1 到 i 的路径数是哪种情况（没有路径，有唯一路径，有多个且有限路径，有无数个路径）。

很裸的 SCC 缩点后 DAG 上 DP。板子硬套即可。

对于 DAG 的 DP，取反图比较好写。如果 u 的下一个点是 v，且 v 到 1 路径数情况已知（可以往下 DFS，也可以拓扑排序），u 的情况也很好计算。注意如果 u 缩点前是多个顶点的 SCC 或者有自环，那 u 只有两种情况，没有路径和有无数个路径。

#include <bits/stdc++.h>
#define repeat(i, a, b) for (int i = (a), ib = (b); i < ib; i++)
#define repeat_back(i, a, b) for (int i = (b) - 1, ib = (a);i >= ib; i--)
#define mst(a, x) memset(a, x, sizeof(a))
#define fi first
#define se second
#define int ll
using namespace std;
namespace start {
	typedef long long ll; const int inf = INT_MAX >> 1; const ll INF = INT64_MAX >> 1;
	typedef pair<int, int> pii;
		ll read() { ll x; if (scanf("%lld", &x) != 1) exit(0); return x; } // will detect EOF
		void print(ll x, bool e = 0) { printf("%lld%c", x, " \n"[e]); }
	const int N = 1000010;
} using namespace start;
vector<int> a[N];
stack<int> stk;
bool vis[N], instk[N];
int dfn[N], low[N], co[N], w[N];
vector<int> sz;
int n, dcnt;
void dfs(int x) { // Tarjan
	vis[x] = instk[x] = 1; stk.push(x);
	dfn[x] = low[x] = ++dcnt;
	for(auto p : a[x]) {
		if (!vis[p]) dfs(p);
		if (instk[p]) low[x] = min(low[x], low[p]);
	}
	if (low[x] == dfn[x]) {
		int t; sz.push_back(0);
		do {
			t = stk.top();
			stk.pop();
			instk[t] = 0;
			sz.back() += w[x];
			co[t] = sz.size() - 1;
		} while (t != x);
	}
}
void getscc() {
	fill(vis, vis + n, 0);
	sz.clear();
	repeat (i, 0, n) if (!vis[i]) dfs(i);
}
void shrink() { // result: a, n (inplace)
	static set<pii> eset;
	eset.clear();
	getscc();
	repeat (i, 0, n)
	for (auto p : a[i])
	if (co[i] != co[p])
		eset.insert({co[i], co[p]});
	n = sz.size();
	repeat (i, 0, n){
		a[i].clear();
		w[i] = sz[i];
	}
	for(auto i : eset){
		a[i.fi].push_back(i.se);
		// a[i.se].push_back(i.fi);
	}
}
int ans[N];
void ddfs(int x) {
	vis[x] = 1; ans[x] = 0;
	if (x == co[0]) { ans[x] = (w[x] >= 2 ? -1 : 1); return; }
	int infty = 0, cnt = 0;
	for (auto p : a[x]) {
		if (!vis[p]) ddfs(p);
		if (ans[p] == -1) infty = 1;
		if (ans[p] == 2) cnt = 2;
		if (ans[p] == 1) cnt++;
	}
	if (cnt && w[x] >= 2) infty = 1;
	if (infty) ans[x] = -1; else ans[x] = min(cnt, 2ll);
}
void Solve() {
	int n0 = n = read(); int m = read();
	fill (w, w + n, 1);
	repeat (i, 0, n) a[i].clear();
	repeat (i, 0, m) {
		int x = read() - 1, y = read() - 1;
		if (x == y) w[x] = 2;
		else a[y].push_back(x);
	}
	shrink();
	fill (vis, vis + n, 0);
	repeat (i, 0, n) if (!vis[i]) ddfs(i);
	repeat (i, 0, n0) print(ans[co[i]], i == n0 - 1);
}
signed main() {
	// freopen("data.txt", "r", stdin);
	int T = 1; T = read();
	repeat (ca, 1, T + 1) {
		Solve();
	}
	return 0;
}

这篇关于Codeforces Round #731 (Div. 3) 题解 (DEFG)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！