比赛链接

cf

A

枚举

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <set>
using namespace std;
const int inf = 0x3f3f3f3f;
const int b[] = {'A' - 'A', 'C' - 'A', 'T' - 'A', 'G' - 'A'};
char str[55];
int n, a[55], ans = inf; 
inline int len (int x, int y){
    return min(abs(x - y), 26 - abs(x - y));
}
int main(){
    scanf("%d%s", &n, str + 1);
    for(int i = 1; i <= n; ++i) a[i] = str[i] - 'A';
    for(int i = 1; i <= n - 3; ++i){
        int res = 0;
        for(int j = i; j < i + 4; ++j)
            res += len(a[j], b[j - i]);
        ans = min(ans, res);
    }
    printf("%d", ans);
    return 0;
}

B

n*m矩阵 从每一行选一个数 使得异或和不为零 \(n,m \leq 500\)

每行都取第一个 如果异或和为零的话 看能不能在某一行换一个不同的数
如果有的话 那异或和一定不为零

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m, pos, val;
bool rec[2000];
int a[505][505];
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) scanf("%d", &a[i][j]);
    int fir, pos = 0, val, sum = 0; 
    for(int i = 1; i <= n; ++i){
        fir = a[i][1], sum ^= fir; 
        for(int j = 2; j <= m; ++j)
            if(a[i][j] != fir) 
                pos = i, val = j;
    }
    if(sum | pos){
        puts("TAK");
        for(int i = 1; i <= n; ++i)
            if(!sum && pos == i) printf("%d ", val);
            else printf("1 ");
    } 
    else puts("NIE");
    return 0;
}

C

求[l, r]区间和 对1e9 + 7取模
\(1 / 2 4 / 3 5 7 9 / 6 8 10 12 / ... / 2^n 个连续奇数 / 2^(n + 1)个连续偶数\)
\(l, r \leq 1e18\)

统计[1, n]的话就算出前n个里有多少个奇数 多少个偶数
等差数列求和加一下再做个前缀和的差

include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>
#define node(x, y) ((x << 1) - y)
using namespace std;
typedef long long ll;
const int N = 105;
const ll P = 1e9 + 7;
ll L, R;
inline ll solve(ll n){
    ll a[2] = {}, i = 1, j = 0;
    while(n - a[0] - a[1] > 0)
        a[j] += min(n - a[0] - a[1], i),
        i <<= 1, j ^= 1;
    a[0] %= P, a[1] %= P;
    return (a[0] * a[0] + a[1] * a[1] + a[1]) % P;
}
int main(){
    scanf("%lld%lld", &L, &R);
    printf("%lld\n", (solve(R) + P - solve(L - 1)) % P);
    return 0;
}

D

长度为n的序列 每个点有两个值a[i], b[i]
\(ans = \sum_{i = 1}^{i <= n} a[i] * (i - 1) + b[i] * (n - i)\)
求\(ans_{min}\) \(n \leq 1e5\)

这道题很国王游戏啊
如果要交换相邻两个数i, i + 1的话
ans = ans + a[i] - a[i + 1] - b[i] + b[i + 1]
所以按照a[i] - b[i]排序就好啦

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;
typedef long long ll;
const ll P = 1e9 + 7;
const int N = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int n, id[N];
ll ans, a[N], b[N];

inline bool rule(int x, int y){
    return a[x] - b[x] > a[y] - b[y];//不要在比较函数里用小于等于
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%lld%lld", &a[i], &b[i]), id[i] = i;
    sort(id + 1, id + n + 1, rule);
    for(int i = 1; i <= n; ++i) ans += 1ll * a[id[i]] * (i - 1) + 1ll * b[id[i]] * (n - i);
    printf("%lld\n", ans);
    return 0;
}

E

有一个长度为n的链 每个点权值为a[]
f(l, r)表示仅保留满足\(l \leq a[] \leq r\)的点时，有多少个连通块
统计所有取值区间的f之和 取模1e9 + 7
\(n, a[] \leq 1e5\)

考虑每个数作为区间右端点的贡献
然后排掉左边点对它的限制

#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <vector>
#include <bitset>
#define node(x, y) ((x << 1) - y)
using namespace std;
typedef long long ll;
int n; 
ll ans;
int main(){
    int pre, x;
    scanf("%d%d", &n, &pre);
    ans += 1ll * pre * (n - pre + 1);
    for(int i = 2; i <= n; ++i){
        scanf("%d", &x);
        if(pre > x) ans += 1ll * x * (pre - x);
        else ans += 1ll * (n - x + 1) * (x - pre);
        pre = x;
    }
    printf("%lld", ans); 
    return 0;
}