Codeforces Global Round 19 A - D

比赛链接

A. Sorting Parts

思路：

签到，判断是否是升序

代码：

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define endl '\n'
#define bug(x) cout << #x << ":" << x << endl;
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
typedef long long ll;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 1e4 + 10;
int a[N];
int n;
void solve(){
    cin >> n;
    for (int i = 0; i < n; i ++){
        cin >> a[i];
    }
    for (int i = 0; i < n - 1; i ++){
        if (a[i] > a[i + 1]){
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--){
        solve();
    }
    return 0;
}
           

B. MEX and Array

题意：

阅读理解题，枚举所有的子数组，将每段子数组分成k段，价值为k + 每段的mex值，求价值和的最大值

思路：

段数作为价值的一种，价值最大的分法肯定是每一个数作为一段，这样非0数有段数1的价值，0有2价值，即使最优情况数组是连续的，最大价值和上述分法相同。

代码：

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
typedef long long ll;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 1e4 + 10;
int n;
int a[N];
void solve(){
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    int ans = 0;
    for(int i = 1; i <= n; i ++){
        for(int j = i; j <= n; j ++){
            for(int k = i; k <= j; k ++){
                if(a[k] == 0) ans ++;
                ans ++;
            }
        }
    }
    cout << ans << endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--){
        solve();
    }
    return 0;
}
           

C. Andrew and Stones

思路：

无解情况:1.n = 3 ， 中间为奇数， 2. [2, n - 1] 全为1

其余情况， 对奇数而言，它必然要经历一次操作使它的值加一转化为偶数，先优先进行此次操作，每次这样的操作后sum 减少一。

代码：

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 1e5 + 10;
int n;
int a[N];
void solve(){
    cin >> n;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    int odd = 0, sum = 0;
    bool ok = false;
    for (int i = 2; i <= n - 1; i ++){
        if (a[i] & 1) odd ++;
        if (a[i] != 1) ok = true;
        sum += a[i];
    }
    if (n == 3 && odd == 1){
        cout << "-1" << endl;
        return;
    }
    if (ok) cout << odd + (sum - odd) / 2 << endl;
    else cout << "-1" << endl; 
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--){
        solve();
    }
    return 0;
}
           

D. Yet Another Minimization Problem

转载于https://zhuanlan.zhihu.com/p/466764407

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 110;
int n;
int a[N], b[N];
int dp[N][N * N];
void solve(){
    cin >> n;
    int 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];
    for (int i = 0; i <= n; i ++)
        for (int j = 0; j <= sum; j ++)
            dp[i][j] = 0;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= sum; j ++){
            if (j >= a[i] && dp[i - 1][j - a[i]]) dp[i][j] = 1;
            if (j >= b[i] && dp[i - 1][j - b[i]]) dp[i][j] = 1;
        }
    }
    int ans = 1e18;
    for (int i = 0; i <= sum; i ++)
        if (dp[n][i]) ans = min(ans, i * i + (sum - i) * (sum - i));
    for (int i = 1; i <= n; i ++) ans += (n - 2) * (a[i] * a[i] + b[i]* b[i]);
    cout << ans << endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--){
        solve();
    }
    return 0;
}