Codeforces Round #636 (Div. 3)

题目链接：https://codeforces.com/contest/1343

A - Candies

随便做做。

B - Balanced Array

随便做做。

D - Constant Palindrome Sum

题意：如题目的名字，给一个 \(n\) 个数字的数组，要保持对称位置的和恒为常数，但是每个数的范围都必须是 \([1,k]\) ，求最少要修改多少次，每次修改可以选一个数改为 \([1,k]\) 。

题解：数据结构选手总是强行套数据结构上去。

先想一个朴素的解法，枚举这个常数 \(x \in [2,2k]\) ，然后每次扫一遍数组检测最少需要修改多少次，注意到若某个数对 \((a,b)\) （这里 \(a\leq b\) ）的和不足 \(x\) ，则应该贪心把小的那个加到至多 \(k\) ，反之要把大的那个数减到至多 \(1\) 。

那么这个朴素的解法复杂度是 \(O(nk)\) ，枚举 \(x\) 的过程无法二分优化，因为不满足单调性。但是注意到枚举 \(x\) 的过程可以迭代，每次把数对从“大于 \(x\) 的数据结构”搬到“小于 \(x\) 的数据结构”。那么这个过程需要用一种这样的数据结构来维护：

1、“小于 \(x\) 的数据结构”可以插入元素
2、“小于 \(x\) 的数据结构”需要贪心把 \(a\) 提升到 \(k\) ，所以要数 \(k-a\leq x-(a+b)\) 的数量，也就是查询 \(x\geq k+b\) 的数量，换言之这个数据结构应该存 \(k+b\) ，然后支持查询 \(x\) 的名次。（其实这里可以把 \(k\) 移项过去节省空间）

1、“大于 \(x\) 的数据结构”可以删除元素。
2、“大于 \(x\) 的数据结构”需要贪心把 \(b\) 减少到 \(1\) ，所以要数 \(b-1\leq (a+b)-x\) 的数量，也就是查询 \(x\leq a+1\) 的数量，换言之这个数据结构应该存 \(a+1\) ，然后支持查询 \(x\) 的名次。

那么这种数据结构就是各种名次树，选择最快的“名次树”——权值线段树，然后改一改接口就可以做。

struct SegmentTree {
#define ls (o<<1)
#define rs (o<<1|1)
    static const int MAXN = 400000;
    int cnt[(MAXN << 2) + 5];
 
    void PushUp(int o) {
        cnt[o] = cnt[ls] + cnt[rs];
    }
 
    void Build(int o, int l, int r) {
        if(l == r)
            cnt[o] = 0;
        else {
            int m = l + r >> 1;
            Build(ls, l, m);
            Build(rs, m + 1, r);
            PushUp(o);
        }
    }
 
    //修改值为p的元素的个数，增量为v，且不能为负
    void Update(int o, int l, int r, int p, int v) {
        if(l == r) {
            cnt[o] += v;
            if(cnt[o] < 0)
                cnt[o] = 0;
            return;
        } else {
            int m = l + r >> 1;
            if(p <= m)
                Update(ls, l, m, p, v);
            if(p >= m + 1)
                Update(rs, m + 1, r, p, v);
            PushUp(o);
        }
    }
 
    //查询<=x的元素的个数
    int GetRank(int o, int l, int r, int x) {
        if(r <= x) {
            return cnt[o];
        } else {
            int m = l + r >> 1;
            if(x <= m)
                return GetRank(ls, l, m, x);
            else
                return cnt[ls] + GetRank(rs, m + 1, r, x);
        }
    }
 
    //查询最小的x，使得<=x的元素个数>=rk（第rk小）
    int GetValue(int o, int l, int r, int rk) {
        if(l == r) {
            return l;
        } else {
            int m = l + r >> 1;
            if(cnt[ls] >= rk)
                return GetValue(ls, l, m, rk);
            else
                return GetValue(rs, m + 1, r, rk - cnt[ls]);
        }
    }
#undef ls
#undef rs
} set1, set2;
 
int n, k;
int a[200005];
pii p[200005];
 
