抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

9月每日总结

发布于：2022年8月31日

总结

数据结构

贪心

dsu on tree

数学，数论

日々私たちが過ごしている日常は、実は、奇跡の連続なのかもしれない。

我们所经历的每个平凡的日常，也许就是连续发生的奇迹。

——《日常》

8.31

T1

现有 nn 个红珠子和 An+BAn+B 个蓝珠子，从左往右放珠子，保证任何时候假如有 xx 个红珠子，蓝珠子数量不超过 Ax+BAx+B 个，问有多少种摆放方法能摆完所有的珠子

组合数学，难点主要在于一个问题的转换，把 🔴 看成横坐标，把 🔵 看成纵坐标，那么就是从 (0,0)(0,0) 走到 (n,An+B)(n, An+B) 且不越过 y=Ax+By = Ax+B 的方案数
令 m=An+Bm = An+B ，总方案数 Cn+mnC_{n+m}^n 枚举能够发生越界的每个位置
即 (p,Ap+B)(p, Ap+B) 走到 (p,Ap+B+1)(p, Ap+B+1)

Cm−Ap−B−1+n−pn−p=A×Cm−Ap−B−1+n−pn−p−1C_{m - Ap -B - 1 + n - p}^{n - p} = A \times C_{m - Ap - B - 1 + n - p}^{n - p - 1}

中间推导过程就是把组合数拆开，提一个 m−Ap−Bn−p\frac{m-Ap-B}{n-p} 出来
那么最终答案 Cn+mn−A×Cn+mn−1C_{n+m}^{n} - A \times C_{n+m}^{n-1}

T2

模拟，没什么好说的，可以用map实现，贪心找最长的关键字还有注意关键字的处理顺序就行

T3

gcd卷积

9.1

给定一些点，从中选取若干个点，使这些点的凸包上的点的个数尽量多

T1

虽然凸包，但是DP

预处理出每个可能成为凸包上的边，枚举端点用 atan2 算一个极角排序就行，然后

f[i][j]f[i][j] 表示最后一个点为 jj 上一个点为 ii 的点数最大值，开一个辅助数组 mxmx 记录走到每个点的点数的最大值，让 f[i][j]f[i][j] 从 mx[i]mx[i] 转移，再转移到 mx[j]mx[j] 就行辣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for(int i = 1; i <= n; i++)
{
	for(int j = 1; j <= n; j++) if(j != i)
	v[++cnt] = vec{i, j, atan2(a[i].y - a[j].y, a[i].x - a[j].x)};    
}
sort(v + 1, v + 1 + cnt, cmp);
for(int i = 1; i <= n; i++)
{
	memset(mx, 0x8f, sizeof(mx));
	mx[i] = 0;
	for(int j = 1; j <= cnt; j++)
	{
		int a = v[j].st, b = v[j].to;
		dp[a][b] = mx[a] + 1;
		mx[b] = max(mx[b], dp[a][b]);
	}
	ans = max(ans, mx[i]);
}

T2

有两个国家 A 国和 B 国。B 国对 A 国发起了侵略。A 国有 nn 个城市，道路网络构成一棵树，道路可以双向通行。通过 ii 条道路需要 lil_i 个单位时间。不妨把 A 国的城市编号为 1∼n1 ∼ n，并把 A 国的首都编号为 11 号。我们定义 “边界城市” 为，以首都为根时，为叶子节点的城市。B 国直接占领了 A 国的所有边界城市。我们记这个时刻为时刻 00。每个被占领的城市每个单位时间可以训练出一个士兵。所有士兵只会朝着首都的方向移动。在每个非边界城市 ii 中有 did_i 个卫兵。当 B 国的一名士兵进入一个城市时，卫兵数量就会且仅会减少 1 。而当一个城市中没有卫兵了之后，这个城市就被 B 国占领了。士兵到达首都并虐了一名首都的卫兵就消失了。请计算出 A 国全部城市都被占领的时刻

对于一个节点 uu ，disudis_u 表示其道根节点的距离，tut_u 表示它的 dd 变成 00 的时间

它在时刻 TT 的 dd 的减少数量是

∑v∈subtree(u)maxT−tu−disv+disu,0 \sum\limits_{v \in subtree(u)} max{T- t_u - dis_v + dis_u, 0}

线段树维护 tv−disyt_v - dis_y 向上合并即可

9.2

T1
模拟，没什么好说的，唯一注意点就是处理输入和参数是否错误，建议 getline() 直接读入一整行，然后处理参数，不符合范围直接 ERROR ，还有就是地图下标从 0 开始，花了半天搞懂样例 😅
T2

虎哥 要去 pp 个菜店买菜，同时地图上还有一些障碍，最小化路程的前提下，刀哥希望能迈更宏大的步子，ii 规模的步伐会占据 (2i+1)×(2i+1)(2i+1) \times (2i+1) 个格子
首先在每个位置的siz可以预处理出来，然后可以对于每一个🌿🏪跑dij来处理路程和路径siz 又注意到菜市场的数量很少，可以状压表示每一个超市去没去过，小DP即可

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
void dij(int x, int y)
{
	priority_queue<qnode> q;
    memset(f[i][j][n][m], 0x3f, sizeof(f[i][j][n][m]));
    f[i][j][n][m][x][y] = node{0, 0};
    q.emplace(qnode{0, 0, x, y});
    while (q.size())
	{
		int dis = q.top().dis;
		int val = q.top().val;
		int x = q.top().x;
		int y = q.top().y;
		q.pop();
		if(f[i][j][n][m][x][y].dis != dis || f[i][j][n][m][x][y].val != val)
			continue;
		for(int i = 0; i < 4; i++)
		{
			int qx = x + dx[i], qy = y + dy[i];
			if(qx < 1 || qx > n || qy < 1 || qy > m || a[qx][qy])
				continue;
			if(f[i][j][n][m][qx][qy].dis > dis + 1 || (f[i][j][n][m][qx][qy].dis == dis + 1 && f[i][j][n][m][qx][qy].val < val + b[qx][qy]))
			{
				f[i][j][n][m][qx][qy].dis = dis + 1;
				f[i][j][n][m][qx][qy].val = val + b[qx][qy];
				q.emplace(qnode{f[i][j][n][m][qx][qy].dis, f[i][j][n][m][qx][qy].val, qx, qy});
			}
		}
	}
}
for(i = 1; i < 1 << p; i++)
for(j = 0; j < p; j++) if((i >> j) & 1) //i得去过
for(k = 0; k < p; k++) if(((i >> k) & 1) && k != j)//k得去过
f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + dis[k][j]);

9.3

有 nn 个数，可以选择有 kk 个数的组合，它的贡献是组合中最大的数，求所有组合贡献之和

T1

考虑每个数产生的贡献，那么就要求选了 kk 个数，而且当前数为最大值，那么当前数一定要选，之后再从小于等
于当前数的数中选剩下的 k−1k-1 个方案数

ansi=Ccnt[ai]k−1×aians_i = C_{cnt[a_i]}^{k-1} \times a_i

但是有数值相同的数时会算重或者少算，有一种巧妙的方法就是直接排序，看代码体会

1
2
3
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++)
ans = ans + C(i-1, k-1) * a[i];

T2

小Q 在独木桥上彷徨了。他知道，他只剩下了 NN 秒的时间，每一秒的时间里，他会向左或向右移动一步。NN 秒之后，小Q 恰好到达出发处，且他每两次经过此位置的时间间隔不会超过 MM 秒。那么问题来了，这 N 秒的时> 间里，小Q 的路线总共会有多少种可能的形式

考试时连题都没看懂 😭

我们把第一次到达某个地点看作左括号，回到这个地点看作右括号，那么合法的移动形成的括号序列长度 ⩽m\leqslant m，而且是偶数 于是我们可以把长度为 2,4,…m2, 4, \dots m 和括号序列有多少种预处理出来

枚举括号长度

f[i]=f[i−len]+a[len]f[i] = f[i-len] + a[len]

发现是一个递推而且的过程 mm 不大，于是考虑矩阵加速

T3

初始一个数 BB，在 nn 秒内每一秒都会增加 AA 求各个时刻数的二进制表示 11 的个数和

不难发现累加 AA 的贡献是有循环节的，也就是说 B+iAB + iA 和 B+2kaB + 2^ka 的 第 kk 位是相同滴。
所以可以计算出前 xx 项的二的整数次幂位上一共有几个 11

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
#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
ll A, B, N, ans;
ll calc(ll x, ll bit) //前x项的第bit位上有几个1
{
	ll ans = 0, f[i][j][n][m] = 0;
    for(ll i = 1; i <= x; i++)
    {
		ll to = B + A*i;
        //bit 是一个2的整次幂,(bit >> 1) 的形式是100...000 与之比较就能确定当前最高位是1还是0 
        if(to % bit < (bit >> 1)) //当前是 0,只能从上一位进位 
        {
			i = min(x, i + ((bit >> 1)-1 - to%bit)/A);
        }
        else //当前位是 1,可以从当前位进位
        {
			f[i][j][n][m]  = min(x, i + (bit-1 - to%bit)/A);
            ans += f[i][j][n][m] - i + 1; i = f[i][j][n][m];
        }
    }
    return ans;
}
int main()
{
	int t;
    scanf("%d", &t);
    while(t--)
    {
		scanf("%lld%lld%lld", &A, &B, &N);
        ll to = B + A*N; ans = 0;
        for(ll i = 2; i < (to << 1); i <<= 1)
        {
			if(N / i) ans += 1LL*(N / i) * calc(i ,i);
            ans += calc(N % i, i);
        }
        printf("%lld\n", ans);
    }

    return 0;
}

9.5

T1 AT4168

给定一个长为 2n2^n 的序列 AA ，编号 0…2n−10 \dots 2^n-1 ，对于每一个 k(0≤k≤2n)k (0 \leq k \leq 2^n) ，求 max(Ai+Aj)(i  or  j⩽k)max(A_i + A_j) (i \; or \; j \leqslant k)

