Educational Codeforces Round 126 A-F

A. Array Balancing

题意：给出序列 $a$ 和 $b$，可以任意交换相同位置的 $a_i,b_i$ ，求 $\sum|a_i-a_{i-1}|+|b_i-b_{i-1}|$ 的最小值

显然，把小的放一边，大的放另一边一定最优。

int n, m;
int a[maxn], b[maxn];

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++){
        cin >> b[i];
        if(b[i] > a[i]) swap(b[i], a[i]);
    }
    ll ans = 0;
    for(int i=1;i<n;i++) {
        ans += abs(a[i] - a[i+1]);
        ans += abs(b[i] - b[i+1]);
    }
    cout << ans << '\n';
}

B. Getting Zero

题意：给出一个数字，你可以对其进行下面的操作：

• $x=x\times2 \mod 32768$
• $x=x+1\mod 32768$

求最少多少次操作可以使 $x$ 变成0

第一个操作相当于二进制下右移一位并舍弃最高位，加法就是末尾+1，我们希望把所有1都舍弃掉，那么要么通过加1进位的方式消1，要么直接右移消1。不论如何，一定是先做加法再做乘法更优。

$32768=2^{15}$，所以15次内一定能够完成，那么只要暴力枚举做加法的次数即可。

int n, m;

int calcu(int x){
    x %= 32768;
    int a = 0;
    while(x != 0){
        x = x * 2 % 32768;
        a++;
    }
    return a;
}

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++){
        int x; cin >> x;
        int r = calcu(x);
        for(int k=1;k<=r;k++){
            r = min(r, calcu(x+k)+k);
        }
        cout << r << " \n"[1 == n];
    }
}

C. Water the Trees

题意：现在有 $n$ 棵树，每棵树有一个初始高度，接下来若干天，每天可以选择一棵树浇水使其增长 $x$，如果是奇数天则 $x=1$，偶数天 $x=2$。也可以不浇水。求最少多少天可以使得所有树一样高。

万恶的模拟题

首先，要么使所有树都涨 $max$，要么都涨到 $max+1$，涨到 $max+2$ 及以上一定不如前两种，分别计算一下

假设一共进行了 $k$ 次偶数浇水，那么进行 $sum-2\times k$ 次奇数浇水，则最大的天数是 $max(2\times k,2\times(sum-2\times k)-1)$

画出这两个函数，交点差不多是 $(2\times sum+1)/6$，那么取 $k$ 为这个值左右小范围内暴力计算即可。

注意还需要额外计算一下最多可以浇偶数水的次数，$k$ 不能超过这个值。

int n, m;
int a[maxn], b[maxn];

void solve(){
    cin >> n;
    int mx = 0;
    for(int i=1;i<=n;i++) cin >> a[i], mx = max(mx, a[i]);
    for(int i=1;i<=n;i++){
        b[i] = mx - a[i] + 1;
        a[i] = mx - a[i];
    }
    ll mxk = 0, sum = 0;
    for(int i=1;i<=n;i++){
        mxk += a[i] / 2;
        sum += a[i];
    }
    ll ans = 1e18;
    ll j = sum - 2 * mxk;
    ans = min(ans, max(2*mxk, 2*j-1));
    for(ll k = max(0ll, sum/3-30); k<=min(mxk, sum/3+30); k++){
        j = sum - 2 * k;
        ans = min(ans, max(2*k, 2*j-1));
    }

    mxk = 0, sum = 0;
    for(int i=1;i<=n;i++){
        mxk += b[i] / 2;
        sum += b[i];
    }
    j = sum - 2 * mxk;
    ans = min(ans, max(2*mxk, 2*j-1));
    for(ll k = max(0ll, sum/3-30); k<=min(mxk, sum/3+30); k++){
        j = sum - 2 * k;
        ans = min(ans, max(2*k, 2*j-1));
    }
    cout << ans << '\n';
}

D. Progressions Covering

题意：现有个序列 $a$，你需要在另一个空序列上进行如下操作：

