P1069:细胞分裂题解

思路转化

题目大意是这样的：给出数字\(N\)，\(m_1\)，\(m_2\)，\(S_{i[1\dots N]}\)，求最小的\(t\)，使得某一\(S_i^t \; mod\; m_1^{m_2}\)。

所以之后就非常的显然了，我们只要分析出每一个数的质因数与\(m_1\)的质因数的关系即可。如果有一个数\(c\)的质因数集为\(A\)，那么我们可以遍历\(m_1\)的质因数集，记录答案。如果质因数集不包含\(m_1\)的质因数集直接退出。

代码

// P1069.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int MX_N = 30020, INF = 0x3f3f3f3f;
ll n, m1, m2, arr[MX_N], pipePrime[MX_N], cellPrime[MX_N], lit, ans = INF;
int main()
{
    scanf("%lld%lld%lld", &n, &m1, &m2);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]);
    if (m1 == 1)
    {
        printf("0");
        return 0;
    }
    for (int i = 2; m1 != 1; i++)
    {
        while (!(m1 % i))
            m1 /= i, pipePrime[i] += m2;
        lit = max(lit, (ll)i);
    }
    for (int i = 1; i <= n; i++)
    {
        ll now = 0;
        for (int j = 2; j <= lit; j++)
            if (pipePrime[j] != 0)
            {
                ll tim = 0;
                while (!(arr[i] % j))
                    arr[i] /= j, tim++;
                if (!tim)
                {
                    now = INF;
                    break;
                }
                now = max(now, (pipePrime[j] - 1) / tim);
            }
        ans = min(ans, now);
    }
    if (ans != INF)
        printf("%lld", ans + 1);
    else
        printf("-1");
    return 0;
}

P2501:「HAOI2006」数字序列题解

主要思路

这道题算是非常的毒瘤了。

首先我们来看第一问，根据 XG 巨佬的话，是非常明显的。我们在序列读入时减去元素自己的序号，找 LIS 长度即可。代码：

scanf("%lld", &n);
for (ll i = 1; i <= n; i++)
    scanf("%lld", &arr[i]), arr[i] -= i, dst[i] = INF;
dst[0] = -INF, dp[1] = 1, len = 1, dst[1] = arr[1], arr[0] = -INF, arr[++n] = INF;
for (ll i = 2; i <= n; i++)
{
    ll addr = upper_bound(dst, dst + 1 + len, arr[i]) - dst;
    len = max(len, addr);
    dp[i] = addr;
    dst[addr] = min(dst[addr], arr[i]);
}
printf("%lld\n", n - dp[n]);

第二问我们引出一个小的结论：如果要把区间\([l\dots r]\)之间变得“好看”，那么这个子区间内一定分为两段：高度为\(arr[l]\)的一段和高度\(arr[r]\)的一段。注意，此时\(arr[]\)内的元素已经剪去了元素编号。

所以这第二问就是一道区间 DP，时间复杂度为\(O(n^3)\)。不过好在序列随机，且我们可以使用邻接表预先存好那些可以处理的区间，然后进行 DP。

代码

// P2501.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll MX_N = 35020, INF = 0x3f3f3f3f;
ll head[MX_N], arr[MX_N], n, len, dst[MX_N], dp[MX_N], M_curt, f[MX_N], sum1[MX_N], sum2[MX_N];
struct edge
{
    ll to, nxt;
} edges[MX_N << 1];
void addpath(ll src, ll dst)
{
    edges[M_curt].to = dst, edges[M_curt].nxt = head[src];
    head[src] = M_curt++;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld", &arr[i]), arr[i] -= i, dst[i] = INF;
    dst[0] = -INF, dp[1] = 1, len = 1, dst[1] = arr[1], arr[0] = -INF, arr[++n] = INF;
    for (ll i = 2; i <= n; i++)
    {
        ll addr = upper_bound(dst, dst + 1 + len, arr[i]) - dst;
        len = max(len, addr);
        dp[i] = addr;
        dst[addr] = min(dst[addr], arr[i]);
    }
    printf("%lld\n", n - dp[n]);
    for (ll i = n; i >= 0; i--)
        addpath(dp[i], i), f[i] = INF;
    f[0] = 0;
    for (ll i = 1; i <= n; i++)
        for (ll e = head[dp[i] - 1]; e != -1; e = edges[e].nxt)
        {
            ll v = edges[e].to;
            if (v > i)
                break;
            if (arr[v] > arr[i])
                continue;
            for (ll k = v; k <= i; k++)
                sum1[k] = abs(arr[k] - arr[v]), sum2[k] = abs(arr[k] - arr[i]);
            for (ll k = v + 1; k <= i; k++)
                sum1[k] += sum1[k - 1], sum2[k] += sum2[k - 1];
            for (ll k = v; k <= i - 1; k++)
                f[i] = min(f[i], f[v] + sum1[k] - sum1[v] + sum2[i] - sum2[k]);
        }
    printf("%lld", f[n]);
    return 0;
}