肯定是在满足条件的数里选两个最大的，那么维护一个集合中的最大值和次大值，暴力枚举集合中的数肯定不行，考虑如何快速的求出符合条件的数的集合。对于一个数 kk ，它的每一个 lowbitlowbit 和 它减去它的这个 lowbitlowbit 或起来一定小于等于它所以枚举 lowbitlowbit 然后再不断更新最大值

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
#include <iostream>
#include <cstdio>
#define MAXN 300005
using namespace std;
int n, N;
struct node { int id, mx, cmx; } a[MAXN];
int ans [MAXN];
node Max (node a, node b)
{
	node c;
    if (a.mx > b.mx)
    {
		c.mx = a.mx;
        c.id = a.id;
        c.cmx = max(a.cmx, b.mx);
    }
    else if(b.mx > a.mx) 
    {
		c.mx = b.mx;
        c.id = b.id;
        c.cmx = max(a.mx, b.cmx);
    }
    else
    {
		c.mx = a.mx;
        c.id = a.id;
        if (a.id == b.id)
		c.cmx = max(a.cmx, b.cmx);
        else c.cmx = b.mx;
    }

    return c;   
}
#define lowbit(i) (i & -i)
int main()
{
	scanf("%d", &n); N = 1 << n;
    for (int i = 0; i < N; i++)
    {
		int x; scanf("%d", &x);
        a[i] = node { i, x };
    }
    for (int k = 1; k < N; k++)
    {
		int now = k;
        while(now)
        {
			int i = lowbit(now);
            a[k] = Max(a[k], a[k - i]);
            now -= i;
        }
    }

    for (int i = 1; i < N; i++)
    {
		ans[i] = max(ans[i-1], a[i].mx + a[i].cmx);
        printf("%d\n", ans[i]);
    }

    return 0;
}

T2

给定一个整数数列 aa，定义 f(a)=max1⩽i⩽j⩽n(aj−ai)f(a)=max_{1 \leqslant i \leqslant j \leqslant n}(a_j−a_i)，保证 f(a)>0f(a)>0，你需要求出至少需要修改 aa 的多少个位置才能使 f(a)f(a) 变小

首先按照最小值分成若干段，显然每段之间互不影响。对于每一段，我们只需要考虑最大值和最小值之差。如果两个极值之差等于 f(a)f(a)，那么必须从中间选定一个位置 ii ，将 ii 之前的最小值和之后的最大值删去

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
#include <iostream>
#include <cstdio>
#define MAXN 1000005
#define cjb 1145141919
using namespace std;
int n;
int a[MAXN];
int mx, mi, ans;
int main()
{
	scanf("%d", &n);
    mi = cjb; mx = -cjb;
    for (int i = 1; i <= n; i++)
    {
		scanf("%d", &a[i]);
        mx = max(mx, a[i] - mi);
        mi = min(mi, a[i]);
    }
    int i, j, cnt = 0, len = 0;
    for (i = 1; i <= n; i = j)
    {
		len = cnt = 0;
        for (j = i; j <= n && a[i] <= a[j]; j++)
        {
			if (a[j] == a[i]) cnt++;
            else if (a[j] - a[i] == mx)
            {
				cnt--;
                len = min(len, cnt);
                ans++;
            }
        }
        ans += len;
    }
    printf("%d", ans);

    return 0;
}

9.6

T1

有 nn 个数。你需要找出它们的一个排列，满足 mm 个条件，每个条件形如 xax_a ​必须在 xbx_b 之前​，求满足条件的最大子段和

最小割。

对每一个数拆点

如果 aia_i 为正数，那么 超🐔源点连向入点，出点连向超🐔汇点 流量为 aia_i 的边， 如果这条边被割了，说明这个数被放到了选中的子序列的前边或后边

如果 aia_i 为负数，那么在入点和出点间连一条流量为 ∣ai∣\left\vert a_i \right\vert 的边，如果这条边被割了，说明这个数被加到了子序列里

对于每个限制，就分别把两个点的入点和出点连起来，流量超🐔大，这样限制一定满足，因为不会被割

答案就是 正数和-最小割

T2 CF1616H

给定一个数列，和一个数 xx ，求有多少个数列的子集，满足集合中的数两两异或都不大于 xx

看到异或，考虑建01Trie，先把集合中的数插入Trie中，因为统计个数，记录每个节点被几个集合中的数用到
然后考虑如何满足限制，经典从高位向地位开始插，然后从高位向第位遍历，分情况讨论

  • 如果当前遍历的两个节点是同一个节点：
    • 如果 xx 在这一位上是 11 ，那么同时递归左子树和右子树
    • 如果 xx 在这一位上是 00 ，那么分别递归左子树和右子树
  • 如果当前遍历的两个节点是不同节点：
    • 如果 xx 在这一位上是 11 ，那么递归两个节点的不同子树，两种情况的答案乘起来
    • 如果 xx 在这一位上是 00 ，那么递归相同子树，再统计一下单独在一棵子树里的答案返回

还有就是注意一些小细节，比如空集重复计算减一的问题

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
64
65
66
#include <iostream>
#include <cstdio>
#define mbit 30
#define MAXN 150005
#define mod 998244353
#define ll long long
using namespace std;
int n, m;
ll pow2[MAXN];
namespace Trie
{
	int tot = 1;
    int siz[MAXN * mbit];
    int ch[MAXN * mbit][2];
    #define ls(i) (ch[i][0])
    #define rs(i) (ch[i][1])
    void insert(int x)
    {
		int u = 1;
        siz[u]++;
        for (int i = mbit; i >= 0; i--)
        {
			int bit = (x >> i) & 1;
            if(!ch[u][bit]) ch[u][bit] = ++tot;
            u = ch[u][bit]; siz[u]++;
        }
    }

}using namespace Trie;
ll dfs(int u1, int u2, int d)
{
	int bit = (m >> d) & 1;
    if(!u1 || !u2) return pow2[siz[u1 + u2]];
    if(u1 == u2)
    {
		if (d < 0) return pow2[siz[u1]];
        if (bit) return dfs(ls(u1), rs(u1), d-1) %mod;
        else return (dfs(ls(u1), ls(u1), d-1) + dfs(rs(u1), rs(u1), d-1) -1 + mod)%mod;
    }
    else 
    {
		if (d < 0) return pow2[siz[u1] + siz[u2]];
        if (bit) return (dfs(ls(u1), rs(u2), d-1) * dfs(rs(u1), ls(u2) , d-1)) %mod;
        else
        {
			ll ans = (dfs(ls(u1), ls(u2), d-1) + dfs(rs(u1), rs(u2), d-1) -1 + mod)%mod;
            ans = (ans + (pow2[siz[ls(u1)]]-1 +mod) * (pow2[siz[rs(u1)]] - 1 + mod)%mod)%mod;
            ans = (ans + (pow2[siz[ls(u2)]]-1 +mod) * (pow2[siz[rs(u2)]] - 1 + mod)%mod)%mod;
            return ans;       
        }
    }
}
int main()
{
	scanf("%d%d", &n, &m); pow2[0] = 1;
    for (int i = 1; i <= n; i++)
    {
		int x; scanf("%d", &x);
        insert(x);
        pow2[i] = pow2[i-1] * 2LL %mod;
    }
    printf("%lld", (dfs(1,  1, mbit)-1 +mod) %mod); 


    return 0;
}

9.7

T1

🐯哥从东百来到广州，要看广州塔，刀哥选择坐船去，可惜堵船了，而且🔪哥恰好在离塔最远的船上，每艘船的船头距离塔的距离为 xix_i，船长为 lil_i ，速度为 viv_i ，计算🐯哥来广州塔需要多长时间

一艘船的能够船头能够碰到广州塔，那么它前面的船的船尾已经经过了塔，所以每艘船一共要走的路程实际上是它的船头到塔的距离加上它前面所有船的船长（除了🐯所在的第一艘船），后面的船会挡到前面的船，所以取max

1
2
3
4
for (int i = 2; i <= n; i++)
sum[i] = sum[i-1] + a[i];
for (int i = 1; i <= n; i++)
ans = max(ans, (x[i] + sum[i])/v[i]);

T2

一张无向图 nn 个点， mm 条边，询问能不能把每条路都走一遍且只走一边，如果实在不能的话使用传送，可以传送到任意城市，询问最少传送几次，输出路径

一眼题目应该是欧拉路径，先对每个连通块处理出度数为奇数的点，使用传送把他们两两连边，在选出每个连通块的起点和终点，把连通块之间连边。最后dfs输出路径

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
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
void bfs(int st)
{
	queue <int> q;
    vector <int> p;
    q.push(st); vis[st] = 1;
    while(q.size())
    {
		int u = q.front(); q.pop();
        if(d[u] & 1) p.push_back(u); 
        for (int i = head[u]; i; i = e[i].nxt)
        {
			int v = e[i].to;
            if (!vis[v])
            {
				vis[v] = 1; q.push(v);
            }
        }
    }
    for (int i = 2; i < p.size(); i += 2) //奇度数点两两连边就能相互抵达
    {
		adde(p[i], p[i+1]);
        adde(p[i+1], p[i]);
        tot++;
    }
    //连通块内起点终点
    if(p.size()) s = p[0], t = p[1];
    //没有奇度数点说明这个连通块是欧拉回路，任选一个点就行 
    else s = t = st;
}
void print()
{
	printf("%d ", sta.size());   
    while(sta.size())
    {
		printf("%d ", sta.top());
        sta.pop();
    }
    ENDL;
}
void dfs(int u)
{
	for (int i = head[u]; i; i = e[i].nxt) if (!vis[i])
    {
		vis[i] = vis[i ^ 1] =  1; head[u] = i;
        int v = e[i].to; dfs(v);
        if(i/2 > m) print(); //题目要求，使用传送换个行
        else sta.push(i & 1 ? -i/2 : i/2);//题目要求，正着走正，反着走负
    }
}
void solve()
{
	for (int i = 1; i <= n; i++) if(head[i])
    {
		if(!vis[i])
        {
			tot++;
            bfs(i);
            if(alls)
            {
				adde(alls, s);
                adde(s, alls);
                allt = t;
            }
            else alls = s, allt = t;//处理整张图的起点终点
        }
    }

    printf("%d\n", tot-1);
    memset(vis, 0, sizeof(vis));
    dfs(alls); print();
}
int main()
{
	freopen("travelling.in", "r", stdin);
    freopen("travelling.out", "w", stdout);
    int t; scanf("%d", &t);
    while(t--)
    {
		clannad();

        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
        {
			int x, y; scanf("%d%d", &x, &y);
            adde(x, y); adde(y, x);
            d[x]++; d[y]++;
        }
        solve();        
    }
}

