• problem link

  • 題目理解：給 N (N <= 10^5) 個數字，第 i 個為 Si (0 <= Si <= 10^5)，給 Q (Q <= 10^5) 個詢問，第 i 個為 Wi (0 <= Wi <= 2 * 10^5)，問是否存在 Si + Sj == Wi (i <= j)？

  • 解法：
    首先先將 S 照升序排序
    對於每筆詢問，先特判一定無解的狀況(S[0] * 2 > W or S[N-1] * 2 < W) 跟 i == j 的狀況(此時 W 為偶數，二分搜 W/2 即可)

    接著尋找 i < j 的狀況
    維護兩個下標 i, j
    首先初始化 i, j
    j 為最大的 j 使得 S[j] <= W (S[j] > W 顯然無解)
    i 為最小的 i 使得 S[i] >= W - S[j] (S[i] < W - S[j] 顯然無解)

    接著對於每個 i ，迭代尋找最大的 j 使得 S[i] + S[j] <= W
    對於下一個 i 而言，因為 S[i] + S[j + 1] > W 而且 S[i + 1] >= S[i]
    所以 S[i + 1] + S[j + 1] > W，故 i + 1 對應的 j 可以從當前的 j 開始尋找

  • 複雜度 O(QN)
    每筆詢問最多遍歷 Ｎ 個數字，有 Q 筆詢問
  • 其實照這題的規模這樣的複雜度應該是過不了的，可能是測資太善良吧
    測資更新惹，我的 code TLE 惹
    等我或其他人想出更好的解再更新吧
  • 蜥蜴說是用 FFT 解，然而我不會 QAQ
Copy 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 228;
int k[maxn];
int N;
bool ok(int w)
{
    if (k[0] * 2 > w || k[N-1] * 2 < w)
        return false;
    if (!(w & 1) && binary_search(k, k + N, w / 2))
        return true;
    if (N < 2 || k[0] + k[1] > w || k[N-2] + k[N-1] < w)
        return false;
    int j = upper_bound(k, k + N, w) - k - 1;
    int i = lower_bound(k, k + j - 1, w - k[j]) - k;
    for (; i < j; ++i) {
        while (i < j && k[i] + k[j] > w)
            --j;
        if (i < j && k[i] + k[j] == w)
            return true;
    }
    return false;
}
int main()
{
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf("%d", k + i);
    sort(k, k + N);
    int Q;
    scanf("%d", &Q);
    while (Q--) {
        int w;
        scanf("%d", &w);
        puts(ok(w) ? "yes" : "no");
    }
}
view raw tnfshoj/196.cpp delivered with ❤ by emgithub