ARC135 赛后总结

比赛链接：https://atcoder.jp/contests/arc135/tasks/arc135_a

A. Floor, Ceil - Decomposition

题目链接：https://atcoder.jp/contests/arc135/tasks/arc135_a

题目大意：每次你可以选择一个数字，分为 $\left\lfloor \frac{x}{2} \right\rfloor, \left\lceil \frac{x}{2} \right\rceil$ ，一开始只有一个数字 $X$ ，问你最终可能的乘积最大值是多少。

做法

很弱智，显然 $\ge 4$ 直接分就行了。

最后只会剩下 $2,3$ 。

但是我的写法比较 SB 。

我写了个堆 + map，每次把最大数字弹出并且记录个数。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
LL ksm(LL x, LL y){
    x %= mod;
    LL ans = 1ll;
    while(y){
        if(y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans;
}
map<LL, LL> m;
priority_queue<LL> p;
void add(LL x, LL y){
    if(m.find(x) == m.end()) p.push(x);
    m[x] += y;
}
int main(){
    LL x;
    cin >> x;
    m[x] = 1ll;
    p.push(x);
    while(p.top() >= 4){
        LL x = p.top();
        p.pop();
        LL cnt = m[x];
        LL a = x / 2, b = x - a;
        add(a, cnt);
        add(b, cnt);
    }
    LL ans = 1ll;
    while(!p.empty()){
        LL x = p.top();
        p.pop();
        ans = ans * ksm(x, m[x]) % mod;
    }
    cout << ans << "\n";
    return 0;
}

有没有更加好写的写法？

有，记忆化搜索。

也是我认为最好写的写法。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
map<LL, LL> dp;
LL dfs(LL x){
    if(dp.find(x) != dp.end()) return dp[x];
    else return dp[x] = dfs(x / 2) * dfs(x - x / 2) % mod;
}
int main(){
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    LL n; cin >> n;
    cout << dfs(n) << "\n";
    return 0;
}

还有一种写法是直接记录 $\left\lfloor \frac{x}{2^k} \right\rfloor, \left\lceil \frac{x}{2^k} \right\rceil$ 以及其个数，直到组合为 $\{2,3\},\{3,4\}$ 时结束。

但我个人感觉这种写法就算比第一种写法好写，也容易写错，所以赛时没有使用。

具体代码没写。

B. Sum of Three Terms

题目链接：https://atcoder.jp/contests/arc135/tasks/arc135_b

题目大意：给你一个数组 $S$ ，要求找到一个长度为 $n+2$ 的数组 $A$ 满足：

1. 非负。
2. $S[i]=A[i]+A[i+1]+A[i+2]$

做法

注意到 $S[i+1]-S[i]=A[i+3]-A[i]$ 。

所以条件可以等价成：$A[1]+A[2]+A[3]=S[1]$ ，以及 $A[i]-A[i-3]=k$ ，以及要求非负。

那么直接求出在非负条件下 $A[1],A[2],A[3]$ 的下界，然后直接随便定个初值就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;
const int N = 3e5 + 5;
const LL inf = 1e9;
int n;
LL S[N], sum[N];
LL l[N];
int main(){
    cin >> n;
    for(int i = 2; i <= n + 1; i++){
        cin >> S[i];
    }
    l[0] = l[1] = l[2] = 0;
    
    for(int i = 3; i <= n + 1; i++){
        sum[i] = sum[i - 3] + S[i] - S[i -1];
        l[i % 3] = max(l[i % 3], -sum[i]);
    }
    if(l[0] + l[1] + l[2] > S[2]){
        cout << "No\n";
        return 0;
    }
    cout << "Yes\n";
    l[2] = S[2] - l[0] - l[1];
    for(int i = 3; i <= n + 1; i++){
        l[i] = l[i % 3] + sum[i];
    }
    for(int i = 0; i <= n + 1; i++){
        cout << l[i] << " ";
    }
    cout << "\n";
    return 0;
}

跟官方做法本质相同，在此不再赘述。

C. XOR to All

题目链接：https://atcoder.jp/contests/arc135/tasks/arc135_c

题目大意：给你一个序列，每次可以选择其中一个数字，然后让序列中所有数字异或这个数字，问最后得到的和的最大值是多少，可以操作无数次。

做法

注意到一个事情，最终答案一定是所有序列异或上某个数字，而且只要操作过，就一定有数字为 $0$ ，综上，我们直到无论操作多少次，都等价于让序列异或上原来序列中的一个数字，也就是操作多次=操作一次。

所以直接枚举统计答案就行了。

时间复杂度：$O(n\log{V})$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5 + 5;
const int L = 30;
LL cnt[L], n, a[N];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        for(int j = 0; j < L; j++) cnt[j] += (a[i] >> j) & 1;
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++){
        ans += a[i];
    }
    for(int i = 1; i <= n; i++){
        LL now = 0;
        for(int j = 0; j < L; j++){
            if((a[i] >> j) & 1) now += (1ll << j) * (n - cnt[j]);
            else now += (1ll << j) * cnt[j];
        }
        ans = max(ans, now);
    }
    cout << ans << "\n";
    return 0;
}