T3

8×88 \times 8 网格图，上面有一些点需要建立基站，每建好一个基站需要和已经建好的基站调试一次，若两个基站的坐标分别为 (x1,y1)(x1,y1) 和 (x2,y2)(x2,y2) 调试的时间是 max(∣x1−x2∣,∣y1−y2∣)max(\left\vert x_1 - x_2 \right\vert,\left\vert y_1 - y_2 \right\vert)，建立这个基站总的调试时间是和这些基站调试时间的最大值，确定一个顺序，使得总共的调试时间最小

如果是一个序列，那么先中间后两边，的调试时间是最小的。网格图也是这样，先中间，后四周。以这个为基础进行DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//计算区域内贡献
int ask(int i, int j, int n, int m, int s1, int t1, int s2, int t2)
{
	int tmp = 0;
	for(int p = s1; p <= s2; p++)
	for(int q = t1; q <= t2; q++)
	{
		if(id[p][q] == 1)
		tmp += max( max(Abs((p-i)), Abs((p-n))), max(Abs((q-j)), Abs((q-m))));
	}
	return tmp;
}
int dp(int i, int j, int n, int m)
{
	if(i > n || j > m) return 0;
	if(f[i][j][n][m] > -1) return f[i][j][n][m]; //记忆化

    //四个方向，扩展一行/列
    f[i][j][n][m] = min(f[i][j][n][m], ask(i, j, n, m, i, j, i, m) + dp(i+1, j, n, m));
	f[i][j][n][m] = min(f[i][j][n][m], ask(i, j, n, m, i, j, n, j) + dp(i, j+1, n, m));
	f[i][j][n][m] = min(f[i][j][n][m], ask(i, j, n, m, n, j, n, m) + dp(i, j, n-1, m));
	f[i][j][n][m] = min(f[i][j][n][m], ask(i, j, n, m, i, m, n ,m) + dp(i, j, n, m-1));
	return f[i][j][n][m];
}

9.8

T1 ARC101C

给定一个大小为 nn 的树，保证 nn 为偶数且小于 50005000。您需要给树上的点两两配对，对于一组对子 (u,v)(u,v) ，在树上将 u→vu \to v 的路径染色，定义一个配对方案合当且仅当所有边都有颜色，求和法染色的方案

先预处理除 ii 个点任意配对的方案数 gig_i ，gi=∏i−2k+1nig_i= \prod\limits_{i - 2k+1}^n i

for (int i = 2; i <= n; i++) g[i] = g[i-2] *(i-1) %mod;

f(s)f(s) 表示边集 SS 内的方案数，全集为 EE ，容斥一下

ans=∑S⊆E(−1)∣S∣f(S)ans = \sum\limits_{S \subseteq E} (-1)^{\vert S \vert} f(S)

然后考虑dp，dp(i,j)dp(i,j) 表示以 ii 为根的子树内，ii 所在的连通块大小为 jj 的答案，枚举子树乘法原理转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(int u, int fa)
{
	siz[u] = 1; dp[u][1] = 1;
    for (int v : e[u])
    {
		if (v == fa) continue;
        dfs(v, u);
        for (int i = 1; i <= siz[u] + siz[v]; i++) f[i] = 0;
        for (int i = 1; i <= siz[u]; i++)
        for (int j = 1; j <= siz[v]; j++)
        {
			f[i] = (f[i] - dp[u][i]*dp[v][j]%mod * g[j]%mod + mod) %mod;
            f[i+j] = (f[i+j] + dp[u][i] * dp[v][j]%mod)%mod;
        }
        siz[u] += siz[v];
        for (int i = 1; i <= siz[u]; i++)
            dp[u][i] = f[i];
    }
}

T2 ARC088C

给定一个字符串，每次可以交换任意相邻的两个字符，询问最少交换几次可以变成一个回文串，无解输出 -1

如果长度为奇数，那么有一个字符出现次数是奇数，如果长度为偶数，那么没有字符出现次数为奇数，否则无解
依次扫描字符串，寻找最靠后的相同字符与它匹配，按这个策略处理出每个字符在回文串中的位置，求逆序对即可
可以预处理除每个字符所有的出现位置

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
for (int i = 1; i <= n; i++)
{
	q[s[i] - 'a'].push_back(i);
    cnt[s[i]- 'a']++;    
}
for (int i = 0; i < 26; i++) if(cnt[i] & 1)
ji++;
if(n % 2 == 0)
{
	if(ji) printf("-1"); return 0;
}
else if(ji > 1) printf("-1"); return 0;
//我这里使用了双端队列维护
for (int i = 1; i <= n; i++) if(!pos[i])
{
	int x = q[s[i] - 'a'].front();
    int y = q[s[i] - 'a'].back();
    if(x == y)
		pos[x] = (n+1)/2;
    else
    {
		q[s[i] - 'a'].pop_back();
        q[s[i] - 'a'].pop_front();
        pos[x] = ++tot;
        pos[y] = n-tot+1;
    }
}
//树状数组求逆序对
for (int i = 1; i <= n; i++)
{
	add(pos[i], 1);
    ans += i - query(pos[i]);
}
printf("%lld", ans);

9.9

T1 CF1422F

给定一个序列，求区间 lcmlcm 。n⩽100000n \leqslant 100000 ，ai⩽2000000a_i \leqslant 2000000

先莽一个线段树上去发现不对，然后考虑对每一个数唯一分解，实际上把问题转化为了素数个数的最大值问题，

人类智慧根号分治

小于等于 a\sqrt{a} 的 质数只有 8686 个，ST表处理

大于 a\sqrt{a} 的问题转化为区间出现过的数的乘积，而且可以发现 aa 只含有一个这样的质因数，维护 preipre_i 表示 ii 上一次出现的位置，用一个单点修改，区间求乘积的主席数维护

T2 CF741D

一个 11 为根节点的数，每条边上有一个字符 a va~v 22种，询问所有子树中最长的简单路径使得路径上的字母重排后可以变成回文串

