9.5

A

长度为 $2^N$ 的序列 $A$ ，编号 $0..2^N-1$
对于每一个 $K (0 < k < 2^N)$ ，求 $\max(A_i + A_j) (i \text{ or } j \le K )$

数学题，码量很小，把 $i,j$ 看成二进制下 $1$ 的集合，就相当于 $i \subseteq k, j \subseteq k $

也就是对于每个 $k$ 去寻找子集最大值和次大值进行一个相加就是答案。

考虑维护这个子集信息，发现可以搞一个 $n$ 维的前缀$\max$ 。然后就行了，写成代码就像是这样 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
#define N 20
#define inf 1e9
struct node{
    int m1,m2;
    node(){}
    node(int _x,int _y) : m1(_x),m2(_y){}
    friend node operator + (node a,node b)
    {
        if(a.m1 > b.m1) return node{a.m1,max(a.m2,b.m1)};
        return node{b.m1,max(a.m1,b.m2)};
    }
}a[1 << N];
 
int n,m;
 
signed main()
{
    ios :: sync_with_stdio(false);
    cin >> n;
    m = 1 << n;
    for(int i = 0;i < m;i++) cin >> a[i].m1,a[i].m2 = -inf;
    for(int i = 0;i < n;i++) 
    for(int j = 0;j < m;j++) 
    if((j >> i) & 1) a[j] = a[j] + a[j ^ (1 << i)];
    int ans = 0;
    for(int j = 1;j < m;j++)
    ans = max(ans,a[j].m1 + a[j].m2),cout << ans << '\n';
    return 0;
}

B

对于两个长度为 $n$ 的 $01$ 串 $s,t$ ，你可以对 $s$ 进行两种操作：把相邻两个 $0$ 变成 $1$ 或把相邻两个 $1$ 变成 $0$ ，定义 $s$ 到 $t$ 的距离为最少操作次数使得 $s$ 变成 $t$ ，如过没法变则距离为 $0$ 。

现在你有两个不完整的字符串，可以把其中的 $?$ 变成 $0$ 或 $1$ ，求所有情况所得到的两个 $01$ 串的距离之和。

多组数据。

考虑把奇数（或者偶数也一样）位置的字符取反，这样我们就把反转操作变成了交换相邻不同项。

我们把取反后的字符串记为 $s’,t’$ 显然充要条件是两字符串中 $1$ 的个数相同。

可以考了通过计算逆序对数来解决这个问题，但是对于 $01$ 串有更好计算的结论 ： 设 $s′$ 中第 $i$ 个 $1$ 的下标为 $x_i$，$t′$ 中第 $i$ 个 $1$ 的下标为 $yi$，那么最少交换次数为 $|xi−yi|$ , 其中 $c$ 表示 $s′,t′$ 中 $1$ 的个数.

考虑进一步化简，设 $a_i$ 表示 $s′$ 中前 $i$ 个数中 $1$ 的个数， $b_i$ 表示 $t′$ 中前 $i$ 个数中 $1$ 的个数，答案就是 $\sum_{i=1}^|ai−bi|$。因为每次交换两个数，最多只能使一个前缀和发生变化。

然后就简单了，我们记 $pre_{i,j}$ 表示前 $i$ 个数使得 $ai−bi=j$ 的方案数， $suf_{i,j}$ 表示对应后缀的方案数，那么贡献就是 $pre_{i,j}×suf_{i+1,−j}×|j|$ 。

代码 ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
 
#define N 2010
const int p = 1e9+7;
typedef long long ll;
 
bool eq(char a,int b)
{
    return a == '?' || a == b + '0';
}
 
int n;
char a[N],b[N];
ll suf[N][N << 1],pre[N][N << 1];
 
inline void work()
{
    scanf("%d%s%s",&n,a+1,b+1);
    for(int i = 0;i <= n + 1;i++)
    for(int j = 0;j <= n << 1;j++)
    suf[i][j] = pre[i][j] = 0 ;
    for(int i = 1;i<=n;i+=2) 
    if(a[i] != '?') a[i] = (a[i] ^ 48 ^ 1) + 48;
    for(int i = 1;i<=n;i+=2) 
    if(b[i] != '?') b[i] = (b[i] ^ 48 ^ 1) + 48;
    pre[0][n] = 1;
    for(int i = 0;i < n;i++)
    for(int j = 0;j <= n << 1;j++)
    for(int k = 0;k <= 1;k++)
    for(int q = 0;q <= 1;q++)
    if(eq(a[i + 1],k) && eq(b[i + 1],q) && j + k - q >= 0)
    (pre[i + 1][j + k - q] += pre[i][j]) %= p;
    suf[n + 1][n] = 1;
    for(int i = n + 1;i >= 2;i--)
    for(int j = 0;j <= n << 1;j++)
    for(int k = 0;k <= 1;k++)
    for(int q = 0;q <= 1;q++)
    if(eq(a[i - 1],k) && eq(b[i - 1],q) && j + k - q >= 0)
    (suf[i - 1][j + k - q] += suf[i][j]) %= p;
    ll ans = 0ll;
    for(int i = 1;i<n;i++)
    for(int j = -n;j<=n;j++)
    (ans += pre[i][j + n] * suf[i + 1][n - j] % p * abs(j) % p) %= p;
    printf("%lld\n",ans);
}
 