D. Add to Square

题目链接：https://atcoder.jp/contests/arc135/tasks/arc135_d

题目大意：给一个表格，然后可以执行一个操作：选择一个 2*2 的子矩阵，然后让其加上同一个值（可以为负数），可以执行无数次，问最小的可能的绝对值和是多少。

做法

一个很典的想法是，先给这个操作找到不变量。

可以发现，如果将表格奇偶染色，然后将奇数格变成负的，然后将操作做对应的变换，那么整个矩阵的和就是不变量，而且不影响最终答案。（显然取负值并不改变绝对值的和）

所以变成这样的问题：选择一个 2*2 的矩阵，使得 $(1,1),(2,2)$ 加上 $x$ ，$(1,2),(2,1)$ 减去 $x$ 。

又可以发现，这里我们相当于有 $(n-1)(m-1)$ 个方程，且不线性相关，所以我们能把左上角消成 $0$ ，只保留最右边和最下边。

但是剩下的数字是多少，这个时候就可以发现，其实每行和每列的和也是不变量，这决定了在把左上角矩阵消成 $0$ 后的矩阵长啥样。

接着就可以发现：两个矩阵能互相到达当且仅当每行和每列的和是一样的。

然后就可以做了，不难发现答案的上界是：行的和的绝对值和，和列的和的绝对值和的最大值。

构造方案就是一个匹配的活。

时间复杂度：$O(nm+n^2+m^2)$ 。

做毕。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5e2 + 5;
LL a[N][N], b[N][N];
int n, m;
LL row[N], col[N];
int sgn(LL x){return x < 0 ? -1 : (x > 0 ? 1 : 0);}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            if((i + j) & 1) a[i][j] = -a[i][j];
            row[i] += a[i][j];
            col[j] += a[i][j];
        }
    }
    memset(a, 0, sizeof(a));
    int type = 0;
    LL ans = 0ll;
    {
        LL ans1 = 0ll, ans2 = 0ll;
        for(int i = 1; i <= n; i++) ans1 += abs(row[i]);
        for(int i = 1; i <= m; i++) ans2 += abs(col[i]);
        if(ans1 < ans2){
            type = 1;
            swap(n, m);
            swap(row, col);
            swap(ans1, ans2);
        }
        ans = ans1;
    }
    while(1){
        int x = -1;
        for(int i = 1; i <= m; i++){
            if(col[i] != 0) {x = i; break;}
        }
        if(x == -1) break;
        int y = -1;
        for(int i = 1; i <= n; i++){
            if(sgn(col[x]) == sgn(row[i])){
                y = i;
                break;
            }
        }
        assert(y != -1);
        a[y][x] = sgn(col[x]) * min(abs(col[x]), abs(row[y]));
        col[x] -= a[y][x];
        row[y] -= a[y][x];
    }
    while(1){
        int x = -1;
        for(int i = 1; i <= n; i++){
            if(row[i] != 0) {x = i; break;}
        }
        if(x == -1) break;
        int y = -1;
        for(int i = 1; i <= n; i++){
            if(row[i] != 0 && sgn(row[x]) != sgn(row[i])){
                y = i;
                break;
            }
        }
        LL val = min(abs(row[x]), abs(row[y]));
        a[x][1] += sgn(row[x]) * val;
        a[y][1] += sgn(row[y]) * val;
        row[x] -= sgn(row[x]) * val;
        row[y] -= sgn(row[y]) * val;
    }
    if(type){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++) b[i][j] = a[i][j];
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++) a[j][i] = b[i][j];
        }
        swap(n, m);
    }
    cout << ans << "\n";
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if((i + j) & 1) a[i][j] = -a[i][j];
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

