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

11月每日总结

发布于：2022年11月4日

日复一日，必有精进？？？？

11.1

T1

有 nn 个选民，编号为 1∼n1 \sim n ，它们中有的人支持Alice，有的人支持Bob，还有的人保持中立。
现在你需要把选民分成若干个区间，每个区间的长度在 [l,r][l,r] 中。如果一个区间中支持Alice的人比支持Bob的人多，那么Alice得一票， Bob多则Bob得一票。 请你合理地分区间，使得Alice获胜。

可以想到一个比较暴力的 DP

令 fif_i 为到 ii 这个位置的最大收益

fi=max⁡j=lrfj−1+get(j,i)f_i = \max\limits_{j = l}^r f_{j-1} + get(j, i)

其中 l,rl, r 指的是在 ii 左侧，能和 ii 划成一个区间的最远和最近的位置。
get(i,j)get(i, j) 指 [i,j][i, j] 的区间内，选票的增减情况，也就是区间和的符号

那么考虑怎么优化，使用线段树科技, 对于 sumsum 为下标维护 ff 优化

T2

小象有 nn 张卡片，第 ii 张卡片上有一个数字 aia_i 。Alice和Bob轮流选择卡片 (不能重复)，如果某次选择后已选择卡片上的数字的最大公约数为 11 或者没有卡片可以选择，那么当前角色失败。
你需要求出：1、如果双方都选择最优策略，谁会获胜；2、如果双方都随机选取，Alice获胜的概率。

直接状压卡片选不选，TLE + MLE

只记录当前 gcd 和 已选卡片数量 TLE 。 有发现可以把 aia_i 中相同的因数去掉。状态数减少

11.2

我爹 AK 了

11.3

T1

给定一个 n∗mn * m 的棋盘。 qq 次询问， 询问一个宽度为 ww 的东西能不能从一个坐标到达另一个坐标。

可以二分预处理出每个点能放得下的最大宽度。

对询问离线，按宽度递减排序，并查集维护连通性。宽度减小扩展并查集就行。

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
#include <bits/stdc++.h>
#define MAXN 2005
#define MXXN 1000005

using namespace std;
namespace OCTANE
{
	template <typename T> inline void read(T &x)
	{
		x = 0; bool f = 0; char ch = getchar();
		while (ch < '0' || ch > '9')
		{
			if (ch == '-') f = 1; ch = getchar();
		}
		while (ch >= '0' && ch <= '9')
		{
			x = (x << 1) + (x << 3) + (ch^48); ch = getchar();
		}
		if (f) x = -x;
	}
	template <typename T> inline void print(T x)
	{
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) print(x / 10);
		putchar(x%10 + '0');
	}
	template <typename T, typename ...TT>
	inline void read(T &x, TT &...y)
	{
		read(x); read(y...);
	}
	#define p_ putchar(' ');
	#define pn putchar('\n');
	#define print_(x) print(x), putchar(' ');
	#define printn(x) print(x), putchar('\n');

}using namespace OCTANE;

int n, m, q;

#define pos(x, y) (((x) - 1) * n + (y))
namespace Union_set
{
	int fa[MXXN], siz[MXXN];
	void init(int n)
	{
		for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;
	}
	int find(int x)
	{
		return x == fa[x] ? x : fa[x] = find(fa[x]);
	}
	bool merge(int x, int y)
	{
		int fx = find(x), fy = find(y);
		if (fx == fy) return false;
		if (siz[x] > siz[y]) swap(x, y);
		fa[fx] = fy; siz[fy] += siz[fx];
		return true;
	}
}

struct query { int sx, sy, tx, ty, w, id; }que[100005];

bool cmp(query a, query b)
{
	return a.w > b.w;
}

char mp[MAXN][MAXN];
int sum[MAXN][MAXN];
int mxz[MAXN][MAXN];

int get(int lx, int rx, int ly, int ry)
{
	return sum[rx][ry] - sum[lx-1][ry] - sum[rx][ly-1] + sum[lx-1][ly-1];
}

vector <pair<int, int>> vr[MAXN];

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void Linkstart(int now)
{
	for (auto v : vr[now])
	{
		int p = pos(v.first, v.second);
		for (int i = 0; i < 4; i++)
		{
			int X = v.first + dx[i], Y = v.second + dy[i];
			if (X > 0 && Y > 0 && X <= n && Y <= m) if (mxz[X][Y] >= now)
				Union_set::merge(p, pos(X, Y));
		}
	}
}

int ans[100005];

int main()
{
	// freopen("data.in", "r", stdin);
	// freopen("vei.out", "w", stdout);
	read(n, m, q);
	for (int i = 1; i <= n; i++)
		scanf("%s", mp[i] + 1);
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + (mp[i][j]^48);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++) if (mp[i][j] == '0')
		{
			int l = 1, r = min(i, j) + 1;
			int res = 1;
			while (l < r)
			{
				int mid = (l + r) >> 1;
				if (!get(i - mid + 1, i, j - mid + 1, j))
					res = mid, l = mid + 1;
				else
					r = mid;
			}
			mxz[i][j] = res;
			vr[res].emplace_back(i, j);
		}
	}

	int now = 0;

	for (int i = 1; i <= q; i++)
	{
		int sx, sy, tx, ty, w;
		read(sx, sy, tx, ty, w); now = max(now, w);
		que[i] = {sx, sy, tx, ty, w, i};
	}
	sort(que + 1, que + 1 + q, cmp);

	Union_set :: init(n * m);

	for (int i = 1; i <= q; i++)
	{
		while (now >= que[i].w) Linkstart(now--);
		if (mxz[que[i].sx][que[i].sy] < que[i].w ||
			mxz[que[i].tx][que[i].ty] < que[i].w) ans[que[i].id] = false;
		else
			ans[que[i].id] = (Union_set::find(pos(que[i].sx, que[i].sy)) == 
		Union_set::find(pos(que[i].tx, que[i].ty)));
	}
	for (int i = 1; i <= q; i++)
	puts(ans[i] ? "Yes" : "No");

	return 0;
}

