双指针 一个指向a的开头 另一个指向b的末尾

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int a[N], b[N];


int main() {
    int n, m, x;
    cin >> n >> m >> x;
    for(int i=0; i < n; ++i) scanf("%d", &a[i]);
    for(int j=0; j < m; ++j) scanf("%d", &b[j]);


    for(int i=0, j=m-1; i < n && j >= 0;) {
        while(a[i] + b[j] < x) i++;
        while(a[i] + b[j] > x) j--;
        if(a[i] + b[j] == x) {
            printf("%d %d", i, j);
            return 0;
        }
    } 


    return 0;
} 

双指针模板题

#include <bits/stdc++.h>

using namespace std;
const int N = 100010;
int a[N];
int st[N];

int main() {
    int n;
    scanf("%d", &n);
    for(int i=0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    int res = 1;
    for(int i=0, j=0; i < n; ++i) {
        st[a[i]]++;
        while(st[a[i]] > 1) {
            --st[a[j]];
            j++;
        }

        res = max(i - j + 1, res);
    }

    cout << res;

    return 0;
}

双指针

思路 当前指针指向x时 更新后指针 并将后指针前移到非x的位置 用后指针减去前指针就是连续x的数

#include <bits/stdc++.h>

using namespace std;
const int N = 110;
char s[N];

int main() {
    int n;
    scanf("%d", &n);
    scanf("%s", s);
    int cnt = 0;
    for(int i=0, j=0; i < n; ++i) {
        if(s[i] == 'x') {
            j = i;
            while(j < n && s[j] == 'x') j++;
            cnt += max(j - i - 2, 0);
            i = j - 1;
        }

    }
    cout << cnt << endl;

    return 0;
} 

二分找到需要插入的位置

细节: 从后开始交换时 起始位置是size - 2 终止位置是r + 1

最后需要比较i 和 res[r] 的大小 来确定是否交换 res[r]和res[r + 1]

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res(1, 1);
        for(int i=2; i <= N; ++i) {

            int l = 0, r = res.size() - 1;
            while(l < r) {
                int mid = l + r + 1 >> 1;
                if(compare(i, res[mid])) r = mid - 1;
                else l = mid;
            }
            res.push_back(i);
            for(int j=res.size() - 2; j > r; --j)
                swap(res[j], res[j+1]);
            if(compare(i, res[r])) swap(res[r], res[r+1]);
        }
        return res;

    }
};

注意计算块数的时候h 和 w需要分别除完再相乘

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int > PII;
typedef long long LL;
const int N = 100010;
int w[N], h[N];
int n, k;

bool check(int mid) {
    int res = 0;
    for(int i=0; i < n; ++i) {
        res += w[i] / mid * (h[i] / mid);
        if(res >= k) return true;   
    }
    return false;
} 