看到对于子树的询问，考虑 dsu on tree 。一个字符串能重排成回文串，那么出现奇数次的字符最多有一个。思考只有22个字符的深意，我们可以状压每一种字符出现的次数为奇数还是偶数，细节看代码

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
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
//cnt[i] 表示子树内字符状态为 i 的最大深度
void dfs(int u, int fa)
{
	siz[u] = 1; dep[u] = dep[fa] + 1;
    for (int i = head[u]; i; i = e[i].nxt)
    {
		int v = e[i].to; 
        //预处理除每个节点到根节点的字符状态
        num[v] = num[u] ^ (1 << e[i].dis);
        dfs(v, u);
        siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}
int now;
void add1(int u)
{
	// 看看有没有出现状态和当前一样节点的，可以合并成一个偶回文串
    ans[now] = max(ans[now], dep[u] + cnt[num[u]]);
    // 枚举状态，合并奇回问串
    for (int i = 0; i < 22; i++)
    ans[now] = max(ans[now], dep[u] + cnt[(1 << i) ^ num[u]]);
}
// 不能自己和自己合并，所以不能写在一个函数里
void add2(int u)
{
	// 用当前节点更新当前状态
    cnt[num[u]] = max(cnt[num[u]], dep[u]);
}
// 加子树贡献
void adds1(int u)
{
	add1(u);
    for (int i = head[u]; i; i = e[i].nxt)
		adds1(e[i].to);
}
void adds2(int u)
{
	add2(u);
    for (int i = head[u]; i; i = e[i].nxt)
		adds2(e[i].to);
}
// 淸子树贡献
void clannad(int u)
{
	cnt[num[u]] = -cjb;
    for (int i = head[u]; i; i = e[i].nxt)
    {
		int v = e[i].to;
        clannad(v);
    }
}
void dsu(int u)
{
	for (int i = head[u]; i; i = e[i].nxt)
    {
		int v = e[i].to; if(v != son[u])
        {
			dsu(v); clannad(v);
        }
    }
    if(son[u]) dsu(son[u]); now = u;

    for (int i = head[u]; i; i = e[i].nxt)
    {
		int v = e[i].to; if(v != son[u])
        {
			adds1(v);
            adds2(v);
        }
    }
    add1(u), add2(u);
    // 这里的ans是限定必须经过u的路径，类似与点分治 
    ans[u] -= dep[u] * 2; //减lca也就是u的深度
    // 因为有必须经过u的限制，所以要和它的子树取max
    for (int i = head[u]; i; i = e[i].nxt)
    ans[u] = max(ans[u], ans[e[i].to]);
}
int main()
{
	scanf("%d", &n);
    for (int i = 0; i < (1 << 22); i++)
    cnt[i] = -cjb;

    for (int i = 2; i <= n; i++)
    {
		int x; char c;
        cin >> x >> c;
        adde(x, i, c - 'a');
    }
    dfs(1, 0); dsu(1);

    for (int i = 1; i <= n; i++)
    cout << max(ans[i], 0) << ' ';

    return 0;
}

9.11

T1 ARC117E

给定 nn 和 kk ，求有多少长度为 2n2n 的列 A(a1,a2,a3⋯a2n)A(a_1,a_2,a_3 \cdots a_{2n}) 满足序列中恰好分别有 nn 个 11 和 nn 个 −1-1 并且有且仅有 kk 对 (l,r)(l, r) 满足 (1⩽l⩽r)(1 \leqslant l \leqslant r) 且 (∑i=lrai)=0(\sum\limits_{i = l}^r a_i) = 0

因为序列中之有 00 和 11 ，所以序列中的前缀和应该是这样的


图片来自官方题解

DP，设状态为 f[i][j][k] 表示当前构造了长度为 ii 的序列，有 jj 个和为 00 的区间，中间有 kk 个没填上的数

于是有转移式 f[i+len][j+Clen2][x−(k+1)]+=f[i][j][k]f[i+len][j+C_{len}^2][x - (k + 1)] += f[i][j][k]

T2 ARC117F

有一个长度为 2n2n 的环 A(a1,a2,⋯a2n)A(a_1, a_2, \cdots a_{2n})，对应的每个位置上有一个限制 bib_i ，表示 bi⩽∑ii+n−1aib_i \leqslant \sum\limits_{i}^{i+n-1} a_i ，请你在满足所有限制的情况下，构造一种方案，使得 ∑ai\sum a_i 最小

记前缀和 SiS_i ，可以发现 S2nS_{2n} 对于这些限制是有单调性的

对于编号小于 nn 的位置，它的限制转化为 bi⩽Si+n−1−Si−1b_i \leqslant S_{i+n-1} - S_{i-1}

对于编号大于 nn 的位置，它的要求可以转化为 S2n−bi⩾Si−1−Si−nS_{2n} - b_i \geqslant S_{i-1} - S_{i-n}

那么对每一个 aia_i 都有 bi⩽Si+n−1−Si−1⩽S2n−bi+nb_i \leqslant S_{i+n-1} - S_{i-1} \leqslant S_{2n} - b_{i+n}

我们可以二分 S2nS_{2n}

T3 CF19D

维护一个二维点集，支持添加一个点，删除一个点，查询点后后继 (x′>x,y′>y)(x' > x, y' > y)

鉴定为数据结构，使用权值线段树维护 xx 值， 套 setset 维护 yy 值

首先 xx 是挺大的，先进行一个离线和离散化，然后就干嘛干嘛就行辣

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
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
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <set>
#define MAXN 200005
#define pir pair <int, int>
#define mkp make_pair
using namespace std;
int h[MAXN], maxx;
struct OPOPOP
{
	int id;
    int x, y;
}q[MAXN];
multiset <int> s[MAXN];
namespace Leitree
{
	struct tree
	{
		int l, r;
        int max;
    }t[MAXN << 2];
    #define ls(i) (i << 1)
    #define rs(i) (i << 1 | 1)

    void push_up(int i)
    {
		t[i].max = max(t[ls(i)].max, t[rs(i)].max);
    }

    void build(int i, int l, int r)
    {
		t[i].l = l; t[i].r = r;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(ls(i), l, mid);
        build(rs(i), mid+1, r);
    }

    void change(int i, int pos, int val, int op)
    {
        if (t[i].l == pos && t[i].r == pos)
        {
	        if (op == 1)
            {
	            s[pos].insert(val);            
                t[i].max = max(t[i].max, val);    
            }
            else 
            {
	            s[pos].erase(val);
                if (s[pos].empty()) t[i].max = 0;
                else t[i].max = *s[pos].begin();
            }
            return;
        }
        int mid = (t[i].l + t[i].r) >> 1;
        if (pos <= mid) change(ls(i), pos, val, op);
        else change(rs(i), pos, val, op);
        push_up(i);
    }

    pir query(int i, int l, int r, int val)
    {
        if (t[i].max <= val) return mkp(-1, -1);
        if (t[i].l == t[i].r)
        {
	            int x = t[i].l;
            return mkp(h[x], *s[x].upper_bound(val));
        }
        int mid = (t[i].l + t[i].r) >> 1;
        pir ans;
        if (t[ls(i)].r >= l)
        {
	            ans = query(ls(i), l, r, val);
            if (ans.first != -1) return ans;
        }
        if (t[rs(i)].l <= r)
        {
	            ans = query(rs(i), l, r, val);
            if (ans.first != -1) return ans;
        }
        return mkp(-1, -1);
    }
}using namespace Leitree;
int main()
{
	int n; scanf("%d", &n);
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
		char op[10]; int x, y;
        scanf("%s%d%d", op+1, &x, &y);
        if (op[1] == 'a') q[i].id = 1;
        if (op[1] == 'r') q[i].id = 2;
        if (op[1] == 'f') q[i].id = 3;
        q[i].x = x; q[i].y = y;
    	h[++cnt] = x; h[++cnt] = x + 1;
    	//这里加入 x+1 是因为查询的时候是查x+1
        //防止离散化出锅，xdm可以试一试
    }

    sort(h + 1, h + 1 + cnt);
    maxx = unique(h + 1, h + 1 + cnt) - h-1;    
    build(1, 1, maxx);

    for (int i = 1; i <= n; i++)
    {
		int x = lower_bound(h + 1, h + 1 + maxx, q[i].x) - h;
        if (q[i].id == 3)
        {
			pir ans = query(1, x+1, maxx, q[i].y);
            if (ans.first != -1)
                printf("%d %d\n", ans.first, ans.second);
            else
                printf("-1\n");
        }
        else 
		change(1, x, q[i].y, q[i].id);

    }

    return 0;
}

9.12

T3 CF1503E

n×mn \times m 的棋盘，每个格子可以染成黄色或者蓝色，定义合格的染色方案是每行有且只有一段蓝色的格子，每列有且只有一段黄色的格子，求一共有多少种合格的染色方案

通过这个定义我们发现，差不多和格的染色方案都是长这样的

也就是说，存在一条分界线，使得所有黄色的连通块互相不越过这条分界线 ，而且都到达了分界线

所以枚举分界线和黄色连通块上 🍌 的两个离得近的点，计算黄色连通块可能的方案数，具体而言就是说计算边界四个点到这两个点的方案数 ，整点组合数算路径

还有一种情况，无非是把棋盘翻转， n,mn,m 交换一下

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
#include <iostream>
#include <cstdio>
#define ll long long
#define mod 998244353
#define RTX 4080
using namespace std;
ll n, m, ans;
ll jc[RTX], ijc[RTX];
ll ksm (ll a, ll b)
{
	ll ans = 1;
    while (b)
    {
	    if (b & 1) ans = ans * a %mod;
        a = a * a %mod; b >>= 1;
    }
    return ans;
}
void get_jc(int RTXON = 4060)
{
	jc[0] = jc[1] = 1; ijc[0] = 1;
    for (int i = 2; i <= RTXON; i++) jc[i] = 1LL*i * jc[i-1] %mod;
    ijc[RTXON] = ksm(jc[RTXON], mod-2);
    for (int i = RTXON-1; i; i--) ijc[i] = ijc[i+1] * 1LL*(i+1) %mod;
}
ll Ways(ll n, ll m)
{
	return jc[n + m] * ijc[n] %mod * ijc[m] %mod;
}
int main()
{
	scanf("%lld%lld", &n, &m); get_jc();
    for (int i = 1; i <= m-1; i++)
    {
	    ll sum = 0;
        for (int j = 1; j <= n-1; j++)
        {
	        sum = (sum + Ways(i, j-1) * Ways(i-1, n-j)%mod)%mod;
            ans = (ans + sum * Ways(m-i-1, j)%mod * Ways(m-i, n-j-1)%mod)%mod;
        }
    }
    swap(n, m);  
    for (int i = 1; i <= m-1; i++)
    {
	    ll sum = 0;
        for (int j = 1; j <= n-1; j++)
        {
	        ans = (ans + sum * Ways(m-i-1, j)%mod * Ways(m-i, n-j-1)%mod)%mod;
            sum = (sum + Ways(i, j-1) * Ways(i-1, n-j)%mod)%mod;
        }
    }

    printf("%lld", ans*2%mod);

    return 0;
}

9.13

T1

给出两颗 nn 点的有根树，TAT_A 和 TBT_B，他们的根都是 11 mm 次询问，每次询问两个点 uu， vv ，求一个编号最大的点 cc ，使得 cc 在 TAT_A 上是 uu 的祖先，在 TBT_B 上是 vv 的祖先

对于 AA 树上的每一个点建立主席树，维护这个点在 BB 树上的的祖先信息，具体而言就是说插入这个点在 BB 树上DFS序，然后对它的子树，进行最大值覆盖

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
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
#include <iostream>
#include <cstdio>
#include <vector>
#define MAXN 100005
using namespace std;
int n, m;
vector <int> e1[MAXN];
vector <int> e2[MAXN];
namespace Leitree
{
	int rt[MAXN << 5];
    int tot;
    struct tree
    {
	    int ls, rs;
        int max;
    }t[MAXN << 5];

    #define ls(i) (t[i].ls)
    #define rs(i) (t[i].rs)

    int newnode()
    {
	    ++tot;
        return tot;
    }

    void push_up(int i)
    {
	    t[i].max = max(t[ls(i)].max, t[rs(i)].max);
    }

    void insert(int &i, int last, int l, int r, int L, int R, int val)
    {
	    i = ++tot; t[i] = t[last];
        if (l >= L && r <= R)
        {
	        t[i].max = max(t[i].max, val);
            return;
        }
        int mid = (l + r) >> 1;
        if (mid >= L) insert(ls(i), ls(last), l, mid, L, R, val);
        if (mid < R) insert(rs(i), rs(last), mid+1, r, L, R, val);
    }
    int query(int i, int l, int r, int pos)
    {
	    if (!i) return 0;
        if (l == pos && r == pos) return t[i].max;
        int mid = (l + r) >> 1;
        if (pos <= mid)
            return max(t[i].max, query(ls(i), l, mid, pos));
        else
            return max(t[i].max, query(rs(i), mid+1, r, pos));
    }
    #undef ls
    #undef rs
}using namespace Leitree;
int T, siz[MAXN], dfn[MAXN], idfn[MAXN];
void dfs1(int u)
{
	siz[u] = 1; dfn[u] = ++T; idfn[T] = u;
    for (int v : e2[u])
    {
	    dfs1(v);
        siz[u] += siz[v];
    }
}
void dfs2(int u, int dad)
{
	insert(rt[u], rt[dad], 1, n, dfn[u], dfn[u] + siz[u] - 1, u);
    for (int v : e1[u])
        dfs2(v, u);   
}
int main()
{
	scanf("%d%d", &n, &m);
    for (int i = 2; i <= n; i++)
    {
	    int x; scanf("%d", &x);
        e1[x].push_back(i);
    }   
    for (int i = 2; i <= n; i++)
    {
	    int x; scanf("%d", &x);
        e2[x].push_back(i);
    }
    dfs1(1); dfs2(1, 0);
    int last_ans = 0;
    for (int i = 1; i <= m; i++)
    {
	    int x, y;
        scanf("%d%d", &x, &y);
        x = (x + last_ans) %n + 1;
        y = (y + last_ans) %n + 1;
        printf("%d\n", last_ans = query(rt[x], 1, n, dfn[y]));
    }

    return 0;
}