11.4

T1

两组玩家，第一组玩家的能力值为 ai,…ana_i, \dots a_n 。第二组玩家的能力值为 b1,…b2b_1, \dots b_2 。玩家之间两两进行游戏。AA 组玩家在一场游戏中获胜的概率是 ai/(ai+bi)a_i / (a_i + b_i) 。 询问 AA 组每个玩＋获胜的期望。ai,bi∈[1,2]a_i, b_i \in [1, 2]

对于每个 aa 求 ∑i=1maa+bi\sum\limits_{i=1}^{m} \dfrac{a}{a + b_i}

转化一下

∑i=1maa+bi=m−∑i=1mbia+bi\sum_{i=1}^{m} \dfrac{a}{a+b_i}\\ =m-\sum_{i=1}^{m}\frac{b_i}{a+b_i}

对后面的分式进行一个泰勒的展开。

f(x)=∑i=0∞f(i)x0i!(x−x0)if(x) = \sum_{i=0}^{\infty } \frac{f^{(i)}{x_0}}{i!} (x - x_0)^i

后在 x=1.5x = 1.5 处展开后面的 x−x0x - x_0 就已经可以忽略了

T2

一棵带权树，每次给两个人两条路径，速度为 11 ， 判断是否存在一个时刻，两个人在一条边上（不算顶点）

分情况讨论，判断路径交不交先，有交分为两种情况：

  • 同向时，如果他们到达路径交的时间差 小于 交上最长的一条边就行。维护区间max
  • 相向时，判断是不是在点上相遇。二分或者倍增跳
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
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
// 我向你走🚶‍♂️了 99 步, 但看到你💃后退 1 步后，我就无法在向前了😭🏃‍♂️🏃‍♂️
#include <bits/stdc++.h>
#define MAXN 10005

using namespace std;
namespace OCTANE
{
	template <typename T> inline void read(T &x)
	{
		x = 0; bool f = 0; char ch = getchar();
		while (ch < '0' || ch > '9')
		{
			if (ch == '-') f = 1; ch = getchar();
		}
		while (ch >= '0' && ch <= '9')
		{
			x = (x << 1) + (x << 3) + (ch^48); ch = getchar();
		}
		if (f) x = -x;
	}
	template <typename T> inline void print(T x)
	{
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) print(x / 10);
		putchar(x%10 + '0');
	}
	template <typename T, typename ...TT>
	inline void read(T &x, TT &...y)
	{
		read(x); read(y...);
	}
	#define p_ putchar(' ');
	#define pn putchar('\n');
	#define print_(x) print(x), putchar(' ');
	#define printn(x) print(x), putchar('\n');

}using namespace OCTANE;

int n, m;

int cnte = 1, head[MAXN];
struct edge
{
	int to, nxt, dis;
}e[MAXN<<1];
void adde(int u, int v, int w)
{
	e[++cnte].to = v;
	e[cnte].dis = w;
	e[cnte].nxt = head[u];
	head[u] = cnte;
}