void TestCase() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n / 2; ++i)
        p[i] = make_pair(a[i] + a[n - i + 1], min(a[i], a[n - i + 1]));
    sort(p + 1, p + 1 + n / 2);
    set1.Build(1, 1, 2 * k);
    set2.Build(1, 1, 2 * k);
    int cntset1 = 0;
    int cntset2 = 0;
    for(int i = 1; i <= n / 2; ++i) {
        set2.Update(1, 1, 2 * k, p[i].second, 1);
        ++cntset2;
    }
    int j = 1;
    int ans = 2 * n;
    for(int x = 2; x <= 2 * k; ++x) {
        int l = j, r = j - 1;
        while(r + 1 <= n / 2 && p[r + 1].first == x)
            ++r;
        j = r + 1;
        for(int i = l; i <= r; ++i) {
            set2.Update(1, 1, 2 * k, p[i].second, -1);
            --cntset2;
        }
        int tmp1 = set1.GetRank(1, 1, 2 * k, x - 1);
        tmp1 = (cntset1 - tmp1) + tmp1 * 2;
        int tmp2 = set2.GetRank(1, 1, 2 * k, x - 1);
        tmp2 = tmp2 + (cntset2 - tmp2) * 2;
        ans = min(ans, tmp1 + tmp2);
        for(int i = l; i <= r; ++i) {
            set1.Update(1, 1, 2 * k, p[i].first - p[i].second + k, 1);
            ++cntset1;
        }
    }
    printf("%d\n", ans);
    return;
}

但是仔细一想，查询的 \(x\) 也满足单调性，这样甚至可以不需要任何数据结构。

E - Weights Distributing

题意：给一个 \(n\) 个点 \(m\) 条边的无向图，给一个 \(m\) 个数字的权重列表，给每条边分配合适的权重，使得 \(a\) 点到 \(b\) 点然后再从 \(b\) 点到 \(c\) 点的最短路权重之和最小。

题解：感觉应该是加入一个 \(x\) 点，分解成一条链： \(a \rightarrow x \rightarrow b \rightarrow x \rightarrow c\) ，然后把最短的边都分配给 \((x,b)\) 之间的路径，再把次短的边分配给 \((x,a)\) 之间的路径和 \((x,c)\) 之间的路径，容易知道这里的“路径”就应该是原图中权重为1时的最短路。那么枚举 \(x\) 求出最短路就是答案，枚举的时候考虑反过来从 \(a,b,c\) 开始的最短路即可。

const int MAXN = 200000;

int n, m, a, b, c;
int p[MAXN + 5];
ll prefixp[MAXN + 5];

int disA[MAXN + 5];
int disB[MAXN + 5];
int disC[MAXN + 5];

vector<int> G[MAXN + 5];
bool vis[MAXN + 5];
queue<int>Q;

void BFS(int s, int *dis) {
    while(!Q.empty())
        Q.pop();
    memset(vis, 0, sizeof(vis[0]) * (n + 1));
    memset(dis, INF, sizeof(dis[0]) * (n + 1));
    dis[s] = 0;
    vis[s] = 1;
    Q.push(s);
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for(auto &v : G[u]) {
            if(!vis[v]) {
                dis[v] = dis[u] + 1;
                vis[v] = 1;
                Q.push(v);
            }
        }
    }
    return;
}

void TestCase() {
    scanf("%d%d%d%d%d", &n, &m, &a, &b, &c);
    for(int i = 1; i <= m; ++i)
        scanf("%d", &p[i]);
    sort(p + 1, p + 1 + m);
    for(int i = 1; i <= m; ++i)
        prefixp[i] = prefixp[i - 1] + 1ll * p[i];
    for(int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    BFS(a, disA);
    BFS(b, disB);
    BFS(c, disC);
    ll ans = LINF;
    for(int i = 1; i <= n; ++i) {
        ll tmp = LINF;
        if(disA[i] + disB[i] + disC[i] <= m)
            tmp = prefixp[disB[i]] + prefixp[disA[i] + disB[i] + disC[i]];
        ans = min(ans, tmp);
    }
    printf("%lld\n", ans);
    for(int i = 1; i <= n; ++i)
        G[i].clear();
    return;
}

需要注意的是，若距离总和超过边的总数，则说明枚举的路径中有反复被走的边，那么这种情况会被枚举到正确的中转点 \(x\) 的情况覆盖掉。