• 选择一段长度为 $m$ 的 $[l,r]$，使得它们从 $l$ 到 $r$ 分别加上1,2,3…m
• 注意 $[l,r]$ 不能超出边界

问最少多少次操作可以使得你的序列每一个位置都大于 $a$ 序列

首先可以想到两个端点上要操作的次数是确定的

如果正着考虑，会比较难判，比如下面这种：

m = 3
a = 1 0 3 6 1 1

处理6的时候，可以让左端点处于0这个位置（尽管这里不需要再增加），让6获得最大的增长速度，这种策略让正着做变得非常复杂。

所以倒着做就行了（

具体而言，我们可以维护一个二阶差分数组，在那上面做单点修改，思路应该不难，可能写起来有点细节，具体看代码。

注意跑到边界的时候要特判

int n, m;
ll a[maxn], dd[maxn];

void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n/2;i++) swap(a[i], a[n-i+1]);
    ll s = 0, d = 0, ans = 0, mxd = 0;
    for(int i=1;i<=n;i++){
        d += dd[i];
        s += d;

        ll k = max(0ll, (a[i] - s + m - 1) / m);
        if(i+m > n+1){
            mxd = max((a[i] - s + n - i) / (n - i + 1), mxd);
            continue;
        }
        ans += k;
        dd[i+1] -= (m + 1) * k;
        dd[i+m+1] += k;
        d += m * k;
        s += m * k;
    }
    cout << ans + mxd << '\n';
}

E. Narrow Components

题意：给出一个三行，$n$ 列的矩阵，其中0表示不可走的地块，1表示可以走的地块，接下来有若干个询问，每次问 $[l,r]$ 列组成的子矩阵中有多少个联通块。

考虑前缀和，求 $[l,r]$ 上的联通块个数首先拿 $sum_r-sum_{l-1}$，然后处理边界，左右两边每有一对不同的联通块相连，就将答案加上1

边界左边的点所属的联通块可以在搞前缀和的时候顺便处理出来，边界右边的点，只有 101 的情况需要多考虑，可以先预处理出每一个 101 的列往右走，到哪一列能够合并起来（或者无法合并），解决查询的时候如果它们合并的点在查询区间之内，则属于同一联通块，否则属于两个联通块。

预处理这个情况可以用并查集，每个 101 的列指向它右边一列，111 的列指向自身，其他列指向n+1。这一列的祖先即为其第一次合并的位置。

写起来也比较麻烦（最近的题怎么全都带点模拟），看代码吧..

int n;
string s[3];
int f[maxn], st[3][maxn];
int nxt[maxn];
int find(int x){
    if(nxt[x] == x) return x;
    return nxt[x] = find(nxt[x]);
}

void solve(){
    cin >> n;
    cin >> s[0] >> s[1] >> s[2];

    int tag = 0;

    for(int i=0;i<3;i++){
        if(s[i][0] == '1'){
            f[0]++, st[i][0] = ++tag;
            if(i != 0 && st[i-1][0]) st[i][0] = st[i-1][0], f[0]--;
        }
    }
    nxt[n+1] = n+1;
    if(s[0][0] == '1' && s[2][0] == '1'){
        if(s[1][0] == '1') nxt[0] = 0;
        else nxt[0] = 1;
    }else nxt[0] = n+1;


    for(int i=1;i<n;i++){
        f[i] = f[i-1];
        for(int k=0;k<3;k++){
            if(s[k][i] == '1'){
                if(s[k][i-1] == '1') st[k][i] = st[k][i-1];
                else{
                    st[k][i] = ++tag;
                    f[i]++;
                }
            }
        }
        set<int> cnt, caf;
        for(int k=0;k<3;k++){
            if(st[k][i]){
                cnt.insert(st[k][i]);
                if(k != 0 && st[k-1][i]) st[k][i] = st[k-1][i];
                caf.insert(st[k][i]);
            }
        }
        f[i] -= cnt.size() - caf.size();

        if(s[0][i] == '1' && s[2][i] == '1'){
            if(s[1][i] == '1') nxt[i] = i;
            else nxt[i] = i+1;
        }else nxt[i] = n+1;
    }

    int Q;
    cin >> Q;
    for(int i=1;i<=Q;i++){
        int l, r;
        cin >> l >> r;
        l--, r--;
        if(l == 0){
            cout << f[r] << '\n';
            continue;
        }
        int ans = f[r] - f[l-1];
        vector<int> tg(3, 0);
        for(int k=0;k<3;k++){
            if(s[k][l] == '1'){
                tg[k] = k+1;
                if(k !=0 && tg[k-1]) tg[k] = tg[k-1];
            }
        }
        if(tg[0] && tg[2] && find(l) <= r) tg[2] = tg[0];
        set<pair<int, int>> cnt;
        for(int k=0;k<3;k++) if(st[k][l-1] && tg[k])
            cnt.insert({st[k][l-1], tg[k]});
        ans += cnt.size();
        cout << ans << '\n';
    }
}