int fa[MAXN], siz[MAXN], dep[MAXN], son[MAXN];
int top[MAXN], dis[MAXN];
#define v (e[i].to)
void dfs1(int u, int dad)
{
	fa[u] = dad; siz[u] = 1; dep[u] = dep[dad] + 1;
	for (int i = head[u]; i; i = e[i].nxt) if (v != dad)
	{
		dis[v] = dis[u] + e[i].dis;
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[v] > siz[son[u]]) son[u] = v;
	}
}
void dfs2(int u, int tup)
{
	top[u] = tup;
	if (son[u]) dfs2(son[u], tup);
	for (int i = head[u]; i; i = e[i].nxt)
		if (v != fa[u] && v != son[u])
		dfs2(v, v);
	
}
#undef v
int LCA(int u, int v)
{
	while (top[u] != top[v])
	{
		if (dep[top[u]] < dep[top[v]])
			swap(u, v);
		u = fa[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}

int dwd[MAXN], cnt1, qwq[MAXN], cnt2;
bool vis[MAXN];
int pos[MAXN];

void get_path(int u, int &t, int to, int op)
{	
	dwd[++cnt1] = u;
	qwq[cnt1] = t;
	vis[u] = 1; pos[u] = cnt1;
	if (u == to) return;
	if (op)
		t = t - dis[u] + dis[fa[u]]; 
	else
		t = t + dis[u] - dis[fa[u]]; 
	get_path(fa[u], t, to, op);
}
void got_path(int u, int t, int to, int op)
{
	if (u == to) return;
	if (op == 1)
		got_path(fa[u], t + (dis[u] - dis[fa[u]]), to, op);
	else
		got_path(fa[u], t + (dis[u] - dis[fa[u]]), to, op);
	dwd[++cnt1] = u;
	qwq[cnt1] = t;
	vis[u] = 1; pos[u] = cnt1;
}
void walk(int u, int v, int t)
{
	for (int i = 1; i <= cnt1; i++)
	vis[dwd[i]] = 0;
	int lca = LCA(u, v), op = 0;
	if (dep[u] < dep[v])
	{
		t += dis[u] + dis[v] - 2 * dis[lca];
		swap(u, v); op = 1;
	}

	cnt1 = 0;
	
	get_path(u, t, lca, op);
	if (op == 1)
		t = t - dis[v] + dis[lca];
	else
		t = t + dis[v] - dis[lca];
	got_path(v, t, lca, op);

}
bool flag = 0;
void get_poth(int u, int &t, int to, int op)
{	
	// cout << u << ' ' << t << '\n';
	if (flag || u == to) return;
	int v = fa[u], fat;
	if (op)
		fat = t - dis[u] + dis[fa[u]];
	else
		fat = t + dis[u] - dis[fa[u]];
	
	if (vis[u] && vis[v])
	{
		int id = pos[u], fid = pos[v];
		if ((qwq[id] - qwq[fid]) * (t - fat) > 0)
		{
			if (qwq[id] > qwq[fid])
			{
				if (!(t < qwq[fid] || fat > qwq[id]))
					return flag = 1, void();
			}
			else
			{
				if (!(t > qwq[fid] || fat < qwq[id]))
					return flag = 1, void();
			}
		}
		else
		{
			if (qwq[id] > t && qwq[fid] < fat || t > qwq[id] && fat < qwq[fid])
			return flag = 1, void();
		}
	}
	t = fat;
	get_poth(fa[u], t, to, op);
}
void got_poth(int u, int t, int to, int op)
{
	// cout << u << ' ' << t << '\n';
	if (flag || u == to) return;
	int v = fa[u], fat;
	if (op == 1)
		fat = t + dis[u] - dis[fa[u]];
	else
		fat = t - dis[u] + dis[fa[u]];
	if (vis[v] && vis[u])
	{
		int id = pos[u], fid = pos[v];
		if ((qwq[id] - qwq[fid]) * (t - fat) > 0)
		{
			if (qwq[id] > qwq[fid])
			{
				if (!(t < qwq[fid] || fat > qwq[id]))
					return flag = 1, void();
			}
			else
			{
				if (!(t > qwq[fid] || fat < qwq[id]))
					return flag = 1, void();
			}
		}
		else
		{
			if (qwq[id] > t && qwq[fid] < fat || t > qwq[id] && fat < qwq[fid])
			return flag = 1, void();
		}
	}
	got_poth(fa[u], fat, to, op);
}
bool check(int u, int v, int t)
{
	int lca = LCA(u, v);
	int op = 0;
	if (dep[u] < dep[v])
	{
		t += dis[u] + dis[v] - 2 * dis[lca];
		swap(u, v);
		op = 1;
	}
	
	get_poth(u, t, lca, op);
	if (flag) return 1;
	if (op)
		t = t - dis[v] + dis[lca];
	else
		t = t - dis[v] + dis[lca];
	got_poth(v, t, lca, op);
	if (flag) return 1;

	return 0;
}

int main()
{
	read(n, m);
	for (int i = 1; i < n; i++)
	{
		int u, v, w; read(u, v, w);
		adde(u, v, w); adde(v, u, w);
	}
	dis[1] = 0; dfs1(1, 0); dfs2(1, 1);
	for (int i = 1; i <= m; i++)
	{
		flag = 0;
		int u, v, t;
		read(u, v, t);
		walk(u, v, t);
		// for (int j = 1; j <= cnt1; j++)
		// cout << dwd[j] << ' ' << qwq[j] << '\n';

		read(u, v, t);
		puts(check(u, v, t) ? "YES" : "NO");
	}
	return 0;
}

/*

8 6
1 2 3
1 3 1
1 4 2
2 5 5
2 6 1
5 7 2
5 8 4
5 3 2 7 4 2
8 6 1 1 7 6
4 5 1 4 5 10
7 8 3 3 4 5
6 7 6 5 1 2
2 1 10 8 3 3

*/

T3

kk 维空间随机游走，每维两个方向，走 nn 步到达的不同位置的期望。

ff 表示 nn 步之后回到这个位置的方案数（可以经过多次）
hh 表示 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
int main()
{
	freopen("qaq.in", "r", stdin);
	freopen("qaq.out", "w", stdout);
	read(n, k, mod); m = n / 2;

	C[0][0] = ppw[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		ppw[i] = ppw[i-1] * 2 * k%mod;
		C[i][0] = 1;
		for (int j = 1; j <= i; j++)
		C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
	}
	f[0] = 1;
	for (int i = 1; i <= k; i++)
	{
		memcpy(g, f, sizeof(f));
		memset(f, 0, sizeof(f));
		for (int j = 0; j <= m; j++)
		{
			for (int k = 0; j + k <= m; k++)
			f[j + k] = (f[j + k] + g[j] * C[(j + k)*2][k * 2]%mod * C[k * 2][k])%mod;
		}
	}
	for (int i = 0; i <= m; i++)
	{
		h[i] = f[i];
		for (int j = 1; j < i; j++)
		h[i] = (h[i] - h[j] * f[i-j]%mod +mod)%mod;
	}
	ans = (n + 1) * ppw[n] %mod;
	for (int i = 1; i <= m; i++)
	ans = (ans - h[i] * ppw[n-i*2]%mod * (n - i * 2 + 1)%mod +mod)%mod;
	print(ans);

	return 0;
}

11.5

T1

给定一个坐标 (x,y)(x, y) ，询问从原点跳 到这个点的最短步数和方案，每次只能移动到曼哈顿距离为 kk 的点

构造，当 x,yx, y 有一个大于 kk 就直接走，否则我建议你看代码

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
#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<int, int> pir;
 
int k;
 
pir f(int x, int y)
{
    if (x > y)
    {
        pir tmp = f(y, x); return {tmp.second, tmp.first};
    }
    if (x < 0)
    {
        pir tmp = f(-x, y); return {-tmp.first, tmp.second};
    }
    if (x + y >= 2 * k)
    {
        return {x, y - k};
    }
    if (x + y == k) return {0, 0};
    int t = k - (x + y) / 2;
    return {-t, y - k + x + t};
}
 
stack <pir, vector<pir> > st;
 
int x, y;
 
int main()
{
    scanf("%d %d %d", &k, &x, &y);
 
    if (!(k & 1)) if ((x & 1) != (y & 1)) return puts("-1"), 0;
 
    st.emplace(x, y);
    for (; x || y; x = st.top().first, y = st.top().second)
        st.emplace(f(x, y));
 
    st.pop(); printf("%d\n", st.size());
    while (st.size())
    {
        printf("%d %d\n", st.top().first, st.top().second); st.pop();
    }
    return 0;
}

T2

nn 个物品。 mm 个商店。 在第 jj 个商店买第 ii 个物品的费用是 ai,ja_{i,j} 。在 ii 个商店买东西需要 bib_i 的花费。

可以状压商店买不买，然后手玩发现答案是子集。高维前缀和整子集

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
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define ll long long
#define MAXN 100005
#define MXLG 26
using namespace std;
namespace OCTANE
{
	template <typename T> inline void read(T &x)
	{
		x = 0; bool f = 0; char ch = getchar();
		while (ch < '0' || ch > '9')
		{
			if (ch == '-') f = 1; ch = getchar();
		}
		while (ch >= '0' && ch <= '9')
		{
			x = (x << 1) + (x << 3) + (ch^48); ch = getchar();
		}
		if (f) x = -x;
	}
	template <typename T> inline void print(T x)
	{
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) print(x / 10);
		putchar(x%10 + '0');
	}
	template <typename T, typename ...TT>
	inline void read(T &x, TT &...y)
	{
		read(x); read(y...);
	}
	#define p_ putchar(' ');
	#define pn putchar('\n');
	#define print_(x) print(x), putchar(' ');
	#define printn(x) print(x), putchar('\n');

}using namespace OCTANE;

#define lowbit(x) (x & (-x))

struct node { int val, id; }a[MAXN][MXLG];
ll b[1<<25], f[1<<25];

int main()
{
	int n, m;
	read(n, m);

	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < m; j++)
			read(a[i][j].val), a[i][j].id = j;
		sort(a[i], a[i] + m, [&](node x, node y) {
			return x.val < y.val;
		});

		int s = 0;
		for (int j = 0; j < m; j++)
		{
			f[s] += a[i][j].val - a[i][j - 1].val;
			s |= 1 << a[i][j].id;
		}
	}

	int S = (1 << m) - 1;
	for (int i = 0; i < m; i++)
	for (int s = 1; s <= S; s++) if ((s >> i) & 1)
		f[s] += f[s ^ (1 << i)];
	
	for (int i = 0; i < m; i++) read(b[1 << i]);

	ll ans = INF;
	for (int s = 1; s <= S; s++)
	{
		if (s == lowbit(s)) continue;
		b[s] = b[lowbit(s)] + b[s ^ lowbit(s)];
	}

	for (int s = 0; s < S; s++)
		ans = min(ans, f[s] + b[s ^ S]);

	print(ans);

	return 0;
}

