前言

思维题比较多，很有趣

D. Split Plus K

题意

给定数组和一个常数 $k$，每次删去其中的一个数字 $x$，然后得到 $y$ 和 $z$，要求 $y+z=x+k$。

问最少操作多少次以后，数组里的数字全都变得一样了。

思路

假设最后全都变成 $y$ 好了，那么一个 $x$ 经过一次操作以后，有：

x + k = y + z1

得到的 $z1$ 依此类推，那么有：

z1 + k = y + z2
z2 + k = y + z3
...
z(n-1) = y + zn

合并所有的式子，我们就得到了 $y=\frac {x+n*k}{n+1}$。

这时候对于这个式子还看不出什么名堂，于是我们分离变量，有

$y=\frac {x-k}{n+1}+1$，即 $y-1=\frac {x-k}{n+1}$。既然所有的 $a_i-k$ 都可以得到这个 $y-1$，而且需要操作次数 $n$ 最少，且所有 $a_i-k$ 都是 $y-1$ 的倍数，显然：

$y-1 = gcd(a_i-k)$

然后这题就做完了。

func solve() {
    n, k := read(), read()
    a := make([]int, n+1)
    s := newSet()
    for i := 1; i <= n; i++ {
        a[i] = read()
        s.insert(a[i])
    }
    if s.size() == 1 {
        println(0)
        return
    }
    gcd := a[1] - k
    for i := 2; i <= n; i++ {
        gcd = __gcd(gcd, a[i]-k)
    }
    ans := 0
    for i := 1; i <= n; i++ {
        if (a[i]-k)/gcd <= 0 {
            println(-1)
            return
        }
        ans += (a[i]-k)/gcd - 1
    }
    println(ans)
}

C. Heavy Intervals

题意

女朋友在催了，我写的简单点吧，给定 $l[],r[],c[]$，代表左端点，右端点，权值，可以改变数组里的数字的顺序，最后让 $\sum_{i=1}^n{(r_i-l_i)*c_i}$ 最小。

做法

既然后者 $c_i$ 无法改变大小，但是前者可以，所以尽量前者大，后者小，这样得到的结果就会小。

然后就会发现倒过来遍历排序后的 $l[]$，然后在 $multiset$ 中找第一个大于等于 $l_i$ 的数，就可以尽量把大的数字留给更小的数字啦。这题也就这样结束了。

int l[N], r[N], c[N];
void solve()
{
    int n;
    cin >> n;
    multiset<int> s;
    for (int i = 1; i <= n; i++) {
        cin >> l[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> r[i];
        s.insert(r[i]);
    }
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    sort(l + 1, l + 1 + n);
    sort(c + 1, c + 1 + n, greater<int>());
    for (int i = n; i >= 1; i--) {
        auto p = s.lower_bound(l[i]);
        if (p != s.end()) {
            r[i] = *p - l[i];
            s.erase(p);
            // cout << "? ";
        }
    }
    sort(r + 1, r + 1 + n);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += (r[i]) * c[i];
    }
    cout << ans << "\n";
}

B. Make Almost Equal With Mod

题意

很有趣，找一个数字 $x$，然后数组中每个数对 $x$ 取模以后，最终只会得到两种值。

思路

首先想到如果有奇数同时又有偶数，那么直接输出 $2$。但是如果全都是奇数或者全都是偶数呢？

先打表一会儿，发现和 $2$ 的幂次有关，于是就可以开始证明其中的数学规律了：

$a_i=k*2^x$

其中 $k$ 是一个奇数，令 $k=2*n+1$，那么：

$a_i \% 2^{x+1}$ = $(2 \ast n+1)*2^x$ $\%$ $2^{x+1}$ = $2^x$

本题保证所有的数字不会全都一样，所以 $k$ 不单单可以拆成 $2*n+1$，还可以 $2*n+3$ 等等，所以这题输出 $2^{x+1}$ 就做完了。

    n := read()
    a := make([]int, n)
    for i := 0; i < n; i++ {
        a[i] = read()
    }
    for i := 2; ; i *= 2 {
        se := newSet()
        for _, val := range a {
            se.insert(val % i)
        }
        if se.size() == 2 {
            println(i)
            return
        }
    }

A. Distinct Buttons

题意

从平面直角坐标系的（0，0）出发，在上下左右四个操作里面，只可以取三个操作来执行，问最终能不能到达给定的点。

思路

把 $x$ 和 $y$ 分开看，就简单得多了。

于是只要出现了同时两种符号的 $x$ 和 $y$，就不可以走到。

    n := read()
    s1, s2 := newSet(), newSet()
    for n > 0 {
        n--
        x, y := read(), read()
        if x != 0 {
            x /= abs(x)
            s1.insert(x)
        }
        if y != 0 {
            y /= abs(y)
            s2.insert(y)
        }
    }
    if s1.size() + s2.size() < 4 {
        println("YES")
        return
    }
    println("NO")