Contestant. Rank 2650. Rating +7.

A. One and Two

题意

给定一个包含 \(1\) 和 \(2\) 的数组，输出最小的 \(k\)，满足 \(a_1 \cdot a_2 \cdot \ldots \cdot a_k = a_{k+1} \cdot a_{k+2} \cdot \ldots \cdot a_n\)。

思路

维护一个后缀和，统计前面和后面的 \(2\) 的个数，输出第一个 \(k\)，满足 \(2\) 的个数一致。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1010;

int a[N], suf[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t;
    while(t --){
        cin >> n;
        memset(a, 0, sizeof a);
        memset(suf, 0, sizeof suf);
        for(int i=1;i<=n;i++)cin >> a[i];
        for(int i=n;i>=1;i--) {
            suf[i] = suf[i + 1];
            if(a[i] == 2) suf[i] ++;
        }
        int tot = 0;
        bool f = true;
        for(int i=1;i<n;i++){
            if(a[i] == 2) tot ++;
            if(tot == suf[i + 1]){
                cout << i << '\n';
                f = false;
                break;
            }
        }
        if(f) cout << -1 << '\n';
    }
    return 0;
}

你一个大铸币是怎么会想着纯模拟的啊（（

B. Sum of Two Numbers

题意

给定一个整数 \(n\)，定义 \(f(x) = x十进制下每位之和\)，输出任意两个数 \(x,y\)，满足 \(x + y = n, |f(x)-f(y)| \leq 1\)。

思路1

我们不妨除以 \(2\)，此时，若 \(n\) 为偶数，直接输出。

若 \(n\) 为奇数，则不可避免会出现十位不相同的情况（进位了）。此时，我们不妨遍历所有 \(i\)，将大的数减 \(5\)，小的数加 \(5\)，那么最后一定可以找到一组满足条件的数。

对上述思路的证明

我们令除 \(2\) 之后较小的数为 \(a\)，较大的数为 \(b\)。

首先，我们只需考虑 \(n\) 的个位为 \(9\) ，且十位为奇数的情况，此时 \(a+1\) 存在向前进位。那么，我们希望能尽量让 \(a\) 的高位总和降低，并让 \(b\) 的高位总和提高。

考虑到个位为 \(9\)，那么我们不妨先让 \(a\) 和 \(b\) 的个位分别变为 \(4\) 和 \(5\)，这样我们只需让高位的所有数之和相等，或者 \(a\) 的高位之和比 \(b\) 的高位之和大 \(1\)。

那么，我们来考虑高位的情况：

若 \(n\) 的十位小于 \(9\)，不难发现，我们只需让 \(a\) 的十位变为 \(b\) 的十位加一，这样可以让 \(a,b\) 的所有位之和相等，也就是说，只要输出 \(a+5,b-5\) 即可；
若 \(n\) 的十位为 \(9\)，那么事态发生了微妙的变化：存在进 \(2\) 位的情况了。但，只要百位不是奇数，我们依然可以按照情况 \(1\) 找出一个答案；
若 \(n\) 的十位为 \(9\)，百位为奇数，且千位不为 \(9\) 时，那么按照上述操作后，\(a+5\) 存在进 \(1\) 位的情况，方案不成立了；此时，有趣的现象出现了：\(a+5\) 和 \(b-5\) 恰好差了 \(9\)，那么我们不妨把个位改为 \(9, 0\)，此时，我们可以构造出 \(a+10,b-10\)，满足差值为 \(1\)；
当千位、乃至更高位都为 \(9\) 时，差值会更大，但~~根据打表~~我们不难发现，\(a+5\) 和 \(b-5\) 的差值均为 \(9\) 的倍数，那么我们只要让高位的差值降低，最后一定能得到解。

时间复杂度：懒得分析

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1010;

int a[N], suf[N];

