Codeforces Global Round 19(A-D）

Problem - A - Codeforces

签到题，判断输入的数列是否已经排好序

AC代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl 'n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector vi;
typedef vector vll;
typedef vector vc;
typedef long long ll;
template T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template T lcm(T a, T b) { return a / gcd(a, b) * b; }
template
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template 
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	int n;
	cin >> n;
	vector a(n + 5);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	if(is_sorted(a.begin(), a.begin() + n)){
		cout << "NO" << endl;
	}
	else{
		cout << "YES" << endl;
	}
    return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}

Problem - B - Codeforces

可知用长度为1的线段来代替长度为k(k>1)的线段它的贡献是不会改变的。考虑两种情况，1.该线段内有0，2.该线段内没有0，因为如果没有0，mex始终等于0，而此时每个长度为1的线段贡献为1，k个贡献为k，如果有0，那么1+mex<=1+k，但长度为1的线段至少贡献1+k，所以可以全部用长度为1的线段代替而且不会降低贡献，所以计算总价值就需要计算所有的线段长度和0的贡献，由数学知识知所有字段长度和为n*(n+1)*(n+2)/6，第i位置上的0贡献为i*(n-i+1) （DP思路很好，时间复杂度O(n)）

AC代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl 'n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector vi;
typedef vector vll;
typedef vector vc;
typedef long long ll;
template T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template T lcm(T a, T b) { return a / gcd(a, b) * b; }
template
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template 
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	int n;
	cin >> n;
	vector a(n + 5);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += i * (n - i + 1) * (1 + (a[i] == 0));
	}
	cout << ans << endl;
    return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}

Problem - C - Codeforces

题意大体就是从2到n-1中遍历每一堆，每次取两个，然后分配给任意两个，要求最少次数把2到n-1的石头全部分配到1和n堆中，当2到n-1全都是1的时候一个也取不了，输出-1，当n=3且a2为奇数的时候无论怎么弄最后剩下1个都取不完，其他当有一个非1的情况下，可以证明偶数可以持续的构造而不会出现1的情况。

AC代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl 'n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector vi;
typedef vector vll;
typedef vector vc;
typedef long long ll;
template T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template T lcm(T a, T b) { return a / gcd(a, b) * b; }
template
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template 
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	int n;
	cin >> n;
	vector a(n + 5);
	int cnt1 = 0, cnt2 = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	if (n == 3 && a[2] & 1) {
		cout << "-1" << endl;
		return;
	}
	bool ok = false;
	for (int i = 2; i < n; i++) {
		if (a[i] != 1) {
			ok = true;
		}
	}
	if (!ok) {
		cout << "-1" << endl;
		return;
	}
	long long ans = 0;
	for (int i = 2; i < n; i++) {
		ans += (a[i] + 1) / 2;
	}
	cout << ans << endl;
    return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}

Problem - D - Codeforces

官方化简，因此题目就变成了让suma的平方+sumb的平方的和最小，根据均值不等式，肯定是suma和sumb的差的绝对值越小，他俩的和就越小，01背包，i表示走到ai，j表示前i个ai的和，dp[i][j]表示前i个的suma和sumb的差

AC代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include
using namespace std;
#define lowbit(x) ((x) & -(x))
#define endl 'n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector vi;
typedef vector vll;
typedef vector vc;
typedef long long ll;
template T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template T lcm(T a, T b) { return a / gcd(a, b) * b; }
template
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template 
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	int n;
	cin >> n;
	vector a(n + 5);
	vector b(n + 5);
	long long sum = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum += a[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		sum += b[i];
	}
	vector> dp(110, vector (10010, INF));
	dp[0][0] = 0;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < 10010; j++) {
			if (j >= a[i + 1] && abs(dp[i + 1][j]) > abs(dp[i][j - a[i + 1]] + a[i + 1] - b[i + 1])) {
				dp[i + 1][j] = dp[i][j - a[i + 1]] + a[i + 1] - b[i + 1];
			}
			if (j >= b[i + 1] && abs(dp[i + 1][j]) > abs(dp[i][j - b[i + 1]] + b[i + 1] - a[i + 1])) {
				dp[i + 1][j] = dp[i][j - b[i + 1]] + b[i + 1] - a[i + 1];
			}
		}
	}
	int ans = INF, pos = 0;
	for (int j = 0; j < 10010; j++) {
		if (abs(dp[n][j]) < ans) {
			ans = abs(dp[n][j]);
			pos = j;
		}
	}
	long long res = 0;
	for (int i = 1; i <= n; i++) {
		res += (a[i] * a[i] + b[i] * b[i]) * (n - 2);
	}
	res += pos * pos + (sum - pos) * (sum - pos);
	cout << res << endl;
    return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}

Codeforces Global Round 19(A-D）

C/C++/C#相关栏目本月热门文章