瓜瓜小屋
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
38
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
int nxt[maxn][26];

char s[maxn], t[maxn];

int main() {
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    for (int i = len; i >= 1; i--) {
        for (int j = 0; j < 26; j++) {
            nxt[i - 1][j] = nxt[i][j];
        }
        nxt[i - 1][s[i] - 'a'] = i;
    }

    int q;
    scanf("%d", &q);
    while(q--) {
        scanf("%s", t);
        int len1 = strlen(t);
        int f = 0;
        for (int i = 0, u = 0; i < len1; i++) {
            int v = t[i] - 'a';
            u = nxt[u][v];
            if(u==0) {
                f = 1;
                break;
            }
        }
        if(f) {
            printf("NO\n");
        }
        else
            printf("YES\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
char s[maxn << 1] = "##";
int n, hw[maxn << 1];
int l[maxn << 1], r[maxn << 1];
void manacher(char* a) {//字符串a下标从0开始
    int len = strlen(a);
    for (int i = 0; i < len; i++) {
        s[i * 2 + 2] = a[i];
        s[i * 2 + 3] = '#';
    }
    n = len * 2 + 2;
    s[n] = 0;
    int maxr = 0, m = 0;
    for (int i = 1; i < n; i++) {
        if (i < maxr)
            hw[i] = min(hw[m * 2 - i], hw[m] + m - i);
        else
            hw[i] = 1;
        while (s[i + hw[i]] == s[i - hw[i]]) hw[i]++;
        if (hw[i] + i > maxr) {
            m = i;
            maxr = hw[i] + i;
        }
    }
}
阅读全文 »

发表于 更新于 分类于 ，

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

使用快慢指针，让nxt指针先向后移动N次

这样nxt指针和pre指针之间的间隔则为N

然后，nxt和pre同时向后移动，当nxt移动到链表的尾部，pre依然和它间隔为N，那么此时的pre就是链表的倒数第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
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* pre = head;
        ListNode* nxt = head;
        for(int i=0;i<n;i++) {
            nxt = nxt->next;
        }
        if(nxt == nullptr) {
            head = head->next;
            return head;
        }

        while(nxt!=nullptr) {
            nxt = nxt->next;
            if(nxt == nullptr) {
                cout<<pre->val<<endl;
                pre->next = pre->next->next;
                return head;                
            }
            pre = pre->next;
        }  
        return head;
    }
};
阅读全文 »

发表于 更新于 分类于 ，

模板

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
struct SegTree {
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    ll a[maxn << 2];
    int tag[maxn << 2];
    void pushup(int rt) {
        a[rt] = min(a[rt << 1], a[rt << 1 | 1]);
    }
    void push(int rt,int x) {
        a[rt] += x;
        tag[rt] += x;
    }
    void pushdown(int rt) {
        if(!tag[rt])
            return;
        push(rt << 1, tag[rt]);
        push(rt << 1 | 1, tag[rt]);
        tag[rt] = 0;
    }
    void build(int l = 1,int r = n,int rt = 1) {
        if(l==r) {
            a[rt] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(lson), build(rson);
        pushup(rt);
    }
    void update(int L, int R, int x, int l = 1, int r = n,int rt = 1) {
        if(L<=l&&r<=R) {
            push(rt, x);
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(rt);
        if(L<=m)
            update(L, R, x, lson);
        if(R>m)
            update(L, R, x, rson);
        pushup(rt);
    }
    ll query(int L, int R, int l = 1, int r = n,int rt = 1) {
        if(L<=l&&r<=R) {
            return a[rt];
        }
        int m = (l + r) >> 1;
        pushdown(rt);
        if(R<=m)
            return query(L, R, lson);
        if(L>m)
            return query(L, R, rson);
        return min(query(L, R, lson), query(L, R, rson));
    }
} f;
阅读全文 »

发表于 更新于 分类于

模板

http://xlorpaste.cn/y0xia1

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
struct Hash() {
    const int mod = 1e9 + 7;
    const int SEED = 13331;
    long long p[maxn], f[maxn], ff[maxn];
    int n;
    void Hash(string s) {
        n = s.size();
        f[0] = s[0] - 'a' + 1;
        p[0] = 1;
        for (int i = 1; i < n; i++) {
            f[i] = (f[i - 1] * SEED % mod + (s[i] - 'a' + 1)) % mod;
            p[i] = p[i - 1] * SEED % mod;
        }
        ff[n - 1] = s[n - 1] - 'a' + 1;
        for (int i = n - 2; i >= 0; i--) {
            ff[i] = (ff[i + 1] * SEED % mod + (s[i] - 'a' + 1)) % mod;
        }
    }
    long long h(int l, int r) {
        if (l == 0)
            return f[r];
        return (f[r] - f[l - 1] * p[r - l + 1] % mod + mod) % mod;
    }
    long long hh(int l, int r)
    {
        if (r == n - 1)
            return ff[l];
        return (ff[l] - ff[r + 1] * p[r - l + 1] % mod + mod) % mod;
    }
};
阅读全文 »

发表于 更新于 分类于

dijkstra 基于贪心思想，利用了三角不等式，因为全局最小值不可能再被其他节点更新

dijkstra 用于解决单源最短路问题

disjstra 用于解决非负权图问题

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
55
56
57
#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 100;
typedef pair<int,int> pii;

struct node {
    int v;
    int w;
};
vector<node> e[maxn];
int dis[maxn];
bool vis[maxn];
int pre[maxn];

void dijkstra(int s) {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    memset(dis, inf, sizeof(dis));
    dis[s] = 0;
    q.push({dis[s], s});
    while(!q.empty()) {
        pii t = q.top();
        q.pop();
        int u = t.second;
        if(vis[u])
            continue;
        vis[u] = true;
        for(node x:e[u]) {
            int v = x.v;
            int w = x.w;
            if(dis[v]>dis[u]+w) {
                dis[v] = dis[u] + w;
                pre[v] = u;
                q.push({dis[v], v});
            }
        }
    }
}

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 0;i<n;i++) {
        pre[i] = -1;
    }
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back((node){v, w});
        // e[v].push_back((node){u, w});
    }
    dijkstra(s);
    for (int i = 1; i <= n;i++) {
        cout << dis[i] << " ";
    }
    cout << endl;
}
阅读全文 »