T2

A,B,C,DA, B, C, D 求有多少个 ii 满足 [A+Bi,A+Ci][A+B_i, A+C_i] 中没有 DD 的整数倍数

求这个

∑i=1n[⌊A+BiD⌋=⌊A+CiD⌋]\sum\limits_{i = 1}^{n}\left [ \left \lfloor \frac{A + Bi}{D} \right \rfloor = \left \lfloor \frac{A + Ci}{D} \right \rfloor \right ]

显然，当 Ci−Bi≥DC_i - B_i \geq D ，时 ii 没有意义，那么上界 n=⌊D−2C−B⌋n = \left\lfloor \frac{D-2}{C-B} \right\rfloor ，那么此时两项之差为 00 或 11 ，所以问题转化为

n−∑i=1n(⌊A+CiD⌋−⌊A+Bi−1D⌋)n - \sum\limits_{i=1}^{n} \left( \left \lfloor \frac{A + Ci}{D} \right\rfloor -\left \lfloor \frac{A + Bi-1}{D} \right \rfloor \right)

可以使用类欧几里德解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ll f(ll a, ll b, ll c, ll n)
{
	if (!a) return 0;
    if (a >= c || b >= c)
    return f(a%c, b%c, c, n) + a/c * (n+1)*n/2 + b/c * (n+1);
    return (a*n + b)/c*n - f(c, c-b-1, a, (a*n+b)/c-1);    
}
int main()
{
	scanf("%d",&t);
    while(t--)
    {
	    ll A, B, C, D; scanf("%lld%lld%lld%lld", &A, &B, &C, &D);
        ll n = (D-2)/(C-B);
        ll res = (f(C, A, D, n) - f(B, A-1, D, n)); 
        printf("%lld\n", n - res);
    }
    return 0;
}

9.14

T1

维护一个长度为 nn 的数列 aia_i ，共有 mm 个操作，这些操作共有两种。
1 l r k 将区间 [l,r][l,r] 内的元素全部修改为 kk
2 l r c 查询区间内是否存在出现次数大于 cc 的数
保证操作 22 中，满足 c≥⌊r−l+15⌋c \geq \lfloor \frac{r-l+1}{5} \rfloor。

区间推平操作，使用珂朵莉树魔法

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
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
#include <iostream>
#include <cstdio>
#include <set>
#define otto auto
#define MAXN 100005
using namespace std;
int a[MAXN];
namespace Chtholly
{
	class node
    {
	public:
        int l, r;
        mutable int val;
        node(int l, int r, int val)
        {
	        this -> l = l;
            this -> r = r;
            this -> val = val;            
        }

        friend bool operator < (node a, node b)
        {
	        return a.l < b.l;
        }

        int length() const
        {
	        return (r - l + 1);
        }
    };

    int length;
    set <node> odt;
    void build(int N)
    {
	    length = N;
        int l = 1;
        for (int i = 2; i <= N + 1; i++) if (a[i-1] != a[i])
        {
	        odt.insert(node(l, i-1, a[i-1]));
            l = i;
        }
    }

    otto split(int pos)
    {
	    if (pos > length) return odt.end();
        otto it = --odt.upper_bound(node(pos, 0, 0));
        if (it -> l == pos) return it;
        int l = it -> l;
        int r = it -> r;
        int val = it -> val;
        odt.erase(it);
        odt.insert(node(l, pos-1, val));
        return odt.insert(node(pos, r, val)).first;
    }

    void assign(int l, int r, int val)
    {
	    otto itr = split(r + 1),  itl = split(l);
        odt.erase(itl, itr);
        odt.insert(node(l, r, val));
    }

    int cnt[MAXN];
    bool query(int l, int r, int c)
    {
	    int flag = 0;
        otto itr = split(r + 1), itl = split(l);

        for (otto it = itl; it != itr; it++)
        {
	        cnt[it -> val] += it -> length();
            if (cnt[it -> val] > c) flag = 1;
        }
        for (otto it = itl; it != itr; it++)
        {
	        cnt[it -> val] -= it -> length();
        }
        return flag;    
    }

}using namespace Chtholly;
int main()
{
	int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    scanf("%d", &a[i]); build(n);


    int m; scanf("%d", &m);
    for (int i = 1; i <= m; i++)
    {
	    int op, l, r, val;
        scanf("%d%d%d%d", &op, &l, &r, &val);
        if (op == 1) assign(l, r, val);
        else
        {
	        if (query(l, r, val))
                printf("laffey\n");
            else
                printf("ayanami\n");
        }
    }

    return 0;
}

T2

P8456
给定一个 nn 个点， mm 条边的无向连通图。每条边标有 D 或 d。
定义无序点对 (u,v)(u, v) 是铁的，当且仅当 u，vu，v 之间存在同时出现 D 和 d 的简单路径
求一共有几个这样的点对

我们考虑什么样的点对是不满足条件的:

  • uu 到 vv 的任意路径只有 D 或 d

  • uu 到 vv 的每一条路径中仅有 D 或 d

对于第一种情况，我们通过在原图中去掉含有 D 或 d 的边，实际上转化率一个联通性问题，考虑圆方树

检出圆方树后我们堵死所有对应点双内含有 D 的方点，这样以后能互相到达的点双之间经过的路径一定是只有一种字母的，所以我们可以用并查集维护连通块统计 siz ，对于 D 和 d 的两种情况分别统计就行

对于第二种情况，我们

9.15

T1

签到题

T2

给定一张有向图，每个点有点权。试找到一条路径，使得该路径上的点权最大值减去点权最小值最大，问这个差最大是多少

记忆化搜索

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
#include <bits/stdc++.h>
#define MAXN 100005
#define MAXM 500005
#define INF 1145141919
using namespace std;
int n, m;
int f[MAXN];
int dis[MAXN];
int mi[MAXN], mx[MAXN];
int cnte = 1, head[MAXN];
struct edge
{
	int to, nxt;
}e[MAXM];
void adde(int u, int v)
{
	e[++cnte].to = v;
    e[cnte].nxt = head[u];
    head[u] = cnte;
}
void dfs(int u, int MX, int MI, int fa)
{
	int flag = 1;
    MX = max(MX, dis[u]), MI = min(MI, dis[u]);
    if (mx[u] < MX) mx[u] = MX, flag = 0;
    if (mi[u] > MI) mi[u] = MI, flag = 0;
    if (f[u] < MX - MI) f[u] = max(f[fa], MX - MI), flag = 0;
    if (flag) return;
    for (int i = head[u]; i; i = e[i].nxt)
    {
	    dfs(e[i].to, MX, MI, u);
    }
}
int main()
{
	freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &dis[i]);
    for (int i = 1; i <= m; i++)
    {
	    int u, v; scanf("%d%d", &u, &v); 
        adde(u, v);
    }
    for (int i = 1; i <= n; i++)
    {
	    mi[i] = INF;
        mx[i] = -INF;
    }
    for (int i = 1; i <= n; i++)
        dfs(i, dis[i], dis[i], 0);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
	    ans = max(ans, f[i]);
    }
    printf("%d", ans);
    return 0;
}

T3

有 nn 个人，每个人都有两把刷子，每个刷子都有一个属性值。如果说一个人拿着的两把刷子的属性值之差的绝对值超过了𝑐，则这个人无法使用他的两把刷子。现在你可以选择交换不同人的某把刷子，使得每个人都能够使用他们的刷子，问最小所需要的交换次数

状压表示每个人是否匹配成功，先把不合法的状态减去，把人分成两部分，各自交换，也就是枚举子集

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
#include <bits/stdc++.h>
#include <cstdio>
#define MAXN 17
#define cjb 1145141919
using namespace std;
int n, c;
int a[MAXN][2];
#define ABS(i) (i < 0 ? -i : i)
#define Abs(i) ABS((i))
int tmp[50], cnt; 
int f[1 << MAXN];
int main()
{
	// freopen("c.in", "r", stdin);
	// freopen("c.out", "w", stdout);
	scanf("%d%d", &n, &c);
	for (int i = 1; i <= n; i++)
	scanf("%d%d", &a[i][0], &a[i][1]);
	int tot = 0;
  	for (int i = 0; i < (1 << n); i++)
    {
	    cnt = 0; int flag = 1;
        for (int j = 1; j <= n; j++) if (i & (1 << (j - 1)))
		{
			tmp[++cnt] = a[j][0];
			tmp[++cnt] = a[j][1];
		}
        sort(tmp + 1, tmp + cnt + 1);
        for (int j = 1; j <= cnt; j += 2) if (tmp[j + 1] - tmp[j] > c)
        {
			flag = 0;
			break;
		}
		if (flag)
		{
			f[i] = 1;
		}
		else f[i] = -0x3f3f3f3f;
    }
	f[0] = 0;
	for (int i = 1; i < (1 << n); i++)
	{
		for (int j = i; j; j = (j-1) & i)
		{
			f[i] = max(f[i], f[j] + f[i^j]);
		}
	}
	if (f[(1 << n)-1] < 0) printf("-1");
	else 
	{
		printf("%d", n - f[(1 << n) - 1]);
	}
	return 0;
}

T4

维护序列，区间加斐波那契，区间和

考虑如何实现区间加，多次加斐波那契的结果，一定是一个类斐波那契数列，有两个重要性质

∑F(n)=F(n+2)−F(2)\sum F(n) = F(n+2) - F(2)

