ad-hoc

EricWan · 2025-05-28 21:16:18 · 题解

随机区分的 trash round，但是来水题解

首先，重复的元素不考虑。

然后，观察 f，假设 x\le y 得到 f(x,y)=x+y\bmod x\in[x,y]。

下面证明一下这个命题：取得答案的 y 一定可以是 \max\limits_{j=1}^ia_j。

如果不可以是，那么 f(x,y)\le f(y,\max\limits_{j=1}^ia_j)，证明完了。

然后我们还可以发现答案理论最大值是 \max\limits_{j=1}^ia_j，这也是比较显然的。

考虑如何维护。

• 遇到存在过的元素或者 i=1 自然是要直接跳过的；
• 如果 a_i<\max\limits_{j=1}^{i-1}a_j，说明 a_i 只能被作为那个 x，然而上面的那个 y 还是 \max\limits_{j=1}^{i-1}a_j 不变，我们看一看能否更新答案即可；
• 如果 \max\limits_{j=1}^{i-1}a_j<a_i<2\times\max\limits_{j=1}^{i-1}a_j，说明 a_i 是新的 y，然后我们发现 f(\max\limits_{j=1}^{i-1}a_j,a_i)=a_i 就是理论最大的答案，把答案进行更新即可。
• 如果 a_i\ge2\times\max\limits_{j=1}^{i-1}a_j，说明我们不好计算答案，我们发现这样的情况最多只有 1+\log_2\max a 次，我们遇到这种情况，将答案更新为 \max\limits_{j=1}^{i-1}f(a_j,a_i) 即可。

代码大概是好懂好写的。

int n, a[1000005], ans, maxa;
signed main() {
    ios::sync_with_stdio(0); // 我不会告诉你不开这两句话会 TLE on 4
    cin.tie(0);
    cout.tie(0);
    multiple_cases(T) {
        cin >> n;
        set<int> st; // 去重用
        ans = maxa = 0;
        #define OVER st.insert(a[i]);           \
                     cout << ans << " ";        \
                     maxa = max(maxa, a[i]);    \
                     continue // 因为需要用两次，偷懒写为宏
        #define f(a, b) ((a) % (b) + (b) % (a)) // 朴素计算 f
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (st.count(a[i]) || i == 1) { // 对应上文说的小分讨
                OVER;
            } else if (a[i] < maxa) {
                ans = max(ans, f(a[i], maxa));
            } else if (a[i] < maxa * 2) {
                ans = a[i];
            } else {
                ans = 0;
                for (int j = 1; j < i; j++) {
                    ans = max(ans, f(a[i], a[j]));
                }
            }
            OVER;
        }
        cout << endl;
    }
    return 0;
}