mxh带窝打多校之Contest 5

OI mxh带窝飞

---

约定

对于两个字符串$a,b$，$ab$表示$a$与$b$首尾相接得到的串。
对于两个字符串$s, S$，$s\in S$表示$s$是$S$的子串。

题意

mxh Round www

1001 MZL's Circle Zhou

给出两个串$S$，$T$，问本质不同的$st(s\in S, t\in T)$有多少种。

1002 MZL's XOR

给出$A$，求$\{A_i+A_j|1\leq i, j\leq N\}$的异或和。

1004 MZL's game

有$N$个格子，初始全为白，每一轮选一个白格子染灰，其他每个白格子有$p$的概率被染黑，若无白格子就停止，对于$1\leq k\leq N$，求一个白格子在第$k$轮被染灰的概率。

1006 MZL's endless loop

对于给定的无向图$G=\{V,E\}$，请为每条边确定一个方向，使得对于任意一点$x$，有$|in_x-out_x|\leq 1$。

1007 MZL's simple problem

维护一个多重集$S$，支持：
1. 向$S$插入元素$x$
2. 删除最小元素
3. 询问最大元素

1008 MZL's manhuff function

给出长度为$N$的数列$A$，令

$$B_i=\sum_{j=i}^NA_i$$

$$f(i,j)=\begin{cases} 0 & (i,j)=(1,1) \\ min(f(i-1,j+1),f(i,\lceil\frac{j}{2}\rceil)+B_i) & i,j\in[1,n],~(i,j)\neq(1,1) \\ 10^{11037} & otherwise \end{cases}$$

求$f(n,1)$。

1009 MZL's Border

$F$是字符串序列。

$F_1=b$
$F_2=a$
$F_n=F_{n-1}F_{n-2}(n>2)$

其中$F_{n-1}F_{n-2}$是拼接$F_{n-1}$与$F_{n-2}$。
令$S=F_N[1\ldots M]$。

求$max\{S[1\ldots i]=S[|S|-i+1\ldots |S|]|i<|S|\}$

题解

1001 MZL's Circle Zhou

考虑对每个串$s$确定唯一的分割方式，即若能在$S$中找到子串则记为$(s, "")$，否则令$s_0$为$s$在$S$的SAM中的最大匹配部分，其余部分记作$s_2$，则将其记为$(s_1,s_2)$。
显然地，对于$s_1$，若$s_1c$在$S$中没有出现，则所有$T$中以$c$开头的子串$s_2$都是合法的。
在SAM上DP即可。
别忘了unsigned long long QAQ

# include <cstdio>
# include <cstring>
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define REP_0N(i, n) for (int i = 0; i <= n; i ++)
# define REP_D(i, n) for (int i = n; i >= 1; i --)
# define CLR(a, x) memset (a, x, sizeof (a))
typedef unsigned long long ll;
const int NR = 100100;
struct Sam {int trans[26], par, l; Sam () {CLR (trans, -1);}} sam[NR << 1];
int d[NR << 1], cnt[NR], lst, sz, q0;
ll f[NR << 1], g[NR << 1], res[30];
char s0[NR], s1[NR];
# define u sam[x]
# define v u.trans[c]
# define vn sam[v]
# define o sam[y]
# define w sam[z]
inline void Init () {REP (x, sz) CLR (u.trans, -1); sam[sz = lst = 1].par = -1;}
void AddChar (int c)
{
    int x = lst, z = ++ sz; lst = z, w.l = u.l + 1;
    for (; x != -1 && v == -1; x = u.par) v = z;
    if (x == -1) w.par = 1;
    else if (u.l + 1 == vn.l) w.par = v;
    else
    {
        int y = ++ sz, tv = v;
        o = vn, o.l = u.l + 1, w.par = vn.par = y;
        for (; x != -1 && v == tv; x = u.par) v = y;
    }
}
void Sort (int len)
{
    REP_0N (i, len) cnt[i] = 0;
    REP (x, sz) cnt[u.l] ++;
    REP (i, len) cnt[i] += cnt[i - 1];
    REP (x, sz) d[cnt[u.l] --] = x;
}
int main ()
{
    for (scanf ("%d", &q0); q0; q0 --)
    {
        scanf ("%s%s", s0 + 1, s1 + 1);
        int l0 = strlen (s0 + 1), l1 = strlen (s1 + 1);
        Init (); REP (i, l1) AddChar (s1[i] - 'a'); Sort (l1);
        REP_D (i, sz) 
        {
            int x = d[i]; g[x] = 1;
            REP_0 (c, 26) if (v != -1) g[x] += g[v];
        }
        {int x = 1; REP_0 (c, 26) v != -1 ? res[c] = g[v] : res[c] = 0;}
        Init (); REP (i, l0) AddChar (s0[i] - 'a'); Sort (l0);
        REP (x, sz) f[x] = (u.par == -1 ? 1 : (u.l - sam[u.par].l));
        REP_D (i, sz)
        {
            int x = d[i];
            REP_0 (c, 26) if (v == -1) f[x] += res[c] * (u.par == -1 ? 1 : (u.l - sam[u.par].l));
            if (u.par != -1) f[u.par] += f[x];
        }
        printf ("%llu\n", f[1]);
    }
    return 0;
}