E. Sequence of Multiples

题目链接：https://atcoder.jp/contests/arc135/tasks/arc135_e

题目大意：给定 $N,X$ ，要求构造一个和最小的长度为 $N$ 的序列 $A$ 满足：

1. 严格递增。
2. $A_1=X$
3. $A_{i}$ 被 $i$ 整除。

做法

注意到一个事情：$A_i=i*B_i$ 。

那么 $A_{i}\equiv -B_i \mod{i+1}$ 。

我们显然关心 $A_{i+1}-A_{i}$ ，而这个显然等于：$B_{i}\mod i+1$ （注，由于严格递增，在整除的时候为 $i+1$）

当 $B_{i}<i+1$ 时，就为 $B_{i}$ ，而且不难发现以后也为 $B_{i}$ 。

即 $B_{i}$ 是非严格单调递减的，而且当 $B_{i}\le i+1$ 后，$B_{i}$ 保持恒定。

具体来说：$B_{i+1}=B_{i}-\left\lfloor\frac{B_{i}-1}{i+1}\right\rfloor$

但是我们可以发现，这个保持恒定的量级可以到 $10^9$ 。

$\ge$ 是显然的，$\le$ 也不难：

往极坏的角度想：在 $i$ 的时候就 $+i$ 。

那么在 $2e9$ 的时候就是：$1e18+\frac{(2e9+1)*2e9}{2}<2e9^2$ 。

所以在 $\le 2e9$ 的时候进入恒定状态。

但我们显然不可能枚举这个量级，怎么办呢？

在苦思冥想下，我突然意识到，复杂度有没有可能是：$O(n^{\frac{1}{3}})$ 的。

因为可以发现在 $1e6$ 量级后，$\frac{B_i-1}{i}$ 的量级也是 $1e6$ 的。（与上面的证明方法类似）

而且 $\left\lfloor\frac{B_{i}-1}{i+1}\right\rfloor$ 是单调递减的，这意味着 $B_{i+1}-B_{i}$ 在 $1e6$ 之后只会有 $1e6$ 种可能的取值。（以上指的都是量级）

所以直接二分出每个可能取值的分界点，就可以在 $O(n^{\frac{1}{3}}\log{n})$ 的复杂度内解决了。

后面发现二分的判别式是一个线性函数，因此可以 $O(1)$ 找到分界点。

而且类似整除分块的，在 $1e6$ 之前的部分同样也可以用这个函数处理，因为也只有 $1e6$ 种取值，不过限制取值数量的条件不是值域，而是定义域，这时求出来的分界点很集中，基本就是自己。

然后就做完了。