signed main()
{
    int T;
    for(scanf("%d",&T);T;T--)
    work();
    return 0;
}

C

给定一个整数数列 $a$，定义 $f(a)=\max_{1\leq i0f(a)>0$。

你需要求出至少需要修改 $a$ 的多少个位置才能使 $f(a)$ 变小。

注意，你修改之后的数也必须是整数。

首先原序列的 $f(x)$ 值 $O(n)$ 易求。然后考虑改变谁的值使答案变小。

容易发现贡献是这样产生的（假装有图）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    ----
    /
   /           ---
  /            /
 /            /
---          /
            /
         -----
                        -　----
                         /
                        /
                       /
                      /
                   ---   -

并且除此之外的部分都不会有贡献，容易找到这样的每一部分，总答案就是每部分答案的和。

考虑如何计算每一部分的答案，考虑在每部分中找到一个点，改变它前缀小值和后缀大值，这个节点通过枚举找到最小贡献，处理前缀后缀可以线性预处理，然而用一些小trick可以避免这个东西。

然后没了

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 1000010
#define inf 1000000000
int n;
int ans;
int a[N];
int premin = inf;
int maxx,mxnum;
signed main()
{
    scanf("%d",&n);
    for(int i = 1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        premin = min(premin,a[i]);
        maxx = max(maxx,a[i] - premin);
    }
    int i,j,cnt1,cnt2;
    for(i = 1;i<=n;i=j,ans += cnt2)
    for(j = i,cnt1 = 0,cnt2 = 0; j <= n && a[i] <= a[j];j++)
    {
        if(a[j] == a[i]) cnt1++;
        else if(a[j] - a[i] == maxx)
        {
            cnt1--;
            cnt2 = min(cnt2,cnt1);
            ans++;
        }
    }
     
    printf("%d",ans);
    return 0;
}

9.6

A

有 $n$ 个数。你需要找出它们的一个排列，满足 $m$ 个条件，每个条件形如 $x_a$ 必须在 $x_b$ 之前。

在此基础上，你要最大化这个排列的子段和。

考虑网络流，首先计算整个序列的正数和，然后考虑减去不合法的贡献。

我们把每个正数拆成两个点，一个连源点，一个连汇点。

然后把每个负数拆成两个点，自己连自己。

对于一个 $x$ 必须在 $y$ 之前的限制，我们在两边的点对 $x$ 向 $y$ 连边，容易发现这样跑出来的二分图最小割就是不合法贡献，减去即可

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
namespace Pozhu{
#define in(i) (i)
#define out(i) (i + n)
using namespace std;
const int N = 2010;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int a[N];
 
struct edge
{
    int v, nxt, w;
} e[M];
int cur[N], head[N], cnt = 1;
int dis[N];
 
void add(int u, int v, int w)
{
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;
 
    e[++cnt].v = u;
    e[cnt].w = 0;
    e[cnt].nxt = head[v];
    head[v] = cnt;
}
 
bool bfs(int s, int t)
{
    memset(dis, 0, sizeof(dis));
    memcpy(cur, head, sizeof(head));
    queue<int> q;
    q.push(s);
    dis[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].v;
            if (!dis[v] && e[i].w)
            {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    return dis[t];
}
 
int dfs(int u, int flow, int t)
{
    if (u == t || !flow)
        return flow;
    int rest = flow, i;
    for (i = cur[u]; i; i = e[i].nxt)
    {
        int v = e[i].v;
        if (dis[v] == dis[u] + 1 && e[i].w)
        {
            int k = dfs(v, min(rest, e[i].w), t);
            if (!k)
                dis[v] = 0;
            e[i].w -= k, e[i ^ 1].w += k;
            rest -= k;
            if (rest == 0)
                break;
        }
    }
    cur[u] = i;
    return flow - rest;
}
 
int dinic(int s, int t)
{
 
    int ans = 0;
    while (bfs(s, t))
        ans += dfs(s, INF, t);
    return ans;
}
 
void main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if (a[i] > 0)
            sum += a[i];
    }
    int s = 2 * n + 1, t = s + 1;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] >= 0)
            add(s, in(i), a[i]), add(out(i), t, a[i]);
        else
            add(in(i), out(i), -a[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(in(a), in(b), INF);
        add(out(a), out(b), INF);
    }
    printf("%d", sum - dinic(s, t));
}
 
}
 
signed main()
{
    Pozhu::main();
    return 0;
}

B

给定整数 $A,B,V,M$ ，其中 $A,B$ 保证互质。另外，还有一个整数 $x$，初始化为 $x=V$。

您可以按任意顺序执行以下四种操作，次数不限。

  • x <- x+A
  • x <- x-A
  • x <- x+B
  • x <- x-B

操作过程中， $0 \le x \le M$ 必须在任意时刻成立
问 $x$ 可以有多少种不同取值。

乍一眼是类欧题，再看看更像类欧题，但是实际上因为类欧没有考虑过程中可能会出现的越界情况本题至少我目前没有发现类欧解法。

于是看题解，题解使用了强周期引理进行特判 ：

