Codeforces Round #266 (Div. 2)_html/css_WEB-ITnose

Codeforces Round #266 (Div. 2)

Question link

A: Just judge which one is bigger

B: Enumerate x to sqrt( n), then you can directly calculate y, and then make a judgment

C: First judge whether the sum is a multiple of 3, and then preprocess the position of the prefix sum and the suffix sum corresponding to sum / 3 numbers, and then Scan from beginning to end and combine the current one with the next one

D: First preprocess the difference so that the array represents the way to add line segments, and then each time there is a -1, it can be combined with the previous one 1 to match, multiply the number of solutions by that number. If it is 0, it can match the previous one

E: Use union lookup to split each query into 2 parts, starting from x, x to the root, and then dfs from the root down each time. If the corresponding query is consistent, the corresponding query will be asked. After dfs, if a query is consistent twice, it will output YES if it is consistent, otherwise it will be NO

Code:

#include <cstdio>#include <cstring>int n, m, a, b;int solve() {	if (b >= m * a) return a * n;	int yu = n % m;	int ans = n / m * b;	if (yu * a < b) return ans + yu * a;	return ans + b;}int main() {	scanf("%d%d%d%d", &n, &m, &a, &b);	printf("%d\n", solve());	return 0;}

B:

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;typedef long long ll;ll n, a, b;int main() {	scanf("%lld%lld%lld", &n, &a, &b);	n = n * 6;	ll ans = 1e18, x, y;	if (a * b >= n) {		x = a;		y = b;		ans = a * b;	}	else {		int flag = 0;		if (a > b) {			flag = 1;			swap(a, b);		}		for (int i = 1; i < 1000000 && i < n; i++) {			ll r = n / i + (n % i != 0);			ll l = i;			if (l > r) swap(l, r);			if (l < a || r < b) continue;			if (i * r < ans) {				ans = i * r;				x = i;				y = r;			}		}		if (flag) swap(x, y);	}	printf("%lld\n%lld %lld\n", ans, x, y);	return 0;}

C:

#include <cstdio>#include <cstring>const int N = 500005;typedef long long ll;int n;ll a[N], pres[N], prec[N], sufs[N], sufc[N];int main() {	scanf("%d", &n);	ll sum = 0;	for (int i = 1; i <= n; i++) {		scanf("%lld", &a[i]);		sum += a[i];	}	if (sum % 3) printf("0\n");	else {		sum /= 3;		for (int i = 1; i <= n; i++) {			pres[i] = pres[i - 1] + a[i];			if (pres[i] == sum)				prec[i] = 1;		}		for (int i = n; i >= 1; i--) {			sufs[i] = sufs[i + 1] + a[i];			sufc[i] = sufc[i + 1];			if (sufs[i] == sum) sufc[i]++;		}		ll ans = 0;		for (int i = 1; i <= n; i++)			ans += prec[i] * sufc[i + 2];		printf("%lld\n", ans);	}	return 0;}

D:

#include <cstdio>#include <cstring>typedef long long ll;const int MOD = 1000000007;const int N = 2005;int n, h, a[N], b[N];int main() {	scanf("%d%d", &n, &h);	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] = h - a[i];	for (int i = 1; i <= n + 1; i++) b[i] = a[i] - a[i -1];	int ans = 1, cnt = 0;	for (int i = 1; i <= n + 1; i++) {		if (b[i] == 0) ans = (ll)ans * (cnt + 1) % MOD;		else if (b[i] == 1) cnt++;		else if (b[i] == -1) ans = (ll)ans * cnt % MOD, cnt--;		else ans = 0;	}	printf("%d\n", ans);	return 0;}

E:

#include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;#define MP(a,b) make_pair(a,b)typedef pair<int, int> pii;const int N = 100005;int n, m, parent[N];int find(int x) {	return x == parent[x] ? x : parent[x]  = find(parent[x]);}vector<pii> p, q[N];vector<int> g[N];int tot, vis[N], cnt[N];void dfs(int u) {	vis[u] = 1;	for (int i = 0; i < g[u].size(); i++)		dfs(g[u][i]);	for (int i = 0; i < q[u].size(); i++) {		if (vis[q[u][i].first])			cnt[q[u][i].second]++;	}	vis[u] = 0;}int main() {	scanf("%d%d", &n, &m);	for (int i = 1; i <= n; i++)		parent[i] = i;	int c, x, y;	while (m--) {		scanf("%d%d", &c, &x);		if (c == 2)			p.push_back(MP(find(x), x));		else {			scanf("%d", &y);			if (c == 1) {				g[y].push_back(x);				int px = find(x);				int py = find(y);				if (px != py)					parent[px] = py;			} else {				q[x].push_back(MP(p[y - 1].first, tot));				q[p[y - 1].second].push_back(MP(x, tot));				tot++;			}		}	}	for (int i = 1; i <= n; i++)		if (parent[i] == i) dfs(i);	for (int i = 0; i < tot; i++)		if (cnt[i] == 2) printf("YES\n");		else printf("NO\n");	return 0;}