时间复杂度：$O(Tn^{\frac{1}{3}})$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod = 998244353;
LL ksm(LL x, LL y){
    LL ans = 1ll;
    while(y){
        if(y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans;
}
LL ni(LL x){return ksm(x, mod - 2);}
const LL n2 = ni(2), n4 = ni(4), n6 = ni(6);
LL mt(LL x){return (x % mod + mod) % mod;}
LL q1(LL x){return mt(x) * mt(x + 1) % mod * n2 % mod;}
LL q1(LL l, LL r){return mt(q1(r) - q1(l - 1));}
LL q2(LL x){return mt(x) * mt(x + 1) % mod * mt(x + x + 1) % mod * n6 % mod;}
LL q2(LL l, LL r){return mt(q2(r) - q2(l - 1));}
// LL q3(LL x){return mt(x) * mt(x) % mod * mt(x + 1) % mod * mt(x + 1) % mod * n4 % mod;}
// LL q3(LL l, LL r){return mt(q3(r) - q3(l - 1));}
int main(){
    int T;
    cin >> T;
    while(T--){
        LL n, X, ans = 0ll;
        cin >> n >> X;
        ans = mt(n) * mt(X) % mod;
        LL val = 2ll;
        while(val < X && val <= n){
            LL cnt = (X - 1) / val;
            LL l = val + 1, r = min(X / cnt, n), mid, pos = val;
            pos = min((X + cnt * val - 1) / (cnt + cnt), n);
            ans += mt(X + val * cnt) * mt(n + 1) % mod * mt(pos - val + 1) % mod;
            ans -= mt(X + val * cnt) * q1(val, pos) % mod;
            ans -= mt(cnt + cnt) * mt(n + 1) % mod * q1(val, pos) % mod;
            ans += mt(cnt + cnt) * q2(val, pos) % mod;

            ans = mt(ans);

            X -= cnt * (pos - val + 1);
            val = pos + 1;
        }
        if(val <= n){
            assert(X <= val);
            ans += mt(n - val + 2) * mt(n - val + 1) % mod * n2 % mod * X;
            ans = mt(ans);
        }
        cout << ans << "\n";
    }
    return 0;
}

但因为没在赛时推出正确的式子，导致无法在赛时 AC 。

不过是 VP ，问题也不是那么大。

和官方做法基本一致，在此不再赘述官方做法。

别的做法

https://www.luogu.com.cn/article/thzagqey

有一种做法，是打表，发现在 $\sqrt{x}$ 后 $A$ 变成了等差数列。

差分一下，发现序列由 $n^{\frac{1}{3}}$ 段等差数列构成，并且总是在即将 $\le 0$ 后转换到下一个等差数列。

更准确的来讲，是说可以把序列分成若干段等差数列，每段都在即将 $\le 0$ 时结束，等差数列的长度可以为 $1$ 。（后面会讲为什么）

直接计算就行了。

时间复杂度：$O(Tn^{\frac{1}{3}})$ 。

问题来了，为什么？

首先等差数列不难理解，在我的做法中，$B_{i-1}-\left\lfloor\frac{B_{i-1}-1}{i}\right\rfloori=B_{i-1}-(B_{i-1}-B_{i})i=B_{i}i-B_{i-1}(i-1)=A_{i}-A_{i-1}$ 就是 $A$ 的差分，二分中的每一段实际就是 $B$ 差分相等的部分，即我们认为：$B_{i+k}=B_{i}-kd$ 。

则有：

$$\begin{align*} &B_{i+k}(i+k)-B_{i+k-1}(i+k-1) \\ =&(B_{i}-kd)(i+k)-(B_{i}-(k-1)d)(i+k-1) \\ =&B_{i}-kd-d(i+k-1) \\ =&B_{i}-2dk-d(i-1) \\ =&-2dk+(B_{i}-d(i-1)) \end{align*}$$

即 $A$ 的一阶差分是个等差数列。

但为什么总是在即将 $\le 0$ 后转换到下一个等差数列呢？

而分界点的条件可以表示为：

最大的 $k$ 满足：$\left\lfloor\frac{B_{i+(k-1)}-1}{i+k}\right\rfloor \ge d,\left\lfloor\frac{B_{i+k}-1}{i+k+1}\right\rfloor < d$ ，这里 $\ge$ 可以写成 $=$ 。

也就是：

$$\begin{align*} \left\lfloor\frac{B_{i+k-1}-1}{i+k}\right\rfloor &\ge d \\ B_{i}-(k-1)d-1&\ge d(i+k)\\ B_{i}&\ge 2dk+d(i-1)+1\\ B_{i}-2dk-d(i-1)&\ge 1\\ A_{i+k}-A_{i+k-1}&\ge 1\\ \left\lfloor\frac{B_{i+k}-1}{i+k+1}\right\rfloor &< d\\ B_{i}-kd-1&<d(i+k+1)\\ B_{i}&<2d(k+1)+d(i-1)+1\\ B_{i}-2d(k+1)-d(i-1)&<1\\ \end{align*}$$

这就证明了这件事情。

但需要注意的是：可以发现，一段长度为 $len+1$ 的 $B$ 的等差数列，对应 $A$ 的差分序列的一段长度为 $len$ 的等差数列，因此会有很多长度为 $1$ 的等差数列。（虽然可以认为相邻两个数字是等差数列，但是这种等差数列并不满足上面的将要 $\le 0$ 就切换到另外一个等差数列的性质）

为此，在实现中的一个简单的解决方法是直接算出后 $10$ 项，如果满足等差数列就直接算，赌他不会这么巧恰好由 $10$ 个长度为 $1$ 的等差数列构成。

但是我们还是希望知道什么时候 $len$ 会稳定的 $\ge 2$ 呢？

我们先设 $C_{i}=B_{i}-1$ ，那么 $C_{i+1}=C_{i}-\left\lfloor\frac{C_{i}}{i+1}\right\rfloor$ 。

那么问题可以抽象成这样：

现在有 $i+1$ 个柱子，均匀放，每次将最少东西的柱子的东西删除，再添加一个柱子均匀放，问经过几轮后能够出现稳定两轮删除的东西数相同？

设 $D_{i}=\left\lfloor\frac{C_{i}}{i+1}\right\rfloor$ ，这里给一个必要条件，当 $D_{i-1} ≠ D_{i}$ 且 $6D_{i}+1\le i$ 时，在此之后 $len\ge 1$ 。

证明就是假定一个 $i*D_{i-1}$ 的长方形（这样对后面的亏损是最大化的），然后开做这个补的过程，发现可以做至少两次，同时可以证明此时 $D_{i-1}=D_{i}+1$ ，所以只能用最上面那一行来补就证明完了。

$$\begin{align*} D_{i}&\le \frac{i-1}{6}\\ C_{i}&\le (i+1)D_{i}+i\le \frac{i^2-1}{6}+i\\ B_{i}=C_{i}+1&\le \frac{i^2+6i+5}{6}\\ A_{i}&\le \frac{i^2+6i+5}{6}*i\\ \end{align*}$$

我们想要估计出 $i$ 的量级：

$$\begin{align*} A_1+\frac{i(i+1)}{2}&\le \frac{i^2+6i+5}{6}*i\\ 10^{18}&\le \frac{i^2+6i+5}{6}*i-\frac{i(i+1)}{2}\\ \end{align*}$$

这条式子在 $\ge 2*10^6$ 处总是满足，而且显然是 $O(n^{\frac{1}{3}})$ 的。

问题就在于什么时候：$D_{i}≠D_{i+1}$ 。

设 $a_{i}=A_{i}-A_{i-1}$ 。

如果 $a_{i+1}>a_{i}$ 或者 $a_{i}-a_{i-1}≠a_{i+1}-a_{i}$ ，那么显然 $D_{i}≠D_{i-1}$ 。

否则：$a_{i-1}\ge a_{i}\ge a_{i+1},a_{i-1}-a_{i}=a_{i}-a_{i+1}$ ，那么有如果 $D_{i-1}≠D_{i}$ ，那么从 $i$ 开始就有长度为 $2$ 的等差数列，公差为 $a_{i}-a_{i+1}$，否则 $D_{i-1}=D_{i}$ ，这个时候 $i$ 依旧是公差为 $a_{i}-a_{i+1}$ 的等差数列的一部分，直接计算就行了。

也就是说，在 $2e6$ 后我们可以在 $O(1)$ 的时间进入求等差数列的过程，这个过程就是：求出公差，一直算到 $\le 0$ 为止，然后接着求下一段直到 $\ge n$ 。（因为 $A$ 为等差数列的阶段等价于 $a$ 为恒为 $0$ 的等差数列的阶段，只不过这个等差数列不会结束而已）

这样这个做法就比较好实现了。

综上，时间复杂度：$O(Tn^{\frac{1}{3}})$ 。但问题是如果我都会证明这个了为什么不直接用上面这个做法

其实说的道理，既然一开始就选择了打表，不妨在实现时就使用多算几项估计一下等差数列，也不会有多难写，还充分发扬了打表省时间的优势，如果尝试证明的话就会浪费不少时间了，不过赛后确实可以花时间证证。