二分與前綴和

二分

整數二分

整數二分要注意邊界，最好背過一套模板

bool check(int x) {
    /*檢查 x 是否滿足要求*/
}

// 區間[l, r]被劃分成[l, mid - 1]和[mid, r]時使用：
void bsearch_1(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }
}
// 區間[l, r]被劃分成[mid + 1, r]和[l, mid]時使用：
void bsearch_1(int l, int r) {
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1;
        else
            r = mid;
    }
}

789. 數的范圍

給定一個按照升序排列的長度為n的整數陣列，以及 q 個查詢，

對于每個查詢，回傳一個元素k的起始位置和終止位置（位置從0開始計數），

如果陣列中不存在該元素，則回傳“-1 -1”，

輸入格式：

第一行包含整數n和q，表示陣列長度和詢問個數，

第二行包含n個整數（均在1~10000范圍內），表示完整陣列，

接下來q行，每行包含一個整數k，表示一個詢問元素，

輸出格式：

共q行，每行包含兩個整數，表示所求元素的起始位置和終止位置，

如果陣列中不存在該元素，則回傳“-1 -1”，

資料范圍：

1≤n≤100000,

1≤q≤10000,

1≤k≤10000

輸入樣例：

6 3
1 2 2 3 3 4
3
4
5

輸出樣例：

3 4
5 5
-1 -1

代碼：

#include<iostream>

using namespace std;
const int N = 100001;
int a[N];

int main() {
    int n, k, x;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < k; i++) {
        cin >> x;
        //先找左端點
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (a[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }
        if (a[r] == x) {
            cout << r << " ";
            //找到左端點后找右端點
            r = n - 1;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (a[mid] <= x)
                    l = mid;
                else
                    r = mid - 1;
            }
            cout << l << endl;
        } else//找不到左端點直接輸出 -1 -1
            cout << "-1 -1" << endl;
    }
    return 0;
}

浮點數二分

相對整數二分來說簡單多了~ 沒有坑人的邊界問題

bool check(int x) {
    /*檢查 x 是否滿足要求*/
}

void bserach(double l, double r) {
    while (r - l > 1e6) {//題目要求精度
        double mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }
}

790. 數的三次方根

給定一個浮點數n，求它的三次方根，

輸入格式：

共一行，包含一個浮點數n，

輸出格式：

共一行，包含一個浮點數，表示問題的解，

注意，結果保留6位小數，

資料范圍：

?10000 ≤ n ≤ 10000

輸入樣例：

1000.00

輸出樣例：

10.000000

代碼：

#include<iostream>
#include<cstdio>

using namespace std;

int main() {
    double n;
    bool fu = false;
    cin >> n;
    if (n < 0) {
        fu = true;
        n *= (-1);
    }
    double l = 0, r = 10001;
    double mid;
    while (r - l > 1e-8) {
        mid = (l + r) / 2;
        if (mid * mid * mid > n)
            r = mid;
        else
            l = mid;
    }
    if (fu)
        mid *= (-1);
    printf("%.6f", mid);
    return 0;
}

前綴和

• 前綴和矩陣 S x y = S x ? 1 , y + S x , y ? 1 ? S x ? 1 , y ? 1 + a x , y S_{xy} = S_{x-1,y} + S_{x,y-1} - S_{x-1,y-1} + a_{x,y} Sxy?=Sx?1,y?+Sx,y?1??Sx?1,y?1?+ax,y? （容斥原理）
• 利用前綴和矩陣計算子矩陣的和 [ x 1 y 1 , x 2 y 2 ] = S x 2 , y 2 ? S x 2 , y 1 ? 1 ? S x 1 ? 1 , y 2 + S x 1 ? 1 , y 1 ? 1 [x_1y_1,x_2y_2] = S_{x_2,y_2} - S_{x_2,y_1-1} - S_{x_1-1,y_2} + S_{x_1-1,y_1-1} [x1?y1?,x2?y2?]=Sx2?,y2???Sx2?,y1??1??Sx1??1,y2??+Sx1??1,y1??1?

1230. K倍區間

給定一個長度為 N 的數列，A1,A2,…AN，如果其中一段連續的子序列 Ai,Ai+1,…Aj 之和是 K 的倍數，我們就稱這個區間 [ i , j ] 是 K 倍區間，

你能求出數列中總共有多少個 K 倍區間嗎？

輸入格式：

第一行包含兩個整數 N 和 K，

以下 N 行每行包含一個整數 Ai，

輸出格式：

輸出一個整數，代表 K 倍區間的數目，

資料范圍：

1 ≤ N , K ≤ 100000

1 ≤ Ai ≤ 100000

輸入樣例：

5 2
1
2
3
4
5

輸出樣例：

6

代碼：

#include<iostream>

using namespace std;
const int N = 100010;
long long int n, k, x, ans = 0;
long long int s[N];
long long int res[N];

int main() {
    cin >> n >> k;
    res[0] = 1;
    //s[0]%k=0,故余數為0的數已經有一個了
    for (long long int i = 1; i <= n; i++) {
        cin >> x;
        s[i] = s[i - 1] + x;
        ans += res[s[i] % k];
        res[s[i] % k]++;
    }
    cout << ans << endl;
    return 0;
}