发表于 更新于 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
priority_queue<int,vector<int>,greater<int> >q;//小顶堆
priority_queue<int> q;//大顶堆,默认

struct node{
    int c, fc;
    bool operator < (const node& a) const {
        return fc < a.fc;//大顶
    }
}
priority_queue<node> q;

struct node2{//重写仿函数
    bool oprator() (node a,node b) {
        return a,x<b.x;//大顶
    }
}
priority_queue<node,vector<node>,node2> q;
阅读全文 »

发表于 更新于 分类于 ，

code

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
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 100;
int head[maxn], to[maxn * 2], nxt[maxn * 2], d[maxn * 2], tot;
int n, m;
void add(int x, int y, int w){
    to[++tot] = y; nxt[tot] = head[x]; d[tot] = w; head[x] = tot;
}
int dp[maxn][20], dep[maxn], dis[maxn];
void dfs(int u, int fa){
    dp[u][0] = fa; dep[u] = dep[fa] + 1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa) continue;
        dis[v] = dis[u] + d[i];
        dfs(v, u);
    }
}
void init(){
    memset(dp, 0, sizeof(dp));
    dep[0] = dis[0] = 0;
    dfs(1, 0); 
    for (int j = 1; j < 20; j++) 
        for (int i = 1; i <= n; i++) 
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
int qlca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int tmp = dep[x] - dep[y];
    for (int i = 0; tmp; i++, tmp >>= 1)
        if (tmp & 1) x = dp[x][i];
    if (x == y) return x;
    for (int i = 19; i >= 0; i--) {
        if (dp[x][i] != dp[y][i]) {
            x = dp[x][i]; y = dp[y][i];
        }
    }
    return dp[x][0];
}
int dist(int x,int y) {
    int u = qlca(x, y);
    int ans =  dis[x] + dis[y] - 2*dis[u];
    return dis[x] + dis[y] - 2*dis[u];
}
阅读全文 »

发表于 更新于 分类于 ，

例题

Equivalent Prefixes-前缀笛卡尔树

序列u，v 对于[1,ans][1,ans]上所有的[L,R][L,R](1<=L<=R<=ans<=n)(1<=L<=R<=ans<=n)

都满足RMQ(u,L,R)=RMQ(v,L,R)RMQ(u,L,R)=RMQ(v,L,R)

求max(ans)max(ans);

分析：考虑判断两个序列的前缀笛卡尔树是否相等

