Codeforces Round 909 (Div. 3)

https://codeforces.com/contest/1899

一个小游戏

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

int n;

int main() {
    cin >> n;
    
    while(n -- ) {
        int x;
        cin >> x;
        if((x + 1) % 3 == 0 || (x - 1) % 3 == 0) {
            cout << "First" << endl;
        } else {
            cout << "Second" << endl;
        }
    }
    
    
    return 0;
}

 将数组分成k分，使绝对值差值最大

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>

using namespace std;

const int N = 150010;

typedef long long LL;

int n;
int a[N];
LL s[N];

int main() {
    int T;
    scanf("%d", &T);
    
    while(T -- ) {
        memset(s, 0, sizeof s);
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
        for(int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
        LL res = 0;
        for(int k = 1; k <= n / 2; k ++ ) {
            if(n % k == 0) {
                LL mi = 1e18, mx = 0;
                for(int j = k; j <= n; j += k) {
                    mi = min(mi, s[j] - s[j - k]);
                    mx = max(mx, s[j] - s[j - k]);
                }
                res = max(res, mx - mi);
            }
        }
        cout << res << endl;
    }
    
    return 0;
}

 找一个和最大的子数组，要求相邻的元素不能有相同的奇偶性

 简单动态规划问题，另f[i]表示以第i项为结尾的，满足条件的最大子序列和。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 2e5 + 10;

int n;
int a[N], f[N];

int main() {
    int T;
    scanf("%d", &T);
    
    while(T -- ) {
        scanf("%d", &n);
        for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]), f[i] = a[i];
        for(int i = 1; i < n; i ++ ) {
            if(((a[i] & 1) == (a[i - 1] & 1))) continue;
            f[i] = max(f[i], f[i - 1] + a[i]);
        }
        
        int mx = -1e8;
        for(int i = 0; i < n; i ++ ) mx = max(mx, f[i]);
        printf("%d\n", mx);
    }
    
    
    return 0;
}

 推公式，按照题目给的条件进行化简即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>

#define LL long long

using namespace std;

const int N = 2e5 + 10;

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

int main() {
    
    int n;
    int T = read();
    LL res;
    int x;
    map<int, int> mp;
    map<int,int>::iterator it;
    while(T -- ) {
        res = 0;
        scanf("%d", &n);
        
        mp.clear();
        for(register int i = 0; i < n; ++ i) {
            x = read();
            ++ mp[x];
        }
        
        // 注意这里不能次次声明，会被卡住
        for(it = mp.begin(); it != mp.end(); ++it) {
            res += it -> second * 1ll * (it -> second - 1) / 2;
        }
        
        res += mp[1] * 1ll * mp[2];
        printf("%lld\n", res);
        
    }    
    
    
    return 0;
}

 贪心，找规律。

我们要得到一个非降序的的序列，操作二可以把小的前移，直到大于等于前一个元素。若我们一直执行操作二，最后会得到一个类似于样例1的序列，然后进行操作一，将大元素插到末尾即可。

在此过程中，如果最小值前面有山峰状数组及形如 3 4 2 的子序列，则无解。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<climits>

using namespace std;

const int N = 2e5 + 10;

int main() {
    int T;
    scanf("%d", &T);
    int a[N];
    int n;
    
    while(T -- ) {
        scanf("%d", &n);
        for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);    
        int mi = INT_MAX, p = -1;
        for(int i = 0; i < n; i ++ ) {
            if(a[i] < mi) {
                mi = a[i];
                p = i;
            }
        }
        
        bool flag = true;
        for(int i = p; i < n - 1; i ++ ) {
            if(a[i] > a[i + 1]) {
                flag = false;
                break;
            }
        }
        if(flag) printf("%d\n", p);
        else printf("%d\n", -1);
        
    }
    
    
    return 0;
}

https://codeforces.com/contest/1899/problem/F

 贪心，维护一条链，让链尾部最后一个节点进行移动即可满足题目条件。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510;

int n, q;
int a[N];

int main() {
    int T;
    scanf("%d", &T);
    int len;
    while(T -- ) {
        scanf("%d%d", &n, &q);
        len = n - 1;
        for(int i = 0; i < q; i ++ ) {
            scanf("%d", &a[i]);
        }
        
        for(int i = 1; i < n; i ++ ) {
            printf("%d %d\n", i, i + 1);
        }
        int f = n - 1;
        for(int i = 0; i < q; i ++ ) {
            if(a[i] == f) {
                printf("%d %d %d\n", -1, -1, -1);
            } else {
                printf("%d %d %d\n", n, f, a[i]);
                f = a[i];
            }
        }
        
    }
    
    return 0;
}

最后一题太难，贴个链接有空再说：https://codeforces.com/contest/1899/problem/G