Codeforces Round #624 (Div.3)

比赛链接

A/B/C

略

---

D. Three Integers

Solution

结论：$1\leq A\leq 2a,1\leq B\leq 2b$. 因为有把 $a$ 变成 $2a$ 的功夫，都可以把 $a$ 变成 $1$ 了，而变成 $1$ 显然是更好的事。所以循环枚举 $A$，再枚举 $A$ 的倍数且小于等于 $2b$ 的数，然后就进计算 $C$ 即可。

复杂度：$O(n\lg n)$

Code

>folded

#include<algorithm>
#include<cstdio>

using namespace std;

typedef long long LL;

int T, a, b, c;

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &a, &b, &c);
        int ans[4] = {(int)1e9}, res = 0;
        for(int i = 1; i <= 2 * a; i++) {
            for(int j = i; j <= 2 * b; j += i){
                int k = c / j * j;
                if(k == 0)  k += j;
                if(ans[0] > abs(a - i) + abs(b - j) + min(abs(c - k), abs(k + j - c))){
                    ans[0] = abs(a - i) + abs(b - j) + min(abs(c - k), abs(k + j - c));
                    ans[1] = i, ans[2] = j, ans[3] = abs(c - k) < abs(k + j - c) ? k : k + j;
                }
            }
        }
        printf("%d\n", ans[0]);
        for(int i = 1; i <= 3; i++) printf("%d ", ans[i]); putchar(10);
    }
    return 0;
}

---

E. Construct the Binary Tree

Solution

二叉树的深度和在完全二叉树的情况下取到最小，在链的情况下取到最大。当 $d$ 落在这个最大与最小的范围之间时一定有解。

我的构造方法是：以完全二叉树为初始情况，深度和不够的话，就从当前最深的且同一层有 $1$ 个以上节点的那一层中取出一个节点往下放，直到深度和达到 $d$ 或者不能继续往下放为止。

复杂度：$O(n)$

Code

>folded

#include<algorithm>
#include<cstdio>
#include<vector>

using namespace std;

typedef long long LL;

const int N = 5005;

int T, n, d, ans[N];
vector<int> v[N];

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &d);
        for(int i = 1; i <= n; i++) v[i].clear();
        int k = 0, now = 1, res = 0;
        while(now - 1 < n)  k++, now <<= 1; // now = 2 ^ k
        now = 1;
        for(int i = 1; i <= k; i++){
            now <<= 1;
            for(int j = now / 2; j < min(n+1, now); j++)  v[i].push_back(j);
            res += (min(n+1, now) - now / 2) * (i - 1);
        }
        if(d > n * (n - 1) / 2 || d < res){
            puts("NO");
            continue;
        }
        int lst = k;
        now = k;
        while(res < d){
            while(v[now].size() == 1)  now--;
            if(v[now].size() > 1){
                int cur = v[now].back();
                v[now].pop_back();
                if(lst + 1 - now <= d - res){
                    v[++lst].push_back(cur);
                    res += lst - now;
                }
                else{
                    v[now + d - res].push_back(cur);
                    res = d;
                }
            }
        }
        v[0].push_back(0);
        puts("YES");
        for(int i = 2; i <= lst; i++)
            for(int j = 0; j < v[i].size(); j++)
                ans[v[i][j]] = v[i-1][j/2];
        for(int i = 2; i <= n; i++) printf("%d ", ans[i]);
        puts("");
    }
    return 0;
}

---

F. Moving Points

Solution

说白了就是求二维偏序并且维护 $x$ 那一维的差值和。

刚好才学了 CDQ 分治，就愉快地用 CDQ 分治过了这道题。

自然，CDQ 分治能做，树状数组也能做。

复杂度：$O(n\lg n)$

Code

>folded

#include<algorithm>
#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 200005;

int n;

struct Node{
    int x, v;
}node[N];
bool cmpv(const Node &A, const Node &B){ return A.v == B.v ? A.x < B.x : A.v < B.v; }

LL ans = 0;
Node tmp[N];
void cdq(int l, int r){
    if(l == r)  return;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid+1, r);
    int ptl = l, ptr = mid + 1, tid = l - 1;
    LL res = 0;
    while(ptl <= mid && ptr <= r){
        if(node[ptl].x <= node[ptr].x){
            res += node[ptl].x;
            tmp[++tid] = node[ptl++];
        }
        else{
            ans += 1ll * (ptl - l) * node[ptr].x - res;
            tmp[++tid] = node[ptr++];
        }
    }
    while(ptl <= mid)   tmp[++tid] = node[ptl++];
    while(ptr <= r)     ans += 1ll * (ptl - l) * node[ptr].x - res, tmp[++tid] = node[ptr++];
    for(int i = l; i <= tid; i++)   node[i] = tmp[i];
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &node[i].x);
    for(int i = 1; i <= n; i++) scanf("%d", &node[i].v);
    sort(node+1, node+n+1, cmpv);
    cdq(1, n);
    printf("%lld\n", ans);
    return 0;
}