\(\Theta(n^2)\)暴力还是很好写的，先枚举水平线，然后再分上下讨论；讨论中，我们都要从左往右枚举，但是我们有两个指针\(lptr, rptr\)，我们可以在过程中维护在\([lptr, rptr]\)之间的颜色数始终严格小于\(k\)，然后再用点个数更新答案。
那么正解就没这么好写了。我们考虑在\(k\)中枚举一个被排除的颜色，然后分情况讨论：
详细见代码：
看到这篇题解之后立马 A 掉了，真的很简洁的一个做法。
我们有\(gcd(x,a_0)=a_1\)，根据结论\(gcd(a,b)=c \to gcd(\frac{a}{c},\frac{b}{c})=1\)，可以推出：
\[gcd(\frac{x}{a_1},\frac{a_0}{a_1})\]
另一个式子\(lcm(x,b_0)=b_1\)可以转换为：
\[ lcm(x,b_0)=b_1 \\ gcd(x,b_0)*lcm(x,b_0)=xb_0 \\ gcd(x,b_0)=\frac{xb_0}{b_1} \\ gcd(\frac{b_1}{b_0},\frac{b_1}{x})=1 \]
可以看出，\(x\)为\(b_1\)的一个约数，\(a_1\)是\(x\)的一个约束，根据这两个条件和两个\(gcd\)条件，进行枚举即可。
// CH3201.cpp
#include <bits/stdc++.h>
using namespace std;
int n, a0, a1, b0, b1;
int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); }
int main()
{
scanf("%d", &n);
while (n--)
{
int ans = 0;
scanf("%d%d%d%d", &a0, &a1, &b0, &b1);
int p = b1 / b0, q = a0 / a1;
for (int x = 1; x * x <= b1; x++)
if (b1 % x == 0)
{
if (x % a1 == 0 && gcd(p, b1 / x) == 1 && gcd(q, x / a1) == 1)
ans++;
int y = b1 / x;
if (x == y)
continue;
if (y % a1 == 0 && gcd(p, b1 / y) == 1 && gcd(q, y / a1) == 1)
ans++;
}
printf("%d\n", ans);
}
return 0;
}
这道题耗了我一个上午。今天上午因为得知 NOIp 2018 成绩之后无法稳定心态去上课，所以翘课来机房写题。而当我看了半天的书和题解之后，我整合出了一个思路。
我们首先把整个序列存入\(pre[]\)数组之中，然后我们从端点\(L=1\)开始枚举右端点。我们选择倍增来加速。写一个\(check(num)\)函数来检测该区间内的校验值是否符合标准。校验值的计算策略是进行排序之后取最大和最小、次大和次小、…进行计算。我们排序可以使用归并排序的思想，因为我们的区间长度是以\(2\)为底的幂，且是从小到的枚举的，所以我们每次只需要排序区间右半部分，然后进行合并操作即可。具体看代码吧。
暑假和小学神仙们集训的时候发过这道题，一直不知道如何去解决。一个月前crazydave大佬给我简述过二分答案的原理，而蒟蒻我今天才搞定这些。
我们先来看例题：洛谷P2678
这是一道NOIP提高组的简单题（我太菜了），主要是通过枚举答案，在每次枚举时检测能不能符合要求即可。先看代码：
// P2678.cpp
#include <iostream>
using namespace std;
const int maxn = 500020;
int L, N, M;
int D[maxn];
bool check(int num)
{
int last = 0;
int cnt = 0;
for (int i = 0; i <= N; i++)
if (D[i] - last < num)
cnt++;
else
last = D[i];
if (cnt > M)
return false;
return true;
}
void solve()
{
int left = 0;
int right = L;
int ans = 0;
while (left <= right)
{
int mid = (left + right) / 2;
if (check(mid))
left = mid + 1, ans = mid;
else
right = mid - 1;
}
cout << ans;
}
int main()
{
cin >> L >> N >> M;
for (int i = 0; i < N; i++)
cin >> D[i];
D[N] = L;
solve();
return 0;
}
check函数就是验证答案num（也就是我们枚举出来的答案）是否符合要求，在这里便是检测当最小距离为num时，移走的石子会不会超过限制。如果超过了，返回false，二分便会把区间调为[left,mid-1]，以降低最大值来试探限制；没有超过，则返回true，二分把区间调整为[mid+1,right]，以追求更大的最大值。
准备枚举一道题答案之前，请考虑二分答案。如果可以二分答案，那么时间复杂度会极度降低，从O(n^2)转变为O(n log n)。二分答案的结构就是二分代码和检验答案正确性代码。如果能通过正确性检查，那么追求更大（小）的答案并重新枚举；如果无法通过，则把区间调整，在较小（大）区间内追求更大（小）的答案。亦复如此。