F. Teleporters

题意：人在坐标轴0点处，x轴上有若干个点 $a_1…a_n$，接下来每次可以走向一个点，消耗能量为 $len^2$，我希望用至多 $m$ 能量走到 $a_n$ ，问至少需要额外添加几个点。

题目相当于给出若干个差值 $d_i$，每次可以选择将一个差值拆开成两份，最少多少刀可以使得 $\sum d^2$ 小于 $m$

首先需要注意的是：每一刀都将最大值切一半并不是最优的，如果选择对一个 $d$ 切两刀，那么三等分是最优的。

设 $cos(d,k)$ 为将 $d$ 切成 $k$ 份的最小花费，那么如果要对这个 $d$ 多切一刀，收益应该是 $cos(d,k)-cos(d,k+1)$

唯一的策略是每次都选取收益最大的一刀去切，题目范围不允许我们暴力枚举每一刀，所以考虑二分。

二分刀数不好做，我们依然不知道每一刀切在哪。

观察注意到切每一刀的收益是递减的，那么可以考虑二分切的最小收益，假设最小收益为 $k$，那么所有收益大于等于 $k$ 的刀都要切。

那么继续对每一个西瓜再次二分，对其切第 $m$ 刀的收益为 $cos(d,m-1)-cod(d,m)$，可以容易二分出每个西瓜切的次数，计算出切的总刀数和总花费。

这样我们就能得出切的最小收益（假设为 $k$），此时总花费为 $sum$，注意在这种意义下，所有收益大于等于 $k$ 的刀都要切，其中可能有若干收益恰好为 $k$ 的刀，默认是全切的。

这样二分只能得出：收益 $\ge k$ 的刀全切能满足条件，且仅切收益 $\gt k$ 的无法满足条件，收益恰为 $k$ 的刀切几次，还需另外判断。

全切时总花费为 $sum$，少切一刀增加 $k$ 的花费，那么可以少切 $(m-sum)/k$ 刀。

ll n, m;
ll a[maxn];

ll cos(ll d, ll k){
    ll t = d / k;
    ll md = d % k;
    return md * (t + 1) * (t + 1) + (k - md) * t * t;
}

ll cnt;
ll calcu(ll mi){//最小收益 只有收益>=mi的刀才切
    ll res = 0;
    cnt = 0;
    for(int i=1;i<=n;i++){
        ll l = 1, r = a[i];
        while(l < r){
            ll mid = (l + r + 1) / 2;
            if(cos(a[i], mid-1) - cos(a[i], mid) >= mi){
                l = mid;
            }else{
                r = mid - 1;
            }
        }
        cnt += l - 1;
        res += cos(a[i], l);
    }
    return res;
}

void solve(){
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=n;i>=1;i--) a[i] = a[i] - a[i-1];
    cin >> m;
    ll l = 0, r = 1e18;
    while(l < r){
        ll mid = (l + r + 1) / 2;
        if(calcu(mid) <= m){
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    ll res = m - calcu(l);
    cout << cnt - res / l << '\n';
}