算法模版

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

bool check(int x) {/* ... */} // 检查x是否满足某种性质

// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
// 查找单调递增序列中 >= x 的最小一个数
int bisectr(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
// 查找单调递增序列中 <= x 的最大一个数
int bisectl(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

ListNode* reverseList(ListNode* head) {
    ListNode *pre = nullptr;
    ListNode *cur=head;
    while(cur)
    {
        ListNode *ne=cur->next;
        cur->next=pre;
        pre=cur;
        cur=ne;
    }
    return pre;
}

1
2
3
4
5
6
7
8
9

int qmi(int a, int b, int mod) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}

1
2
3

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j) {
        do i++;
        while (q[i] < x);
        do j--;
        while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = (l + r) >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include<deque>
using namespace std;

const int N=1000010;
int n,k;
int a[N];
int main()
{
    cin>>n>>k;
    deque<int> q;
    // 维护长度k区间的最小值
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(q.size()>0 && i-k+1>q.front()){
            q.pop_front();
        }
        while(q.size()>0 && a[q.back()]>=a[i]){
            q.pop_back();
        }
        q.push_back(i);
        if(i>=k-1){
            cout<<a[q.front()]<<" ";
        }        
    }
    q.clear();
    cout<<endl;
    // 维护长度k区间的最大值
    for(int i=0;i<n;i++){
        if(q.size()>0 && i-k+1>q.front()){
            q.pop_front();
        }
        while(q.size()>0 && a[q.back()]<=a[i]){
            q.pop_back();
        }
        q.push_back(i);
        if(i>=k-1){
            cout<<a[q.front()]<<" "; 
        }
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include<stack>

using namespace std;
int n;
int a[100010];
int main(){
    cin>>n;
    stack<int> stk;
    for(int i=0;i<n;i++){
        cin>>a[i];
        while(stk.size()>0 && stk.top()>=a[i]){
            stk.pop();
        }
        if(stk.size()>0){
            cout<<stk.top()<<" ";
        }
        else cout<<"-1 ";
        stk.push(a[i]);
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Trie {
public:
    vector<Trie*> children;
    bool isEnd;

    Trie()
        : children(26)
        , isEnd(false) {}

    void insert(string& w) {
        Trie* node = this;
        reverse(w.begin(), w.end());
        for (char& c : w) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new Trie();
            }
            node = node->children[idx];
        }
        node->isEnd = true;
    }

    bool search(string& w) {
        Trie* node = this;
        for (int i = w.size() - 1, j = 0; ~i && j < 201; --i, ++j) {
            int idx = w[i] - 'a';
            if (!node->children[idx]) {
                return false;
            }
            node = node->children[idx];
            if (node->isEnd) {
                return true;
            }
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int f[N], sz[N], n;
void init() {
    for (int i = 0; i <= n; i++) {
        f[i] = i;
        sz[i] = 1;
    }
}
int find(int x) {
    if (x != f[x]) f[x] = find(f[x]);
    return f[x];
}
void merge(int a, int b) {
    int fa = find(a), fb = find(b);
    if (fa == fb) return;
    if (sz[fa] < sz[fb]) {
        f[fa] = fb;
        sz[fb] += sz[fa];
    } else {
        f[fb] = fa;
        sz[fa] += sz[fb];
    }
}
init();

1
2
3
4
5
6
7
8

int find(int x) {
    int ans = 0;
    for (int i = x; i!=0; i -= i & -i) ans += tr[i];
    return ans;
}
void add(int x, int c) {
    for (int i = x; i <= n; i += i & -i) tr[i] += c;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

typedef long long ll;
ll a[N],tr[4*N],t[4*N];

void pushup(int u)
{
    tr[u]=tr[u<<1]+tr[u<<1|1];
}
void pushdown(int u,int l,int r)
{
    if(t[u]!=0)
    {
        int mid=l+r>>1;
        tr[u<<1]+=t[u]*(mid-l+1);
        tr[u<<1|1]+=t[u]*(r-mid);
        t[u<<1]+=t[u];
        t[u<<1|1]+=t[u];
        t[u]=0;
    }
}
void build(int u,int l,int r)
{
    if(l==r)
    {
        tr[u]=a[l];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}
ll sum(int u,int l,int r,int s,int e)
{
    if(s<=l&&e>=r)return tr[u];
    int mid=l+r>>1;
    pushdown(u,l,r);
    ll res = 0;
    if(s<=mid)res+=sum(u<<1,l,mid,s,e);
    if(e>=mid+1)res+=sum(u<<1|1,mid+1,r,s,e);
    return res;
}
void update(int u,int l,int r,int s,int e,ll c)
{
    if(s<=l&&e>=r)
    {
        tr[u]+=c*(r-l+1);
        t[u]+=c;
        return ;
    }
    int mid = l+r>>1;
    pushdown(u,l,r);
    if(s<=mid)update(u<<1,l,mid,s,e,c);
    if(e>=mid+1)update(u<<1|1,mid+1,r,s,e,c);
    pushup(u);
}

1
2
3
4
5
6
7
8

int v[N];
void primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (v[i]) continue;
        cout << i << endl;
        for (int j = i; j <= n/i; j++) v[i*j] = 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int primes[N], cnt;
bool st[N];
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

queue<int> q;
for(int i=1;i<=n;i++)
    if (!indegree.count(i))
    {
        indegree[i] = 0;
        q.push(i);
    }
while(q.size())
{
    node = q.front();
    res.push_back(node);
    q.pop();
    for (auto ne:pre[node])
    {
        indegree[ne]--;
        if (indegree[ne]==0) q.push(ne);
    }
}
if (res.size()!=n) cout << -1;
else{
    for (int i=0;i<res.size();i++)
    {
        cout << res[i] << ' ';
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

dijskra+heap
void dijkstra() {
typedef pair<int, int> PII;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    pq.push({0, 1});
    while (pq.size()) {
        int x = pq.top().second;
        pq.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                pq.push({d[y], y});
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

void spfa() {
    queue<int> q;
    memset(d, 0x3f, sizeof d);
    d[1] = 0, v[1] = 1;
    q.push(1);
    while (q.size()) {
        int x = q.front();
        q.pop();
        st[x] = 0;
        for (int i = head[x]; i; i = ne[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                if (!v[y]) q.push(y), v[y] = 1;
            }
        }
    }
}

1
2
3
4
5
6
7

for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void prim() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for (int i = 1; i < n; i++) {
        int x = 0;
        for (int j = 1; j <= n; j++) {
            if (!v[j] && (x == 0 || d[j] < d[x]))
                x = j;
        }
        v[x] = 1;
        for (int y = 1; y <= n; y++) {
            if (!v[y]) d[y] = min(d[y], a[x][y]);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

struct edge {
    int x, y, w;
    bool operator<(const edge& b) {
        return w < b.w;
    }
} e[M];
sort(e + 1, e + m + 1);
// 并查集
for (int i = 1; i <= n; i++) f[
int find(int x)
{
    if(x!=f[x])f[x]=find(f[x]);
    return f[x];
}
for (int i = 1; i <= m; i++) {
    int x = find(e[i].x);
    int y = find(e[i].y);
    if (x == y) continue;
    f[x] = y;
    ans += e[i].z;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

p为模板串
s为目标串
int n=p.size(),m=s.size();
void calcne() {
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
}
for (int i = 1, j = 0; i <= m; i++) {
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j++;
    if (j == n) {
        printf("%d ", i - n);
    }
}

1
2
3
4
5
6
7

for(int i=1;i<=n;i++)//遍历物品
{
    for(int j=V;j>=v[i];j--)//遍历体积 只能用一次反向遍历，无限用正向遍历
    {
        dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

typedef long long ll

int k[n.length];   
ll f[n.length];    
ll dfs(int pos,int lead,int limit){
    if(!pos){return 1;} 
    if(!limit&&!lead&&f[pos]!=-1)return f[pos];
    int up=limit?k[pos]:9;
    int res=0;
    for(int i=0;i<=up;++i){
        if(){}
        else if(){}
        ans+=dfs(pos-1,limit&&i==up,lead&&i==0);
    }
    if(!limit&&!lead)f[pos]=res;
    return res;
}
ll dp(int x){//获取n的上界数组
    int pos=0;
    while(x){
        k[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,true,true);
}
int cntnums(int n) {
    memset(f,-1,sizeof f);
    return f(n);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

for(int i=0;i<n;i++)
    {
        dp[i]=1;//以i结尾 的最大上升子序列长度
        for(int j=0;j<=i;j++)
        {
            if(q[i]>q[j])
            {
                dp[i] = max(dp[i],dp[j]+1);
            }
        }
    }
二分优化𝑂(𝑛𝑙𝑜𝑔𝑛)


stk.push_back(q[0]);
    for(int i=1;i<n;i++)
    {
        if (q[i]>stk.back())
            stk.push_back(q[i]);
        else
        {
            int l=0,r=stk.size();
            while(l<r)
            {
                int mid=(l+r)/2;
                if(stk[mid]<q[i]) l=mid+1;
                else r=mid;
            }
            stk[l] = q[i];
        }
    }

1
2
3
4
5
6
7
8

for(int subset=set;subset!=0;subset=(subset-1)&set)
{
    f[set] = f[subset] + 转移规则
}
subset = set
while(subset):
    f[set] = f[subset] + 转移规则 
    subset = (subset-1)&set

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

for(int cur=0;cur<1<<N;cur++):
{
    for(int i=0;i<N;i++)
    {
        if (state>>i)&1:
        {
            for(int j=0;j<N;j++)
            {
                if(j!=i && (state>>j)&1)
                {
                    f[cur] += f[cur-1<<i-1<<j];
                }
            }
        }
    }
}
    
return f[(1<<N)-1]

1
2
3
4
5
6
7
8
9

void dfs(int u)
{
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j = e[i];
        dfs(j);
        f[u] += max(f[u],f[j]);
    }
}