11.7

我爹 Ak 了

11.8

T1

一个长度为 nn 的01串，下标 0∼n−10 \sim n-1 。有两种操作：

  • A: 选择一个 xx ，将序列循环左移 xx 位。也就是新序列的第 (i+x) mod n(i+x) \bmod n 位对应原序列的第 ii 位。
  • B: 选择一个 xx , 满足序列的第 xx 个位置为 11 , 且第 (x+1) mod n(x+1) \bmod n 位置不为 11 , 交换序列的第 $x $ 个位置和第 (x+1) mod n(x+1) \bmod n 个位置的字符。
    构造一个由 ll 个长度为 nn 的01串构成的序列 ss ，使得序列中每个串恰好有 kk 个 11 。且对于 0≤i<l−10 \leq i<l-1 , s[i] 既可以通过一种 A 类型的操作, 也可以通过一种 B 类型的操作, 变为 s[i+1] 。

设 ss 中所有 11 下标之和为 ww

对于第一个操作，那么整体左移一位也就是说有一个 xx 使得 wi+x×k≡wi+1 mod nw_i + x\times k \equiv w_{i+1} \bmod n

对于第二个操作，那么就是说 wi+1≡wi+1 mod nw_i + 1\equiv w_{i+1} \bmod n

那么 n×k≡1 mod nn \times k \equiv 1 \bmod n ，也就是说 kk 在  mod   n\bmod \; n 有逆元 xx ，所以 n,kn, k 互质

然后构造方案的话，使 s[i]的 ik,i+1k,⋯ ,k+i−1k\frac{i}{k}, \frac{i+1}{k}, \cdots, \frac{k+i-1}{k} 为 11 就行

T2

nn 个字符串，从每个字符串里选出一个任意一个非空前缀按任意顺序组成一个新字符串。使得这个字符串最小

正解听难想的，因为 nn 很小 , 长度也很小。使用机房 :: 的随机化算法，随机选取 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
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 55;

int n;

string s[MAXN];

string dfs(int x)
{
	if (x == n) return s[x].substr(1, 1);
	string ans = dfs(x + 1);
	vector <string> tmp;
	for (int i = 1; i < s[x].size(); i++)
		tmp.push_back(s[x].substr(1, i) + ans);
	sort(tmp.begin(), tmp.end());
	return tmp[0];
}
string ans;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		cin >> s[i], s[i] = " " + s[i];
	ans = dfs(1);
	sort(s + 1, s + 1 + n);
	int tim = 4500;
	while (tim--)
	{
		int l = rand()% n + 1;
		int r = rand()% n + 1;
		swap(s[l], s[r]);
		string tmp = dfs(1);
		if (tmp < ans)
		ans = tmp;
		else swap(s[l], s[r]);
	}
	cout << ans;

	return 0;
}

T3

一棵 11 为根的树，从 11 出发, 每条边需要一定的价值才能开通，到达除 11 外的每个节点都可以获得一定的价值，询问要到达某个叶子节点开始需要准备的最小价值。

挺经典的打怪问题。

先考虑如果是一个序列的话。能赚的放在前边，能赚的里要钱少的放在前边，会亏的放在后边，会亏的里回血多的放在前面。

既然在树上，我们就找到这样排在最前边的节点，从他回到 11 ，直到能够到达询问的节点。