gn=g1(n−2)+g2(n−1)g_n = g_1(n-2) + g_2(n-1) ，gg 表示 g1,g2g_1,g_2 两个对应项相加

我们只需要维护首项和第二项就可以根据这两个式子合并

9.16

T1

给由一个正整数 NN，构造一个长度为 kk 的数列 A，为从 N 开始的连续 kk 个数按顺序拼接生成，即 A={N,N+1,N+2,....,N+k−1}A=\{N,N+1,N+2,....,N+k-1\} ，把数列 AA 中的每个数都只保留一个数字，得到数列 BB。

现在给出 KK 和数列 BB，请求出最小的合法的 nn。

枚举每一位数的起点，然后每十位数合并，在接着十位十位地枚举

T2CF1119H

你的生日礼物是nn个整数三元组。第ii个三元组是{ai,bi,ci}\{a_i,b_i,c_i\},所有数字jj都满足0≤j<2k0\le j<2^k,kk是一个固定的数字，将由题目输入。

一天，你玩三元组玩腻了，所以你有了3个新的整数x,y,zx,y,z,然后填充了nn个数组。第ii个数组有xx个aia_i,yy个bib_i,zz个cic_i.这样，每个数组的大小都是x+y+zx+y+z.

你希望从每个数组里选择1个整数，使得它们的xor(按位异或)值恰好为tt. 对于区间[0,2k−1][0,2^k-1]内的每个数字tt,输出满足上面的条件的方案数 模 998244353998244353

异或考虑 FWT

统计方案想到生成函数卷积，我们把这些三元组看作一个多项式，cc 表示异或卷积的变换系数

最后的卷积就是

∏k=1n((−1)i&akx+(−1)i&bky+(−1)i&ckz) \prod_{k=1}^{n}\left((-1)^{i \& a_{k}} x+(-1)^{i \& b_{k}} y+(-1)^{i \& c_{k}} z\right)

cntcnt 表示二进制下 11 的个数

按 x,y,zx,y,z 的系数四种情况解方程

T3CF241B

给定n个整数a1,a2...ana1,a2...an,求两两异或值前k大的和。 其中n<=50000,ai<=109n<=50000,ai<=10^9。答案对1000000007(109+7)1000000007 (10^9+7)取模。

二分 kk 大值 ，枚举每个数，查询疑惑和大于 midmid 的数量

对原数建 01Trie，预处理出树上子树上的叶子节点上二进制下每一位是 11 的数的个数。

这样就可以方便地快速计算出整棵子树异或上一个数的和。

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
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
130
131
132
133
134
135
136
137
#include <bits/stdc++.h>
#define MXBT 30
#define MAXN 50005
#define ll long long
#define inv2 500000004
#define mod 1000000007
using namespace std;
int n; ll k;
int a[MAXN];
ll ans;
namespace Trie
{
	int tot;
    int siz[MAXN * MXBT];
    int kid[MAXN * MXBT][2];
    int cnt[MAXN * MXBT][MXBT+1];
    void insert(int x)
    {
	    int now = 0;
        for (int i = MXBT; i >= 0; i--)
        {
	        int bit = (x >> i) & 1;
            if (!kid[now][bit]) kid[now][bit] = ++tot;
            now = kid[now][bit]; siz[now]++;
        }
    }
}using namespace Trie;
ll check(int x)
{
	ll sum = 0;
    for (int i = 1; i <= n; i++)
    {
	    int now = 0;
        for (int j = MXBT; j >= 0; j--)
        {
	        int u = (a[i] >> j) & 1;
            int v = (x >> j) & 1;
            if (!v)
            {
	            sum += siz[kid[now][u^1]];
                now = kid[now][u];
            }
            else now = kid[now][u^1];
            if (!now) break;
        }
        sum += siz[now];
    }
    return sum/2;
}
void init(int u, int d, int z)
{
	if (u == 0) return;
    if (d == 0)
    {
	    for (int i = 0; i <= MXBT; i++)
        {
	        if ((z >> i) & 1)
            cnt[u][i] = siz[u];
        }
        return ;
    }
    init(kid[u][0], d-1, z);
    init(kid[u][1], d-1, z | (1 << (d - 1)));
    for (int i = 0; i <= MXBT; i++)
    cnt[u][i] = cnt[kid[u][0]][i] + cnt[kid[u][1]][i];
}
void solve(int x)
{
	for (int i = 1; i <= n; i++)
    {
	    int now = 0;
        for (int j = MXBT; j >= 0; j--)
        {
	        int u = (a[i] >> j) & 1;
            int v = (x >> j) & 1;
            if (!v)
            {
	            int t = kid[now][u^1];
                for (int k = 0; k <= MXBT; k++)
                {
	                int w = (a[i] >> k) & 1;
                    if (w)
                        ans = (ans + 1LL*(siz[t] - cnt[t][k]) * (1LL << k)) %mod;
                    else
                        ans = (ans + 1LL*cnt[t][k] * (1LL << k)) %mod;
                }
                now = kid[now][u];
            }
            else  now = kid[now][u^1];
            if (!now) break;
        }
        ans = (ans + 1LL * siz[now] * x)%mod;
    }
}
int main()
{
	scanf("%d%lld", &n, &k); if (!k)
    {
	    putchar('0');
        return 0; 
    }
    for (int i = 1; i <= n; i++)
    {
	    scanf("%d", &a[i]);
        insert(a[i]);
    }
    // cout << tot << " I',m tot\n";    
    init(kid[0][0], MXBT, 0);
    init(kid[0][1], MXBT, 1 << MXBT);
    // for (int i = 1; i <= tot; i++)
    // {
	//     for (int j = 0; j <= 30; j++)
    //     {
	//         printf("%d ", cnt[i][j]);
    //     }
    //     cout << '\n';
    // }
    int l = 0, r = 1 << MXBT, kth;
    while (l <= r)
    {
	    int mid = (l + r) >> 1;
        // cout << l << ' ' << mid << ' ' << r << '\n';
        if (check(mid) >= k)
        {
	        kth = mid;
            l = mid+1;
        }
        else r = mid-1;
    }
    // printf("%d KTH\n", kth);
    solve(kth);
    // cout << ans << "dada\n";
    ans = ans * inv2 %mod;
    ans = ((ans - 1LL * (check(kth) - k) * kth%mod)%mod + mod)%mod;
    printf("%lld", ans);
    return 0;
}

9.17

原题赛，skip

9.19

T1JOISC2013 T4

这个游戏要用到一些写有J,O,IJ,O,I 中任一文字的圆盘。这些圆盘的直径互不相同。游戏开始时，这些圆盘按照直径大的
在下面的规则堆叠。你需要用这些圆盘做尽量多的迷你 JOIOI 塔。迷你 JOIOI 塔由 个圆盘构成，从直径较小的圆盘开始分别为J,O,IJ,O,I 或分别为I,O,II,O,I 。不过，每个圆盘最多只能使用一次
现在给出长为 nn 的字符串 ss，表示直径从小到大的圆盘上的文字。请编写程序求出使用这些圆盘能够做出的迷你 JOIOI 塔个数的最大值

倒叙扫描维护 i ,oi ,ioi, joi 的个数

  • 如果有 o 与 i 合成 oi
  • 如果有 i 与 ioi 合成 ioi
  • 如果有 j 把 ioi 拆成 joi 和 i
Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (int I = n; I; I--)
{
	if (s[I] == 'J') if (i && oi)
	{
		if (oi == ioi || i == ioi * 2) ioi--;
		oi--; i--; joi++;
	}
	if (s[I] == 'O') oi = min(i, oi+1);
	if (s[I] == 'I')
	{
		if (oi > ioi && i > ioi * 2)
		ioi++;
		i++;
	}
}
printf("%d", ioi + joi);

T2

nn 个数 a1,…,ana_1, \dots, a_n，定义 f(i,j)=ai  opt  ajf(i,j) = a_i \; opt \; a_j，

g(i)=max⁡res=1i−1f(ai,ares),i∈[2,n]g(i)=\max _{r e s=1}^{i-1} f\left(a_{i}, a_{r e s}\right), i \in[2, n]

以及 g(i)g(i) 的个数

逆天 dp ，把结果的前四位和后四位分开看

Code

gg 表示对应情况的个数

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
int n, TYPE;
int ans, cnt;
int f[MAXN][MAXN];
int g[MAXN][MAXN];
char op[5];
int F (int x, int y)
{
	return op[1] == 'a'? x&y : op[1] == 'o' ? x|y : x^y;
}
int main()
{
	freopen("meltdown.in", "r", stdin);
	freopen("meltdown.out", "w", stdout);
	scanf("%d%s%d", &n, op+1, &TYPE);
	memset(f, 0xcf, sizeof(f));
	int x, y, now, mx;
	for (int k = 1; k <= n; k++) 
	{
		scanf("%d", &x);
		y = x & S; x >>= 8; ans = -cjb; cnt = 0;
		for (int i = 0; i <= S; i++)
		{
			now = f[x][i] + F(i, y);
			if (now > ans) { ans = now; cnt = 0; }
		if (now == ans) cnt += g[x][i];
		}
		for (int i = 0; i <= S; i++)
		{
			now = F(i, x) << 8;
			if (f[i][y] < now) { f[i][y] = now, g[i][y] = 0; }
		if (f[i][y] == now) g[i][y]++;
		}
		if (k > 1)
		{
			if  (TYPE)
				printf("%d %d\n", ans, cnt);
			else
				printf("%d\n", ans);
		}
	}
	return 0;
}

T4P6965

给定 n 个01串，每个字符串至多有一位是未知的，可以填 0 或 1 ，求是否存在一种方案，使得任意一个字符串不是其它任意一个字符串的前缀

