Codeforces Round #579 (Div. 3) 题解

比赛链接：https://codeforc.es/contest/1203/

A. Circle of Students

题意：$T$组询问，每组询问给出$n$个数字，问这$n$个数字能否围成圆环。（围成圆环指，从某一位开始顺时针或逆时针遍历，数组为$1, 2, 3, ..., n$）

分析：把数组复制一份，两个数组首尾相接，正反判定两次即可。

AC代码：

#include<bits/stdc++.h>

#define SIZE 200010

#define rep(i, a, b) for(int i = a; i <= b; ++i)

using namespace std;

typedef long long ll;

void io() {

	ios::sync_with_stdio(false);

	cin.tie(nullptr);

	cout.tie(nullptr);

}

ll n, m, k, t, a[SIZE];

int main() {

	io(); cin >> t;

	while (t--) {

		cin >> n;

		bool flag = true;

		rep(i, 1, n) cin >> a[i];

		rep(i, n + 1, n + n) a[i] = a[i - n];

		rep(i, 1, n) {

			if (a[i] == 1) {

				ll cnt = 1;

				rep(j, i + 1, i + n - 1) {

					if (++cnt != a[j]) {

						flag = false;

						break;

					}

				}

			}

		}

		if (flag) cout << "YES\n";

		else {

			flag = true;

			rep(i, 1, n / 2) swap(a[i], a[n - i + 1]);

			rep(i, n + 1, n + n) a[i] = a[i - n];

			rep(i, 1, n) {

				if (a[i] == 1) {

					ll cnt = 1;

					rep(j, i + 1, i + n - 1) {

						if (++cnt != a[j]) {

							flag = false;

							break;

						}

					}

				}

			}

			if (flag) cout << "YES\n";

			else cout << "NO\n";

		}

	}

}

　

B. Equal Rectangles

题意：$q$组输入，每组输入给出一个整数$n$，然后输入$4n$个整数。判断这些数字能否构成$n$个面积相同的矩形。

分析：先确定矩形的面积，显然应该是这些整数中的最小值乘最大值。然后我们对这些数排序，每次从首尾分别取两个数字判断是否构成矩形，面积是否相等即可。

AC代码：

#include<bits/stdc++.h>

#define SIZE 200010

#define rep(i, a, b) for(int i = a; i <= b; ++i)

using namespace std;

void io() {

	ios::sync_with_stdio(false);

	cin.tie(nullptr);

	cout.tie(nullptr);

}

int a[SIZE], n, t;

int main(){

	io(); cin >> t;

	while(t--) {

		cin >> n;

		rep (i, 1, 4 * n) cin >> a[i];

		sort(a + 1, a + 4 * n + 1);

		bool flag = true;

		int L = 1, R = 4 * n;

		int s = a[L] * a[R];

		while(L < R){

			if(a[L] != a[L + 1] || a[R] != a[R - 1]) { flag = false; break; }

			else if(s != a[L] * a[R]) { flag = false; break; }

			L += 2, R -= 2;

		}

		if (flag) cout << "YES\n";

		else cout << "NO\n";

	}

}

　

C. Common Divisors

题意：给出$n$个正整数，找出能整除这$n$个数的正整数个数。

分析：即求最大公因数的因子个数。

AC代码：

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define SIZE 500010

#define rep(i, a, b) for(long long i = a; i <= b; ++i)

using namespace std;

typedef long long ll;

void io() {

	ios::sync_with_stdio(false);

	cin.tie(nullptr);

	cout.tie(nullptr);

}

ll n, m, k, t, cnt = 0, a[SIZE];

int main() {

	io(); cin >> n;

	ll minx = 1e15;

	rep(i, 1, n) {

		cin >> a[i];

		minx = min(minx, a[i]);

		if (a[i] == 1) { cout << 1; return 0; }

	}

	rep(i, 1, n) {

        if (a[i] % minx == 0) continue;

        else minx = __gcd(minx, a[i]);

    }

	rep(i, 1, sqrt(minx)) {

		if (minx % i == 0) {

			if (i * i != minx)cnt += 2;

			else cnt++;

		}

	}

	cout << cnt;

}

　

D2. Remove the Substring (hard version)

题意：给定两个字符串$s$和$t$，求一个最大的长度$n$，使得在字符串$s$中删除连续$n$个字符后$t$仍然可以为$s$的子串。

分析：我们考虑下面这个样例：

$asxxxxasdxxxd$

$asd$

可以发现我们删除的最大连续$n$个字符有两种情况，一种是从头或尾开始删（像CF给出的样例），另一种就是上面这样删除中间的字符。因此，我们考虑用$t$串去和$s$串匹配，记录前缀和和后缀和，在所有前缀和$+$后缀和$=$ $t$串长度的情况中找到最大值。

AC代码：

#include<bits/stdc++.h>

#define SIZE 500010

#define rep(i, a, b) for(long long i = a; i <= b; ++i)

using namespace std;

typedef long long ll;

void io() {

	ios::sync_with_stdio(false);

	cin.tie(nullptr);

	cout.tie(nullptr);

}

char s1[SIZE], s2[SIZE];

int pre[SIZE], post[SIZE], cnt, len1, len2, ans = 0;

int main() {

	io(); cin >> (s1 + 1) >> (s2 + 1);

	len1 = strlen(s1 + 1), len2 = strlen(s2 + 1);

	for (int i = 1, j = 1; i <= len2; ++i) {

		while (s1[j] != s2[i]) ++j;

		pre[i] = j++;

	}

	for (int i = len2, j = len1; i; --i) {

		while (s1[j] != s2[i]) --j;

		post[i] = j--;

	}

	ans = max(len1 - pre[len2], post[1] - 1);

	rep(i, 1, len2 - 1) ans = max(ans, post[i + 1] - pre[i] - 1);

	cout << ans;

}

　

