国庆 Day 5 模拟赛赛后题解与总结

A 动物世界

给出序列 a_i，求一对 (i, j)，使得 a_i \geq a_j，且 a_i \bmod a_j 最大。

输出这个最大值。

n \leq 2\times 10^5, a_i \leq 10^6

场上写了一个数据分治，成功卡过去了

考虑按 a_i 去重后升序排序，直接暴力找即可。

最坏复杂度也是 O(n + \dfrac{n}{2} + \dfrac{n}{3} \cdots + \dfrac{n}{\max a_i}) = O(n \ln n) 的。

const int MAXN = 2e5 + 10;
const int MAXVAL = 1e6 + 10;

int n, arr[MAXN], mxval[MAXVAL], ans;
bool cnt[MAXVAL];

int main() {
    IO::read(n);
    rep(i, 1, n) IO::read(arr[i]), cnt[arr[i]] |= true;
    sort(arr + 1, arr + n + 1); int m = unique(arr + 1, arr + n + 1) - arr - 1;
    rep(i, 1, MAXVAL - 1) mxval[i] = cnt[i] ? i : mxval[i - 1];
    rep(i, 1, m) {
        for (int j = arr[i]; j <= MAXVAL - 1; j += arr[i]) {
            if (mxval[min(j + arr[i] - 1, MAXVAL - 1)] >= arr[i]) ans = max(ans, mxval[min(j + arr[i] - 1, MAXVAL - 1)] % arr[i]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

B 走进科学

有 n 个车在 [-10^9, 10^9] 上移动。开始时 i 号点在 a_i，并且或向左或向右。速度为 1，任意时刻若两车相撞，则各自改变方向并保持原来速度。有 q 个询问，询问 i 号车在 t 时刻的坐标。

n, q\leq 2\times10^5

发现任意一次坐标均不会改变任意车与任意车的相对位置。

因此如果我们忽略标号，会发现各车坐标关于时间是若干条斜率为 \pm1 的一次函数。并且询问本质上是求横坐标为 t 时第 k 大（k 取决于 i 在初始时的位置）的值。

二分值。

发现将斜率为 1 的和斜率为 -1 的一次函数分开考虑，例如考虑斜率为 1 的一次函数。

假设二分的值是 x，则求有多少个斜率为 1 的一次函数在 t 处小于 x，等价与

即

由于值域很大，只能 lower_bound 一下求出 a_i 的数量。

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

还有更优的做法。

如果我们仍然忽略序号，碰撞本质就是交换序号。仅仅考虑一个标记：有标记的那个车就是这个时刻 i 号车应该交换到的那个车。最后只需要回答有标记的那辆车即可。

考察一辆向左的车的碰撞过程：与左边第一辆向右的车交换；与右边第一辆向左的车交换；与左边第二辆向右的车交换；与右边第二辆向左的车交换 \cdots

因此，从某种角度来看，标记访问过的车的下标，是连续的。（具体而言，如果我们单独考虑向左的车构成的下标，和向右的车构成的下标集合，那么标记访问的会是在向右的车中 i 号车下标左边的一段后缀，在向左的车中 i 号车右边的一段前缀）。并且与向左的车交换的次数与向右的车交换的次数差不多都是相同的（有可能差 1，要根据奇偶性讨论）。

这启发我们，如果我们知道一共交换了多少次，就能求出最后一次交换是哪两辆车的碰撞，进而检查能否在 t 时刻内发生这么多次。

所以二分交换了多少次即可。

typedef long double db;
typedef pair<int, int> pii;

const int MAXN = 2e5 + 10;

int n, q, val[MAXN], pos[2][MAXN], D[2][MAXN], cnt[2];
pii arr[MAXN];
char str[MAXN];

bool chk(int x, int flg, int k, int t) {
    if (!k) return true;
    int lp, rp;
    if (flg && (k & 1)) {
        if (pos[0][x] - k / 2 < 1 || pos[1][x] + k / 2 > cnt[1]) return false;
        lp = pos[0][x] - k / 2;
        rp = pos[1][x] + k / 2;
    } else if (flg && !(k & 1)) {
        if (pos[0][x] - k / 2 + 1 < 1 || pos[1][x] + k / 2 > cnt[1]) return false;
        lp = pos[0][x] - k / 2 + 1;
        rp = pos[1][x] + k / 2;
    } else if (!flg && (k & 1)) {
        if (pos[1][x] + k / 2 + 1 > cnt[1] || pos[0][x] - k / 2 < 1) return false;
        rp = pos[1][x] + k / 2 + 1;
        lp = pos[0][x] - k / 2;
    } else {
        if (pos[1][x] + k / 2 > cnt[1] || pos[0][x] - k / 2 < 1) return false;
        rp = pos[1][x] + k / 2;
        lp = pos[0][x] - k / 2;
    }
    int tt = (D[1][rp] - D[0][lp]);
    return tt <= t * 2;
}

int main() {
    IO::read(n), IO::read(q);
    rep(i, 1, n) {
        IO::read(arr[i].first), arr[i].second = i, val[i] = arr[i].first;
    }
    sort(arr + 1, arr + n + 1);
    scanf("%s", str + 1);
    rep(i, 1, n) {
        D[str[arr[i].second] == 'L'][++cnt[str[arr[i].second] == 'L']] = arr[i].first;
        pos[0][arr[i].second] = cnt[0], pos[1][arr[i].second] = cnt[1];
    }
    rep(i, 1, q) {
        int x, t;
        IO::read(x), IO::read(t);
        int l = 0, r = n, res;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (chk(x, str[x] == 'L', mid, t)) res = mid, l = mid + 1;
            else r = mid - 1;
        }
        int ans;
        int tmp = str[x] == 'L';
        if (str[x] == 'L' && (res & 1)) {
            ans = D[0][pos[0][x] - res / 2] + t;
        } else if (str[x] == 'L' && !(res & 1)) {
            ans = D[1][pos[1][x] + res / 2] - t;
        } else if (str[x] == 'R' && (res & 1)) {
            ans = D[1][pos[1][x] + res / 2 + 1] - t;
        } else {
            ans = D[0][pos[0][x] - res / 2] + t;
        }
        printf("%d\n", abs(ans));
    }
    return 0;
}

总结

A 写了个假的（事实上也不是很假）算法过了还是挺幸运的。不过标算也挺显然的（

B 和正解就差一步，已经考虑到了一个车忽略序号只考虑标记那个地步，并且手玩了一下（（