P3899:「湖南集训」谈笑风生题解

“This is a big mistake!”

主席树的迁移

如何把对主席树“能解决区间第 k 大问题”这个印象迁移到这道非常暴力的题目上呢？我们可以把整棵树用 DFS 序来入手（连续性在本题会比离散型更好）。我们可以先用一个 DFS 来记录 DFS 序、Low 数组、子树大小。

然后，我们以深度为权值，子树大小为要维护的信息。以 DFS 序的顺序来计算前缀子树和、创建主席树。具体见代码：

代码

// P3899.cpp
#include <iostream>
#include <cstdio>
#include <vector>
#define ll long long
#define mid ((l + r) >> 1)
using namespace std;
const ll MX_N = 3e5 + 1000;
ll ncnt, dfn[MX_N], low[MX_N], antiDFN[MX_N], ndfn, dep[MX_N], fa[MX_N], n, q, tmpx, tmpy;
ll subtree[MX_N], roots[MX_N];
vector<ll> G[MX_N];
struct node
{
    ll sum, ls, rs;
} nodes[MX_N * (2 << 5)];
ll build(ll l, ll r)
{
    ll p = ++ncnt;
    if (l == r)
        return p;
    nodes[p].ls = build(l, mid), nodes[p].rs = build(mid + 1, r);
    nodes[p].sum = 0;
    return p;
}
ll update(ll l, ll r, ll previous, ll depth, ll ad)
{
    ll curt = ++ncnt;
    nodes[curt].ls = nodes[previous].ls, nodes[curt].rs = nodes[previous].rs;
    nodes[curt].sum = nodes[previous].sum + ad;
    if (l == r && l == depth)
        return curt;
    if (depth <= mid)
        nodes[curt].ls = update(l, mid, nodes[previous].ls, depth, ad);
    else
        nodes[curt].rs = update(mid + 1, r, nodes[previous].rs, depth, ad);
    return curt;
}
ll query(ll ql, ll qr, ll l, ll r, ll p)
{
    if (ql <= l && r <= qr)
        return nodes[p].sum;
    if (mid >= qr)
        return query(ql, qr, l, mid, nodes[p].ls);
    if (mid < ql)
        return query(ql, qr, mid + 1, r, nodes[p].rs);
    return query(ql, qr, l, mid, nodes[p].ls) + query(ql, qr, mid + 1, r, nodes[p].rs);
}
void dfs(ll u)
{
    dfn[u] = ++ndfn, subtree[u]++;
    antiDFN[ndfn] = u, dep[u] = dep[fa[u]] + 1;
    ll siz = G[u].size();
    for (ll i = 0; i < siz; i++)
        if (G[u][i] != fa[u])
            fa[G[u][i]] = u, dfs(G[u][i]), subtree[u] += subtree[G[u][i]];
    low[u] = ndfn;
}
int main()
{
    scanf("%lld%lld", &n, &q);
    for (int i = 0; i < n - 1; i++)
        scanf("%lld%lld", &tmpx, &tmpy), G[tmpx].push_back(tmpy), G[tmpy].push_back(tmpx);
    dfs(1), roots[0] = build(1, n);
    for (int i = 1; i <= n; i++)
        roots[i] = update(1, n, roots[i - 1], dep[antiDFN[i]], subtree[antiDFN[i]] - 1);
    while (q--)
    {
        scanf("%lld%lld", &tmpx, &tmpy);
        ll ret = min(dep[tmpx] - 1, tmpy) * (subtree[tmpx] - 1);
        ll another = query(dep[tmpx], dep[tmpx] + tmpy, 1, n, roots[low[tmpx]]) -
                     query(dep[tmpx], dep[tmpx] + tmpy, 1, n, roots[dfn[tmpx]]);
        printf("%lld\n", ret + another);
    }
    return 0;
}