若 $a + b \le m+1$，则答案为 $m+1$ ，证明

剩下的情况就是两条链，一条链是 $+a,-b$ 得到的结果，另一条链是 $-a,+b$ 得到的结果。

可以证明两链没有公共点（无重复情况）

所以答案就是两链边数和加一。

考虑实现发现不好实现，于是直接贴代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
namespace Pozhu
{
    using namespace std;
    typedef long long ll;
    ll a, b, v, m;

    ll solve(ll , ll, ll, ll, ll, ll );

    void main()
    {
        cin >> a >> b >> v >> m;
        if (a > b)
            swap(a,b);
        if (a + b <= m + 1)
            cout << m + 1 << endl;
        else
            cout << solve(a, b, v, m, 1, 1) + solve(a, b, m - v, m, 1, 1) + 1 << endl;
        return;
    }

    ll solve(ll a, ll b, ll v, ll m, ll x, ll y)
    {
        if (v >= a)
            return solve(a, b, v % a, m, x, y) + v / a * y;
        if (b + v > m)
            return 0;
        return solve(b % a, a, m - b + b % a - v, m - b + b % a, y, x + b / a * y);
    }

}

signed main()
{
    int T;
    for (std ::cin >> T; T; T--)
        Pozhu ::main();
    return 0;
}

C

给一个长度为 $N$ 的数列 $A_{1..N}$ 和整数 $X$

求有多少个 $\{1,2,\dots,n\}$ 的子集 $S$ 使 $ \forall i,j\in S,A_i\,\text{xor}\,A_j\le X$ 对 $998244353$ 取模

经典异或题，经典 $01 trie$ 。
$f(u,v)$ 表示从 $u$ 的子树和 $v$ 的子树中选一些数，两两异或不大于 $X$ 的方案数
答案是 $f(1,1)$
如果 $X$ 当前位是 $0$ ，那么 $f(u,v)=f(lsu,lsv)+f(rsu,rsv)−1$ ，减 $1$ 是减掉出现两次的空集，如果 $u\neq v$，也就是更高位出现了 $1$ ，如果现在只在一颗子树中选相当于撤回了更高位的 $1$ ，就不需要考虑这一位了，补上对应的方案
如果 $X$ 当前位是 $1$ ，如果 $u=v，f(u,u)=f(lsu,rsu)$ ，如果 $u\neq v$，发现 $f(lsu,rsv)$ 与 $f(rsu,lsv)$ 相互独立，也就是 $f(u,v)=f(lsu,rsv)×f(rsu,lsv)$

于是贴一下别人代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
/**************************************************************
    Problem: 4595
    User: 2022hb07
    Language: C++
    Result: Accepted
    Time:142 ms
    Memory:148100 kb
****************************************************************/
 
 
#include <bits/stdc++.h>
using namespace std;
const int p = 998244353;
#define Maxn 150010
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define int long long
namespace IOI
{
#ifdef ONLINE_JUDGE
#define IOSIZE (1 << 21)
char ibuf[IOSIZE], obuf[IOSIZE];
char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1 == p2) and (p2 = (p1 = ibuf) + fread(ibuf, 1, IOSIZE, stdin), p1 == p2) ? (EOF) : (*p1++))
#define putchar(x) ((p3 == obuf + IOSIZE) && (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf), *p3++ = x)
#define dwd (fwrite(obuf, p3 - obuf, 1, stdout), void())
#else // fread in OJ
#define dwd
#endif // stdio in local
bool ioflag;
inline int read()
{
    ioflag = true;
    int s = 0, w = 1;
    char c = getchar();
    while (!isdigit(c) and c != EOF)
    {
        if (c == '-')
            w = -1;
        c = getchar();
    }
    if (c == EOF)
        return ioflag = false;
    while (isdigit(c))
    {
        s = s * 10 + c - '0';
        c = getchar();
    }
    return s * w;
}
inline void write(int x)
{
    static int st[20];
    int top = 0;
    if (x < 0)
        putchar('-'), x = -x;
    if (x == 0)
        st[++top] = '0';
    while (x)
    {
        st[++top] = x % 10 + '0';
        x /= 10;
    }
    while (top)
        putchar(st[top--]);
}
} // namespace IOI
using namespace IOI;
int n, m;
int f[Maxn];
int ch[Maxn * 40][2];
int s[Maxn * 40], cnt = 1;
inline void ins(int x)
{
    int w = 1;
    s[w]++;
    for (int i = 30; i >= 0; i--)
    {
        if (!ch[w][x >> i & 1])
            ch[w][x >> i & 1] = ++cnt;
        w = ch[w][x >> i & 1], s[w]++;
    }
    return;
}
inline int dfs(int x, int y, int k)
{
    if (!x or !y)
        return f[s[x | y]];
    if (x == y)
    {
        if (k < 0)
            return f[s[x]];
        if (m >> k & 1)
            return dfs(ls(x), rs(x), k - 1);
        else
            return (dfs(ls(x), ls(x), k - 1) + dfs(rs(y), rs(y), k - 1) - 1 + p) % p;
    }
    else
    {
        if (k < 0)
            return f[s[x] + s[y]];
        if (m >> k & 1)
            return dfs(ls(x), rs(y), k - 1) * dfs(rs(x), ls(y), k - 1) % p;
        else
        {
            int res = (dfs(ls(x), ls(y), k - 1) + dfs(rs(x), rs(y), k - 1) - 1 + p) % p;
            res = (res + (f[s[ls(x)]] - 1 + p) % p * (f[s[rs(x)]] - 1 + p) % p) % p;
            res = (res + (f[s[ls(y)]] - 1 + p) % p * (f[s[rs(y)]] - 1 + p) % p) % p;
            return res;
        }
    }
}
inline void work()
{
    n = read(), m = read();
    for (int i = 1, x; i <= n; i++)
        x = read(), ins(x);
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        f[i] = f[i - 1] * 2 % p;
    write((dfs(1, 1, 30) - 1 + p) % p);
    return dwd;
}
 
