翻车笔记 ZKY 学长的杂题2 [杂题, 清奇脑回路]

第一篇文章莫名就1w字了

辣鸡Typora打开已经有点卡了...于是新开一个...

计数器:

5

种树

这类问题的合集

[NOI2010]超级钢琴

这个题和上一个一脉相承啊... = =

这个限制不用合并区间 也就不用搞链表了 挺舒服的

然而写着写着发现还有区间重复的问题... = =

去参拜了一发题解才发现还要记录当前的右端点是从哪个区间里选出来的 然后就不会重复了... = =

/**************************************************************
    Problem: 2006
    User: Cansult
    Language: C++
    Result: Accepted
    Time:4484 ms
    Memory:82800 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define LL long long
#define int LL 
#define MAXN (500000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (LS(dq) | 1)
using namespace std;
struct node {
    int le, ri, zh;
} b[MAXN << 2];
struct num {
    int le, ri, zh, lil, lir;
    num() {}
    num(int l, int r, int z, int ll, int rr): le(l), ri(r), zh(z), lil(ll), lir(rr) {}
};
struct cmp {
    bool operator () (const num x, const num y) { return x.zh < y.zh; }
}; 
int n, k, L, R, fr[MAXN], ans;
priority_queue<num, vector<num>, cmp> q;
void js(int dq, int le, int ri) {
    b[dq].le = le, b[dq].ri = ri, b[dq].zh = le;
    if (le == ri) return ;
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi), js(RS(dq), mi + 1, ri);
    b[dq].zh = (fr[b[LS(dq)].zh] > fr[b[RS(dq)].zh]) ? b[LS(dq)].zh : b[RS(dq)].zh;
}
int cx(int dq, int le, int ri) {
    if (le > ri || le < 1 || ri > n) return n + 1;
    if (b[dq].le == le && b[dq].ri == ri) return b[dq].zh;
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (le > mi) return cx(RS(dq), le, ri);
    else if (ri <= mi) return cx(LS(dq), le, ri);
    else {
        int ls = cx(LS(dq), le, mi), rs = cx(RS(dq), mi + 1, ri);
        return (fr[ls] > fr[rs]) ? ls : rs;
    }
}
main() {
    scanf("%lld%lld%lld%lld", &n, &k, &L, &R);
    for (int i = 1, dqx; i <= n; i++) scanf("%lld", &dqx), fr[i] = fr[i - 1] + dqx;
    js(1, 1, n);
    for (int i = 1, maxi; i + L - 1 <= n; i++) maxi = cx(1, i + L - 1, min(n, i + R - 1)), q.push(num(i, maxi, fr[maxi] - fr[i - 1], i + L - 1, i + R - 1));
    for (int i = 1, maxi; i <= k; i++) {
        num dq = q.top();
        q.pop();
        ans += dq.zh;
        maxi = cx(1, max(dq.lil, dq.le + L - 1), min(dq.lir, dq.ri - 1));
        if (maxi >= 1 && maxi <= n) q.push(num(dq.le, maxi, fr[maxi] - fr[dq.le - 1], max(dq.lil, dq.le + L - 1), min(dq.lir, dq.ri - 1)));
        maxi = cx(1, max(dq.lil, dq.ri + 1), min(n, min(dq.lir, dq.le + R - 1)));
        if (maxi >= 1 && maxi <= n) q.push(num(dq.le, maxi, fr[maxi] - fr[dq.le - 1], max(dq.lil, dq.ri + 1), min(dq.lir, dq.le + R - 1)));
    }
    printf("%lld", ans);
    return 0;
}

[Noi2014]动物园

emmmm...一开始看错题了...以为要求最长的不超过中间的border...

后来发现是要求个数... = = 感觉用树状数组做肥肠显然啊

感觉我的kmp似乎要重新学习一个了... = =

/**************************************************************
    Problem: 3670
    User: Cansult
    Language: C++
    Result: Accepted
    Time:3512 ms
    Memory:93596 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define lowbit(i) ((i) & (-(i)))
#define MAXN (1000000 + 5)
#define Aufun (1000000000 + 7)
#define LL long long
using namespace std;
struct edg {
    int from, to, next;
} tb[MAXN << 1];
int g[MAXN], cntb, b[MAXN], n, nex[MAXN];
LL ans;
char s[MAXN];
void xg(int wz, int zh) {
    if (!wz) return ;
    for (int i = wz; i <= n; i += lowbit(i)) b[i] += zh;
}
int cx(int wz) {
    int re = 0;
    for (int i = wz; i; i -= lowbit(i)) re += b[i];
    return re;
}
void adn(int from, int to) {
    tb[++cntb].next = g[from];
    tb[cntb].from = from, tb[cntb].to = to;
    g[from] = cntb;
}
void dfs(int dq, int fa) {
    ans = ans * (cx((dq) / 2) + 1) % Aufun;
    xg(dq, 1);
    for (int i = g[dq]; i; i = tb[i].next) 
        if (tb[i].to != fa)
            dfs(tb[i].to, dq);
    xg(dq, -1);
}
void solve() {
    memset(g, 0, sizeof(g));
    memset(b, 0, sizeof(b));
    memset(nex, 0, sizeof(nex));
    cntb = 0;
    n = strlen(s + 1);
    adn(0, 1);
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && s[j + 1] != s[i]) j = nex[j];
        nex[i] = j += (s[i] == s[j + 1]);
        adn(nex[i], i);
    }
    ans = 1;
    dfs(0, 0);
    printf("%lld\n", ans);
}
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s", s + 1);
        solve();
    }
    return 0;
}

我怎么感觉\(\mathrm O(n)\)的那个递推和这个差不多呢 = = 这复杂度真的是\(\mathrm O(n)\)的吗...

[Poi2000]病毒

复(学)习字符串...

trie图上找环...找到了就说明可以一直匹配...

环上的任意节点跳fail到root都不能是结尾(以病毒串为后缀)

发现我不会找环了都...

/**************************************************************
    Problem: 2938
    User: Cansult
    Language: C++
    Result: Accepted
    Time:96 ms
    Memory:1900 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (30000 + 5)
#define MAXC (2)
using namespace std;
struct node {
    int fail, son[MAXC], isend;
} b[MAXN];
int cntb, n;
bool vis[MAXN], inq[MAXN];
char s[MAXN];
void init() {
    queue<int> q;
    for (int i = 0; i < MAXC; i++) 
        if (b[0].son[i])
            q.push(b[0].son[i]);
    while (!q.empty()) {
        int dq = q.front();
        q.pop();
        for (int i = 0; i < MAXC; i++)
            if (b[dq].son[i]) b[b[dq].son[i]].fail = b[b[dq].fail].son[i], q.push(b[dq].son[i]);
            else b[dq].son[i] = b[b[dq].fail].son[i];
    }
}
bool pd(int dq) {
    for (int i = dq; i; i = b[i].fail)
        if (b[i].isend)
            return false;
    return true;
}
void dfs(int dq) {
    if (inq[dq]) { // 必须要是从这个点走 又回到自己才能叫环(排除横叉边)
        puts("TAK");
        exit(0);
    }
    inq[dq] = true;
    for (int i = 0; i < MAXC; i++) 
        if (!vis[b[dq].son[i]] && pd(b[dq].son[i])) // 这个地方要求只要判断有没有环 所以不用再顺着横叉边去找一遍(如果有早就退出了)
            dfs(b[dq].son[i]);
    inq[dq] = false;
    vis[dq] = true;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        int dqn = strlen(s), dq = 0;
        for (int i = 0; i < dqn; i++) {
            if (!b[dq].son[s[i] - '0']) b[dq].son[s[i] - '0'] = ++cntb;
            dq = b[dq].son[s[i] - '0'];
        }
        ++b[dq].isend;
    }
    init();
    dfs(0);
    puts("NIE");
    return 0;
}

[Noi2011]阿狸的打字机

是我太菜了还是这题太神了...

首先明确一下 一个串的子串就是这个串在trie的那条路径上的每个节点上 跳fail到根, 途中遇到的每个结尾就是这个串的子串

考虑建一个fail树, 然后考虑从\(x\)出发 如何得出答案: 在这个节点的子树里 有多少个点是\(y​\)的节点

我们就可以遍历trie树, 把当前的点在fail树的dfs序上的位置+1, 然后每到达一个终点, 就枚举所有以这个串为\(y\)的询问, 这时\(x\)的子树和就是这个询问的答案

最后...我又把编号搞乱了...

又及: 我在想这题的时候...yy了一个东西 然后似乎发现 这东西叫dsu on tree... = = 为什么当时学长讲课的时候我连这玩意要干啥都没听懂...此题最大收获在于让我学会了dsu on tree

/**************************************************************
    Problem: 2434
    User: Cansult
    Language: C++
    Result: Accepted
    Time:764 ms
    Memory:27244 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (100000 + 5)
#define MAXC (26)
#define lowbit(i) ((i) & (-(i)))
#define pii pair<int, int>
using namespace std;
struct node {
    int son[MAXC], fail, fa;
    bool isnt[MAXC];
    vector<int> bh;
} b[MAXN];
struct edg {
    int from, to, next;
} tb[MAXN << 1];
int cntb, g[MAXN], cntt, n, cntbh, a[MAXN], cnta, ans[MAXN], q, fuck[MAXN];
pii be[MAXN];
vector<pii> que[MAXN];
char s[MAXN];
void xg(int wz, int zh) {
    for (int i = wz; i <= cntb + 1; i += lowbit(i)) a[i] += zh;
}
int cx(int le, int ri) {
    int re = 0;
    for (int i = ri; i; i -= lowbit(i)) re += a[i];
    for (int i = le - 1; i; i -= lowbit(i)) re -= a[i];
    return re;
}
void adn(int from, int to) {
    tb[++cntt].next = g[from];
    tb[cntt].from = from, tb[cntt].to = to;
    g[from] = cntt;
}
void init() {
    queue<int> q;
    for (int i = 0; i < MAXC; i++)
        if (b[0].son[i]) q.push(b[0].son[i]);
        else b[0].isnt[i] = true;
    while (!q.empty()) {
        int dq = q.front();
        q.pop();
        for (int i = 0; i < MAXC; i++) 
            if (b[dq].son[i]) b[b[dq].son[i]].fail = b[b[dq].fail].son[i], q.push(b[dq].son[i]);
            else b[dq].isnt[i] = true, b[dq].son[i] = b[b[dq].fail].son[i];
    }
    for (int i = 1; i <= cntb; i++)
        adn(b[i].fail, i);
}
void dfsonfail(int dq) {
    be[dq].first = ++cnta;
    for (int i = g[dq]; i; i = tb[i].next)
        dfsonfail(tb[i].to);
    be[dq].second = cnta;
}
void dfsontrie(int dq) {
    xg(be[dq].first, 1);
    for (int i = 0; i < b[dq].bh.size(); i++)
        for (int j = 0; j < que[b[dq].bh[i]].size(); j++)
            ans[que[b[dq].bh[i]][j].second] += cx(be[que[b[dq].bh[i]][j].first].first, be[que[b[dq].bh[i]][j].first].second);
    for (int i = 0; i < MAXC; i++)
        if (!b[dq].isnt[i])
            dfsontrie(b[dq].son[i]);
    xg(be[dq].first, -1);
}
int main() {
    scanf("%s", s);
    n = strlen(s);
    for (int i = 0, dq = 0; i < n; i++) {
        if (s[i] == 'B') dq = b[dq].fa;
        else if (s[i] == 'P') b[dq].bh.push_back(++cntbh), fuck[cntbh] = dq;
        else {
            if (!b[dq].son[s[i] - 'a']) b[b[dq].son[s[i] - 'a'] = ++cntb].fa = dq;
            dq = b[dq].son[s[i] - 'a'];
        }
    }
    scanf("%d", &q);
    for (int i = 1, srx, sry; i <= q; i++) 
        scanf("%d%d", &srx, &sry), que[sry].push_back(make_pair(fuck[srx], i));
    init();
    dfsonfail(0);
    dfsontrie(0);
    for (int i = 1; i <= q; i++) 
        printf("%d\n", ans[i]);
    return 0;
}

By 准备退役旅游的 Cansult