链接：Codeforces Round #636 (Div. 3)

A - Candies

题意：求出一个x满足$x + 2x + 4x + \dots + 2^{k-1}*x = n$且$k>1$

思路：提出x得$x*(1+2+4+\dots + 2^{k-1})=n$，从小到大枚举k，直到满足$n \mid (1+2+4+\dots + 2^{k-1})$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

int T, n;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        int now = 3, t = 4;
        while (0 != n % now) {
            now += t;
            t *= 2;
        }
        printf("%d\n", n / now);
    }
    return 0;
}

B - Balanced Array

题意：给你一个偶数n，要求你构造出一个数列，满足前$\frac{n}{2}$个数为偶数，后$\frac{n}{2}$个数为奇数，每个数都为互不相同的正整数，且前$\frac{n}{2}$个数的和等于后$\frac{n}{2}$个数的和

思路：奇数和偶数的差为奇数，如果$\frac{n}{2}-1$为奇数，那么对于前$\frac{n}{2}-1$对奇数和偶数，合起来的差为偶数，那么第$\frac{n}{2}$对奇数和偶数就无法构造出来，所以$\frac{n}{2}$必须为偶数，即$n\mid 4$，显然可以构造出这样的数列$2\ \ 4\ \ 6\cdots n\ \ 1\ \ 3\ \ 5\cdots (n-3)\ \ (n+\frac{n}{2}-1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

int T, n;

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        if (n % 4) {
            printf("NO\n");
            continue;
        }
        printf("YES\n");
        for (int i = 1; i <= n / 2; i++) printf("%d ", 2 * i);
        for (int i = 1; i <= n / 2 - 1; i++) printf("%d ", 2 * i - 1);
        printf("%d\n", n + n / 2 - 1);
    }
    return 0;
}

C - Alternating Subsequence

题意：就是给你n个数，你需要找出其中的最长子序列，并且这个子序列是正负交替的，并且尽量让这个子序列的和最大

思路：由于要子序列最长，所以把n个数按照正负分成几块(块内元素正负性相同)，然后再在每个块内贪心取一个数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef long long ll;

const int N = 200010;
const ll INF = 1000000000000000000;

int T, n;
ll a[N];

void solve(ll &imax, ll &imin, int l, int r)
{
    for (int i = l; i <= r; i++) {
        imax = max(imax, a[i]);
        imin = max(imin, a[i]);
    }
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
        int lst = 1, now = 2;
        ll res = 0;
        while (now <= n) {
            if ((a[now] > 0) != (a[now - 1] > 0)) {
                ll imax = -INF, imin = -INF;
                solve(imax, imin, lst, now - 1);
                if (a[lst] > 0) res += imax;
                else res += imin;
                lst = now;
            }
            now += 1;
        }
        ll imax = -INF, imin = -INF;
        solve(imax, imin, lst, n);
        if (a[lst] > 0) res += imax;
        else res += imin;
        printf("%lld\n", res);
    }
    return 0;
}

D - Constant Palindrome Sum

题意：给定一个长度为n的数列，n为偶数，保证每个元素在[1,k]之间，每次操作可以把某个位置的数字变成[1,k]内的任意数字，要求让这个数列满足：对于所有的i$\in$[1,$\frac{n}{2}$]，a[i]+a[n-i+1]是一个定值，问最少的操作次数

思路：设imin=min(a[i],a[n-i+1])，imax=max(a[i],a[n-i+1])，分三种情况，不进行操作a[i]+a[n-i+1]不变，操作一次能够使a[i]+a[n-i+1]$\in$[imin+1,imax+k]，操作两次能使a[i]+a[n-i+1]$\in$[2,2*k]，根据贪心的思想，对于每一对(a[i],a[n-i+1])，[imin+1,imax+k]操作次数加1，[2,imin]和[imax+k+1,2*k]操作次数加2，a[i]+a[n-i+1]操作次数不变，用差分数组维护一下，最后找到[2,2*k]内的最小操作次数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 400010;
const int INF = 0x3f3f3f3f;

int T, n, k, a[N], b[N];

void add(int *d, int l, int r, int x)
{
    d[l] += x;
    d[r + 1] -= x;
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= 2 * k; i++) b[i] = 0;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n / 2; i++) {
            int imin = min(a[i], a[n - i + 1]);
            int imax = max(a[i], a[n - i + 1]);
            if (2 <= imin) add(b, 2, imin, 2);
            add(b, imin + 1, imax + k, 1);
            if (imax + 1 <= k) add(b, imax + k + 1, 2 * k, 2);
        }
        for (int i = 1; i <= 2 * k; i++) b[i] += b[i - 1];
        for (int i = 1; i <= n / 2; i++) b[a[i] + a[n - i + 1]] -= 1;
        int res = INF;
        for (int i = 2; i <= 2 * k; i++) res = min(res, b[i]);
        printf("%d\n", res);
    }
    return 0;
}

E - Weights Distributing

题意：给定一张n个顶点的有权无向图，m条边和m个权值和三个点a，b，c。问如何分配边权能使a到b，b再到c的权值和最小，求最小值

思路：很直观的感受就是，求出a到b，b再到c的最短路径，然后将m个权值从小到大分配即可，如果同时有多条最短路径，我们应该选择重合最多的两条最短路径(因为这样用的边会更少)，并且此时重合的部分应该分配权值最小的边，所以我们可以用bfs或者dfs求出a，b，c到其他所有点的最短距离da[],db[],dc[]，然后枚举每个点x，假设a到b，b再到c的路径拆为a到x，x到b，b到x，x再到c，枚举所有的点x，一定会包含上述的两种(两条路径重叠与不重叠)的情况，并且此时b到x应该分配最小的边权，将m个边权排序，求前缀和sum[]，那么对于点x，答案就是sum[db[x]]+sum[da[x]+db[x]+dc[x]]

参考：https://blog.csdn.net/qq_34261446/article/details/105753266

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef long long ll;

const int N = 200010;
const int INF = 0x3f3f3f3f;

struct node {
    int to, nex;
};

int T, n, m, a, b, c;
ll p[N], sum[N];
int head[N], cnt, da[N], db[N], dc[N];
node edge[2 * N];
queue<int> q;

void init()
{
    cnt = 0;
    for (int i = 1; i <= n; i++) head[i] = 0;
    for (int i = 1; i <= n; i++) da[i] = db[i] = dc[i] = INF;
}

void add_edge(int u, int v)
{
    edge[++cnt].to = v;
    edge[cnt].nex = head[u];
    head[u] = cnt;
}

void bfs(int s, int *d)
{
    while (!q.empty()) q.pop();
    d[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; 0 != i; i = edge[i].nex) {
            int v = edge[i].to;
            if (d[v] != INF) continue;
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
}

int main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);
        init();
        for (int i = 1; i <= m; i++) scanf("%lld", &p[i]);
        sort(p + 1, p + m + 1);
        for (int i = 1; i <= m; i++) sum[i] = sum[i - 1] + p[i];
        for (int i = 1; i <= m; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            add_edge(u, v);
            add_edge(v, u);
        }
        bfs(a, da);
        bfs(b, db);
        bfs(c, dc);
        ll res = 1000000000000000000;
        for (int i = 1; i <= n; i++) {
            if (da[i] + db[i] + dc[i] > m) continue;
            res = min(res, sum[db[i]] + sum[da[i] + db[i] + dc[i]]);
        }
        printf("%lld\n", res);
    }
    return 0;
}