int cal(int x){
    int res = 0;
    while(x > 0){
        res += x % 10;
        x /= 10;
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t;
    while(t --){
        cin >> n;
        int p = n / 2, q = n - p;
        while(abs(cal(p) - cal(q)) > 1) p += 5, q -= 5;
        cout << p << ' ' << q << '\n';
    }
    return 0;
}

思路2

按照上述证明的思路，我们可以找出一个规律：

首先，偶数直接输出 \(\frac{n}{2},\frac{n}{2}\)；

其次，个位不是 \(9\)，直接输出 \(\frac{n}{2},n-\frac{n}{2}\)；

否则，从证明思路，我们可以发现，以 \(10\) 为单位枚举从 \(9\) 开始的所有数，需要加减 \(5\) 的次数每隔 \(20,200,2000 \ldots\) 会变为一个特定值，该值我们可以打表找出，记该数组为 \(ans\)。

因此，对于该情况，我们只需从低位向高位枚举，找出第一个不是 \(9\) 的位置 \(cnt\)，以及该位置的数 \(val\)。若 \(val\) 为偶数，那么加减 \(ans[cnt-1] \times 5\)，否则加减 \(ans[cnt] \times 5\)。

时间复杂度：\(O(\log_{10} n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1010;

int ans[10] = {0, 1, 2, 10, 18, 100, 180, 1000, 1800, 10000};

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t;
    while(t --){
        cin >> n;
        if(n % 2 == 0) cout << n / 2 << ' ' << n / 2 << '\n';
        else if(n % 10 != 9) cout << n / 2 << ' ' << n - n /2 << '\n';
        else{
            int p = n / 2, q = n - p;
            int cnt = 0;
            while(n % 10 == 9) n /= 10, cnt ++;
            int val = n % 10;
            if(val == 0) val = 9, cnt --;
            if(val % 2 == 0) cout << p + ans[cnt - 1] * 5 << ' ' << q - ans[cnt - 1] * 5 << '\n';
            else cout << p + ans[cnt] * 5 << ' ' << q - ans[cnt] * 5 << '\n';
        }
    }
    return 0;
}

我好蠢

C. Matching Numbers

题意

给定一个整数 \(n\)，配对 \(1,2n\) 内的所有数，使 \(n\) 对数的和按照升序排列后单调递增，且相邻数相差 \(1\)。输出一种配对。

思路

我们不难发现，若是偶数的话，我们是找不出这个序列的，可以通过计算验证。

对于奇数的话，我们可以根据等差公式算出中间的值 \(2n+1\)，而对于右边的数，我们不妨将小的数加上 \(2\)，大的数减去 \(1\)，这样就可以满足差值为 \(1\)，那么，如果中间的那对数为 \(1,2n\)，那么刚好右边可以组成 \(\frac{n}{2}\) 对，而剩下的数，我们恰好可以得到两对连续的数字，将小的和大的相加，恰好就是我们想要的。

输出即可。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1010;

int a[N], suf[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t;
    while(t --){
        cin >> n;
        if(n % 2 == 0) cout << "No\n";
        else{
            cout << "YES\n";
            for(int i=1;i<=n/2+1;i++){
                cout << i * 2 - 1 << ' ' << 2 * n - i + 1 << '\n';
            }
            for(int i=1;i<=n/2;i++){
                cout << i * 2 << ' ' << 2 * n - i - n / 2 << '\n';
            }
        }
    }
    return 0;
}

md，思路很清晰但wa了一发

D. Moving Dots

题意

给定 \(n\) 个数轴上升序排序的点，所有点在同一时刻以相同的速度向与相邻数差值最小的数的方向移动（若差值相同，向左移动），两点相遇则停止移动。对于所有可不连续的子序列，统计每个子序列最后汇聚的点的个数，并输出总数。

思路

我们将问题转化为：对于所有 \([i,j]\) 内让点汇聚到两个及以上点的区间，排除这个区间内的所有数，剩下的数一定会汇聚到一个点，那么对于每个点，有选与不选两种情况，因此最后输出 \(2^p\)，\(p\) 为剩余的数的数量。

那么，对于这个区间的确定，我们不妨来考虑下面的两种情况：

对于汇聚到左边的点，最左边的点 \(i\) 应该向右边移动，那么我们找出从 \(i\) 开始，往前找第一个向左移动的即可，也就是说，应满足 \(k < x_i, x_i - k \leq x_j - x_i\)。
同理，满足 \(k > x_j,k - x_j < x_j - x_i\)。

综上，\(2x_i - x_j \leq k < 2x_j - x_i\)。

考虑到单调性，我们可以用二分查找。

时间复杂度：\(O(n^2 \log n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3010;

int x[N], pows[N], mod = 1e9 + 7;

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    pows[0] = 1;
    for(int i=1;i<=n;i++) { //Awesome but strange solution from the official tutorial.
        cin >> x[i];
        pows[i] = (pows[i - 1] * 2) % mod;
    }
    int ans = 0;
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++) {
            int l = lower_bound(x + 1, x + n + 1, 2 * x[i] - x[j]) - (x + 1),
                    r = lower_bound(x + j + 1, x + n + 1, 2 * x[j] - x[i]) - x;
            ans = (ans + pows[n - r + l + 1]) % mod;
        }
    cout << ans << '\n';
    return 0;
}

妙啊