几度风雨几度春秋 风霜雪雨博激流
历尽苦难痴心不改 少年壮志不言愁

n 个格子上有 m 个棋子,Alice 和 Bob 轮流行动,每次可以选择一个棋子向左移动至少一步,但不能跨越已有的棋子,不能的移动的一方算输,求 Alice 必胜的方案数。

READ MORE

有一个 n 个数的序列,每一个数在 1 \dotsc D 中随机生成,定义一个序列是合法的当且仅当能取出至少 m 个对子(相同的数),对于 D^n 种可能的序列,求合法序列数。D \leq 10^5, n, m \leq 10^9

羡慕你们能去 CTS 的 [大哭]

READ MORE

给定一个长为 n 的序列 A_1,\dotsc,A_n ,求一个长为 n 的不下降序列 B_1,\dotsc,B_n ,使得 \sum_{i=1}^n (A_i-B_i)^2 最小,只需要输出最小值。

以及 m 次互相独立的修改,每次会更改一个位置的值,要求输出修改后的答案。答案对 998244353 取模。

n,m \leq 10^5

READ MORE

傻逼题,写来放松身心。

考虑到 \displaystyle dep_u^k = \sum_{i=0}^{\infty} dep_{fa^i(u)}^k - dep_{fa^{i+1}(u)}^k,假设我们要求 \displaystyle dep_{\operatorname{lca}(u, v)},可以把 u1 的路径上每个点 x 加上 dep_x^k - dep_{fa(x)}^k 的权值,查询时从 v 向根节点跳把沿途的权值加上即可。

离线所有查询到 x 上,扫描 x,树剖维护修改和查询即可。

READ MORE

定义一个基环树的点分治过程如下

  • 选定一个点 u
  • 断开所有与 u 相连的边
  • 对于剩下的每个联通块递归点分

定义一种选点方式的代价为每层的 size 之和。

求每次选点都在当前联通块内随机选择的期望代价。

n \leq 3000

READ MORE

给定 n 个节点的树,每个点有个权值 a_i,保证 \{a_{1 \cdots n}\} 是一个 1n 的排列,求:

\frac 1 {n(n-1)} \sum_{i=1}^n \sum_{j=1}^n \varphi(a_i \times a_j) \times \operatorname{dist}(i, j)

READ MORE

一道非常有意思的(动态)DP 题。

讲道理的我考场上是会 70 分的但是由于 T1 傻逼了太久没调出来(报警了)

假设不修改的情况下答案为 W ,叶子节点的个数为 m,我们把总共的 2^m - 1 种选法分两种情况讨论:

  • W 被选中,这样的情况一共有 2^{m-1} 种,可见只要花费 1 的代价一定可以使根节点的值发生改变,下面不再讨论;
  • W 未被选中,这样的情况一共有 2^{m - 1} - 1 种,我们可以考虑 DP 解决。枚举当前的 C,求出所有花费代价 \leq C 的方案数,显然如果我们可以求得对于 C \in [L - 1, R],差分后就可得到答案数组。

READ MORE

傻逼题。

设当前的数为 x = a_k

如果 x 没有被修改,那么可以修改的数为 \displaystyle{\{{a_i, i \neq k \text{ and } (a_i < \frac x2 \text{ or } a_i \geq x)}\}}

如果 x 被修改,可以先把所有的数都修改掉,再撤销一些修改(也就是除以 2),那么可以修改的数为 \displaystyle{\{ a_i, i \neq k\text{ and } (a_i \geq 2x \text{ or } a_i < x) \}}

注意处理 a_i = 0 的情况。

READ MORE