signed main()
{
    work();
    return 0;
}

9.7

题面较长所以略去题意简述

懒得找自己代码所以直接放std（

A

简单题，考虑一手枚举是哪只船挡了路，然后计算一下答案即可。

std :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 +5;
struct edge{
    double v,s,len;
}es[maxn];
int main()
{
    freopen("cruise.in","r",stdin);
    freopen("cruise.out","w",stdout);
    int n,test;
    scanf("%d",&test);
    while(test--)
    {
        int m = 1;
        scanf("%d", &n);
        for(int i = 1;i <= n + 1;i++) scanf("%lf",&es[i].len);
        for(int i = 1;i <= n + 1;i++) scanf("%lf",&es[i].s);
        for(int i = 1;i <= n + 1;i++) scanf("%lf",&es[i].v);
        double ans = 0;
        double lazy = 0;
        for(int i = 1;i <= n + 1;i++)
        {
            if(i != 1) lazy += es[i].len;
            double t = (es[i].s + lazy) / es[i].v;
            ans = max(t,ans);
        }
        printf("%.10f\n",ans);
    }
    return 0;
}

B

欧拉回路相关问题 %%% wx 当场爆切。

每个连通块内奇点两两连边，随便把连通块连起来，然后对整张图随便找个欧拉回路然后把加的虚边去掉剩下的就是路径

std : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
const int maxn =1e5+5;
struct Edge{
    int to,id,next;
    bool f;
}edges[maxn<<4];
int tot,head[maxn],cnt;
bool vis[maxn];
vector<int> res[maxn];
int deg[maxn];

void init()
{
    tot=0;
    cnt=0;
    memset(deg,0,sizeof(deg));
    memset(vis,0,sizeof(vis));
    memset(head,-1,sizeof(head));
}

void AddEdge(int u,int v ,int id)
{
    edges[tot].f = 0;edges[tot].to=v;edges[tot].id = id;edges[tot].next =head[u];
    head[u]=tot++;
}

void dfs(int u)
{
    vis[u]=true;
    //cout<<u<<" in "<<cnt<<endl;
    for(int i=head[u];~i;i=edges[i].next){
        int v =edges[i].to,id =edges[i].id;
        if(!edges[i].f){
            edges[i].f = edges[i^1].f = true;       //将边和反向边标记
            dfs(v);
            if(id) res[cnt].push_back(-id);     //退栈记录边的id
            else cnt++;                         //扫到虚边，那么路径加1
            //cout<<u<<" out "<<cnt<<endl;
        }
    }
}

void Print()
{
    printf("%d\n",cnt-1);
        for(int i=1;i<=cnt;++i){
            printf("%d",res[i].size());
            int k = res[i].size();
            for(int j=0;j<k;++j) printf(" %d",res[i][j]);
            printf("\n");
            res[i].clear();  
    }
}

int main()
{
    freopen("travelling.in","r",stdin);
    freopen("travelling.out","w",stdout);
    int T,N,M,u,v,tmp;
    scanf("%d", &T);
    
    while(T--){
        scanf("%d%d",&N,&M);
        init();
        for(int i=1;i<=M;++i){
            scanf("%d%d",&u,&v);
            deg[u]++,deg[v]++;
            AddEdge(u,v,i);
            AddEdge(v,u,-i);
        }
        u=0;
        for(int i=1;i<=N;++i){
            if(deg[i]&1){
                if(u){ 
                    AddEdge(u,i,0);
                    AddEdge(i,u,0);
                    u=0;  
                }          //将奇度数点两两连边
                else u=i;
            }
        }
        for(int i=1;i<=N;++i){
            if(!vis[i] && (deg[i]&1)){   
                cnt++;  
                dfs(i);
                cnt--;
            }
        }
        for(int i=1;i<=N;++i){
            if(!vis[i] && deg[i]){
                cnt++;
                dfs(i);
            }
        }
        Print();
    }
    return 0;
}

C

贪心+分治 罢大概是

状压DP有部分分。

考虑每次处理一个矩形，发现先中间后两边的解法一定能达到最优解，所以每次枚举最后处理哪条边，剩下的递归继续求，搞一个记忆化就能过，挺简单的。

std ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int oo = 1000000000;

char a[10][10];
int f[10][10][10][10];