具体可以对每个结点维护一个 set 然后合并到根节点。

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
#include <bits/stdc++.h>

using namespace std;
namespace OCTANE
{
	template <typename T> inline bool read(T &x)
	{
		x = 0; bool f = 0; char ch = getchar();
		if (ch == EOF) return false;
		while (ch < '0' || ch > '9')
		{
			if (ch == '-') f = 1; ch = getchar();
		}
		while (ch >= '0' && ch <= '9')
		{
			x = (x << 1) + (x << 3) + (ch^48); ch = getchar();
		}
		if (f) x = -x; return true;
	}
	template <typename T> inline void print(T x)
	{
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) print(x / 10);
		putchar(x%10 + '0');
	}
	template <typename T, typename ...TT>
	inline void print(T x, char c)
	{
		print(x); putchar(c);
	}
	template <typename T, typename ...TT>
	inline int read(T &x, TT &...y)
	{
		return read(x) + read(y...);
	}

}using namespace OCTANE;

#define ll long long
#define pir pair<ll, ll>
const int MAXN = 2e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n;

multiset <pir> s[MAXN];

vector <int> e[MAXN];

ll val[MAXN], cost[MAXN];

void dfs(int u)
{
	for (int v : e[u])
	{
		dfs(v);
		if (s[u].size() < s[v].size()) s[u].swap(s[v]);
		s[u].insert(s[v].begin(), s[v].end());
		s[v].clear();
	}

	ll cst = cost[u], w = val[u] - cost[u];
	while (!s[u].empty() && (w <= 0 || cst >= s[u].begin()->first))
	{
		auto tmp = *s[u].begin();
		cst += max(0ll, tmp.first - cst - w);
		w += tmp.second;
		s[u].erase(s[u].begin());
	}

	if (w > 0) s[u].emplace(cst, w);
}

int main()
{
	read(n);
	cost[1] = INF;
	for (int i = 2; i <= n; i++)
	{
		int f; read(f, val[i], cost[i]);
		f++;
		e[f].push_back(i);
		if (val[i] == -1) val[i] = INF << 1;
	}

	dfs(1);

	cout << s[1].begin()->first - INF;

	return 0;
}

11.9

T1

nn 个点的树，有点权，您有血量，到达一个点就会获得这个点的点权，如果血量小于 00 就寄。每次给出初始血量，询问能否从 ss 走到 tt 点。可以经过别的的点，也可以多次经过一个点，没经过一次都会获得相应的点权

能行是这两种情况。

直接走，或者去到路径外的地方加血。

如果相邻两个点的值加起来是正的，那么就可以在这两个点加很多血量。

第一种情况维护前缀和最小值，第二种情况 DP 求每个点到达特殊点需要的最少血量。

T2

对于一个 1,…,n1,…,n1,\dots,n1,…,n 的排列 a1,…,ana_1,\dots,a_n ，定义 ii 处的顺序对数 f(i)f(i) 为满足 $ 1\leq j$ 且 aj<aia_j < a_i 的 jj 的数量，给定 nn ，对于每个 k=0,1,…,n−1k=0,1,\dots,n-1 求出满足 max⁡i=1n∣f(i)−g(i)∣=k\max_{i=1}^n |f(i) - g(i)| = k 的数量模 109+710^9+7

一个一个算不好整，我们把等号变成小于号，然后差分得到答案。

11.10

T1

∑in∑jm[gcd(i,j)≤a]lcm(i,j)\sum_{i}^{n} \sum_{j}^{m} \left [ gcd(i,j) \le a \right ] lcm(i, j)

n≤105n \le 10^5 并且 10410^4 次询问。

\begin{align} &\sum_{i}^{n} \sum_{j}^{m} \left [ gcd(i,j) \le a \right ] lcm(i, j) \nonumber\\ =&\sum_{i}^{n} \sum_{j}^{m} \left [ gcd(i,j) \le a \right ] \frac{ij}{gcd(i,j)} \nonumber\\ \end{align}

枚举 gcdgcd , i/ki / k 替换 ii , j/kj / k 替换 jj

∑kak∑i⌊nk⌋∑j⌊mk⌋[gcd(i,j)=1]ij\sum_{k}^{a} k\sum_{i}^{\left \lfloor \frac{n}{k}\right \rfloor} \sum_{j}^{\left \lfloor \frac{m}{k}\right \rfloor} \left [ gcd(i,j) = 1 \right ]ij

开始经典莫反

\begin{align} &\sum_{k}^{a} k \sum_{i}^{\frac{n}{k}} \sum_{j}^{\frac{m}{k}} \left [ gcd(i,j) = 1 \right ]ij \nonumber\\ =&\sum_{k}^{a} k \sum_{d}^{\left \lfloor \frac{lim}{k}\right \rfloor} \mu(d) d^2\sum_{i}^{\left \lfloor \frac{n}{kd}\right \rfloor} \sum_{j}^{\left \lfloor \frac{m}{kd}\right \rfloor} ij \nonumber\\ =&\sum_{k}^{a} k \sum_{d}^{\left \lfloor \frac{lim}{k}\right \rfloor} \mu(d) d^2\sum_{i}^{\left \lfloor \frac{n}{kd}\right \rfloor} \times \sum_{j}^{\left \lfloor \frac{m}{kd}\right \rfloor} \nonumber\\ \end{align}

现在后面两个 O(1)O(1) 等差数列整 前面调和级数 单次询问 O(nlogn)O(nlogn)

现在可以整除分块 kk 和 dd 。单次询问是接近 O(n)O(n) 。 都只能50pts

所以还需优化

注意到答案随 aa 单调增

可以先把询问离线下来，按从小到大排序。新加入一个 aa 就加入后面那一坨对应了答案。可以用树状数组维护

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
#include <bits/stdc++.h>
#define ll long long
const ll mod = 1e9 + 7;
const ll inv2 = 500000004;
const int MAXN = 1e5 + 5;
const int maxn = 1e5;