POJ2104:K-th Number 题解

主要思路

其实这道题没什么思路…就是一道主席树的模板题，用前缀和 \(sum[]\) 来维护不同版本之间数字出现的个数即可。

代码

// POJ2104.cpp
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define mid ((l + r) >> 1)
using namespace std;
const int MX_N = 1e5 + 20;
struct node
{
    int ls, rs, info, weight;
} nodes[(2 << 5) * MX_N];
int n, m, ncnt, seq[MX_N], misc[MX_N], len, roots[MX_N], sum[(2 << 5) * MX_N];
int getId(int val) { return lower_bound(misc + 1, misc + 1 + len, val) - misc; }
int build(int l, int r)
{
    int p = ++ncnt;
    if (l == r)
        return p;
    nodes[p].ls = build(l, mid);
    nodes[p].rs = build(mid + 1, r);
    return p;
}
int update(int l, int r, int previous, int c)
{
    int p = ++ncnt;
    nodes[p].ls = nodes[previous].ls;
    nodes[p].rs = nodes[previous].rs;
    sum[p] = sum[previous] + 1;
    if (l == r)
        return p;
    if (c <= mid)
        nodes[p].ls = update(l, mid, nodes[p].ls, c);
    else
        nodes[p].rs = update(mid + 1, r, nodes[p].rs, c);
    return p;
}
int query(int l, int r, int previous, int now, int k)
{
    int lsWeight = sum[nodes[now].ls] - sum[nodes[previous].ls];
    if (l == r)
        return l;
    if (k <= lsWeight)
        return query(l, mid, nodes[previous].ls, nodes[now].ls, k);
    else
        return query(mid + 1, r, nodes[previous].rs, nodes[now].rs, k - lsWeight);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &seq[i]);
    memcpy(misc, seq, sizeof(misc));
    sort(misc + 1, misc + 1 + n);
    len = unique(misc + 1, misc + 1 + n) - misc - 1;
    roots[0] = build(1, len);
    for (int i = 1; i <= n; i++)
        roots[i] = update(1, len, roots[i - 1], getId(seq[i]));
    while (m--)
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", misc[query(1, len, roots[l - 1], roots[r], k)]);
    }
    return 0;
}

P2414:「NOI2011」阿狸的打字机题解

令人窒息的字符串读入

这道题我要非常强调的是字符串的读入问题（我被卡了一下午和一晚上）。我们需要边读入边进行 trie 树的 insert 操作，不要存下字符子串！要不然你就会像我一样 MLE。具体代码：

// in function main();
int now = root;
for (int i = 1, l = strlen(buff + 1); i <= l; ++i)
{
    if (buff[i] >= 'a' && buff[i] <= 'z')
    {
        if (!nodes[now].nxt[buff[i] - 'a'])
            nodes[now].nxt[buff[i] - 'a'] = ++tot, nodes[tot].fa = now;
        now = nodes[now].nxt[buff[i] - 'a'];
    }
    if (buff[i] == 'B')
        now = nodes[now].fa;
    if (buff[i] == 'P')
    {
        nds[++n] = now;
        nodes[now].id = n;
    }
}

正式思路

刚刚讲完了我的悲惨教训之后，我来正式阐述以下本题思路。我们要把这些字符串全部加入 Trie 树并且生成 Fail 失配指针。这些都是基本操作对吧。

void insert(string str, int id)
{
    int p = root;
    for (int i = 0; i < str.length(); i++)
    {
        int curt = str[i] - 'a', fa = p;
        if (nodes[p].nxt[curt] == 0)
            nodes[p].nxt[curt] = ++tot;
        p = nodes[p].nxt[curt];
        nodes[p].fa = fa;
    }
    nodes[p].id = id, nds[id] = p;
}
void bfs()
{
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (nodes[root].nxt[i] != 0)
            q.push(nodes[root].nxt[i]);
    while (!q.empty())
    {
        int curt = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
            if (nodes[curt].nxt[i] != 0)
                nodes[nodes[curt].nxt[i]].fail = nodes[nodes[curt].fail].nxt[i],
                q.push(nodes[curt].nxt[i]);
            else
                nodes[curt].nxt[i] = nodes[nodes[curt].fail].nxt[i];
    }
}