int calc(int x1, int y1, int x2, int y2, int i1, int j1, int i2, int j2)
{
	int res = 0;
	for (int i = i1; i <= i2; ++ i) 
		for (int j = j1; j <= j2; ++ j) 
			if (a[i][j] == '#') 
				res += max(max(abs(i-x1), abs(i-x2)), max(abs(j-y1), abs(j-y2)));
	return res;
}

int dp(int x1, int y1, int x2, int y2)
{
	if (x1 > x2 || y1 > y2) return 0;
	int &res = f[x1][y1][x2][y2];
	if (res > -1) return res;
	
	res = calc(x1, y1, x2, y2, x1, y1, x1, y2) + dp(x1+1, y1, x2, y2);
	res = min(res, calc(x1, y1, x2, y2, x2, y1, x2, y2) + dp(x1, y1, x2-1, y2));
	res = min(res, calc(x1, y1, x2, y2, x1, y1, x2, y1) + dp(x1, y1+1, x2, y2));
	res = min(res, calc(x1, y1, x2, y2, x1, y2, x2, y2) + dp(x1, y1, x2, y2-1));
	
	return res;
}

int main()
{
	freopen("station.in", "r", stdin);
	freopen("station.out", "w", stdout);
	
	for (int i = 1; i <= 8; ++ i) 
		scanf("%s", a[i] + 1);
		
	memset(f, -1, sizeof(f));
	printf("%d\n", dp(1, 1, 8, 8));
	
	return 0;
}

9.8

A

给定一个大小为 $n$ 的树，保证 $n$ 为偶数且小于 $5000$。

您需要给树上的点两两配对，对于一组对子 $(u,v)$ ，在树上将 $u\to v$ 的路径染色，定义一个配对方案合法当且仅当所有边都有颜色。

求方案数对 $10^9+7$ 取模。

树形DP，用容斥合并贡献。

code : 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 5010
const int p = 1e9+7;
typedef long long ll;
 
int n;
ll ans;
int g[N];
vector<int>G[N];
int f[N][N],tmp[N],siz[N];
 
void dfs(int ,int );
 
void main()
{
    ios :: sync_with_stdio(false);
    cin >> n;
    // for(int j = 1;j<=__cplusplus;j++)
    //     int *i = (int*) malloc(__cplusplus);
    g[0] = 1;
    for(int i = 2;i<=n;i+=2) g[i] = 1ll * g[i - 2] * (i-1) % p;
    int u,v;
    for(int i = 1;i<n;i++)
    {
        cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1,0);
    cout << (p - f[1][0]) % p;
    return ;
}
 
