CodeforcesGlobalRound19(A-D）

Problem - A - Codeforces

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

AC代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize("Ofast")#includeusing 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; }templateT 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")#includeusing 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; }templateT 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")#includeusing 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; }templateT 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")#includeusing 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; }templateT 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;}