int main() {
    cin >> n >> k;
    for(int i=0; i < n; ++i) scanf("%d%d", &h[i], &w[i]); 
    int l = 1, r = 1e5;
    while(l < r) {
        int mid = l + r + 1>> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << r << endl;
    return 0;
}

STL里的hash表会超时

自己手写的 ac了

#include <bits/stdc++.h>


using namespace std;
typedef pair<int, int> PII;
const int N = 5000010;

int main() {
    int n;
    scanf("%d", &n);
    PII m[N];
    memset(m, -1, sizeof m);

    for(int i=0; i * i <= n; ++i) {
        for(int j=i; i * i + j * j <= n; ++j) {
            int x = i * i + j * j;
            if(m[x].first == -1) m[x] = {i, j};
        }
    }

    for(int i=0; i * i <= n; ++i) {
        for(int j=i; i * i + j * j <= n; ++j) {
            int x = n - i * i - j * j;
            if(m[x].first != -1) {
                printf("%d %d %d %d\n", i, j, m[x].first, m[x].second);
                return 0;
            } 
        }

    }

    return 0;
}

二分

查找最左边满足条件 二分中需写成a[mid] >= s

#include <bits/stdc++.h>

using namespace std;
const int N = 5000010;
int n, m;

struct Sum {
    int s, c, d;
    bool operator < (Sum& t) const {
        if(s != t.s) return s < t.s;
        if(c != t.c) return c < t.c;
        return d < t.d;
    }
}sum[N];


int main() {

    scanf("%d", &n);
    for(int c=0; c * c <= n; ++c) {
        for(int d=c; c * c + d * d <= n; ++d){
            int s = c * c + d * d;
            sum[m++] = {s, c, d};
        }
    }

    sort(sum, sum + m);

    for(int a=0; a * a <= n; ++a) {
        for(int b=a; a * a + b * b <= n; ++b) {
            int s = n - a * a - b * b;
            int l = 0, r = m - 1;
            while(l < r) {
                int mid = l + r >> 1;
                if(sum[mid].s >= s) r = mid;
                else l = mid + 1;
            }
            if(sum[r].s == s) {
                printf("%d %d %d %d", a, b, sum[l].c, sum[l].d);
                return 0;
            }
        }
    }   
    return 0;
}

二分模板

#include <bits/stdc++.h>

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

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for(int i=0; i < n; ++i) scanf("%d", &a[i]);

    while(q--) {
        int k;
        scanf("%d", &k);
        int l = 0, r = n - 1;
        while(l < r) {
            int mid = l + r >> 1;
            if(a[mid] >= k) r = mid;
            else l = mid + 1;
        }
        if(a[r] != k) {
            cout << "-1 -1" << endl;
            continue;
        }
        cout << r << " ";

        l = 0, r = n - 1;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if(a[mid] <= k) l = mid;
            else r = mid - 1;
        }
        cout << r << endl;

    }

    return 0;
}

数据范围很小 因此直接使用暴力

枚举子串的长度以及字串的起点 并使用set 或 map存储当前枚举的字串

优化的话 可以使用二分去枚举字串的长度

#include <bits/stdc++.h>

using namespace std;
const int N = 110;


int main() {
    int n;
    scanf("%d", &n);
    string s;
    cin >> s;
    map<string, int> m;
    for(int len=1; len <= n; ++len) {
        bool flag = true;
        for(int i=0; i + len - 1 < n; ++i) {
            string t = s.substr(i, len);
            if(m.count(t)) {
                flag = false;
                break;
            }
            m.insert({t, 1});
        }
        if(flag) {
            cout << len << endl;
            break;
        }
    }
    return 0;
} 

注意统计差分数组中正数和负数时需要不能只+1 需要加上当前的数值

#include <bits/stdc++.h>

using namespace std;
typedef long long LL; 
const int N = 100010;
LL a[N];
LL d[N];


int main() {
    int n;
    scanf("%d", &n);
    for(int i=1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        d[i] = a[i] - a[i - 1];
    }

    LL pos = 0, neg = 0;
    for(int i=2; i <= n; ++i) {
        if(d[i] > 0) pos += d[i];
        else if(d[i] < 0) neg -= d[i];
    }
    printf("%lld\n%lld", max(pos, neg), abs(pos - neg) + 1);

    return 0;
} 

模板题

#include <bits/stdc++.h>

using namespace std;
const int N = 1010;
int a[N][N];
int d[N][N];

void add(int x1, int y1, int x2, int y2, int v) {
    d[x1][y1] += v;
    d[x1][y2 + 1] -= v;
    d[x2 + 1][y1] -= v;
    d[x2 + 1][y2 + 1] += v;
}


int main() {
    int q, n, m;
    cin >> n >> m >> q;
    for(int i=1; i <= n; ++i) {
        for(int j=1; j <= m; ++j) {
            cin >> a[i][j];
            add(i, j, i, j, a[i][j]);
        }
    }

    while(q--) {
        int x1, x2, y1, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        add(x1, y1, x2, y2, c);
    }

    for(int i=1; i <= n; ++i) {
        for(int j=1; j <= m; ++j) {
            d[i][j] = d[i-1][j] + d[i][j-1] - d[i-1][j-1] + d[i][j];
            printf("%d ", d[i][j]);
        }
        puts("");
    } 


    return 0;
}