01 考虑 2-SAT ，显然的是一个字符不能与它的前缀同时出现，那么他与他的前缀连边，n2n^2 T掉
考虑优化建图，全是 01 还可以方便的维护前缀，考虑 01Trie

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
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
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
#include <type_traits>
#define MAXN 3000005
using namespace std;
int n;
string s[MAXN];
vector <int> e[MAXN];
unordered_map <string, int> mp;
vector <int> q[MAXN];
void adde(int u, int v)
{
	e[u].push_back(v);
}
namespace Trie
{
	int rt, tot;
	int N[MAXN];
	int ch[MAXN][2];
	void insert(string s, int id)
	{
		int now = rt;
		for (int i = 0; s[i]; i++)
		{
			int bit = s[i] - '0';
			if (!ch[now][bit]) ch[now][bit] = ++tot;
			now = ch[now][bit];
		}
		q[now].push_back(id);
	}
}using namespace Trie;
#define inv(i) ((i > n ? i - n : i + n))
void build(int u, int fa)
{
	if (!u) return;
	N[u] = ++tot;
	if (fa) adde(u, fa), adde(N[fa], N[u]);
	for (int v : q[u])
	{
		adde(v, fa);
		adde(u, inv(v));
		adde(N[u], inv(v));
	}
	for (int v : q[fa])
		adde(v, N[u]);
	for (int v : q[u]) for (int z : q[u])
	{
		if (v != z)
		adde(v, inv(z));
	}
	build(ch[u][0], u);
	build(ch[u][1], u);
}
int vis[MAXN];
int dfn[MAXN], low[MAXN], T;
int sta[MAXN], scc[MAXN], top;
int cnt;
void Tarjan(int u)
{
	// cout << u << '\n';
	dfn[u] = low[u] = ++T;
	sta[++top] = u; vis[u] = 1;
	for (auto v : e[u])
	{
		if (!dfn[v])
		{
			Tarjan(v);
			low[u] = min(low[u], low[v]);
		}else if (vis[v])
			low[u] = min(low[u], dfn[v]);
	}
	if (low[u] == dfn[u])
	{
		++cnt;
		while(sta[top] != u)
		{
			int v = sta[top--];
			scc[v] = cnt;
			vis[v] = 0;
		}
		scc[sta[top]] = cnt;
		vis[sta[top--]] = 0;
	}
}
int main()
{
	cin >> n; rt = tot = n << 1 | 1;
	for (int i = 1; i <= n; i++)
	{
		cin >> s[i];
		if (++mp[s[i]] >= 3)
		{
			printf("NO"); return 0;
		}
		for (int j = 0;  ; j++)
		{
			if (s[i][j] == '?')
			{
				s[i][j] = '0'; insert(s[i], i);
				s[i][j] = '1'; insert(s[i], i+n);
				s[i][j] = '?'; break;
			}
			if (j == s[i].size() - 1)
			{
				insert(s[i], i);
				insert(s[i], i + n);
				break;
			}	

		}
	}
	build(rt, 0);

	for (int i = 1; i <= tot; i++)
	if (!dfn[i]) Tarjan(i);
	for (int i = 1; i <= n; i++)
	{
		if (scc[i] == scc[i + n])
		{
			printf("NO");
			return 0;
		}
	}
	printf("YES\n");
	for (int i = 1; i <= n; i++)
	{
		int len = s[i].size();
		for (int j = 0; j < len; j++)
		{
			if (s[i][j] == '?')
			{
				s[i][j] = '0' + (scc[i] > scc[i + n]);
				cout << s[i] << '\n'; break;
			}
			if (j == len-1)
			{
				cout << s[i] << '\n';
				break;
			}
		}
	}
	return 0;
}

9.20

T1

对于一个序列 AA ，上升对表示 ai<ai+1a_i < a_{i+1} ，定义 XiX_i 表示序列中前 ii 个元素内的上升对的数量，定义 nb 序列为满足以下条件的序列：

  • a1=0a_1 = 0
  • ai⩽Xi−1+1a_i \leqslant X_{i-1}+1
  • 不存在 1≤i<j<k≤n1 \leq i < j < k \leq n，满足 ak<ai<aja_k < a_i < a_j
    求长度为 nn 的 nb 序列的数量

打表题

T2ARC111F

给定一个初始为 00 的长度为 nn 的序列和一个数 MM，有 qq 次操作：

  • 1 l r v: 使 al∼ara_l \sim a_r 对 vv 取最小值
  • 2 l r v: 使 al∼ara_l \sim a_r 对 vv 取最大值
  • 3 l r: 将 al∼ara_l\sim a_r 的和加到 ansans 上
    0≤v<m0 \leq v < m
    求所有可能的 ansans 的和

考虑一个位置在这些操作中被修改的可能，以及可能被修改成什么值在经过复杂的推式子

T3ARC120E

数轴上有一些点，每一时刻每个点都可以向左或向右移动一个单位距离，求出最小的需要的时间 kk ，每一个 ii 和 i+1i+1 这两个点都重合过一次

对于 ii 个点，让他向右，第 i+1i+1 个点向左，这样强制匹配这两个点，DP
f[i]f[i] 表示强制匹配 i−1i-1 和 ii

Code 
1
2
3
4
a[0]=a[1],a[n+1]=a[n];
f[2]=a[2]-a[1];
for(int i=3;i<=n+1;i++)
f[i]=min(max(f[i-2],a[i]-a[i-3]),max(f[i-3],a[i]-a[i-4]));

9.22

T1ARC135F

一个长度为 nn 的序列 AA ，有 kk 次操作，每次删除序列中下标为 3i+13i + 1 的所有数
求 kk 次操作后序列中所有数的和

不难想到 11 次操作以后 ⌊3i+12⌋\left\lfloor\frac{3 i+1}{2}\right\rfloor 就是第 ii 个位置上的数是哪个，那么我们设 f(i)=⌊3i+12⌋f(i) = \left\lfloor\frac{3 i+1}{2}\right\rfloor 那么 fk(i)f^k(i) 就是 kk 此操作后第 ii 个位置的数

我们可以求出每次操作后剩下的数，那么答案就是 ∑icntfk(i)\sum\limits_i^{cnt} f^k(i) 暴力递推的复杂度是 ∑kcntk×k\sum\limits_{}^k cnt_k\times k

显然的是每次操作只会剩下 23n\frac{2}{3}n 个数，那么总时间复杂度大约是 nk(23k)nk(\frac{2}{3}^k) 的，当 kk 大一点的时候可以通过

fk(n+xk)=fk(n)+3kf^k(n + x^k) = f^k(n) + 3^k ，把式子展开一层就证出来了

所以我们枚举每一个位置 ii，求 fk(i+2yj)=fx(fy(i+2yj))=fx(fy(i)+3yj)f^k(i + 2^yj) = f^x(f^y(i+2^yj)) = f^x(f^y(i) + 3^yj)

T2ARC127E

给 A+BA + B 的序列 (x1,x2,…,xA+N)(x_1, x_2, \dots,x_{A+N}) ，包含 AA 个 11 和 BB 个 22。
维护一个集合，如果 xi=1x_i = 1 ，那么选择一个 v，1≤v≤Av，1 \leq v \leq A
如果 xi=2x_i = 2 ，那么删除集合中最大的数
求集合最后有多少种可能的状态

我们有一个结论，字典序比可能的状态小的一定能满足，所以我们求出字典序最大的集合然后从字典序比他小的状态转移

fi,j=fi,j−1+fi−1,j−1f_{i,j} = f_{i, j-1} + f_{i-1, j-1}

fi,jf_{i,j} 表示前 ii 个元素中最大值为 jj 有几种可能

9.23

T1

给定一个序列 aa ，两种操作
l m r 归并 al,al+1,…,am,am+1,am+2,…,ar{a_l, a_{l+1}, \dots, a_m}, {a_{m+1},a_{m+2},\dots,a_{r}}
i 询问 aia_i 的值
归并指的是一轮归并排序

对序列建平衡树，每次归并分裂出 l∼ml \sim m 和 m+1∼rm+1 \sim r ，每次在一颗子树中查找小于另那个一棵子树的极长前缀，平衡树维护就行

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
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <bits/stdc++.h>
#include <time.h>
#define MAXN 100005
using namespace std;
int n, m;
int a[MAXN];
namespace FHQ_Treap
{
	int rt, tot;
	struct tree
	{
		int siz, val, key, max, ch[2];
	}t[MAXN];
	#define ls(i) (t[i].ch[0])
	#define rs(i) (t[i].ch[1])
	int new_node(int k)
	{
		++tot;
		t[tot].siz = 1;
		t[tot].val = k;
		t[tot].max = k;
		t[tot].key = rand();
		return tot;
	}
	void push_up(int i)
	{
		t[i].siz = t[ls(i)].siz + t[rs(i)].siz + 1;
		t[i].max = max(max(t[ls(i)].max, t[rs(i)].max), t[i].max);
	}
	int build(int l, int r)
	{
		if (l > r) return 0;
		int mid = (l + r) >> 1;
		int now = new_node(a[mid]);
		ls(now) = build(l, mid-1);
		rs(now) = build(mid+1, r);
		push_up(now);
		return now;
	}
	int merge(int x, int y)
	{
		if (!x || !y) return x | y;
		if (t[x].key < t[y].key)
		{
			rs(x) = merge(rs(x), y);
			push_up(x); return x;
		}
		else
		{
			ls(y) = merge(x, ls(y));
			push_up(y); return y; 
		}
	}
	void split_val(int i, int &x, int &y, int val)
	{
		if (!i) { x = y = 0; return; }
	if (max(t[ls(i)].max, t[i].val) <= val)
		{
			x = i;
			split_val(rs(i), rs(x), y, val);
		}
		else
		{
			y = i;
			split_val(ls(i), x, ls(y), val);
		}
		push_up(i);
	}
	void split_siz(int i, int &x, int &y, int siz)
	{
		if (!i) { x = y = 0; return; }
	if (t[ls(i)].siz < siz)
		{
			x = i;
			split_siz(rs(i), rs(x), y, siz-t[ls(i)].siz-1);
		}
		else
		{
			y = i;
			split_siz(ls(i), x, ls(y), siz);
		}
		push_up(i);
	}
	int find(int i)
	{
		while(ls(i)) i = ls(i);
		return t[i].val;
	}
	void solve(int l, int mid, int r)
	{
		int a, b, c, d, e, f;
		split_siz(rt, a, b, l-1);
		split_siz(b, b, c, mid-l+1);
		split_siz(c, c, d, r-mid);
		rt = a;
		while(b && c)
		{
			int cur1 = find(b);
			int cur2 = find(c);
			if (cur1 > cur2)
			{
				swap(cur1, cur2);
				swap(b, c);
			}
			split_val(b, e, b, cur2);
			rt = merge(rt, e);
		}
		if (c) rt = merge(rt, c);
		rt = merge(rt, d);
	}