1002 MZL's XOR

注意到$1\leq i, j\leq N$，所以对于$i\neq j$的贡献都是0。

# include <cstdio>
int main ()
{
    int q0, n, m, z, l;
    for (scanf ("%d", &q0); q0; q0 --)
    {
        scanf ("%d%d%d%d", &n, &m, &z, &l);
        int res = 0, a = 0;
        for (int i = 2; i <= n; i ++) a = (1ll * a * m + z) % l, res ^= (a << 1);
        printf ("%d\n", res);
    }
    return 0;
}

1004 MZL‘s game

考虑编号从小到大染灰。
令$F(i,j)$为第$j$轮时第$i$个格子之前全为有色格子的概率。
$F(i,j)=(1-p)^jF(i-1,j-1)+(1-(1-p)^j)F(i-1,j)$

1006 MZL's endless loop

考虑一个环，做法是显然的。
把所有环删掉以后原图变为森林。
在树上DFS一遍显然可以定向。

# include <cstdio>
# include <cstring>
# include <cassert>
# include <algorithm>
# include <iostream>
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_G(i, x) for (int i = pos[x]; i; i = g[i].f)
# define RST(a) memset (a, 0, sizeof (a))
using namespace std;
const int NR = 100100, ER = 300100;
int q0, n, m, gsz, top, f[NR], pos[NR], stk[NR], cur[NR], pre[NR];
bool vis[NR], col[ER], del[ER];
struct Edge {int y, f; void Set (int yr, int fr) {y = yr, f = fr;}} g[ER << 1];
void AE (int x, int y) {g[++ gsz].Set (y, pos[x]), pos[x] = gsz;}
# define v g[i].y
void DFS (int S)
{
    vis[stk[top = 1] = S] = 1;
    while (top)
    {
        int x = stk[top]; bool EXIT = 0;
        for (int &i = cur[x]; i; i = g[i].f)
        {
            if ((pre[x] ^ 1) == i || del[i >> 1]) continue;
            if (vis[v])
            {
                del[i >> 1] = 1, col[i >> 1] = (i & 1);
                for (; stk[top] != v; top --) del[pre[stk[top]] >> 1] = 1, col[pre[stk[top]] >> 1] = (pre[stk[top]] & 1), vis[stk[top]] = 0;
                i = g[i].f;
                EXIT = 1; break;
            }
            else {vis[stk[++ top] = v] = 1; pre[v] = i, i = g[i].f; EXIT = 1; break;}
        }
        if (!EXIT) vis[x] = 0, top --;
    }
}
void Calc (int x)
{
    vis[x] = 1;
    REP_G (i, x)
        if (!vis[v] && !del[i >> 1])
        {
            if (!f[x]) f[x] = 1, f[v] = -1, col[i >> 1] = (i & 1), Calc (v);
            else col[i >> 1] = ((f[x] == 1) ^ (i & 1)), f[v] = f[x], f[x] = 0, Calc (v);
        }
}
int main ()
{
    for (scanf ("%d", &q0); q0; q0 --)
    {
        scanf ("%d%d", &n, &m), gsz = 1; int t1, t2;
        RST (f), RST (col), RST (vis), RST (del), RST (pos);
        REP (i, m) 
        {
            scanf ("%d%d", &t1, &t2); 
            if (t1 == t2) gsz += 2;
            else AE (t1, t2), AE (t2, t1);
        }
        REP (i, n) cur[i] = pos[i];
        REP (i, n) DFS (i);
        REP (i, n) if (!vis[i]) Calc (i);
        REP (i, m) printf ("%d\n", col[i]);
    }
    return 0;
}

