一些值得看的题目记录qwq

白兔的字符串【字符串hash】
思路：根据题目描述，可以把T串扩展成2倍，然后每lenT段求一个字符串hash值，这样就可以求得所有同构串的hash值了。然后对于新串，每隔长度为lenT段求一个hash，看这个hash值是否出现即可。
tips:这题听说map会T, 可以手写一个二分查找，起到一样的效果。

#include<bits/stdc++.h>
#define ll unsigned long long 
using namespace std;

const int N = 2000010, P = 131;

int n,m,len;
ll h[N],p[N];
char t[N],s[N];

ll query(int l, int r){ return h[r] - h[l - 1] * p[r - l + 1];} 

int main(){
    cin >> t + 1;
    len = strlen(t + 1);
    for(int i = 1; i <= len; ++ i)    t[i + len] = t[i];
    p[0] = 1;
    for(int i = 1; i <= N - 10; ++ i)    p[i] = p[i - 1] * P;
    for(int i = 1; i <= 2 * len; ++ i)    h[i] = h[i - 1] * P + t[i];
    vector<ll> v;
    for(int i = 1; i <= len; ++ i)    v.push_back(query(i, i + len - 1));
    sort(v.begin(), v.end());
    cin >> m;
    while(m --){
        cin >> s + 1;
        int lens = strlen(s + 1), ans = 0;
        for(int i = 1; i <= lens; ++ i)    h[i] = h[i - 1] * P + s[i];
        for(int i = 1; i + len - 1 <= lens; ++ i){
            ll now = query(i, i + len - 1);
            int pos = lower_bound(v.begin(), v.end(), now) - v.begin();
            if(v[pos] == now)    ans ++;
        }
        cout << ans << endl;
    } 
    return 0;
}

假的字符串【Trie + 拓扑排序】
题意：
给定n个字符串，互不相等，你可以任意指定字符之间的大小关系（即重定义字典序），求有多少个串可能成为字典序最小的串，并输出它们。
思路：最直观的思路就是用字典树处理字符串，如果一个串是其他字符串的前缀，那这些其他字符串都不可能满足要求。
但是还需要判断其他：如aba abb bab bba,abb永远不可能满足要求【如果最后一次比较b > a，那最小的串第一位会是b,不可能是a】, 所以还需要用topsort判断一下可不可能出现环。
tips:这里我一开始in初始化成-1是为了方便判断某个字母是不是出现过了。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 300010, M = 1010, S = 30010;

string s[S];
int son[N][26],idx,n,col[N],in[M],top[M],num;
int edgeidx,ne[M],h[30],e[M];

void add(int a, int b){ e[edgeidx] = b, ne[edgeidx] = h[a], h[a] = edgeidx ++, in[b] ++;}

void insert(string s){
    int p = 0;
    for(int i = 0; s[i]; ++ i){
        int u = s[i] - 'a';
        if(!son[p][u])    son[p][u] = ++ idx;
        p = son[p][u];
    }
    col[p] ++;
}

bool query(string s){
    int p = 0;
    for(int i = 0; s[i]; ++ i){
        int u = s[i] - 'a';
        for(int j = 0; j <= 25; ++ j){
            if(j == u)    continue ;
            if(son[p][j]){
                if(in[u] == -1)    in[u] = 0;
                if(in[j] == -1)    in[j] = 0;
                add(u, j);
            }
        }
        if(col[p])    return false;
        p = son[p][u];
    }
    return true;
}

bool topsort(){
    queue<int> q;
    for(int i = 0; i <= 25; ++ i){
        if(in[i] == -1)    continue ;
        num ++;
        if(!in[i])    q.push(i);
    }
    int cnt = 0;
    while(!q.empty()){
        int fr = q.front(); q.pop();
        cnt ++;
        for(int i = h[fr]; ~i; i = ne[i]){
            int j = e[i];
            if(!(-- in[j]))    q.push(j); 
        }
    } 
    return cnt == num;
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; ++ i){
        cin >> s[i];
        insert(s[i]);
    }
    vector<string> v;
    for(int i = 1; i <= n; ++ i){
        edgeidx = 0,  num = 0;
        memset(h, -1, sizeof h);
        memset(in, -1, sizeof in);
        if(query(s[i]) && topsort())    v.push_back(s[i]);
    }
    cout << v.size() << endl;
    for(auto u : v)    cout << u << endl;
    return 0;
}

奶牛异或【01字典树，前缀和】
思路：经典题了，写一次有一次的收获。
异或和加有很像的性质，既然要求连续的一段，可以利用前缀和的思想求前缀异或和。
几个注意事项：
1.这样写的01字典树求的是和s[i]相比能异或得到的最大数，如果要得到异或值，query之后还需要异或；
2.如何保证尽可能靠前？从前向后求，只有now > ans才更新，可以保证；
3.如何保证序列尽可能短？为每个数建立01字典树之后，更新id数组，这样可以保证后面的数（的下标）覆盖前面相同的数（的下标），求得的自然是最短的；
4.为什么一开始要插入一个0,0？因为有可能只有1个数，插入0,0可以不用特殊判断，方便快捷，起到哨兵的作用；
5.为什么不可以先全部insert再query? 因为全部插入后求得的最大值有可能是当前段和后面的段异或得到的，这样l, r就乱了【只能得到异或的最大值】。
6.注意id数组要开M的大小，不能开N，因为id = p,取决于p的大小。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;

const int N = 100010, M = N * 21;

int idx, son[M][2], id[M], n;
int a[N],s[N],l = 1,r = 1,ans;

void insert(int x, int no){
    int p = 0;
    for(int i = 20; i >= 0; -- i){
        int u = x >> i & 1;
        if(!son[p][u])    son[p][u] = ++ idx;
        p = son[p][u];
    }
    id[p] = no;
}

int query(int x){
    int p = 0, res = 0;
    for(int i = 20; i >= 0; -- i){
        int u = x >> i & 1;
        if(son[p][!u])    p = son[p][!u];
        else    p = son[p][u];
    }
    return id[p];
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)    scanf("%d",&a[i]), s[i] = s[i - 1] ^ a[i];
    insert(0, 0);
    for(int i = 1; i <= n; ++ i){
        insert(s[i], i);
        int t = query(s[i]);
        int now = s[i] ^ s[t];
        if(now > ans)    ans = now, l = t + 1, r = i;
    }
    printf("%d %d %d", ans, l, r);
    return 0;
}

巨木之森【思维，树形DP】
思路：本来以为可以换根DP，但是发现不太好写qwq
转化一下可以发现，如果访问全部的节点还要回到起点，那路径长度就是整个树的边权* 2，不用回来就是从起点开始挑一条最长的路，只走1次。【有一点换根的感觉，因为要求每个点作为根节点时的最长路径】。
但是可以发现，到每个点最远的点一定是树的直径的其中一个点【可以反正：假设A,B是直径端点，当前点X距离最远的是C点。如果C不是A,B的任意一点，那A->X->C > A->X->B，AC就比AB长了】。
所以先求树的直径【这里要求出两个端点，只能两次dfs，没法用树形dp求】，然后预处理这两个端点到所有点的距离即可。
tips：这题的dfs函数都是一样的，只是数组不同，可以传参数写，可以简化代码书写难度。而且可以少写一次dfs(见注释).

一些值得看的题目记录qwq

全站热榜