	int print(int x)
	{
		int a, b, c;
		split_siz(rt, a, b, x-1);
		split_siz(b, b, c, 1);
		int ans = t[b].val;
		rt = merge(merge(a, b), c);
		return ans;
	}
}using namespace FHQ_Treap;
void dfs(int u)
{
	if (ls(u)) dfs(ls(u));
	cout << t[u].val << ' ';
	if (rs(u)) dfs(rs(u));
}
int main()
{
	scanf("%d%d", &n, &m); srand(time(0));
	for (int i = 1; i <= n; i++)
	scanf("%d", &a[i]);rt = build(1, n);
	// dfs(rt); cout << '\n';

	for (int i = 1; i <= m; i++)
	{
		int op; scanf("%d", &op);
		if (op == 1)
		{
			int l, mid, r; scanf("%d%d%d", &l, &mid, &r);
			solve(l, mid, r);
			// dfs(rt); cout << '\n';
		}
		else
		{
			int x; scanf("%d", &x);
			printf("%d\n", print(x));
		}
	}
	return 0;
}

T2ARC112E

给定一个序列 , mm 次操作，删除一个数，并把它加到开头或结尾求所有方案总数，两种方案相同，当且仅当每次操作都选择了相同元素，移动到了相同的方向

对每个数进行的最后一次操作，才是决定这个数的位置的操作，称之为关键操作

dpi+1,l,r=dpi,l,r∗2(l+r)+dpi−1,l+1,r+dpi−1,l,r+1dp_{i+1,l,r} = dp{i,l,r} * 2(l+r) + dp{i-1,l+1,r} + dp_{i-1,l,r+1}

ii 次操作， ll 次向左， rr 次向右

实际上 ll 和 rr 的顺序没有必要

dpi,j=dpi+1,j∗2∗j+dpi+1,j−1dp_{i, j} = dp_{i+1, j} * 2 * j + dp_{i+1, j-1}

ii 次操作，jj 次关键操作

T3ARC120F

给定一个序列 aa ，定义一个子序列是 nb 的，满足两个条件 :

  • 长度为 kk
  • 没有原序列中连续的两个元素在序列中
    求所有 nb 序列的和

首先一个序列 不相邻选 kk 个的方案 Cn−k+1kC_{n-k+1}^k, 记为 CC
考虑求出每一个数会在多少种方案中出现，记为 cntcnt
如果是一个环，那么 cnt=C×kncnt = \frac{C \times k}{n} ，而是一个序列，只是多了 a1a_1 和 ana_n 都选的情况

9.26

T1

猎魔人杰洛特来到了牛堡。牛堡可以被视为一个二维平面，而牛堡的街道可以被视为一条条直线。堡共有 nn 条南北向街道，其中第 ii 条为直线 x=aix = a_i ，另外还有 mm 条东西向街道，其中第 ii 条为直线 y=biy= bi 。沿着第 ii 条南北向街道行进 11 单位距离需要 tit_i 的时间，而沿着任意一条东西向街道行进 11 单位距离均需要 t0t_0 的时间。他希望你帮忙计算从城市入口 (0,0)(0,0) 出发到达各个十字路口的最短时间。具体来说，令 f(ai,bj)f(ai,bj) 表示从 (0,0)(0,0) 出发，沿着街道行进并到达十字路口 (ai,bj)(ai,bj) 所需的最短时间，杰洛特请你对于所有 1≤i≤n1 \leq i \leq n 分别计算下式的值

横向的道路费用是完全相同的。
第一种情况是可以 O(1)O(1) 求的，发现横着走一样，那么有区别的就是竖着走的路程和横着多走出来的
以横着走到路程为 xx ，那么竖着的花费是一个常数，横着的花费是系数。可以构造出一个一次函数，斜率优化维护上凸壳

T2

给一个长为 nn 的序列和模数，33 中操作，区间乘，单点除，查询区间和

区间乘很简单，难的是单点除，模数不一定是质数，所以不一定有逆元
把模数分解，维护每个数和模数的公共质因数，先把这些因数除了，剩下的就是和模数互质的，可以有逆元

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
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <bits/stdc++.h>
#include <string>
#define ll long long
#define MAXN 500005
#define mul(x, y) ((x) = ((x) * (y))%mod)
int n, m;
ll mod, a[MAXN];
ll prime[MAXN], mp[MAXN];
int cntp;
void exgcd(ll a, ll b, ll &x, ll &y)
{
	if (b == 0)
	{
		x = 1; y = 0; return;
	}
	exgcd(b, a%b, y, x);
	y -= a / b * x;
}
ll inv(ll val)
{
	ll a, b;
	exgcd(val, mod, a, b);	
	return (a %mod + mod) %mod;
}
ll ksm (ll a, ll b)
{
	ll ans = 1;
	while (b)
	{
		if (b & 1) ans = ans * a %mod;
		a = a * a %mod; b >>= 1;
	}
	return ans;
}
namespace Leitree
{		
	int cnt[MAXN << 2][20];
	struct tree
	{
		int l, r;
		ll d;
		ll sum, lz;
	}t[MAXN << 2];
	#define ls(i) (i << 1)
	#define rs(i) (i << 1 | 1)
	void push_up(int i)
	{
		t[i].sum = (t[ls(i)].sum + t[rs(i)].sum) %mod;
	}
	void push_down(int i)
	{
		mul(t[ls(i)].sum, t[i].lz); mul(t[ls(i)].lz, t[i].lz); mul(t[ls(i)].d, t[i].d);
		mul(t[rs(i)].sum, t[i].lz); mul(t[rs(i)].lz, t[i].lz); mul(t[rs(i)].d, t[i].d);
		t[i].d = t[i].lz = 1;
		for (int j = 1; j <= cntp; j++)
		{
			cnt[ls(i)][j] += cnt[i][j];
			cnt[rs(i)][j] += cnt[i][j]; 
			cnt[i][j] = 0;
		}
	}
	void build(int i, int l, int r)
	{
		t[i].l = l; t[i].r = r; t[i].lz = 1; t[i].d = 1;
		if (l == r)
		{
			t[i].sum = a[l];
			ll x = a[l];
			for (int j = 1; j <= cntp; j++)
			{
				while(x % prime[j] == 0)
				{
					cnt[i][j]++;
					x /= prime[j];
				}
			}
			t[i].d = x;
			return ;
		}
		int mid = (l + r) >> 1;
		build(ls(i), l, mid);
		build(rs(i), mid+1, r);
		push_up(i);
	}
	void add(int i, int l, int r, ll val)
	{
		if (t[i].l >= l && t[i].r <= r)
		{
			mul(t[i].sum, val); mul(t[i].lz, val);
			for (int j = 1; j <= cntp; j++)
			{
				while (val % prime[j] == 0)
				{
					cnt[i][j]++; val /= prime[j];
				}
			}
			mul(t[i].d, val);
			return;
		}
		push_down(i);
		if (t[ls(i)].r >= l) add(ls(i), l, r, val);
		if (t[rs(i)].l <= r) add(rs(i), l, r, val);
		push_up(i);
	}
	void change(int i, int pos, ll val)
	{
		if (t[i].l == pos && t[i].r == pos)
		{
			for (int j = 1; j <= cntp; j++)
			while (val % prime[j] == 0)
			{
				cnt[i][j]--; val /= prime[j];
			}
			mul(t[i].d, inv(val));
			t[i].sum = t[i].d;
			for (int j = 1; j <= cntp; j++) if (cnt[i][j])
			{
				mul(t[i].sum, ksm(prime[j], cnt[i][j]));
			}
			return;
		}
		push_down(i);
		int mid = (t[i].l + t[i].r) >> 1;
		if (pos <= mid)
			change(ls(i), pos, val);
		else
			change(rs(i), pos, val);
		push_up(i);
	}
	ll query(int i, int l, int r)
	{
		if (t[i].l >= l && t[i].r <= r) return t[i].sum %mod;
		push_down(i); ll ans = 0;
		if (t[ls(i)].r >= l) ans = (ans + query(ls(i), l, r)) %mod;
		if (t[rs(i)].l <= r) ans = (ans + query(rs(i), l ,r)) %mod;
		push_up(i);
		return ans;
	}
	#undef ls
	#undef rs
}using namespace Leitree;
void devide(ll x)
{
	for (ll p = 2; p * p<= x; p++)
	{
		if (x % p == 0)
		{
			prime[++cntp] = p;
		}
		while (x % p == 0) x /= p;
	}
	if (x != 1)
	{
		prime[++cntp] = x;
	}
}
int main()
{
	read(n, mod);
	for (int i = 1; i <= n; i++)
	read(a[i]);
	devide(mod);
	build(1, 1, n);
	read(m);
	for (int i = 1; i <= m; i++)
	{
		int op; read(op);
		if (op == 1)
		{
			int l, r; ll val; read(l, r, val);
			add(1, l, r, val);
		}
		if (op == 2)
		{
			int pos; ll val; read(pos, val);
			if (val == 1) continue;
			change(1, pos, val);
		}
		if (op == 3)
		{
			int l, r; read(l, r);
			printf("%d\n", query(1, l, r) );
		}
	}
	return 0;
}
9月每日总结
https://ve1bae.github.io/2022/08/31/9月每日总结/
本文作者
Veibae
发布于
2022年8月31日
更新于
2022年11月14日
许可协议
CC BY-NC-SA 4.0
署名-非商业性使用-相同方式共享 4.0 国际。

更新于：2022年11月14日

总结

数据结构

贪心

dsu on tree

数学，数论

评论