注意，如果前缀笛卡尔树相等，则可以判断每一个栈深都相同，想想为什么？、

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
#include <bits/stdc++.h>
#include<stdint.h>
#define int long long
#define scan(n) scanf("%lld", &(n))
#define scann(n, m) scanf("%lld%lld", &(n), &(m))
#define scannn(a, b, c) scanf("%lld%lld%lld", &(a), &(b), &(c))
#define prin(n) printf("%lld", (n))
#define pb push_back
#define mp make_pair
#define ms(a) memset(a, 0, sizeof(a))
#define fo(i, a, b) for (int i = (a); i <= (b); i++)
#define ro(i, a, b) for (int i = (a); i >= (b); i--)
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 1e5+100;
int n;
int a[maxn],b[maxn];
int s1[maxn],s2[maxn];
int32_t main() {
    while(scan(n)!=EOF){
        fo(i,1,n)scan(a[i]);
        fo(i,1,n)scan(b[i]);
        int head1=1,head2=1,tail1=1,tail2=1;
        s1[head1]=s2[head2]=inf;
        int maxpos=1;
        fo(i,1,n){
            while(head1<=tail1&&s1[tail1]>a[i])tail1--;
            while(head2<=tail2&&s2[tail2]>b[i])tail2--;
            if(tail1!=tail2)break;
            s1[++tail1]=a[i],s2[++tail2]=b[i];
            maxpos=i;
        }
        cout<<maxpos<<endl;
    }
    return 0;
}
阅读全文 »

发表于 更新于 分类于 ，

树形DP

Tree painting

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
#include <bits/stdc++.h>
#include<stdint.h>
#define int long long
#define scan(n) scanf("%lld", &(n))
#define scann(n, m) scanf("%lld%lld", &(n), &(m))
#define scannn(a, b, c) scanf("%lld%lld%lld", &(a), &(b), &(c))
#define prin(n) printf("%lld", (n))
#define pb push_back
#define mp make_pair
#define ms(a) memset(a, 0, sizeof(a))
#define fo(i, a, b) for (int i = (a); i <= (b); i++)
#define ro(i, a, b) for (int i = (a); i >= (b); i--)
const int inf = 0x3f3f3f3f;
using namespace std;
const int maxn = 2e5+100;
vector<int>e[maxn];
int siz[maxn];
int ans,n;
int u,v;
void getsize(int v,int u){
    siz[v]=1;
    for(int x:e[v]){
        if(x==u)continue;
        getsize(x,v);
        siz[v]+=siz[x];
    }
}
void dfs(int v,int u,int t){
    ans=max(ans,t);
    cout<<v<<" "<<u<<" "<<t<<endl;
    for(int x:e[v]){
        if(x==u)continue;
        dfs(x,v,t-2*siz[x]+n);
    }
}
int32_t main() {
    scan(n);
    fo(i,1,n-1){
        scann(u,v);
        e[u].pb(v);e[v].pb(u);
    }
    getsize(1,0);
    int t=0;
    fo(i,1,n)t+=siz[i];
    dfs(1,0,t);
    printf("%lld",ans);
    return 0;
}
阅读全文 »

发表于 更新于 分类于 ，

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int c[maxn * 2];
int lowbit(int x) {
    return x & (-x);
}

void add(int i,int d) {
    while(i<maxn*2) {
        c[i] += d;
        i += lowbit(i);
    }
}

int query(int i) {
    int ret = 0;
    while(i>0) {
        ret += c[i];
        i -= lowbit(i);
    }
    return ret;
}
阅读全文 »

发表于 更新于 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;

bitset<5> b, a;
int main() {
    cout << b << endl; //00000

    b.set(2);
    cout << b << endl;//00100

    a.set(3);
    cout << a << endl;//01000

    b ^= a;//(00100)^(01000)
    cout << b << endl;//01100

    b.reset(3);//00100
    cout << b << endl;

    b.flip();//11011
    cout << b << endl;
}
阅读全文 »

发表于 更新于 分类于 ，

prefix function 前缀函数

1
2
3
4
5
6
7
8
9
10
vector<int> prefix_function(int n){
    vector<int> pi(n);
    for (int i = 1; i < n;i++){
        int j = pi[i - 1];
        while(j>0&&t[i]!=t[j])j = pi[j - 1];
        if(t[i]==t[j])j++;
        pi[i] = j;
    }
    return pi;
}
阅读全文 »

发表于 更新于 分类于

模板

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 6000 + 5;
int fa[maxn],sz[maxn];
struct node{
    int x, y, w;
} e[maxn];
bool operator < (node a,node b) {
    return a.w < b.w;
}
int find(int x) {
    return (x == fa[x] ? x : find(fa[x]));
}
void init(int n) {
    for (int i = 1; i <= n;i++) {
        fa[i] = i;
        sz[i] = 1;
    }
}
int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        int n;
        scanf("%d", &n);
        init(n);
        for (int i = 1; i <= n-1;i++) {
            scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].w);
        }
        sort(e + 1, e + 1 + n - 1);
        ll ans = 0;
        for (int i = 1; i <= n - 1;i++) {
            int x = find(e[i].x);
            int y = find(e[i].y);
            int w = e[i].w;
            if(x==y)
                continue;
            ans += (w + 1) * (sz[x] * sz[y] - 1);
            fa[x] = y;
            sz[y] += sz[x];
        }
            printf("%lld\n", ans);
    }
}
阅读全文 »