PKUSC2022 游记

上午随便看了点题，感觉没看什么题就开考了。

开考之后先看 T1，发现 T1 好像不是那么简单。

T1 ：

九条可怜有两个账号，她每次都会打 \(\rm rating\) 低的号。

九条可怜每次打比赛的 \(\rm rating\) 变化量的绝对值都 \(\le m\)。她的 \(\rm rating\) 的变化量为 \(i\) 的概率为 \(\frac{w_i}{10^8}\)。如果她的 \(\rm rating\) 小于 \(0\)，那么她的 \(\rm rating\) 会变成 \(0\)。

求九条可怜的 \(\rm rating\) 高的号的 \(\rm rating\) 最后是多少。答案对 \(998244353\) 取模。

数据范围：\(n \le 1000, m \le 50, \max_{i=1}^m w_i \ge 1\)。

然后想着想着就会了，然后写着写着就想到了一种更好写也更不容易除 \(0\) 的方法，于是果断换方法，大概在 \(45\) 分钟的时候通过了。

然后看 T2，是计算几何题，不过更像是数据结构。

T2 :

给定 \(n\) 条线段 \((a_i,b_i) \to (c_i,d_i)\)，保证 \(a_i < c_i\)，\(b_i > d_i\)，\(q\) 次询问，每次询问 \((-C,-C)\) 和 \((x_i,y_i)\) 围成的矩形中，每条线段出现的长度之和。

数据范围：\(n \le 10^5\)，\(q \le 1.5 \times 10^5\)，\(C = 3 \times 10^5\)，\(|a_i|,|b_i|,|c_i|,|d_i| \le C\)。

想了一会儿终于会了，感觉挺有趣。但是感觉很难写，于是就先看 T3。

然后发现原来 T3 才是签到题。花了 \(\rm eps\) 的时间过掉了。这个时候大概 \(\rm 80\min\)。

T3 :

给定 \(n\) 只猫，每只猫都可能想被撸或者不想被撸。集合 \(S\) 的猫想被撸的概率是 \(f_S\)。设 \(p_i\) 为第 \(i\) 只猫想被撸的概率（即 \(p_i = \sum_{i \in S} f_S\)）。你要设计一个二维数组 \(g\) 满足 \(\sum_{i \in S} g_{S,i} = f_S\)，使得满足 \(\forall i, \sum_{i \in S} g_{S,i} \ge p_i \times c\) 的 \(c\) 最大化。

数据范围：\(n \le 20\)。

于是开始想 T2 怎么实现。

想了想就大致想清楚了。既然是 IOI 赛制，那么就随便交！先打了个暴力，然后一步一步该对。最后大概在 \(\rm 175min\) 的时候过了，写了 \(5k\)。

T1 题解

容易想到设计一个 DP：\(\rm DP_{i,j}\) 表示大号 \(\rm rating = i\) 且小号 \(\rm rating = j\) 的期望。

我们考虑如何做这个 \(\rm DP\)：求小号超越大号要多长的时间，以及超越时 \(\rm rating = k\) 的概率。

我们只关心从 \(i\) 开始，到达比 \(i\) 大的数要多长的时间，以及最后是什么数。

于是设计 \(f_{i,j}\) 表示从 \(i\) 开始到的第一个比 \(i\) 大的数是 \(i + j\) 的概率，\(g_i\) 是需要的期望时间。

转移是好转移的。

然后用这个数组去维护 \(\rm DP\) 数组的转移就好了。

直接做预处理 \(f\) 复杂度是 \(\Theta(nm^2)\)，\(\rm DP\) 的复杂度是 \(\Theta(n^2m)\)。

其实仔细思考一下可以发现 DP 的时候利用到的只有 \(i - j \le m\) 的元素，所以可以做到 \(\Theta(nm^2)\)。

T2 题解 T3 题解

开场先看 T1。

这个 T1 的数据范围 40 让人感觉一脸拆分数，而且这个题目看起来也是用拆分数做的，于是我就开始想怎么用拆分数。

想了想感觉脑子不太清醒，仔细想了想决定先写暴力。写着写着发现好像瞎拆成 \(e^x * x^k\) 的形式就做完了。

于是准备先把暴力写完。大概在 46 分钟的时候写完了。

于是开始改暴力，最后在 70 分钟的时候过了。

然后看 T2。我开始看错题了，以为是只能经过出现了一次的边，然后想这不是憨憨题吗。

于是开始写，写着写着看了下样例，发现不对！于是重新读了一下终于读了正确的题面。推了几下感觉不简单，于是就先看 T3。

T3 看着像是大模拟，但是题面并不长。想了想发现暴力就行，于是开始写，在 122 分钟的时候过了。

于是回来做 T2。有了一些思路，但是感觉非常难实现。

又想了好一会儿就想到了一个很好的转化，让问题简单了 114514 倍，于是就开始写。

我先把暴力写了，再慢慢改成正解。最后改改调调，最后写了 250 行 6k，在 214 分钟的时候过了。

---

题解：

T1 :

首先枚举 \(f_a(x_i) = f_b(y_i) = W_i\) 的 \(W_i\) 的取值。本质不同的 \(W_i\) 只有 \(n\) 的拆分数种。所以我们枚举这个 \(W_i\) 的拆分数。

枚举完之后 \(f_a\) 和 \(f_b\) 就独立了。问题可以转化成给定 \(W\)，求满足 \(f_a(x_i) = W_i\) 的概率。

设第 \(i\) 个数出现了 \(a_i\) 次。那么所求即为：

\[\prod_{i = 1}^m (\sum\limits_{i=0} \frac{x^i i^{a_i}}{i!}) [x^m]
\]

然后把 \(i^{a_i}\) 变成斯特林数：

\[\prod_{i = 1}^m (\sum_{j = 0}^{a_i} S_{a_i, j} \sum\limits_{i=0} \frac{x^i i^{\underline{j}}}{i!}) [x^m]
\]

\[\prod_{i = 1}^m (\sum_{j = 0}^{a_i} S_{a_i, j} \sum\limits_{i=0} \frac{x^i}{(i - j)!}) [x^m]
\]

\[\prod_{i = 1}^m (\sum_{j = 0}^{a_i} S_{a_i, j} x^j e^x) [x^m]
\]

\[e^{mx} \prod_{i = 1}^m (\sum_{j = 0}^{a_i} S_{a_i, j} x^j) [x^m]
\]

对于 \(a_i = 0\) 我们可以直接忽略。可以 \(\Theta(n^2)\) 算出 \(\prod_{i = 1}^m (\sum_{j = 0}^{a_i} S_{a_i, j} x^j)\)，然后计算答案。

时间复杂度 \(\Theta(\pi(n) n^2)\)。

---

T2 :

写这篇题解的时候我发现我的代码其实有些小问题，不过也过了 /jy。

首先对于每种颜色，这种颜色的边必须在一条链上，否则必然不能经过这种颜色。

然后考虑如果每种颜色的边只有两种怎么做：给每种颜色随机赋 unsigned long long 的权值。

---

T3 :

枚举去掉的是哪些牌，然后对于每种颜色 DP 再合并即可。