之后我们会发现，对于每一次询问 \((x,y)\)，我们所要求的就是在 Trie 树上，从字符串 \(y\) 的末尾节点开始沿着 fail 指针向上跳，每经历一个尾节点 \(x\) 时，答案计数加一。

当然，我做了一些小优化，离线处理每个询问，按关键字 \(y\) 进行从小到大的排序，然后对于每一个点\(x\)我们都用树状数组来记录能沿着 fail 指针树行进的（对了我们一定要用 fail 指针建一棵树来搞定这个）、能到达的以\(y\)结尾的点的个数，及维护前缀答案来搞定。

在获取答案之前，我们要写一个 DFS，来记录每个结点 low 和 dfn 的值。然后，统计答案时，因为答案分布在一整条链上，且链上的点的时间戳是由单调性的，所以可以用树状数组统计。

具体代码：

// P2414.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define lowbit(num) (num & -num)
using namespace std;
const int MX_N = 200200;
int head[MX_N], current = 0;
struct egde
{
    int to, nxt;
} edges[MX_N];
char buff[MX_N];
int T, anses[MX_N], root, nds[MX_N], tree[MX_N], tim, n, ql[MX_N], qr[MX_N], tot;
struct node
{
    int nxt[26], fail, fa, pre[26], id, dfn, low;
} nodes[MX_N];
struct queryInfo
{
    int x, y, ans, id;
    bool operator<(const queryInfo &q) const { return y < q.y; }
} qi[MX_N];
inline int read()
{
    int x = 0, t = 1;
    char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-')
        ch = getchar();
    if (ch == '-')
        t = -1, ch = getchar();
    while (ch <= '9' && ch >= '0')
        x = x * 10 + ch - 48, ch = getchar();
    return x * t;
}
void addpath(int src, int dst) { edges[current].to = dst, edges[current].nxt = head[src], head[src] = current++; }
void update(int x, int c)
{
    while (x <= tim)
        tree[x] += c, x += lowbit(x);
}
int getsum(int x)
{
    int ret = 0;
    while (x > 0)
        ret += tree[x], x -= lowbit(x);
    return ret;
}
void insert(string str, int id)
{
    int p = root;
    for (int i = 0; i < str.length(); i++)
    {
        int curt = str[i] - 'a', fa = p;
        if (nodes[p].nxt[curt] == 0)
            nodes[p].nxt[curt] = ++tot;
        p = nodes[p].nxt[curt];
        nodes[p].fa = fa;
    }
    nodes[p].id = id, nds[id] = p;
}
void bfs()
{
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (nodes[root].nxt[i] != 0)
            q.push(nodes[root].nxt[i]);
    while (!q.empty())
    {
        int curt = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
            if (nodes[curt].nxt[i] != 0)
                nodes[nodes[curt].nxt[i]].fail = nodes[nodes[curt].fail].nxt[i],
                q.push(nodes[curt].nxt[i]);
            else
                nodes[curt].nxt[i] = nodes[nodes[curt].fail].nxt[i];
    }
}
void dfs(int u)
{
    nodes[u].dfn = ++tim;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        dfs(edges[i].to);
    nodes[u].low = tim;
}
void dfsans(int u)
{
    update(nodes[u].dfn, 1);
    if (nodes[u].id != 0)
        for (int i = ql[nodes[u].id]; i <= qr[nodes[u].id]; i++)
            qi[i].ans = getsum(nodes[nds[qi[i].x]].low) - getsum(nodes[nds[qi[i].x]].dfn - 1);
    for (int i = 0; i < 26; i++)
        if (nodes[u].pre[i] != 0)
            dfsans(nodes[u].nxt[i]);
    update(nodes[u].dfn, -1);
}
int main()
{
    memset(head, -1, sizeof(head));
    root = 0;
    scanf("%s", buff + 1);
    int now = root;
    for (int i = 1, l = strlen(buff + 1); i <= l; ++i)
    {
        if (buff[i] >= 'a' && buff[i] <= 'z')
        {
            if (!nodes[now].nxt[buff[i] - 'a'])
                nodes[now].nxt[buff[i] - 'a'] = ++tot, nodes[tot].fa = now;
            now = nodes[now].nxt[buff[i] - 'a'];
        }
        if (buff[i] == 'B')
            now = nodes[now].fa;
        if (buff[i] == 'P')
        {
            nds[++n] = now;
            nodes[now].id = n;
        }
    }
    for (int i = 0; i <= tot; i++)
        for (int j = 0; j < 26; j++)
            nodes[i].pre[j] = nodes[i].nxt[j];
    bfs();
    for (int i = 1; i <= tot; i++)
        addpath(nodes[i].fail, i);
    dfs(root);
    T = read();
    for (int i = 1; i <= T; i++)
        qi[i].x = read(), qi[i].y = read(), qi[i].id = i;
    sort(qi + 1, qi + 1 + T);
    for (int i = 1, pos = 1; i <= T; i = pos)
    {
        ql[qi[i].y] = i;
        while (qi[i].y == qi[pos].y)
            pos++;
        qr[qi[i].y] = pos - 1;
    }
    dfsans(root);
    for (int i = 1; i <= T; i++)
        anses[qi[i].id] = qi[i].ans;
    for (int i = 1; i <= T; i++)
        printf("%d\n", anses[i]);
    return 0;
}