void dfs(int u,int fa)
{
    f[u][1] = 1;siz[u] = 1;
    for(auto v : G[u])
    {
        if(v == fa) continue;
        dfs(v,u);
        for(int i = 1;i<=siz[u] + siz[v];i++) tmp[i] = 0;
        for(int i = 1;i<=siz[u];i++)
        for(int j = 0;j<=siz[v];j++)
        (tmp[i+j] += 1ll * f[u][i] * f[v][j] % p) %= p;
        for(int i = 1;i<=siz[u] + siz[v];i++) f[u][i] = tmp[i];
        siz[u] += siz[v];
    }
    for(int i = 2;i<=siz[u];i+=2)
    {
        (f[u][0] += p - 1ll * f[u][i] * g[i] % p ) %= p;
    }
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

B

给你一个字符串 $S$ ，只包含小写字母，每次你可以交换两个相邻的字母，询问最少多少次可以将 $S$ 变成回文串。

简单串串题。奇数个数小于2判无解，从前往后扫一遍，每次找到最后的相同字符，标号为倒数的对应位置，单个字符（最后一个和当前相同） 放中间。最后对得到的标号序列求逆序对就是答案，大概这也就是这道题叫 “Papple Sort” 的原因吧 —— 逆序对数即为冒泡排序的交换次数，其实对于最终序列每次交换相邻两项进行排序也就是进行冒泡排序。

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
namespace Pozhu
{
    using namespace std;
#define N 200010
#define lowbit(x) (x & -x)
    typedef long long ll;
    char s[N];
    int db[N];
    int f[N];
    ll ans;
    int len;
    int tott;
    int tot[27];
    bool vis[N];
    vector<int> pos[27];
 
    void add(int);
    int query(int);
 
    void main()
    {
        scanf("%s", s + 1);
        len = strlen(s + 1);
        for (int i = 1; i <= len; i++)
            tot[s[i] - 'a']++, pos[s[i] - 'a'].push_back(i);
        int tmp = 0;
        for (int i = 0; i < 26; i++)
            if (tot[i] & 1)
                tmp++;
        if (tmp > 1)
        {
            puts("-1");
            return;
        }
        int top = len >> 1;
        for (int i = 1; i <= len; i++)
        {
            if (vis[i])
                continue;
            int tmp = s[i] - 'a';
            int p = *(pos[tmp].end() - 1);
            pos[tmp].erase(pos[tmp].end() - 1);
            vis[i] = vis[p] = true;
            if (p == i)
            {
                db[i] = top + 1;
                continue;
            }
            db[i] = ++tott;
            db[p] = len - tott + 1;
        }
        for (int i = 1; i <= len; i++)
        {
            add(db[i]);
            ans += i - query(db[i]);
        }
        printf("%lld", ans);
        return;
    }
 
    int query(int x)
    {
        int ans = 0;
        for (; x; x -= lowbit(x))
            ans += f[x];
        return ans;
    }
 
    void add(int x)
    {
        if (!x)
            return;
        for (; x <= len; x += lowbit(x))
            f[x]++;
        return;
    }
 
}
 
signed main()
{
    Pozhu ::main();
    return 0;
}

C

我们按以下方式定义一个字符串是否合法：
1、空串是合法的。

2、如果 $S$ 是合法的，那么 $aSa,bSb,cSc$ 是合法的。

3、如果 $S$ 和 $T$ 是合法的，那么 $ST$ 是合法的。

4、不能被以上方式定义为合法的字符串都是不合法的。

给定一个只包含 $a,b,c$ 的字符串 $S$ ，求有多少种方案交换两个不同字符后使得交换之后 $S$ 合法。

观察题面可知一个字符串合法当且仅当它可以被拆成若干个长度为偶数的回文串的首尾相接。

但是考虑原题中的交换操作，发现这个信息不好维护

结论是使用栈和hash来维护。

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
 
#include <bits/stdc++.h>
namespace Pozhu
{
    using namespace std;
#define N 100010
    typedef long long ll;
    typedef unsigned long long ull;
    const ull m = 31;
    char s[N];
    int a[N];
    ull wx[N];
    int n;
 
    struct hash_stack
    {
        vector<int> v;
        vector<ull> has, invhas;
        hash_stack() : has({0}), invhas({0}) {}
        void clear() { v.clear(), has.resize(1), invhas.resize(1); }
        int getsize() { return v.size(); }
        void push(int val)
        {
            if (v.empty() || v.back() != val)
            {
                ull ls = has.back(), rs = invhas.back();
                has.emplace_back(ls * m + val);
                invhas.emplace_back(rs + val * wx[getsize()]);
                v.emplace_back(val);
            }
            else
                v.pop_back(), has.pop_back(), invhas.pop_back();
        }
        ull suf(int l)
        {
            return has.back() - wx[l] * *(has.end() - l - 1);
        }
    } pre, suf, pre2, suf2;
 
    int divide(int, int, int, int);
 
    void main()
    {
        scanf("%s", s + 1);
        n = strlen(s + 1);
        wx[0] = 1;
        for (int i = 1; i <= n; i++)
            wx[i] = wx[i - 1] * m, a[i] = s[i] - 'a';
        ll ans = 0;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (i != j)
                    ans += divide(1, n, i, j);
        printf("%lld", ans);
        return;
    }
 
    int divide(int l, int r, int f, int t)
    {
        if (l == r)
            return 0;
        map<ull, int> c;
        int mid = (l + r) >> 1;
        ll res = 0;
        suf2.clear();
        for (int i = mid; i >= l; i--)
            suf2.push(a[i]);
        for (int i = l; i <= mid; i++)
        {
            suf2.push(a[i]);
            if (a[i] == f)
            {
                pre.push(t);
                int l2 = 0, r2 = min(pre.getsize(), suf2.getsize());
                while (l2 < r2)
                {
                    int mid2 = (l2 + r2 + 1) >> 1;
                    if (pre.suf(mid2) == suf2.suf(mid2))
                        l2 = mid2;
                    else
                        r2 = mid2 - 1;
                }
                c[pre.has[pre.getsize() - l2] * wx[suf2.getsize() - l2] + suf2.invhas[suf2.getsize() - l2]]++;
                pre.push(t);
            }
            pre.push(a[i]);
        }
        res += divide(mid + 1, r, f, t);
        for (int i = mid; i >= l; i--)
            pre.push(a[i]);
        pre2.clear();
        for (int i = mid + 1; i <= r; i++)
            pre2.push(a[i]);
        for (int i = r; i > mid; i--)
        {
            pre2.push(a[i]);
            if (a[i] == t)
            {
                suf.push(f);
                int l2 = 0, r2 = min(pre2.getsize(), suf.getsize());
                while (l2 < r2)
                {
                    int mid2 = (l2 + r2 + 1) >> 1;
                    if (pre2.suf(mid2) == suf.suf(mid2))
                        l2 = mid2;
                    else
                        r2 = mid2 - 1;
                }
                res += c[suf.has[suf.getsize() - l2] * wx[pre2.getsize() - l2] + pre2.invhas[pre2.getsize() - l2]];
                suf.push(f);
            }
            suf.push(a[i]);
        }
        res += divide(l, mid, f, t);
        for (int i = mid + 1; i <= r; i++)
            suf.push(a[i]);
        return res;
    }
 
}
 
signed main()
{
    Pozhu ::main();
    return 0;
}

9.9

A

给出 $n$ 和一个长度为 $n$ 的数列 $a_{1 \dots n}$ 。
有 $q$ 次询问，每次询问给出 $l_i,r_i$ ，表示询问 $a_{l_i \dots r_i}$ 中所有数的最小公倍数模 $10^9+7$ 的结果。

一些数 $b_1,\dots,b_m$ 的最小公倍数定义为一个最小的正整数 $M$ ，使得 $\forall 1 \le i \le m$，有 $b_i \mid M$ ，也就是 $M$ 为最小的被所有 $b$ 都整除的正整数。

强制在线。

区间查询最小公倍数，观察数据范围为 $1e5$ 显然暴力没有出路

考虑用数据结构维护，但是需要转化以下问题才好维护 ：

回想最小公倍数的本质，我们发现最小公倍数是对两个（或多个）数唯一分解后对每个素数的指数取 $\max$ ，考虑维护这个 $\max$ ，考虑对 $a$ 分解质因数后最多有一个大于 $\sqrt{a}$ 的素因子，而小于等于 $\sqrt{2\times10^5}$ 的素数只有 $86$ 个。于是这一部分我们考虑维护 $86$ 个$RMQ$ 直接查询答案，再具体的话就是开 $86$ 棵线段树，因为ST表的空间消耗过大。

然后问题转化成求区间内不同的大于$\sqrt{a}$ 的素因子的乘积。

和区间颜色数类似，可以预处理出一个 $pre_i$ 表示 $a_i$ 含有的大质数在序列上上一次出现的位置，然后询问就变成了区间中 $pre_i$ 小于等于询问左端点的所有 $a_i$ 中大质数的乘积。

可以利用可持久化线段树维护这一信息 ： 每个位置 $i$ 用一棵线段树维护 $1…i$ 内，$pre_i$ 在一段区间内的大质数乘积。这样时间复杂度为 $O(n \log n+q \log n)$。

我们将两部分的答案进行一个相乘就可以得到最终答案了。

总时间复杂度为 $O(nk+n\log n+qk\log n +q\log 2n)$等，取决于实现方式。

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
namespace Pozhu
{
    using namespace std;
#define N 100010
#define M 200000
#define K 200010
    const int mod = 1e9 + 7;
 
    int n, m;
    int rt[N], sum[N * 400], tot;
    int inv[K], f[K], s[K], x;
    int ans, l, r;
    int ls[N * 400], rs[N * 400];
 
    int query(int, int, int, int);
    int merge(int, int, int, int, int);
 
    void main()
    {
        ios ::sync_with_stdio(false);
        cin.tie(0), cout.tie(0);
 
        cin >> n >> m;
        inv[1] = 1, sum[0] = 1;
        for (int i = 2; i <= M; i++)
        {
            inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
            if (!f[i])
                for (int k = i; k <= M; k += i)
                    f[k] = i;
        }
        for (int i = 1; i <= n; i++)
        {
            cin >> x;
            rt[i] = rt[i - 1];
            while (f[x])
            {
                int k = f[x], t = 1;
                while (x % k == 0)
                {
                    t = t * k;
                    x = x / k;
                    if (s[t])
                        rt[i] = merge(rt[i], 1, n, s[t], inv[k]);
                    s[t] = i;
                }
                rt[i] = merge(rt[i], 1, n, i, t);
            }
        }
        for (int i = 1; i <= m; i++)
        {
            cin >> l >> r;
            l = (l + ans) % n + 1;
            r = (r + ans) % n + 1;
            if (l > r)
                swap(l, r);
            ans = query(rt[r], 1, n, l);
            cout << ans << '\n';
        }
        return;
    }
 
    int merge(int pre, int l, int r, int x, int num)
    {
        if (l > x || r < x)
            return pre;
        int rt = ++tot;
        if (l == r)
        {
            sum[rt] = 1ll * sum[pre] * num % mod;
            return rt;
        }
        int mid = (l + r) >> 1;
        ls[rt] = merge(ls[pre], l, mid, x, num), rs[rt] = merge(rs[pre], mid + 1, r, x, num);
        sum[rt] = 1ll * sum[ls[rt]] * sum[rs[rt]] % mod;
        return rt;
    }
 
    int query(int rt, int l, int r, int x)
    {
        if (l >= x)
            return sum[rt];
        if (r < x)
            return 1;
        int mid = (l + r) >> 1;
        return 1ll * query(ls[rt], l, mid, x) * query(rs[rt], mid + 1, r, x) % mod;
    }
 
}
 
signed main()
{
    Pozhu ::main();
    return 0;
}

B

有一个序列，初始时为空。

你会不停地往序列末尾添加一个 $[1,m]$ 中的随机整数。在任意时刻，若序列末尾的两个整数相同（记为 $x$ ）且小于 $t$ ，那么它们会立即合并为 $x+1$。如果序列长度为 $n$ 且无法合并，那么结束操作。

你需要求出结束时序列中所有数的和的期望值。对 $10^9+7$ 取模。

期望难题。

考虑枚举第一格的数，那么我们需要知道 f[i][j] 表示长度限制为 i ，结束时第一格为 j 的概率，g[i][j] 表示此时答案的期望。
求 f 和 g 时需要知道 x[i][j] 表示长度限制为 i，第一格弄出 j 的概率，以及 u[i][j] 表示长度限制为 i，初始时第一格为 j 的期望答案。
具体转移方程可以参考标程。
写出转移方程后不难发现将 g[i][j] 改为长度限制为 i，初始时第一格为 j，结束时第一格还是 j 的概率*期望，就可以不用记 f[i][j]，同时转移方程会简化很多，
复杂度还会少个 $\log$(模数)。
时间复杂度 $O(nm)$

代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
namespace Pozhu
{
    using namespace std;
#define N 2022
    typedef long long ll;
    const int mod = 1e9 + 7;
 
    ll n, m, t;
    ll inv, lim;
    ll f[N][N], g[N][N], p[N][N], q[N][N], ans[N];
 
    ll ksm(ll, ll);
 
    void main()
    {
        ios ::sync_with_stdio(false);
        cin.tie(0), cout.tie(0);
        cin >> n >> m >> t;
        lim = min(n + m - 1, t);
        ll inv = ksm(m, mod - 2);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= lim; j++)
            {
                p[i][j] = ((j <= m) * inv + p[i][j - 1] * p[i - 1][j - 1]) % mod;
                q[i][j] = (1 - (j < lim) * p[i - 1][j] + mod) % mod;
            }
            for (int j = lim; j >= 1; j--)
            {
                g[i][j] = (q[i][j] * j + ans[i - 1] - (j < lim) * p[i - 1][j] * f[i - 1][j] % mod + mod) % mod;
                f[i][j] = (g[i][j] + (j < lim) * (1 - q[i][j] + mod) * f[i][j + 1]) % mod;
                ans[i] = (ans[i] + p[i][j] * g[i][j] % mod) % mod;
            }
        }
        cout << ans[n];
        return;
    }
 
    ll ksm(ll a, ll b)
    {
        ll ans = 1;
        for (; b; b >>= 1, a = a * a % mod)
            if (b & 1)
                ans = ans * a % mod;
        return ans;
    }
 
}
 