using namespace std;
namespace OCTANE
{
	template <typename T> inline bool read(T &x)
	{
		x = 0; bool f = 0; char ch = getchar();
		if (ch == EOF) return false;
		while (ch < '0' || ch > '9')
		{
			if (ch == '-') f = 1; ch = getchar();
		}
		while (ch >= '0' && ch <= '9')
		{
			x = (x << 1) + (x << 3) + (ch^48); ch = getchar();
		}
		if (f) x = -x; return true;
	}
	template <typename T> inline void print(T x)
	{
		if (x < 0) putchar('-'), x = -x;
		if (x > 9) print(x / 10);
		putchar(x%10 + '0');
	}
	template <typename T, typename ...TT>
	inline void print(T x, char c)
	{
		print(x); putchar(c);
	}
	template <typename T, typename ...TT>
	inline int read(T &x, TT &...y)
	{
		return read(x) + read(y...);
	}

}using namespace OCTANE;

#define cntp prime[0]
bool pis[MAXN];
int prime[MAXN];
ll mu[MAXN];

struct Bit
{
	#define lowbit(i) (i & -i)
	ll t[MAXN], lim;
	void add(int i, ll val)
	{
		if (!i) return;
		for (; i <= lim; i += lowbit(i)) t[i] = (t[i] + val)%mod;
	}
	ll query(int i)
	{
		ll res = 0;
		for (; i; i -= lowbit(i)) res = (res + t[i])%mod;
		return res;
	}
	ll query(int l, int r)
	{
		return (query(r) - query(l-1) +mod)%mod;
	}
}t;

void get_prime(int n)
{
	pis[1] = mu[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		if (!pis[i])
		{
			prime[++cntp] = i; mu[i] = -1;
		}
		for (int j = 1; j <= cntp && i * prime[j] <= n; j++)
		{
			pis[i * prime[j]] = 1;
			if (i % prime[j] == 0) break;
			mu[i * prime[j]] = -mu[i];
		}
	}
}

struct que { int n, m, a, id; }q[MAXN];

ll S(ll x, ll y) { return (x + y) * (y - x + 1)%mod * inv2%mod; }

void add(int x)
{
	for (int i = x; i <= maxn; i += x)
	{
		t.add(i, 1LL*i * 1LL*i / x%mod * mu[i / x]%mod);
	}
}
ll work(int n, int m)
{
	ll res = 0;
	int N = min(n, m);
	for (int l = 1, r; l <= N; l = r + 1)
	{
		r = min(n / (n / l), m / (m / l));
		res = (res + S(1LL, (ll)(n / l)) * S(1LL, (ll)(m / l))%mod * t.query(l, r)%mod) %mod;
	}
	return res;
}

ll ans[MAXN];
int main()
{
	t.lim = maxn;
	get_prime(maxn);
	int T; read(T);
	for (int i = 1; i <= T; i++)
	{
		int n, m, a;
		read(n, m, a) ;
		q[i] = { n, m, a, i };
	}
	sort(q + 1, q + 1 + T, [&](que a, que b) { return a.a < b.a; });

	int now = 1;
	for (int i = 1; i <= T; i++)
	{
		while (now <= q[i].a)
			add(now++);
		ans[q[i].id] = work(q[i].n, q[i].m);
	}
	for (int i = 1; i <= T; i++)
		print(ans[i], '\n');

	return 0;
}

T2

一张联通的平面图，两种操作：

  • 删去边 (x,y)(x, y) ，并且询问几个连通块
  • 询问点 x,yx, y 是否在同一连通块内

这是一张平面图。就建出它的对偶图来

我们每删去一条边，就把它在对偶图对应的边连起来。当对偶图的边把一个部分围起来时，这个部分就形成了一个新的连通块。

对于第二种询问，我们在形成一个新连通块中，可以对新的连通块重新编号。但是尽量遍历少的点保证时间复杂度，我们就选择大小小的联通块来标号。

11.11

T1

给定一个序列，每个数都是由两个不相同的质数的乘积。若 a=p1∗q1(p1<q1),b=p2∗q2(p2<q2)a=p_{1} * q_{1}\left(p_{1}<q_{1}\right), b=p_{2} * q_{2}\left(p_{2}<q_{2}\right) ， q1=p2q_1 = p_2 时， bb 能接在 aa 后。最长能接多长？。

对于每个数，向 pp 的值和它的 qq 相等的连边，表示它俩能接起来。

最后建出来是一张 DAG 。在上面找最长链即可。

T2

nn 个点 mm 条边，给一个生成树，可以把一条边权减一，询问要多少操作才能使他成为最小生成树。

两个点在如果有路径的话，那么生成树的路径上的每一条边的边权都不能大于它才能成为最小生成树。

所以枚举每条非树边，对树上路径进行最小值覆盖。最后边权减少了多少就是答案。

T3

给定两个数 AA , BB 。问有多少序列满足：

  • 序列递增
  • 值域 ∈[A,B]\in [A, B]
  • 所有数字两两互质。

虽然 A,BA, B 是 101810^{18} 级别，但是 B−A≤100B - A \le 100 ，那么可以状压 100100 以内的质数来 DPDP 。

只出现一次也没影响，那么状压只出现多次的质因子就行了。

DP 就是枚举补集的子集更新。

T4

给定一个序列，询问序列的最长子串。能够最多加 kk 个数构成公差为 dd 的等差数列。

考虑能构成等差数列的话，那么字串里的每个数  mod d\bmod d 都相等。所以判断条件就是  mod 的\bmod 的 相等并且除的极差 −- 区间长度不超过 kk 。

右端点确定，左端点具有单调性。所以枚举右端点，线段树维护每个左端点的极差。

枚举整俩单调栈，然后在线段树上二分找答案。

11.12

T1

