HydroOJ 每日将从主题库及精选域中选出一题配以题解在此分享给大家。

如果你也想为 Hydro 提供每日一题,可以联系 Macesuted

每日一题将以评论的方式在此贴下发布,无关用户请勿直接回复本帖,允许用户发布二级评论(即允许评论每日一题)。

6 条评论

  • @ 2021-10-10 15:42:55

    #006 2021.10.10

    [IOI2018] werewolf 狼人

    题目大意

    给出一个 nn 个点 mm 条边的无向联通图,有 qq 组询问,每组询问给出 x, y, l, rx,~y,~l,~r,询问是否存在一个点 pp 满足:

    1. 存在一条从 xxpp 的路径满足路径上所有节点(包含两个端点)编号均不小于 ll
    2. 存在一条从 ppyy 的路径满足路径上所有节点(包含两个端点)编号均不大于 rr

    n, q2×105, m4×105n,~q \le 2 \times 10^5,~m \le 4 \times 10^5

    题解

    分析

    由于对 xpx \to ppyp \to y 的路径的限制均为“均不小于 xx”或“均不大于 xx”的形式,我们考虑使用 Kruskal 重构树解决这一问题。因为当我们将每条边的边权设为其两端端点的较大值时重构树上两点的 LCA 的权值即为这两点在原图上点权最大值最小的路径所对应的路径点权最大值。维护最大的路径最小值的方法同理。

    由于我们无法同时满足这两个限制,因此我们考虑建两棵 Kruskal 重构树,第一棵维护路径上最大的最小值,第二棵维护路径上最小的最大值。对于一组询问,考虑合法的 pp 可能在什么位置:

    1. pp 在第一棵树上位于 xx 的深度最小的满足 l\ge l 的祖先 fxfx 的子树中。
    2. pp 在第二棵树上位于 yy 的深度最小的满足 r\le r 的祖先 fyfy 的子树中。

    考虑在两棵树上分别求出所有节点的 dfs 序 dfn[0/1][i],对于节点 ii 将其视为坐标系上一个位于 (dfn[0][i], dfn[1][i])(dfn[0][i],~dfn[1][i]) 的点。则每个询问等同于询问坐标系上一个矩形内是否存在点。将所有询问离线后二维数点即可。

    代码

    /**
     * @author Macesuted (i@macesuted.moe)
     * @copyright Copyright (c) 2021
     */
    
    #include <bits/stdc++.h>
    using namespace std;
    
    template <typename T>
    inline T read() {
        T x = 0, f = 1;
        char c = getchar();
        for (; c < '0' || c > '9'; c = getchar())
            if (c == '-') f = -1;
        for (; c <= '9' && c >= '0'; c = getchar())
            x = x * 10 + (c & 15);
        return x * f;
    }
    
    #define maxn 200005
    #define maxlgn 20
    
    typedef pair<int, int> pii;
    
    class KruskalTree {
       private:
        int f[maxn];
        bool vis[maxn];
    
        int getfa(int p) { return f[p] == p ? p : f[p] = getfa(f[p]); }
    
       public:
        vector<vector<int>> tree;
        int fa[maxn][maxlgn], dfni[maxn], dfno[maxn], tim = 0;
        void dfs(int p, int pre) {
            dfni[p] = ++tim;
            fa[p][0] = pre;
            for (int i = 1; i < maxlgn; i++) fa[p][i] = fa[fa[p][i - 1]][i - 1];
            for (auto i : tree[p]) dfs(i, p);
            dfno[p] = tim;
            return;
        }
        void build(int n, const vector<vector<int>>& graph, int p[]) {
            for (int i = 1; i <= n; i++) vis[i] = false, f[i] = i;
            tree.resize(n + 1);
            for (int i = 1; i <= n; i++) {
                vis[p[i]] = true;
                for (auto j : graph[p[i]])
                    if (vis[j] && getfa(p[i]) != getfa(j))
                        tree[p[i]].push_back(getfa(j)), f[getfa(j)] = p[i];
            }
            return dfs(p[n], p[n]);
        }
    } T[2];
    class BIT {
       private:
        int tree[maxn];
    
       public:
        void add(int p, int v) {
            for (int i = p; i < maxn; i += i & -i) tree[i] += v;
            return;
        }
        int sum(int p) {
            int sum = 0;
            for (int i = p; i; i -= i & -i) sum += tree[i];
            return sum;
        }
    } bit;
    
    struct Ask {
        int l, r, id, op;
    };
    
    int p[maxn];
    
    vector<vector<int>> graph;
    vector<Ask> asks[maxn];
    int points[maxn];
    int answer[maxn];
    
    int main() {
        ios::sync_with_stdio(false);
        cout << setiosflags(ios::fixed) << setprecision(8);
        int n = read<int>(), m = read<int>(), q = read<int>();
        graph.resize(n + 1);
        for (int i = 1; i <= m; i++) {
            int x = read<int>() + 1, y = read<int>() + 1;
            graph[x].push_back(y), graph[y].push_back(x);
        }
        for (int i = 1; i <= n; i++) p[i] = n - i + 1;
        T[0].build(n, graph, p), reverse(p + 1, p + n + 1), T[1].build(n, graph, p);
        for (int i = 1; i <= n; i++) points[T[0].dfni[i]] = T[1].dfni[i];
        for (int i = 1; i <= q; i++) {
            int S = read<int>() + 1, E = read<int>() + 1, l = read<int>() + 1, r = read<int>() + 1;
            for (int i = maxlgn - 1; ~i; i--)
                if (T[0].fa[S][i] >= l) S = T[0].fa[S][i];
            for (int i = maxlgn - 1; ~i; i--)
                if (T[1].fa[E][i] <= r) E = T[1].fa[E][i];
            if (T[0].dfni[S] - 1) asks[T[0].dfni[S] - 1].push_back({T[1].dfni[E], T[1].dfno[E], i, -1});
            asks[T[0].dfno[S]].push_back({T[1].dfni[E], T[1].dfno[E], i, +1});
        }
        for (int i = 1; i <= n; i++) {
            bit.add(points[i], +1);
            for (auto j : asks[i]) answer[j.id] += j.op * (bit.sum(j.r) - bit.sum(j.l - 1));
        }
        for (int i = 1; i <= q; i++) cout << (answer[i] >= 1) << endl;
        return 0;
    }
    
  • @ 2021-09-25 13:25:18

    #005 2021.9.25

    Greg and Caves

    题意

    问满足下列条件的 n×mn \times m 的 01 矩阵 aa 的数量:

    1. [l, r](1lrn)\exists [l,~r] (1 \le l \le r \le n),满足 i[l, r], jai,j=2\forall i \in [l,~r],~\sum_j a_{i,j} =2i[l, r], jai,j=0\forall i \notin [l,~r],~\sum_j a_{i,j}=0
    2. [l, r][l,~r] 中的每一行的第一个值为 11 的位置的下标为 xix_i,第二个值为 11 的位置的下标为 yiy_i,则:t[l, r]\exists t \in [l,~r],满足 i[l, t1], xixi+1, yiyi+1\forall i \in [l,~t-1],~x_i \ge x_{i+1},~y_i \le y_{i+1}i[t, r1], xixi+1, yiyi+1\forall i \in [t,~r-1],~x_i \le x_{i+1},~y_i \ge y_{i+1}
    题解

    分析

    考虑使用 DP 解决本题。

    f[i][j]f[i][j] 表示考虑洞的前 ii 行(该 ii 行都在洞的中间位置 tt 的上方)且第 ii 行的 yixi+1=jy_i-x_i+1=j 时该洞的构造方案(不考虑洞在矩阵中的摆放位置)。

    考虑枚举第 i1i-1 行的长度以及与第 ii 行的相对位置,得出转移方程:

    f[i][j]=t=0jf[i1][t]×(jt+1)f[i][j]=\sum_{t=0}^{j}f[i-1][t] \times (j-t+1)

    尝试使用该数据描述最终答案 AnsAns,考虑枚举中间位置 tt 的行编号以及该行 yixi+1y_i-x_i+1 的大小。同时由于可能存在构造洞的方案满足第 tt 行与相邻的几行的形态完全相同,为了防止算重,考虑令 tt 为洞的最大的满足 yixi+1y_i-x_i+1 最大的行数,同时枚举 t+1t+1 行的长度(小于 tt 行长度),算出最终答案:

    Ans=i=1na=0m2(ma1)×(l=1if[il+1][a])×(1+b=0a1(r=i+1nf[ri][b])×(ab+1))=i=1na=0m2(ma1)×(t=1if[t][a])×(1+b=0a1(t=1nif[t][b])×(ab+1))\begin{aligned} Ans&=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times \big( \sum_{l=1}^{i} f[i-l+1][a] \big) \times (1 + \sum_{b=0}^{a-1} \big( \sum_{r=i+1}^{n} f[r-i][b] \big) \times (a - b + 1))\\\\ &=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times \big( \sum_{t=1}^{i} f[t][a] \big) \times (1 + \sum_{b=0}^{a-1} \big( \sum_{t=1}^{n-i} f[t][b] \big) \times (a - b + 1)) \end{aligned}

    g[i][j]=k=1if[k][j]g[i][j] = \sum_{k=1}^{i} f[k][j]

    Ans=i=1na=0m2(ma1)×g[i][a]×(1+b=0a1g[ni][b]×(ab+1))Ans=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times g[i][a] \times (1 + \sum_{b=0}^{a-1} g[n-i][b] \times (a-b+1))

    h[i][j]=k=0j1g[i][k]×(jk+1)h[i][j]=\sum_{k=0}^{j-1} g[i][k] \times (j-k+1)

    Ans=i=1na=0m2(ma1)×g[i][a]×(1+h[ni][a])Ans=\sum_{i=1}^{n} \sum_{a=0}^{m-2} (m-a-1) \times g[i][a] \times (1 + h[n-i][a])

    处理 f[i][j]f[i][j] 前缀和优化到 O(nm)O(nm),处理 g[i][j]g[i][j] O(nm)O(nm),处理 h[i][j]h[i][j] 前缀和优化到 O(nm)O(nm),计算答案 AnsAns O(nm)O(nm)

    总时间复杂度 O(nm)O(nm)

    代码

    /**
     * @author Macesuted (macesuted@outlook.com)
     * @copyright Copyright (c) 2021
     * @brief
     *      My Draft: https://img-kysic-1258722770.file.myqcloud.com/b78115e628143efb1c9163c7bd5d44c7/75b95a13254dd.png
     *      My solution: https://www.macesuted.cn/article/cf295d/
     */
    
    #include <bits/stdc++.h>
    using namespace std;
    
    namespace io {
    #define SIZE (1 << 20)
    char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
    int f, qr;
    inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
    inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
    inline void putch(char x) {
        *oS++ = x;
        if (oS == oT) flush();
        return;
    }
    string getstr(void) {
        string s = "";
        char c = getch();
        while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
        while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) s.push_back(c), c = getch();
        return s;
    }
    void putstr(string str, int begin = 0, int end = -1) {
        if (end == -1) end = str.size();
        for (register int i = begin; i < end; i++) putch(str[i]);
        return;
    }
    template <typename T>
    inline T read() {
        register T x = 0;
        for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
            if (c == '-') f = -1;
        for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
        return x * f;
    }
    template <typename T>
    inline void write(const T& t) {
        register T x = t;
        if (!x) putch('0');
        if (x < 0) putch('-'), x = -x;
        while (x) qu[++qr] = x % 10 + '0', x /= 10;
        while (qr) putch(qu[qr--]);
        return;
    }
    struct Flusher_ {
        ~Flusher_() { flush(); }
    } io_flusher_;
    }  // namespace io
    using io::getch;
    using io::getstr;
    using io::putch;
    using io::putstr;
    using io::read;
    using io::write;
    
    #define maxn 2005
    #define mod 1000000007
    
    long long f[maxn][maxn], g[maxn][maxn], h[maxn][maxn], cac[maxn][maxn];
    
    int main() {
        int n = read<int>(), m = read<int>();
        for (register int i = 0; i <= m - 2; i++) f[1][i] = 1;
        for (register int i = 2; i <= n; i++) {
            f[i][0] = cac[i][0] = f[i - 1][0];
            for (register int j = 1; j <= m - 2; j++)
                cac[i][j] = (cac[i][j - 1] + f[i - 1][j]) % mod, f[i][j] = (f[i][j - 1] + cac[i][j]) % mod;
        }
        for (register int i = 1; i <= n; i++)
            for (register int j = 0; j <= m - 2; j++)
                g[i][j] = (g[i - 1][j] + f[i][j]) % mod;
        memset(cac, 0, sizeof(cac));
        for (register int i = 1; i < n; i++)
            for (register int j = 1; j <= m - 2; j++)
                cac[i][j] = (cac[i][j - 1] + g[i][j - 1]) % mod, h[i][j] = (h[i][j - 1] + cac[i][j] + g[i][j - 1]) % mod;
        long long answer = 0;
        for (register int i = 1; i <= n; i++)
            for (register int j = 0; j <= m - 2; j++)
                answer = (answer + (m - j - 1) * g[i][j] % mod * (1 + h[n - i][j])) % mod;
        write(answer), putch('\n');
        return 0;
    }
    
    • @ 2021-09-25 16:25:27

      你们开始卷快速I/O了/kk

  • @ 2021-09-18 16:10:54

    #004 2021.9.18

    bzoj3836 Tourism

    题意简述

    给定 nn 个点,mm 条边的无向图,第 ii 个点建旅游站的费用为 cic_i。保证任意两点间不存在长度超过 1010 的路径。

    问最小的费用,使得每个点建立了旅游站,或与其直接相连的点里有至少一个建立了旅游站。

    题解

    Analysis

    显然是个 NP 问题,然而题目保证「任意两点间不存在节点数超过 1010 的简单路径」,就有了一定可操作性。

    先考虑图为树的简化版。就是一个最小覆盖集的问题。经典的树形 dp,用 dpi,s={0/1/2}dp_{i,s=\{0/1/2\}} 表示满足 ii 的子树(不包含 ii)被完全覆盖,选择了 ii、未选 ii 且未被覆盖、未选 ii 但已经被覆盖的情况。事实上就是简单的状压。

    由于每个连通快的搜索树的深度最大只有 1010,且非树边一定是 Back edge,因此同样可以考虑状压。同样记 dpi,sdp_{i,s} 表示 ii 点的状态。由于从树上问题变为图上问题,一个点同时会被其子树中的点影响,也会被其祖先影响,因此这里 dpdp 的定义有一点点不同。

    定义 dpi,sdp_{i,s} 为,满足 ii 的“子树”被覆盖(不包含 ii),且 dfs 序比 ii 小的点被覆盖(不包含 ii 到“根”路径上的点),ii 到“根”的路径上每个点的状态为 ss 的最小代价。状态 ss 中,其第 jj 位为 ii 到根的路径上深度为 jj 的点的状态。与树上的情形类似,状态有三种:

    1.选了 ii

    2.没选 ii,且 ii 未被覆盖;

    3.没选 ii,且 ii 已被覆盖。

    由于祖先和儿子相互影响,每个点的状态需要更新两次。即 fathersonfather \to sonsonfatherson\to father。首先用父亲来更新儿子。

    ii 不选,若有直接与 ii 相连且已经选了的点,那么有:

    dpfai,sdpi,s+2×3depidp_{fa_i,s}\to dp_{i,s+2\times 3^{dep_i}}

    否则:

    dpfai,sdpi,s+3depidp_{fa_i,s}\to dp_{i,s+3^{dep_i}}

    ii 选,由于存在 Back edge,ii 到“根”的路径上一些点的状态可能由 11 变到 22。我们记新的状态为 ss',则:

    dpfai,s+cidpi,sdp_{fa_i,s}+c_i \to dp_{i,s'}

    剩下的就是 ii 的“子树”对 ii 的影响了。由于要先统计“子树”的状态,需要在递归完每个“子树”时将 dpidp_i 从“子树”更新一次:

    dpi,s=min(dpi,s,dpsoni,s+2×3depi)dp_{i,s}=\min(dp_{i,s},dp_{son_i,s+2\times 3^{dep_i}})

    在以上过程中,每个“子树”会先继承“祖先”的贡献,然后再重新反过来更新“父亲”。这样就处理了“子树”对 ii 到“根”的路径的贡献。

    最后一点就是优化空间。注意到以上方法的空间是 O(310×n)\mathcal{O}(3^{10}\times n) 的,显然会挂。我们将第一维改为点在搜索树中的深度,空间优化至 O(10×310)\mathcal{O}(10\times 3^{10})

    时间复杂度为 O(10×310×n)\mathcal{O}(10\times 3^{10} \times n)

    code

    #include <bits/stdc++.h>
    #define ll long long
    #define reg register
    #define F(i,a,b) for(reg int i=(a);i<=(b);++i)
    #define For(i,x) for(reg int i=head[(x)];i;i=net[(i)])
    using namespace std;
    bool beginning;
    inline int read();
    const int N = 2e4 + 5, E = 6e4 + 5, inf = 0x3f3f3f3f;
    int n, m, c[N], dep[N];
    int ver[E], net[E], head[N], tot;
    inline void add(int x, int y) {
    	ver[++tot] = y, net[tot] = head[x], head[x] = tot;
    }
    bool vis[N];
    int pw[20] {1}, dp[15][E];
    #define bit(x,i) (((x)/pw[(i)])%3)
    #define Min(x,y) ((x)>(y) and ((x)=(y)))
    void dfs(int x) {
    
    	vis[x] = true;
    	memset(dp[dep[x]], 0x3f, sizeof(dp[dep[x]]));
    
    	if (dep[x] == 0) {
    
    		dp[0][0] = c[x];
    		dp[0][1] = 0;
    		dp[0][2] = inf;
    	} else {
    
    		static bool ok[N];
    		memset(ok, 0, sizeof(ok));
    
    		For(i, x) {
    			if (vis[ver[i]])
    				ok[dep[ver[i]]] = true;
    		}
    
    		F(s, 0, pw[dep[x]] - 1) {
    
    			if (dp[dep[x] - 1][s] < inf) {
    
    				bool hav = false;
    				int sta = s;
    
    				F(i, 0, dep[x] - 1) {
    					hav |= ok[i] and bit(s, i) == 0;
    					sta += pw[i] * (ok[i] and bit(s, i) == 1);
    				}
    
    				if (hav)
    					Min(dp[dep[x]][s + pw[dep[x]] * 2], dp[dep[x] - 1][s]);
    
    				else
    					Min(dp[dep[x]][s + pw[dep[x]]], dp[dep[x] - 1][s]);
    
    				Min(dp[dep[x]][sta], dp[dep[x] - 1][s] + c[x]);
    			}
    
    		}
    	}
    
    	For(i, x) {
    
    		if (vis[ver[i]])
    			continue;
    
    		dep[ver[i]] = dep[x] + 1;
    		dfs(ver[i]);
    		F(s, 0, pw[dep[x] + 1] - 1) {
    			dp[dep[x]][s] = min(dp[dep[x] + 1][s], dp[dep[x] + 1][s + pw[dep[x] + 1] * 2]);
    		}
    
    	}
    
    }
    bool ending;
    int main() {
    	//  printf("%.2lfMB\n",1.0*(&beginning-&ending)/1024/1024);
    	n = read(), m = read();
    	F(i, 1, n)c[i] = read();
    	int x, y;
    	F(i, 1, m) {
    		x = read(), y = read();
    		add(x, y), add(y, x);
    	}
    
    	F(i, 1, 10)pw[i] = pw[i - 1] * 3;
    
    	int ans = 0;
    
    	F(i, 1, n)if (!vis[i])
    		dfs(i), ans += min(dp[0][0], dp[0][2]);
    
    	printf("%d", ans);
    	return 0;
    }
    inline int read() {
    	reg int x = 0;
    	reg char c = getchar();
    
    	while (!isdigit(c))
    		c = getchar();
    
    	while (isdigit(c))
    		x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    
    	return x;
    }
    
    • @ 2021-09-21 00:16:27

      提个建议,后括号之后也要加空格

    • @ 2021-09-21 06:52:10

      @ 按照一些规范来说是不应该加的,另外不要那么严格对待格式么(。

    • @ 2021-09-22 22:03:07

      @ 强迫症晚期,不要介意((

  • @ 2021-09-17 10:42:02

    #003 2021.9.17

    [COCI2016-2017 Contest#7 T6] Klavir

    题意简述

    给定一个字符串,每次等概率随机产生一个新的字符。问产生该字符串的每一前缀的期望次数。

    题解

    Declare

    • 下文中,记弹 1i1\to i 的期望弹奏次数为 dpidp_i,且 dp1=ndp_1=n
    • 记音符串为 aia_i

    Analysis

    首先读懂题意,我们发现,对于当前正在弹奏的一段乐曲,有以下两种情况:

    • 当前段的某一后缀与前缀相同。
    • 当前段的任何后缀都与前缀不同。(当前串是“独立”的串)

    第二种情况比较简单,对于第二种情况,那么有:

    dpi=dpi1+1n+1n×(dpidp1+1)+n2n×(dpi+1)dp_i=dp_{i-1}+\frac{1}{n}+\frac{1}{n}\times(dp_i-dp_1+1)+\frac{n-2}{n}\times(dp_i+1)

    dpi=n×dpi1\Rightarrow dp_i=n\times dp_{i-1}

    其中,第一个 1n\frac{1}{n} 表示第 ii 个音符直接弹奏正确的期望,1n×(dpidp1+1)\frac{1}{n}\times(dp_i-dp_1+1) 表示这个音符弹奏错误,但与第一个音符相同的期望,n2n×(dpi+1)\frac{n-2}{n}\times(dp_i+1) 表示这个音符弹奏错误,同时与第一个音符不同的期望。

    样例三对应的就是这种情况。

    3
    3
    1 2 3 
    
    3
    9
    27 
    

    接下来讨论第一种情况。

    前后缀显然可以用 KMP 预处理处理。

    设已经弹奏了 1i1\to i,现在要弹奏第 i+1i+1 个音符。枚举当前弹奏音符 jj。弹错时,需要找到最长的已经弹对的前缀,记为 kjk_j,于是有:

    dpi+1=dpi+1n+1n×j=1n(dpi+1dpkj+1)(jai+1)dp_{i+1}=dp_i+\frac{1}{n}+\frac{1}{n}\times\sum\limits_{j=1}^n(dp_{i+1}-dp_{k_j}+1)(j\neq a_{i+1})

    dpi+1=dpi+n+j=1n(dpi+1dpkj)(jai+1)\Rightarrow dp_{i+1}=dp_i+n+\sum\limits_{j=1}^n(dp_{i+1}-dp_{k_j})(j\neq a_{i+1})

    其中 1n×j=1n(dpi+1dpkj+1)(jai+1)\frac{1}{n}\times\sum\limits_{j=1}^n(dp_{i+1}-dp_{k_j}+1)(j\neq a_{i+1}) 表示弹错了,但已经弹对前缀 1k1\to k,接着从 k+1k+1 弹到 n+1n+1 的期望。两层循环跑一下就完了。时间复杂度 O(n×m2)\mathcal{O}(n\times m^2),实测可过(大概是机子跑得快的原因)。

        dp[1] = n;
        F(i, 1, m) {//弹第 i 个音符
            long long s = 0;
            F(j, 1, n){//枚举弹的音符
                if (j != a[i + 1]) {
                    k = fail[i];
                    while (k && a[k + 1] != j) k = fail[k];
                    if (a[k + 1] == j) ++k;
                    s += dp[i] - dp[k];
                }
            }
            dp[i + 1] = (s + n + dp[i]) % mod;
        }
    

    虽然可过,但理论上还是蛮卡的。接下来我们考虑优化。

    我们记当前为第 ii 个音符,下一个音符是 jj 时,最终跳到的位置为 fi,jf_{i,j},那么 fi,jf_{i,j}ffaili,jf_{fail_i,j} 只有在 j=ai+1j=a_{i+1} 时是不同的。因此对于 dpi+1dp_{i+1} 可以直接继承 dpfaili+1dp_{fail_{i+1}} 的答案,再额外计算 j=ai+1j=a_{i+1} 的贡献即可。从上面方法中,可以看出 j=ai+1j=a_{i+1} 的贡献就是 ni+1n^{i+1}

    综上可得:

    dpi=dpfaili+nidp_i=dp_{fail_i}+n^i

    时间复杂度 O(m)\mathcal{O}(m),算是十分优秀了。

    code

    #include <bits/stdc++.h>
    #define reg register
    #define ll long long
    #define _min(x, y) ((x) < (y) ? (x) : (y))
    #define _max(x, y) ((x) > (y) ? (x) : (y))
    #define Min(x, y) ((x) > (y) and ((x) = (y)))
    #define Max(x, y) ((x) < (y) and ((x) = (y)))
    #define F(i, a, b) for (reg int i = (a); i <= (b); ++i)
    #define PF(i, a, b) for (reg int i = (a); i >= (b); --i)
    #define For(i, x) for (reg int i = head[(x)]; i; i = net[(i)])
    using namespace std;
    bool beginning;
    inline int read();
    const int N = 1e6 + 5, mod = 1e9 + 7;
    int n, m, a[N], fail[N];
    inline void init() {
        int j = 0;
        F(i, 2, m) {
            while (j and a[j + 1] != a[i]) j = fail[j];
            j += (a[j + 1] == a[i]);
            fail[i] = j;
        }
    }
    bool ending;
    int main() {
        // printf("%.2lfMB\n",1.0*(&beginning-&ending)/1024/1024);
        n = read(), m = read();
        F(i, 1, m) {
            a[i] = read();
        }
        init();
        int t = n;
        F(i, 1, m) {
            a[i] = a[fail[i]] + t;
            if (a[i] >= mod) a[i] -= mod;
            t = 1ll * t * n % mod;
            printf("%d\n", a[i]);
        }
        return 0;
    }
    inline int read() {
        reg int x = 0;
        reg bool f = 1;
        reg char c = getchar();
        while (!isdigit(c)) {
            f = c ^ 45;
            c = getchar();
        }
        while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
        return f ? x : -x;
    }
    

    特别鸣谢

    Macesuted 提供优化思路。/bx

    • @ 2021-09-09 07:25:42

      #002 2021.9.9

      Ynoi2008 stcm

      题目大意

      给出一棵 nn 个点的树,需要你构建一个操作序列使得树上每一个结点均被标记一次,操作序列由下面三种操作构成:

      1. +x: 向当前集合中插入 xx 号点。
      2. -: 撤销上一次插入操作。
      3. =x: 确定当前集合为 xx 号点的子树补集并标记 xx

      xx 号点子树补集的定义为 xx 号点子树构成的点集在整棵树点集中的补集。

      题意可能较难理解,也不是非常容易以较简单的方式字面描述,如果你还是不理解可以手推一下样例。

      每个测试点有 TT 组测试数据。

      n105, T3,n \le 10^5,~T \le 3, +x 操作数量 4.5×106\le 4.5 \times 10^6

      题解

      分析

      观察限制的 +x 操作数量大约在 O(nlogn)O(n \log n) 级别,容易想到对树进行重链剖分,然后依次处理每一条重链。

      我们发现如果当前集合为 pp 点的子树补集且 pp 为其所在重链的顶端,我们可以用 O(siz[p])O(siz[p]) 的操作标记 pp 所在重链上的所有点:假设 pp 重链上的点从上到下为 x1, x2, x3,x_1,~x_2,~x_3,\dots,我们可以先标记 x1x_1,然后将 x1x_1x1x_1 的所有轻儿子为根的子树加入集合,然后标记 x2x_2,再将 x2x_2x2x_2 的所有轻儿子为根的子树加入集合,以此类推,最终可以 O(siz[p])O(siz[p]) 标记该重链上的所有点。全局花在该操作上的次数为 O(nlogn)O(n \log n) 级别,证明类似 dsu on tree。

      我们现在已经可以处理一条重链上的信息了,接下来我们要考虑如何完成重链间的切换。为完成重链间的切换,我们显然是枚举 pp 所在重链的所有节点的所有轻儿子,然后考虑将当前集合变为该轻儿子的子树补集然后递归处理该轻儿子所在重链信息。考虑如何在较小的操作步数中将所有轻儿子的子树补集都构造一次。

      考虑极端情况,即整棵树为一个菊花图的情况,考虑如何构造方案。稍微尝试一些方法后会发现最优策略为你构造一个类似线段树的结构,然后你从线段树根开始遍历这个线段树:

      1. 如果当前节点为叶子节点,标记该节点并跳过下面的步骤并回溯。
      2. 将当前节点右儿子对应区间内的所有节点加入集合。
      3. 递归处理左儿子。
      4. 撤销 2 步骤中的插入操作。
      5. 将当前节点左二子对应区间内的所有节点加入集合。
      6. 递归处理右儿子。
      7. 撤销 5 步骤中的插入操作。

      容易发现该方法可以用 O(nlogn)O(n \log n) 此操作标记所有的点,因为每一个点一共被操作的次数等于其祖先数量。

      我们同样可以使用该方法处理我们的轻儿子的问题。我们可以先将重链上的所有节点加入集合,然后将每个轻儿子视为一个点,对所有的轻儿子构建一棵线段树,然后在线段树上从根开始递归处理,到叶子结点时将原本的“标记该结点”换为“递归处理该节点所在的重链”。

      但是容易发现这样的方法并不能保证操作次数复杂度一定正确,因为修改每一个轻儿子的花费是 siz[轻儿子]siz[\text{轻儿子}] 而不是 11。考虑这棵线段树上的总操作数是等于 i叶子节点siz[i]×dep[i]\sum_{i \in \text{叶子节点}} siz[i] \times dep[i],我们想要最小化它的值。这时我们发现哈夫曼树正好就是在最小化这个值,所以我们将“构造线段树”换为“构造哈夫曼树”就可以使该操作复杂度成为 O(siz[p]logsiz[p])O(siz[p] \log siz[p]),递归方法不变。与处理重链时的复杂度证明相似,可以发现全局花在这一操作上的总操作次数为 O(nlogn)O(n \log n)

      总操作次数 O(nlogn)O(n \log n)

      代码

      /**
       * @author Macesuted (macesuted@outlook.com)
       * @copyright Copyright (c) 2021
       * @brief
       *      My tutorial: https://macesuted.cn/article/h1031/
       */
      
      #include <bits/stdc++.h>
      using namespace std;
      
      namespace io {
      #define SIZE (1 << 20)
      char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
      int f, qr;
      inline void flush(void) { return fwrite(obuf, 1, oS - obuf, stdout), oS = obuf, void(); }
      inline char getch(void) { return (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++); }
      inline void putch(char x) {
          *oS++ = x;
          if (oS == oT) flush();
          return;
      }
      string getstr(void) {
          queue<char> que;
          char c = getch();
          while (c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF) c = getch();
          while (!(c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == EOF)) que.push(c), c = getch();
          string s;
          s.resize(que.size());
          for (register int i = 0; i < s.size(); i++) s[i] = que.front(), que.pop();
          return s;
      }
      void putstr(string str, int begin = 0, int end = -1) {
          if (end == -1) end = str.size();
          for (register int i = begin; i < end; i++) putch(str[i]);
          return;
      }
      template <typename T>
      inline T read() {
          register T x = 0;
          for (f = 1, c = getch(); c < '0' || c > '9'; c = getch())
              if (c == '-') f = -1;
          for (x = 0; c <= '9' && c >= '0'; c = getch()) x = x * 10 + (c & 15);
          return x * f;
      }
      template <typename T>
      inline void write(const T& t) {
          register T x = t;
          if (!x) putch('0');
          if (x < 0) putch('-'), x = -x;
          while (x) qu[++qr] = x % 10 + '0', x /= 10;
          while (qr) putch(qu[qr--]);
          return;
      }
      struct Flusher_ {
          ~Flusher_() { flush(); }
      } io_flusher_;
      }  // namespace io
      using io::getch;
      using io::getstr;
      using io::putch;
      using io::putstr;
      using io::read;
      using io::write;
      
      #define maxn 100005
      
      vector<vector<int> > graph;
      
      int siz[maxn], son[maxn];
      
      void insert(int p) {
          putch('+'), write(p);
          for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++) insert(*i);
          return;
      }
      void erase(int p) {
          for (register int i = 1; i <= siz[p]; i++) putch('-');
          return;
      }
      
      class HuffmanTree {
         public:
          struct Node {
              int id, siz;
              Node *l, *r;
              Node(int _id = 0) { siz = ::siz[id = _id], l = r = NULL; }
          };
      
          typedef pair<int, Node*> pin;
      
          Node* root;
      
          void destroy(Node* p) {
              if (p == NULL) return;
              if (p->l != NULL) destroy(p->l);
              if (p->r != NULL) destroy(p->r);
              delete p;
          }
      
          HuffmanTree(void) { root = NULL; }
          ~HuffmanTree(void) { destroy(root); }
          void build(const vector<int>& sons) {
              static priority_queue<pin, vector<pin>, greater<pin> > que;
              while (!que.empty()) que.pop();
              for (vector<int>::const_iterator i = sons.cbegin(); i != sons.cend(); i++) {
                  Node* p = new Node(*i);
                  que.push((pin){siz[*i], p});
              }
              while (que.size() > 1) {
                  Node* l = que.top().second;
                  que.pop();
                  Node* r = que.top().second;
                  que.pop();
                  Node* p = new Node();
                  p->l = l, p->r = r;
                  p->siz = l->siz + r->siz;
                  que.push((pin){p->siz, p});
              }
              root = que.top().second, que.pop();
              return;
          }
          void insert(Node* p) {
              if (p == NULL) return;
              if (p->id) return ::insert(p->id);
              if (p->l != NULL) insert(p->l);
              if (p->r != NULL) insert(p->r);
              return;
          }
          void erase(Node* p) {
              if (p == NULL) return;
              if (p->id) return ::erase(p->id);
              if (p->l != NULL) erase(p->l);
              if (p->r != NULL) erase(p->r);
              return;
          }
      };
      
      void dfs1(int p) {
          siz[p] = 1, son[p] = 0;
          for (vector<int>::iterator i = graph[p].begin(); i != graph[p].end(); i++) {
              dfs1(*i);
              siz[p] += siz[*i];
              if (son[p] == 0 || siz[*i] > siz[son[p]]) son[p] = *i;
          }
          return;
      }
      void dfs3(HuffmanTree&, HuffmanTree::Node*);
      void dfs2(int p) {
          vector<int> chain, sons;
          chain.clear(), sons.clear();
          int x = p;
          while (x) chain.push_back(x), x = son[x];
          for (vector<int>::iterator i = chain.begin(); i != chain.end(); i++) {
              putch('='), write(*i), putch('+'), write(*i);
              for (vector<int>::iterator j = graph[*i].begin(); j != graph[*i].end(); j++)
                  if (*j != son[*i]) sons.push_back(*j), insert(*j);
          }
          for (vector<int>::reverse_iterator i = sons.rbegin(); i != sons.rend(); i++) erase(*i);
          for (vector<int>::reverse_iterator i = chain.rbegin(); i != chain.rend(); i++) putch('-');
          for (vector<int>::iterator i = chain.begin(); i != chain.end(); i++) putch('+'), write(*i);
          if (!sons.empty()) {
              HuffmanTree tree;
              tree.build(sons);
              dfs3(tree, tree.root);
          }
          for (vector<int>::reverse_iterator i = chain.rbegin(); i != chain.rend(); i++) putch('-');
          return;
      }
      void dfs3(HuffmanTree& tree, HuffmanTree::Node* p) {
          if (p == NULL) return;
          if (p->id) return dfs2(p->id);
          tree.insert(p->r);
          if (p->l != NULL) dfs3(tree, p->l);
          tree.erase(p->r);
          tree.insert(p->l);
          if (p->l != NULL) dfs3(tree, p->r);
          tree.erase(p->l);
          return;
      }
      
      int main() {
          ios::sync_with_stdio(false);
          cin.tie(0);
          int n;
          while (cin >> n) {
              graph.resize(n + 1);
              for (register int i = 2, fa; i <= n; i++) cin >> fa, graph[fa].push_back(i);
              dfs1(1), dfs2(1);
              putch('!'), putch('\n');
              graph.clear();
          }
          return 0;
      }
      
      • @ 2021-09-12 09:09:57

        class+public: 是为了让别人看不懂么……

      • @ 2021-09-12 09:10:45

        @创造君: (而不用 struct)

      • @ 2021-09-13 07:43:44

        @创造君: 个人代码习惯。OOP

      • @ 2021-09-13 20:46:18

        @创造君: 比如我,就喜欢用class(逃

    • @ 2021-09-03 15:13:19

      #001 2021.9.3

      [COCI2018-2019 Final T4] TENIS

      题解

      Analysis

      思维题。

      拿到题目首先观察样例。

      4 4
      1 2 3 4
      2 1 3 4
      2 4 3 1
      1 1
      1 4
      2 3 1 4
      1 4
      

      针对第二个事件,我们发现,虽然在前两个场地 44 都是最弱的,但是在第三个场地 44 能打赢 1133,而在第一个场地 11 又能打赢 22。因此只需让能被选手 44 打败的人先去打选手 44 打不过的人,选手 44 才有可能获得胜利。

      将以上策略抽象成图,将每一个人视为一个结点,向每个他能打败的人(不管在哪个场地)都连一条边,那么询问就是看从这个人的结点出发,能否遍历其他所有结点。如下图:

      hyhUZq.png

      (此处 1.1,1.2,1.31.1,1.2,1.3 为选手 11 在三个场地的排名,在这种方法中可缩为一个点)

      这时处理询问的复杂度为 O(n)\mathcal{O}(n),总时间复杂度为 O(n×Q)\mathcal{O}(n\times Q),期望得分 3030 分。

      我们发现问题的瓶颈在于处理询问,而上述处理方法基于连向其他结点的边。为方便观察,先将这些边删去。我们来随手搓一组。

      5 0
      1 2 4 3 5
      2 1 4 5 3
      1 4 2 3 5
      

      将同一个选手在三个场地的位置用边连接,如下图:

      hytAmR.png

      此时选手 11、选手 22、选手 44 可能获胜。

      可以发现,能获胜的选手和不能获胜的选手中间有一道明显的分隔线。这条分割线满足:没有一条边横跨分割线。这时在分割线左边的选手能获胜,右边的则不能。

      然而随手一组就 Hack 掉了。比如:

      5 0
      1 2 3 4 5
      1 2 3 4 5
      1 2 3 4 5
      

      在这组中有多条满足要求的分割线,怎么办?显然只有最左边的是正确的。考虑维护最左边的分割线

      为什么这样是正确的?考虑分割线左边选手的情况。显然左边的选手可以直接或间接打败在左边的其他选手。假设某一个选手不能打败左边的其他选手,那么这条分割线一定可以向左移动,把这个选手排除在外。那么这样就不满足最左边的分割线这一前提条件。因此假设不成立。

      基于以上事实,分割线左边的选手必定可以直接或间接打败其他选手。同样的,分割线右边的选手不可能直接或间接打败左边的全部选手。(同样可以反证)

      这条线如何维护呢?我们记数组 pppip_i 表示有 pip_i 个选手的边没有跨过 ii。记第 ii 位选手的在第 jj 个场地的排名为 di,j(1j3)d_{i,j}(1\le j\le 3),那么对于这名选手来说,他的边不会跨过 max(di,j)n (1j3)\max(d_{i,j})\to n~(1\le j\le 3),体现在 pp 数组上即对 pipnp_i \to p_n 区间加 11

      最后,pp 何时满足条件?根据 pip_i 的定义可知,若 pi=ip_i=i,则此处有一条分割线。找最左边的一条即可。

      总结上文,需要支持的操作有:

      • 区间加。
      • 区间查询。

      用线段树维护即可。时间复杂度 O(Qlogn)\mathcal{O}(Q \log n)

      tips:线段树叶节点可以赋初值 l-l,其中 ll 为结点代表的范围。在每个结点里记最大值。查询时树上二分,若左子树最大值为 00,查左子树,否则查右子树。

      code

      #include<bits/stdc++.h>
      #define ll long long
      #define reg register
      #define _max(a,b) ((a)>(b)?(a):(b))
      #define Max(x,y,z) ((x)>(y)?_max((x),(z)):_max((y),(z)))
      #define _Max(x) Max(d[1][x],d[2][x],d[3][x])
      #define F(i,a,b) for(reg int i=(a);i<=(b);++i)
      using namespace std;
      bool beginning;
      inline int read();
      const int N=1e5+5;
      int n,q,d[4][N],Ans;
      struct P {
      	int l,r,Mx,lz;
      } f[N<<2];
      #define ls (x<<1)
      #define rs (x<<1|1)
      void build(int x,int l,int r) {
      	f[x].l=l,f[x].r=r;
      	if(l==r) {
      		f[x].Mx=-l;
      		return;
      	}
      	int mid=l+r>>1;
      	build(ls,l,mid);
      	build(rs,mid+1,r);
      	f[x].Mx=_max(f[ls].Mx,f[rs].Mx);
      }
      inline void push_down(int x) {
      	if(!f[x].lz)return;
      	f[ls].lz+=f[x].lz,f[rs].lz+=f[x].lz;
      	f[ls].Mx+=f[x].lz,f[rs].Mx+=f[x].lz;
      	f[x].lz=0;
      }
      void modify(int x,int l,int r,int val) {
      	if(l<=f[x].l and f[x].r<=r) {
      		f[x].lz+=val,f[x].Mx+=val;
      		return;
      	}
      	push_down(x);
      	int mid=f[x].l+f[x].r>>1;
      	if(l<=mid)modify(ls,l,r,val);
      	if(r>mid)modify(rs,l,r,val);
      	f[x].Mx=_max(f[ls].Mx,f[rs].Mx);
      }
      int query(int x,int l,int r) {
      	if(l==r)return l;
      	int mid=l+r>>1;
      	push_down(x);
      	if(!f[ls].Mx)return query(ls,l,mid);
      	return query(rs,mid+1,r);
      }
      bool ending;
      int main() {
      //  printf("%.2lfMB\n",1.0*(&beginning-&ending)/1024/1024);
      	n=read(),q=read();
      	build(1,1,n);
      	F(i,1,3)F(j,1,n)d[i][read()]=j;//记排名 
      	F(i,1,n)modify(1,_Max(i),n,1);//将初始结点插入答案 
      	Ans=query(1,1,n);//记录分割线 
      	reg int op,x,y,z;
      	while(q--) {
      		op=read();
      		if(op==1) {
      			x=read();
      			puts(d[1][x]<=Ans?"DA":"NE");
      		} else if(op==2) {
      			z=read(),x=read(),y=read();
      			modify(1,_Max(x),n,-1);
      			modify(1,_Max(y),n,-1);
      			swap(d[z][x],d[z][y]);
      			modify(1,_Max(x),n,1);
      			modify(1,_Max(y),n,1);
      			Ans=query(1,1,n);
      		}
      	}
      	return 0;
      }
      inline int read() {
      	reg int x=0;
      	reg char c=getchar();
      	while(!isdigit(c))c=getchar();
      	while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
      	return x;
      }
      
    • 1