24.10.12

KinNa-Sky / 2024-10-13 / 原文

所谓 NOIp 模拟赛。

~~怎么会有 NOIp 模拟赛放 AT 银牌题呢哈哈~~。

A

暴力：枚举点对 $(c, s)$，合法点对的贡献是 $(A - c + 1)\times (B - s + 1)$。

对于 $x = 1$ 的部分分，打表发现合法点对只有 $c = s$ 的点对，那么贡献为

\[\begin{aligned} &\sum_{i = 1}^{\min(A, B)}(A - i + 1)(B - i + 1)\\ =&\sum_{i = 0}^{\min(A, B) - 1} (A - i)(B - i) \\ \end{aligned} \]

令 $C = \min(A, B) - 1$.

\[\begin{aligned} =&ABC - (A + B) * \sum_{i = 1}^{C}i +\sum_{i = 1}^{C}i^2 \end{aligned} \]

模数是 $2^{23}$，自然数和建议开 __int128 直接乘，$3$ 的逆元是 $2796203$。

然后暴力跑了几组数据发现 $s \neq c$ 的合法点对数量好像不是很多，并且 $s$ 很小。

考虑 $s(c + x) | c(s + x)$ 化成 $\dfrac{c(s + x)}{s(c + x)} = d$，那么枚举 $s$ 可以算出 $c = \dfrac{dsx}{x + s - ds} \in [1, A]$，这里由于要求 $c \neq s$，所以 $d > 1$，那么 $s \le x$，并且 $d\in\left[\max\left(2, \dfrac{x + s}{sx + s}\right), \dfrac{x + s}{\frac{sx}{A} + s}\right]$，枚举 $s$ 和 $d$，差不多是调和级数 $O(x \ln x)$。

B

每个点集均满足以下两个条件之一：

该点集中的元素两两之间均有边。

该点集中的元素两两之间均没有边。

对于任意点 $u$ 以及任意不包含 $u$ 的点集 $S$，需满足以下两个条件之一：

$S$ 中的每个节点与 $u$ 都有边。

$S$ 中的每个节点与 $u$ 都没有边。

这些点集的并是点的全集。

那么两个点 $x, y$ 在同一个集合里的充分条件是 $\forall i \neq x \wedge i \neq y,w(x, i) = w(y, i)$。

用异或哈希维护每个点相连的集合。

维护 $hash_x$ 表示与 $x$ 相连的点的权值异或和，那么两个点可以在一个集合满足 $hash_x = hash_y$（两点间无边）或 $hash_x \oplus val_x = hash_y \oplus val_y$（两点间有边）。

先算出所有哈希值。依次加入点，维护所有出现的哈希值，如果加入 $x$ 时如果 $hash_x$ 或 $hash_x \oplus val_x$ 存在，说明 $x$ 可以放到已有集合，不然 $x$ 就要新开一个集合。

修改时先把 $x, y$ 从维护的值里删去，修改后在加进去。

C,D

战绩可查 23/0/0，改不动。

对了这是 D。C 比 D 还抽象。

P4045

P4045 [JSOI2009] 密码

经典 AC 机上 DP，要求每个串都包含状压一下就好了。

然后对于输出方案可以搜出每个状态是否可行，然后输出就好了。

int g[N][N][1 << 10];
bool dfs(int l, int x, int sta) {
	if (~g[l][x][sta]) return g[l][x][sta]; g[l][x][sta] = 0;
	if (l == L) {return g[l][x][sta] = sta == Base;}
	for (int i = 0; i < 26; ++i) g[l][x][sta] |= dfs(l + 1, tr[x][i], sta | ed[tr[x][i]]);
	return g[l][x][sta];
}

void dfs2(int l, int x, int sta, string ans) {
	if (l == L) {cout << ans << endl; return ;}
	for (int i = 0; i < 26; ++i) if (g[l + 1][tr[x][i]][sta | ed[tr[x][i]]])
		dfs2(l + 1, tr[x][i], sta | ed[tr[x][i]], ans + char(i + 'a'));
}

P5369

P5369 [PKUSC2018] 最大前缀和

第一反应：令 $f_{sta, mx}$ 表示填了 $sta$，最大前缀和是 $mx$ 的方案数，第二维用 map。

喜提 55pts.

发掘最大前缀和的性质，假设 $\sum_{i=1}^p a_i$ 是最大前缀和，那么

不存在 $x(1 < x \le p)$ 使得 $\sum_{i = x}^p a_i < 0$，即没有一段真后缀和 $< 0$。
不存在 $x(p < x \le n)$ 使得 $\sum_{i = p + 1}^x a_i \ge 0$，即没有一段前缀和 $\ge 0$。

设 $f_{sta, 0/1}$ 表示 $sum_{sta}$ 否 / 是小于 0，且任何真后缀和 $\ge 0$ 的排列数，$g_{sta}$ 表示 $sta$ 任何前缀和都 $< 0$ 的排列数。

转移 $f$ 时相当于从后往前加数，转移 $g$ 时从前往后加数，满足对应条件转移。

\[\begin{aligned} f_{sta, 0} &\gets \sum_{i \in sta} f_{sta\setminus i, 1} & (sum_{sta} < 0)\\ f_{sta, 1} &\gets \sum_{i \in sta} f_{sta\setminus i, 1} & (sum_{sta} \ge 0)\\ g_{sta} &\gets \sum_{i \in sta} g_{sta\setminus i} & (sum_{sta} < 0) \end{aligned} \]

答案为 $\displaystyle \sum_{S} sum_{sta} \times (f_{sta, 0} + f_{sta, 1}) \times g(\complement_{U}sta)$。