1007 MZL's simple problem

维护最大值和当前集合大小。

1008 MZL's manhuff function

考虑题目和哈夫曼树有关。
原函数的意义是添加到位置$i$现在有$j$棵树需要合并时的最小代价。
用哈夫曼树求得的解显然是最优的。

# include <cstdio>
# include <queue>
# define REP(i, n) for (int i = 1; i <= n; i ++)
using namespace std;
priority_queue <long long> Q;
int main ()
{
    int q0;
    for (scanf ("%d", &q0); q0; q0 --)
    {
        int ta, n;
        scanf ("%d", &n);
        REP (i, n) scanf ("%d", &ta), Q.push (- ta);
        long long ans = 0;
        while (1)
        {
            int w0 = - Q.top (), w1; Q.pop ();
            if (Q.empty ()) break;
            w1 = - Q.top (); Q.pop ();
            ans += w0 + w1, Q.push (- w0 - w1);
        }
        printf ("%I64d\n", ans);
    }
    return 0;
}

1009 MZL's Border

打表，不会证。

# include <cstdio>
# include <cstring>
# include <algorithm>
# include <iostream>
# define REP(i, n) for (int i = 1; i <= n; i ++)
# define REP_0(i, n) for (int i = 0; i < n; i ++)
# define REP_D0(i, n) for (int i = n - 1; i >= 0; i --)
# define FOR(i, a, b) for (int i = a; i <= b; i ++)
# define RST(a) memset (a, 0, sizeof (a))
using namespace std;
const int NR = 10000;
const int P = 258280327;
const int W = 100000000;
int poolA[NR], la, poolB[NR], lb, poolC[NR], lc;
int f[20000];
bool Comp (int *a, int *b, int la, int lb)
{
    if (la > lb) return 1;
    if (la < lb) return 0;
    REP_D0 (i, la) 
    {
        if (a[i] > b[i]) return 1;
        if (a[i] < b[i]) return 0;
    }
    return 0;
}
void Minus (int *a, int *b, int &la, int lb)
{    
    REP_0 (i, lb) 
    {
        a[i] -= b[i];
        if (a[i] < 0)
        {
            a[i] += W, a[i + 1] --;
            if (i + 1 == lb) lb ++;  
        }
    }
    if (la == lb) while (!a[la - 1]) la --;
}
void Add (int *a, int *b, int &la, int lb)
{
    REP_0 (i, lb)
    {
        a[i] += b[i];
        if (a[i] >= W)
        {
            a[i] -= W, a[i + 1] ++;
            if (i + 1 == lb) lb ++;
        }
    }
    if (lb > la) la = lb;
}
char s[2000];
int main ()
{
    int q0, n; f[0] = 0, f[1] = 1;
    FOR (i, 2, 15000) 
    {
        f[i] = f[i - 1] + f[i - 2];
        if (f[i] >= P) f[i] -= P;
    }
    for (scanf ("%d", &q0); q0; q0 --)
    {
        scanf ("%d%s", &n, s), RST (poolA), RST (poolB), RST (poolC);
        int len = strlen (s);
        REP_0 (i, len) if (i < len - i - 1) swap (s[len - i - 1], s[i]);
        if (n < 3) {printf ("%d\n", 0); continue;}
        la = lb = lc = 0;
        int *a = poolA, *b = poolB, *c = poolC, tW = 0;
        REP_D0 (i, len)
        {
            tW = 1ll * tW * 10 + s[i] - '0';
            if (!(i % 8)) a[la ++] = tW, tW = 0;
        }
        REP_0 (i, la) if (i < la - i - 1) swap (a[la - i - 1], a[i]);
        int cur = 0, lev = 0, aw = 0;
        lb = lc = b[0] = c[0] = 1;
        while (Comp (a, b, la, lb))
        {
            Minus (a, b, la, lb), Add (c, b, lc, lb);
            swap (b, c), swap (lb, lc);
            cur += f[lev ++]; if (cur >= P) cur -= P;
        }
        REP_D0 (i, la) aw = (1ll * W * aw + a[i]) % P;
        cur += aw - 1; if (cur >= P) cur -= P;
        printf ("%d\n", cur);
    }
    return 0;
}