9.30
A
题目描述
给定 \(5\) 个长度为 \(n\) 的整数序列 \(A,B,C,D,E\)，求
\[\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n\sum_{l=1}^l\sum_{m=1}^n med(A_i,B_j,C_k,D_l,E_m) \mod 998244353 \]其中，\(med(a,b,c,d,e)\) 为 \(a,b,c,d,e\) 的中位数。
枚举中位数，计算即可。
B
题目描述
给定一个 \(n\) 个点 \(m\) 条边的有向图。不保证不存在重边自环。
记 \(f(x,y,k)\) 表示从 \(x\) 到 \(y\) 经过恰好 \(k\) 条边的不同路径数量，两条路径不同当且仅当存在存在某个 \(i\) 使得两条路径的第 \(i\) 条边不同。
称一个有向图是有趣的，当且仅当存在 \(x,y\)，不存在任何正整数 \(M\)，使得 \(k \ge M\) 时 \(f(x,y,k)\) 为一常数，也即 \(\lim\limits_{k\to+ \infty} f(x,y,k)\) 不存在。
你需要判断给定的有向图是不是有趣的。
仔细分析，如果有长度 \(\ge 2\) 的环，那么是有趣的。
如果两个自环可以互相到达，那么也是有趣的。
注意一个点有两个自环的情况。
否则就是无趣的。
C
题目描述
有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\)个，\(A\) 和 \(B\) 玩游戏，\(A\) 先手，每次操作可以进行以下操作：
- 选定一个还有石子的石子堆 \(i\)，记剩下的石子为 \(a_i'\)。
- 选定一个 \(1\le x\le a_i'\)，将该堆中的 \(x\) 个石子移走。
- 选定一个 \(0\le y\le a_i'-x\)，将该堆中的 \(y\) 个石子以任意方式分配到剩余的非空石子堆中。
第一个不能操作者输，问 \(A\) 是否有必胜策略，多测。
如果所有数出现次数都为偶数则为必败态。
-
如果没有石子，那么所有数出现次数为偶数，此时为必败态。
-
对于一个必胜态，一定能转移到必败态。
设出现次数为奇数的点从小到大排序为 \(a_1,\cdots,a_m\)。如果 \(m\) 是奇数，可以用 \(a_m\) 把 \(a_x\) 补成 \(a_{x+1}\)，\(x<m\) 且为奇数。最后剩下的 \(a_m\) 拿走。如果 \(m\) 是偶数，可以用 \(a_m\) 把 \(a_x\) 补成 \(a_{x+1}\)，\(x<m\) 且为偶数，\(a_m\) 留下 \(a_1\) 颗石子，最后剩下的 \(a_m\) 拿走。
-
对于一个必败态，一定只能转移到必胜态。
所有数去重后从小到大排序为 \(a_1,\cdots,a_m\)。如果拿走 \(a_t\)，那么第 \(a_t\) 的出现次数就是奇数，需要用 \(a_x(x < t)\) 去把 \(a_t\) 补成偶数出现次数。这时候 \(a_x\) 的出现次数又变成奇数了，以此类推。最终 \(a_1\) 出现次数是奇数，只能用拿走部分后剩下的 \(a_t'\) 去补。这时候发现总和是不变的，但是要求每一步至少总和 \(-1\)，所以是不能转移到必败态的。
D
题目描述
你有一个奇怪的计数器，计数器上有一个数字 \(x\)，每次你可以做如下操作：
选择一个 \(x=\overline{b_kb_{k-1}\cdots b_1b_0}_{(10)}\)中的一个数位 \(b_i\)。将 \(x\) 变为 \(x+b_i\) 或者 \(x-b_i\)。
例如，当 \(x=(616)_{10}\) 时，你可以选择 \(b=1\)，然后让 \(x\) 变为 \(x−b=(615)_{10}\)。
你想要通过最少步数把 \(x\) 变成 \(y\)，问最少步数是多少。
分治。对于区间 \([l,r]\)，找到中间的 \(9\) 个数 \(x,\cdots,x+8\)。
由于每次最多走 \(9\) 个数，所以任意两个跨过中间数的点，在 \([x, x+8]\) 中，一定停留至少一个点。
对于中间的点分别对于区间 \([l,r]\) 跑最短路，处理区间 \([l,r]\) 的点到中间点的最短路和中间点到 \([l,r]\) 的最短路。
向下分治 \([l,x-1]\) 和 \([x+9,r]\) 即可。
询问时找到对应区间，枚举中间停留点即可。
标签：Training,le,次数,必败,sum,石子,Records,奇数 From： https://www.cnblogs.com/Estelle-N/p/18442333