A.Candies

题意：

给定一个等式 $x + 2x + 4x + ... + 2^{k-1}x = n$ ，其中 $n$ 给定，要求输出一个 $k ≥ 2$ 时满足该等式的一个 $x$ 。

题解：

系数满足等比数列， $x + 2x + 4x + ... + 2^{k-1}x=(2^k-1)x=n$ ，因此只要枚举 $k$ ，当 $n \%(2^k-1)=0$ 时输出对应的 $x$ 即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n;
    scanf("%d", &n);
    for (int i = 2;; i++)
    {
        if (n % ((1 << i) - 1) == 0)
        {
            printf("%d\n",n/((1<<i)-1));
            return;
        }
    }
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.Balanced Array

题意：

给定一个 $n$ ，要求构造一个长度为 $n$ 数字序列满足：

前一半的数均为偶数，后一半的数均为奇数
所有数两两不同且都为正整数
前一半的数之和与后一半的数之和相等

如果存在这样的序列则输出 $YES$ ,并输出具体的序列，否则输出 $NO$

题解：

首先知道前一半的数均为偶数，所以和也会是偶数，但是后一半的数为奇数个时则不可能构造出偶数和，所以 $(n/2)\%2==1$ 时输出 $NO$ ,其他情况前面的数从 $2$ 开始，后面的数从 $1$ 开始，最后一个数特殊算即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
void solve()
{
    int n;
    scanf("%d", &n);
    if ((n / 2) % 2 == 1)
    {
        puts("NO");
        return;
    }
    puts("YES");
    int sum = 0;
    for (int i = 1; i <= n / 2; i++)
    {
        printf("%d ", i * 2);
        sum += i * 2;
    }
    for (int i = 1; i < n / 2; i++)
    {
        printf("%d ", i * 2 - 1);
        sum -= i * 2 - 1;
    }
    printf("%d\n", sum);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Alternating Subsequence

题意：

给定序列 $a_n$ ，在所有满足正负相间的子序列中要求找出最长的那个子序列，如果长度最大的不止一个则输出元素和最大的那个

题解：

要求长度最长则贪心尽可能多的选取元素，要求元素和最大可以用滑动窗口对于一段符号均相同的区间取其中的最大者即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll a[maxn];
void solve()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    ll ans = 0;
    for (int i = 0; i < n;)
    {
        int j = i + 1;
        while (j < n && a[i] * a[j] > 0)
            j++;
        sort(a + i, a + j);
        ans += a[j - 1];
        i = j;
    }
    printf("%lld\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

D.Constant Palindrome Sum

题意：

给定一个长度为 $n$ 的数字序列 $a_n$ 和一个 $k$ ，可以对序列进行若干次操作，每次操作可以将其中一个 $a_i$ 替换成 $[1,k]$ 中的任意一个数，要求经过若干次操作后对于每个 $i,i\leq\frac{n}{2}$ 都满足 $a_{i}+a_{n-1-i}=x$ ，要求最少的操作次数

题解：

可以想到 $x \in [2,2*k]$ ,那么对于每个 $x$ ，每对 $a_{i}+a_{n-1-i}$ 所需操作的最小次数是可以确定的，

$d=\begin{cases}0&a+b=x\\1&a+b\not=x,x∈[a,a+k]∪[b,b+k]\\2&a+b\not=x,x\in[2,a]∪[b+k+1,2*k]\end{cases}$
那么可以用差分算出每个 $x$ 对应的最小贡献 $cost[l]+=d,cost[r+1]-=d$ ，遍历每个 $x$ ，取最小值即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int a[maxn], cost[maxn << 1];
void solve()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    for (int i = 0; i <= 2 * k + 1; i++)
        cost[i] = 0;
    for (int i = 0; i < n / 2; i++)
    {
        int x = a[i], y = a[n - i - 1];
        if (x > y)
            swap(x, y);
        cost[0] += 2;
        cost[x + 1] -= 2;
        cost[x + 1] += 1;
        cost[(x + y - 1) + 1] -= 1;
        cost[x + y + 1] += 1;
        cost[(y + k) + 1] -= 1;
        cost[y + k + 1] += 2;
        cost[k * 2 + 1] -= 2;
    }
    int ans = INF;
    for (int i = 1; i <= k * 2; i++)
    {
        cost[i] += cost[i - 1];
        ans = min(ans, cost[i]);
    }
    printf("%d\n", ans);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

E.Weights Distributing

题意：

给一个 $n$ 个点和 $m$ 条边的无向图以及三个节点 $a、b、c$ ，给定 $m$ 个权值 $p_m$ ，要求给出一种分案权值的方案使得 $a->b->c$ 的最短路权重之和最小。

题解：

图片说明

观察两个样例就可以发现： $a、b、c$ 三个点要么通过一个中间节点相连，或者三者直接成一条直线，所以最短路 $a->x->b->x->c$ ，对于第二种情况 $x=b$ 也成立，那么只需要算出每个节点到 $a、b、c$ 三者的最短路( $bfs$ )，将权值 $p_m$ 升序排序，因为 $dis(b,x)$ 走了两次，将最短的分给 $b-x$ 路径，其余的分给 $a-x$ 和 $c-x$ 即可，枚举每个节点，求最小值

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
ll n, m, a, b, c, p[maxn];
vector<int> G[maxn];
vector<ll> bfs(int v)
{
    queue<int> q;
    q.push(v);
    vector<ll> dis(n, INF);
    dis[v] = 0;
    while (q.size())
    {
        int x = q.front();
        q.pop();
        for (int y : G[x])
        {
            if (dis[y] > dis[x] + 1)
            {
                dis[y] = dis[x] + 1;
                q.push(y);
            }
        }
    }
    return dis;
}
void solve()
{
    scanf("%lld%lld%lld%lld%lld", &n, &m, &a, &b, &c);
    a--, b--, c--;
    for (int i = 0; i < n; ++i)
        G[i].clear();
    for (int i = 0; i < m; ++i)
        scanf("%lld", &p[i]);
    for (int i = 0; i < m; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        u--, v--;
        G[v].push_back(u);
        G[u].push_back(v);
    }
    sort(p, p + m);
    for (int i = 1; i < m; ++i)
        p[i] += p[i - 1];
    vector<ll> da = bfs(a), db = bfs(b), dc = bfs(c);
    if (a == b && a == c)
    {
        puts("0");
        return;
    }
    ll res = 1e18;
    for (int i = 0; i < n; ++i)
        if (da[i] + db[i] + dc[i] <= m)
            res = min(res, p[da[i] + db[i] + dc[i] - 1] + (db[i] ? p[db[i] - 1] : 0ll));
    printf("%lld\n", res);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

Codeforces Round #636 (Div. 3)

A.Candies

题意：

题解：

B.Balanced Array

题意：

题解：

C.Alternating Subsequence

题意：

题解：

D.Constant Palindrome Sum

题意：

题解：

E.Weights Distributing

题意：

题解：