7月29日

基础组：P1154 奶牛分厩

题意翻译：找到一个最小的 $K$ ，使得对于任意的两个不同的正整数 $i$ 和 $j$，都满足 $a_i \not\equiv a_j \bmod K$。也就是任何两个数模 $K$ 都不同余。

由于 $S_i$ 的上限很小，所以可以枚举 $K$ ，然后 $O(N)$ 去验证。时间复杂度是 $O(|S_I|N)$ 的，会T。

所以我们来解一个同余方程式。

题目要求是求不同余，我们将同余式子变形：

也就是，任意两数之间的差，都不是 $K$ 的倍数。而且注意到 $N$ 只有 $5000$ ，因此我们完全可以先把所有的差值都预处理出来，然后枚举 $K$ ，检查是否有差值为 $K,2K,3K...$ 这样的值就行。

bool st[N]; // st[i] = true 表示存在差值为i的数对

for (int k = 1; k <= 1000001; k ++ ) {
    bool flag = true;
    for (int i = k; i <= 1000000; i += k) {
        if (st[i]) {
            // 发现有差值为k的倍数的数，所以这个k不满足
            flag = false;
            break;
        }
    }
    if (flag) {
        cout << k << endl;
        break;
    }
}

注意，这个和埃氏筛的时间复杂度是一致的，所以不会T，可以近似看作 $O(|S_i|\log\log|S_i|)$

提高组：P1311 [NOIP 2011 提高组] 选择客栈

这是一道计数题，对于这种选数对的计数题，通常可以用双指针或者二分来实现。

具体来说，我们可以枚举其中一个数，然后看另一个数怎么选。通常来说，如果另一个数选择的方式满足单调性，那么就可以用二分或者双指针来实现。

我们再来看这题，也尝试枚举其中一个端点，如下图：

现在枚举固定了其中一个端点 $l$，它的色调是 $x$ ，消费是 $y$ ，然后我找到的最近的一个消费小于等于 $p$ 的点在 $r$ 处，色调是 $z$ 。

也就是说，接下来所有色调为 $x$ 的在 $r$ 及之后的客栈全部都可以作为另一个端点，所以找出这个方案数，累加到答案中即可。其中找方案数可以用二分来实现。

具体来说，可以对每一种色调的客栈都开一个vector，vector<int> v[N]; 中，v[i] 表示色调为 i 的客栈编号组成的数组。我们在这个数组中二分查找 $\ge r$ 的数有几个就可以了。

然后我们思考，当 $l$ 变到 $l+1$ 时，$r$ 依然是 $r$ ，不用走回头路。除非在这之前 $l = r$ 的，需要重新枚举。满足双指针的性质。

综上所述，我们可以双指针+二分解决这道题目。时间复杂度 $O(N \log N)$ 。

$bonus$：思考 $O(N)$ 的做法。

注意到，对于 `v[i]` 来说，其实每次对它查找，也是具有单调性的，也就是下一次查找到的值的位置一定不会比上次查找到的位置要早。那么根据这一点，我们也可以对每个 `v[i]` 设置一个指针，用 `p[i]` 表示当前查找到色调为 `i` 的客栈的位置，初始值都为 `0` (因为vector中push_back数字的时候，默认0下标开始)，然后如果当前不满足就一直往下找就行。

总体来说，每个位置最多会被遍历3次（左指针一次，右指针一次，p[i]一次），所以总的时间复杂度是 $O(N)$ 的。