E. Boxers

题意：有$n$个拳击手，给出他们的体重$a_i$，每个拳击手的体重可以加$1$或减$1$（体重必须是正整数），询问最多能选出几个体重不同的拳击手。

分析：由于数据很小，用一个布尔数组保存所有可能的体重取值，然后贪心。

AC代码：

#include<bits/stdc++.h>

#define SIZE 500010

#define rep(i, a, b) for(long long i = a; i <= b; ++i)

using namespace std;

typedef long long ll;

void io() {

	ios::sync_with_stdio(false);

	cin.tie(nullptr);

	cout.tie(nullptr);

}

ll n, m, k, t, x, num[SIZE];

bool a[SIZE];

int main() {

	io(); cin >> n;

	rep(i, 1, n) {

		cin >> x;

		a[x] = true;

		num[x]++;

	}

	if (a[1]) a[2] = true;

	rep(i, 2, 150001)

		if (a[i])

			a[i - 1] = a[i + 1] = true;

	int cnt = 0;

	rep(i, 1, 150000 + 1) {

		if (a[i]) {

			if (num[i - 1]) { num[i - 1]--; cnt++; }

			else if(num[i]) { num[i]--; cnt++; }

			else if (num[i + 1]) { num[i + 1]--; cnt++; }

		}

	}

	cout << cnt;

}

　

F1. Complete the Projects (easy version)

题意：给定$n$个项目，和一个初始权值$r$。每个项目有两个数值构成，$a$表示要进行这个项目的最低权值需求，$b$表示进行完这个项目后权值将会变化的数值。询问能否完成所有的项目。

分析：首先我们肯定先做权值变化为正的项目，然后再做变化为负的项目。对于变化为正的项目，我们以$a$为关键字排序，对于变化为负的项目，我们以$a+b$为关键字排序。下证为什么以$a+b$为关键字排序：

我们考虑两项工作$A_1$和$A_2$，如果排序时$A_1$在前，则有$$a_1 \leq r$$ $$a_2 \leq r+b_1$$

同理，对于$A_2$在前时有$$a_2 \leq r$$ $$a_1 \leq r+b_2$$

转化为$$max(a_1, a_2-b_1) \leq r$$ $$max(a_2, a_1-b_2) \leq r$$

由于我们需要让$A_1$在前时更优，于是有$max(a_1, a_2-b_1) \leq max(a_2, a_1-b_2)$。分析后得到这个式子等价于$a_2+b_2 \leq a_1+b_1$

AC代码：

#include <bits/stdc++.h>

#define SIZE 200010

#define rep(i, a, b) for(int i = a; i <= b; ++i)

using namespace std;

typedef long long ll;

ll n, r, x, y;

void io() {

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

}

struct node {

	ll a, b;

}p1[SIZE], p2[SIZE], tp;

bool cmp1(node a, node b) {

	return a.a < b.a;

}

bool cmp2(node a, node b) {

	return a.a + a.b > b.a + b.b;

}

int main(){

	io(); cin >> n >> r;

	int j = 1, k = 1;

	rep (i, 1, n) {

		cin >> tp.a >> tp.b;

		if (tp.b >= 0) p1[j++] = tp;

		else p2[k++] = tp;

	}

	sort(p1 + 1, p1 + j, cmp1);

	rep (i, 1, j - 1) {

		if (r < p1[i].a) { cout << "NO"; return 0; }

		else r += p1[i].b;

	}

	sort(p2 + 1, p2 + k, cmp2);

	rep (i, 1, k - 1) {

		if (r < p2[i].a) { cout << "NO"; return 0; }

		else r += p2[i].b;

	}

	if (r >= 0)	cout << "YES";

	else cout << "NO";

}

　

F2. Complete the Projects (hard version)：

题意：和easy version基本一样，就是询问变成了最多能做几个项目。

分析：先排序贪心，然后取负数项目时dp。

AC代码：

#include <bits/stdc++.h>

#define SIZE 200010

#define rep(i, a, b) for(long long i = a; i <= b; ++i)

using namespace std;

typedef long long ll;

void io() {

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

}

int n, r;

struct node {

	ll a, b;

}p1[SIZE], p2[SIZE], tp;

bool cmp1(node a, node b) {

	return a.a < b.a;

}

bool cmp2(node a, node b) {

	return a.a + a.b < b.a + b.b;

}

int main() {

	io(); cin >> n >> r;

	int j = 1, k = 1, cnt = 0;

	rep(i, 1, n) {

		cin >> tp.a >> tp.b;

		if (tp.b >= 0) p1[j++] = tp;

		else p2[k++] = tp;

	}

	sort(p1 + 1, p1 + j, cmp1);

	rep(i, 1, j - 1) {

		if (r < p1[i].a) { continue; }

		else r += p1[i].b;

		cnt++;

	}

	sort(p2 + 1, p2 + k, cmp2);

	vector<int> dp(r + 1);

	rep(i, 1, k - 1) {

		for (int j = r; j >= max(p2[i].a, abs(p2[i].b)); --j) {

			dp[j] = max(dp[j], dp[j + p2[i].b] + 1);

		}

	}

	cout << cnt + dp[r];

}

巴特西

Codeforces Round #579 (Div. 3) 题解

最新文章

热门文章