一颗带权树，树上有黑点和白点，求割掉一些边，把黑点和白点分开需要的最小代价。

fu,0/1f_{u, 0/1} 表示在 uu 强制为 黑点/白点 时的答案。

和儿子不一样就要割掉这条边。不合法情况赋极小值

T2

nn 道题目，每道题您需要 aia_i 的时间来 A 掉。做 mm 道题您就能 AuAu ，但是您不知道每个题的难度，只知道找人写题目的难度构成 aa 这个序列。求使用最优策略最坏要多长时间才能 AuAu 。

因为是最坏，所以做的题的难度一定是下降的。也就是说题目难度和时间是一个下降的直线。

那么要 A 一道题一定是每次都用这道题的时间做，然后发现没A ，就换下一道题，知道 A 掉这道题。

设 fi,jf_{i, j} 表示做到第 ii 道题，已经 A 了 jj 到需要的时间。

fi,j=fk,j−1+(i−k)∗aif_{i,j} = f_{k, j-1} + (i-k) * a_i

发现可以斜率优化。

11.14

T1

平面直角坐标系上，从 (a,b)(a, b)，每次可以上下左右走一个单位(保证坐标非负)。走到 (c,d)(c,d)。疲劳值初始值为 00。如果当前位置 (x,y)(x,y) 满足 x and⁡ y>0x \, \operatorname{and} \, y > 0，疲劳值就要加 11，否则疲劳值不增加。求最小疲劳值。

打个表可以发现，xand⁡y=0x \operatorname{and} y = 0 的位置组成了一个谢尔宾斯基三角形。

而且是四联通的，所以我们从 (a,b)(a,b) 走到 (c,d)(c,d) 就有两种可能是最优的方案：

  • 都走到费用为 00 的点。
  • 直接走

那个三角形看上去挺递归的，我们也递归求。

找到覆盖 (x, y) 的三角形。由于 dis(x,y)=dis(y,x)dis(x, y) = dis(y, x) ，设 x≤yx \le y。

设三角形的边长为 LL 。

  • 如果 x+y≥Lx + y \ge L ，说明 (x,y)(x, y) 位于该正方形右下部分的等腰直角三角形，走到三角形三边的疲劳值分别是 x+y−L,L−x−1,L−y−1x + y - L, L - x - 1, L - y - 1，取最小值

  • 否则 (x,y)(x, y) 在该正方形右上部分。把 向左平移 L/2L / 2 长度不改变答案，所以直接平移递归下去。

T2

给你一个只包含字符 a 和 b 的字符串 ss，你需要求出最多有多少不相交的子序列 abab。
不相交的定义为：对于 ss 种的每个字符，其最多处于一个子序列中。
Solution

发现 abab 可以拆成两个 ab，问题就变成了去除尽可能多的不相交的 ab 。
不能同时选的 ab 存在一个分界点 p∈[1,n]p \in [1,n]，使得所有 a 的位置小于等于 pp，所有 bb 的位置大于等于 pp。
设不能同时选的 ab 的最大值为 mxmx，共有 cntcnt 对 ab，那么答案就是 min⁡(⌊cnt2⌋,cnt−mx)\min(\lfloor \frac{cnt}{2} \rfloor, cnt-mx)。

现在就需要使 mxmx 最小化，这个可以使每个 bb 去匹配它前面最近的未被匹配的 aa，这样可以使这一对 ab 包含的其他 ab 最少，所以用一个栈做一下括号匹配就行了。

T3

用 00 代表空树，如果一个节点没有左子树，那么认为它的左子树是空树(右子树同理)。对任意二叉树 AA，0≤A0 \le A 成立；对任意非空二叉树 AA，A≤0A \le 0 不成立，则对于非空二叉树 A,BA,B，A≤BA \le B 当且仅当 ls⁡(A)≤ls⁡(B)\operatorname{ls}(A) \le \operatorname{ls}(B) 且 rs⁡(B)≤rs⁡(A)\operatorname{rs}(B) \le \operatorname{rs}(A)。
问有多少不同在 AA 上加 mm 个点的 BB ，满足 A≤BA \le B。

我们只能在特定的节点放，可以一次 dfsdfs 求出。

有 cc 个互相独立的位置，放上 mm 个节点，问最终形成的二叉树森林有几种。

设 f(c,m)f(c,m) 表示上述问题的答案。

f(c,m)=f(c+1,m−1)+f(c−1,m)f(c,m) = f(c+1,m-1) + f(c-1, m) ，因为

如果有一个节点挂在第 cc 个位置，节点数减少 11，互相独立的位置数反而增加了 11，状态转移为 f(c+1,m−1)f(c+1,m-1)。

如果没有节点挂在第 cc 个位置，也就是再也不用位置 cc，状态转移为 f(c−1,m)f(c-1,m)。

这个式子可以转化为路径计数：

如果位置在 (x,y)(x,y)，下一步可以走到 (x−1,y+1)(x-1,y+1) 或 (x+1,y)(x+1,y)，但始终保证 x>0x > 0，求从 (1,0)(1,0) 走到 (c,m)(c,m) 的路径条数。

把坐标变换为 (x+y,y)(x+y, y)，得到更熟悉的形式：

如果位置在 (x,y)(x,y)，下一步可以走到 (x,y+1)(x,y+1) 或 (x+1,y)(x+1,y)，但始终保证 x>yx > y，求从 (1,0)(1,0) 走到 (c+m,m)(c+m,m) 的路径条数。

答案为 Cc+2m−1m−Cc+2m−1cC_{c+2m-1}^{m} - C_{c+2m-1}^{c}

11.15

T1

爆搜

T2

现在有一个长度为 nn 的全 00 序列，并且有 mm 个不同的操作，(li,ri,xi,ci)\left(l_{i}, r_{i}, x_{i}, c_{i}\right) 。你可以花费 CC 购买 ci<Cc_i < C 的所有操作。每个操作可以把去区间或一个小于 2x−12^{x-1} 的数。