signed main()
{
    Pozhu ::main();
    return 0;
}

C

给一颗 $N$ 个结点的以 $1$ 为根的树，每个条边上写了一个字母 $a…v$，一条 Dk 路径是经过的所有字母重新排序可以构成回文串的路径。求每个点的子树中最长的 Dk 路径的长度

这是DSU on Tree 算法的提出者专门为这个算法出的题，属于是这个算法的经典题。所以算法就是这个算法，发现字母数量不是很多就可以状压，合并时就是异或，整条路经的状态就是异或和。

具体如何合并贡献见代码 ： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 500010
 
int n,cnt;
int dfntot;
int t[1 << 22];
int ans[N],head[N];
int to[N],nxt[N],w[N];
int siz[N],hson[N],dfn[N],rk[N],dep[N],val[N];
 
void dfs1(int );
void dfs(int ,bool );
void get_ans(int );
void add(int ,int ,int );
int query(int ,int );
 
void main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i = 2;i<=n;i++)
    {
        int f;char ch;
        cin >> f >> ch;
        add(f,i,ch - 'a');
    }
    dep[1] = 1;
    dfs1(1);
    dfs(1,true);
    get_ans(1);
    for(int i = 1;i<=n;i++)
    cout << ans[i] << ' ';
    return;
}
 