P2444:「POI2000」病毒题解

主要思路

这道题铁定是要用 AC 自动机来进行实现的。我们把这些字符串全部通过 insert 操作放入了自动机之后，怎样改写 build_AC_automation 操作来搞定这道题呢？

首先，我们发现 fail 指针可以把整个 trie 树变成一张图（每一个点都加了一条虚边）。所以我们会发现，只要我们找到这张图的一个环，且这个环上所有的点都不是某个不安全代码的结尾点，就可以认定有无限长的代码安全。原因解析起来非常的简单，因为如果有一个这样安全的环，那么无限长的代码势必在这个环内无限循环，且因为这是安全的，所以也可以保证这一长串的代码是安全的。

详见代码。

代码

// P2444.cpp
#include <iostream>
#include <queue>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
const int MX_N = 30020;
struct node
{
    node *nxt[2], *fail;
    bool sum, ins, vis;
    node() { nxt[0] = nxt[1] = fail = NULL, sum = 0, ins = vis = false; }
};
node *root;
int n, longest;
void insert(string str)
{
    int siz = str.length();
    node *p = root;
    for (int i = 0; i < siz; i++)
        p = (p->nxt[str[i] - '0'] == NULL) ? (p->nxt[str[i] - '0'] = new node()) : p->nxt[str[i] - '0'];
    p->sum = true;
}
void build_ac_automation()
{
    queue<node *> q;
    q.push(root);
    while (!q.empty())
    {
        node *curt = q.front();
        q.pop();
        for (int i = 0; i < 2; i++)
            if (curt->nxt[i] != NULL)
            {
                if (curt == root)
                    curt->nxt[i]->fail = root;
                else
                {
                    node *p = curt->fail;
                    while (p)
                        if (p->nxt[i] != NULL)
                        {
                            curt->nxt[i]->fail = p->nxt[i];
                            curt->nxt[i]->sum |= p->nxt[i]->sum;
                            break;
                        }
                        else
                            p = p->fail;
                    if (p == NULL)
                        curt->nxt[i]->fail = root;
                }
                q.push(curt->nxt[i]);
            }
            else if (curt->fail != NULL)
                curt->nxt[i] = curt->fail->nxt[i];
    }
}
bool dfs(node *curt)
{
    if (curt->ins)
        return true;
    if (curt->vis || curt->sum > 0)
        return false;
    curt->vis = curt->ins = true;
    for (int i = 0; i < 2; i++)
        if (curt->nxt[i] != NULL && dfs(curt->nxt[i]))
            return true;
    curt->ins = false;
    return false;
}
char buff[30020];
int main()
{
    scanf("%d", &n);
    root = new node();
    for (int i = 1; i <= n; i++)
        scanf("%s", buff), insert(buff);
    build_ac_automation();
    if (dfs(root))
        printf("TAK");
    else
        printf("NIE");
    return 0;
}