区间操作差分一下，每次相当于 ll 和 r+1r+1 连边，拆位维护连通块个数。 答案就是 2n2cnt\frac{2^n}{2^cnt} 。

T3

给定一棵树，询问满足 dis(i,j)≤j−i,(j>i)dis(i, j) \le j - i, (j > i) 的点对有多少个。

统计路径问题就点分治一下。

统计答案有两个限制，不好整，看能不能消掉一个 ii 或 jj 。

disdis 表示到当前分分治的根的距离

disi+disj≤j−idisi−i+disj−j≤−2i dis_i + dis_j \le j - i \\ dis_i - i + dis_j - j \le -2i\\

就重新定义 disdis 为原来的 disdis 减去下标。

那么对于 ii 来说 满足条件的 jj 就是 disj≤−disi−2idis_j \le -dis_i - 2i 。

这是 i<ji < j 的情况。

否则 disdis 加上下标差不多维护。

维护权值树状数组即可。

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
#include <bits/stdc++.h>
#define ll long long
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
using namespace std;
namespace OCTANE
{
    #define BUFS1Z 1000000
    char ibuf[BUFS1Z], obuf[BUFS1Z];
    char *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
    #ifdef ONLINE_JUDGE
        #define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,BUFS1Z,stdin),p1==p2)?(EOF):(*p1++))
        #define putchar(x) ((p3==obuf+BUFS1Z)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
    #endif
    struct freadender
    {
        ~freadender()  { fwrite(obuf, p3-obuf, 1, stdout); }
        bool flag = 0;
        operator bool() { return flag; }
    }io;
    template <typename T> inline bool read(T &x)
    {
        x = 0;
        bool f = 0; char ch = getchar();
        if (ch == EOF) return 0;
        while (ch < '0' || ch > '9')
        {
            if (ch == '-') f = 1; ch = getchar();
        }
        while (ch >= '0' && ch <= '9')
        {
            x = (x << 1) + (x << 3) + (ch^48); ch = getchar();
        }
        if(f) x = -x; return 1;
    }
    template <typename T> inline void print(T x)
    {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) print(x / 10);
        putchar(x % 10 + '0');
    }
    template <typename T, typename ...TT>
    inline void print(T x, char c)
    {
        print(x); putchar(c);
    }
    template <typename T, typename ...TT>
    inline int read(T &x, TT &...y)
    {
        return read(x)+read(y...);
    }
    
}using namespace OCTANE;

vector <int> e[MAXN];
int n;

struct bit
{
    int t[MAXN*4], lim;
    #define lowbit(i) (i & -i)
    
    void add(int i, int val)
    {
        i += 3 * n;
        if (!i) return;
        for (; i <= lim; i += lowbit(i)) t[i] += val;
    }
    int query(int i, int res = 0)
    {
        i += 3 * n;
        for (; i; i -= lowbit(i)) res += t[i];
        return res;
    }
}t1, t2;

int siz[MAXN], sixz, tot, rt;
int dis[MAXN];
bool vis[MAXN];
ll ans;

void get_zx(int u)
{
    int msiz = 0;
    vis[u] = siz[u] = 1;
    for (int v : e[u]) if (!vis[v])
    {
        get_zx(v);
        siz[u] += siz[v];
        msiz = max(msiz, siz[v]);
    }
    msiz = max(msiz, tot - siz[u]);
    if(msiz <= sixz) {sixz = msiz; rt = u;}
    vis[u] = 0;
}
int top1, top2;
pair <int, int> sta1[MAXN];
pair <int, int> sta2[MAXN];
void get_dis(int u)
{
    vis[u] = 1;
    sta1[++top1] = {dis[u], u};
    for (int v : e[u]) if (!vis[v])
    {
        dis[v] = dis[u] + u + 1 - v;
        get_dis(v);
    }
    vis[u] = 0;
}
void get_ans(int u)
{
    top2 = 0;
    vis[u] = 1;
    t1.add(-u, 1);
    t2.add(u, 1);
    for (int v : e[u]) if (!vis[v])
    {
        top1 = 0;
        dis[v] = 1 - v; get_dis(v);

        for(int j = 1; j <= top1; j++)
        {
            ans += t1.query(-sta1[j].first - 2*sta1[j].second);    
            ans += t2.query(-sta1[j].first);
        }
        for(int j = 1; j <= top1; j++)
        {
            sta2[++top2] = sta1[j];
            t1.add(sta1[j].first, 1); 
            t2.add(sta1[j].first + 2 * sta1[j].second, 1); 
        } 
    }
    t1.add(-u, -1);
    t2.add(u, -1);
    for(int i = 1; i <= top2; i++) t1.add(sta2[i].first, -1);
    for(int i = 1; i <= top2; i++) t2.add(sta2[i].first + 2 * sta2[i].second, -1);
    vis[u] = 0;
}
void solve(int u)
{
    get_ans(u);
    vis[u] = 1;
    for (int v : e[u]) if (!vis[v])
    {
        tot = siz[v]; sixz = INF;
        get_zx(v);
        solve(rt);
    }
}
int main()
{
    read(n);
    t1.lim = 4 * n;
    t2.lim = 4 * n; 
    for(int i = 1; i < n; i++)
    {
        int u, v; read(u, v);        
        e[u].push_back(v);
        e[v].push_back(u);
    }
    tot = n; sixz = INF;
    get_zx(1);
    solve(rt);
    print(ans);

    return 0;
}
11月每日总结
https://ve1bae.github.io/2022/11/04/11月每日总结/
本文作者
Veibae
发布于
2022年11月4日
更新于
2022年11月15日
许可协议
CC BY-NC-SA 4.0
署名-非商业性使用-相同方式共享 4.0 国际。

更新于：2022年11月15日

评论