int query(int x,int lca)
{
    int ans = 0;
    int tmp = val[x];
    if(t[tmp])
        ans = max(ans,t[tmp] + dep[x] - 2 * dep[lca]);
    for(int k = 0;k < 22;k++)
    {
        tmp = val[x] ^ (1 << k);
        if(t[tmp])
            ans = max(ans,t[tmp] + dep[x] - 2 * dep[lca]);
    }
    return ans;
}
 
void dfs(int x,bool save)
{
    for(int i = head[x];i;i = nxt[i])
    {
        int v = to[i];
        if(v == hson[x]) continue;
        dfs(v,false);
    }
    if(hson[x])
    {
        dfs(hson[x],true);
    }
    t[val[x]] = max(t[val[x]],dep[x]);
    for(int i = head[x];i;i = nxt[i])
    {
        int v = to[i];
        if(v == hson[x]) continue;
        for(int j = dfn[v];j <= dfn[v] + siz[v] - 1;j++)
        ans[x] = max(ans[x],query(rk[j],x));
        for(int j = dfn[v];j <= dfn[v] + siz[v] - 1;j++)
        t[val[rk[j]]] = max(t[val[rk[j]]],dep[rk[j]]);
    }
    ans[x] = max(ans[x],query(x,x));
    if(!save)
    {
        for(int j = dfn[x];j <= dfn[x] + siz[x] - 1;j++)
        t[val[rk[j]]] = 0;
    }
}
 
void get_ans(int x)
{
    for(int i = head[x];i;i = nxt[i])
    {
        get_ans(to[i]);
        ans[x] = max(ans[x],ans[to[i]]);
    }
    return;
}
 
void dfs1(int u)
{
    siz[u] = 1;
    dfn[u] = ++dfntot;
    rk[dfntot] = u;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        dep[v] = dep[u] + 1;
        val[v] = val[u] ^ (1 << w[i]);
        dfs1(v);
        siz[u] += siz[v];
        if(siz[v] > siz[hson[u]]) hson[u] = v;
    }
    return;
}
 
void add(int u,int v,int _w)
{
    to[++cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
    w[cnt] = _w;
    return;
}
 
}
 
signed main()
{
    Pozhu :: main();
    return 0;
}

by Pozhu
2022.9.10