PKUSC2023游记
max67
·
·
个人记录
前言
今天先把题面写了
Day.1(5.6)
T1
给定两个字符串长度为 1 \le n \le 2\times 10^6，n 个询问，第 i 个询问把 s_i 替换成 t_i（询问互相独立），输出 s 的最长的不等于 n 的 border（没有就输出 0）。
时限 1s
题解
乱搞即可
T2
%1e9+7
代码限制 8k
时限 3s
### 题解
min-max 可以做到 $n^5$，正解不知道。
代码限制还有可能限制 mtt？
### T3
一个树（$n\le 3\times 10^5$），每个节点的值 $a_i$ 有 $p_i$ 的概率为 $1$，$1-p_i$ 的概率为 $0$。每个节点的 $b_i$ 是他的子节点的 $b_i $ 与 $a_i$ 的众数（子节点个数为偶数）。问 $b_1$ 是 $1$ 的概率。 $q \le 1\times 10^5$ 次询问，单点修改 $a_i$。再询问答案（修改不独立）
%998244353
时限 2s？
### 题解
显然树剖，显然只需要维护子节点乘积的乘积的一半少一点和一半多一点就可以矩阵转移。问题出在多项式除一次式的复杂度上。听说可以用多项式 exp？
## Day.2（5.7）
### T1
维护一个序列。有 $n \le 3e5$ 个操作
* ```1 x``` 如果执行这个操作，那么意味着：新开一个编号为顺位（++tot）的点，并放在 x 的后面，x的后面的数的前面。（若 $x=0$ 则放到开头）
* ``` 2 x y``` 找到把编号为 x 加入的操作 $id$，把操作 $id$ 修改成 ```1 y```。
* ```3 z``` 依次执行所有 ```1 x``` 的操作，并询问 z 的位置。
时限 1s
### 题解
显然可以建成一颗树，边权为操作的时间。子节点之间的偏序关系就是按边权从大到小排序。询问即问 $z$ 的 dfn 序。操作 2 就是断一条边加一条边（保证子节点都是一个点）。操作 1 就新塞一个点和一条边。
你可以直接上 lct 维护。你也可以把移动的子树转成区间上平衡树。你也可以把暴力建树用询问分块，把大小用虚树砍到根号。
但我什么都不会。
### T2
$T\le 100$ 组询问
给你 $\sum L \le 5\times 10^4$ 个集合，每个集合的大小 $n_i\le 10$。元素都是二元组 $(0<a_{i,j}\le 100,0<b_{i,j}\le 100)$。现在给你 $q \le 10$ 组询问。每次给成 $1\le A,B\le 10^7$，要你再每个集合中恰好选出一个元素，满足 $(A+\sum a_{i,j})(B+\sum b_{i,j})$ 最大，输出方案。
设你的解的值是 $x$，std 的解为 $y$，最优解的值为 $z$。若满足 $|x-y| \le 2500$ 则算答案正确。满足 $|y-z| \le 2500
a_{i,j},b_{i,j},A,B\in R
时限 2s
题解
神秘三维凸包。但乱搞能骗分
T3
每次给出 $m=5$ 个方程，形如
$$
a_ix+(x\ mod\ b_i +1)(x^i \mod [x^{\frac{1}{2}}])=c_i \pmod P
$$
其中 $ [x]$ 表示不超过 $x$ 的最大整数。
保证解在 $(0,P)$ 之间且解唯一。
$9\times 10^{17} \le P \le 10^{18}$ 且 $P$ 是质数
$0< a_i <P
一些包满足 b_i=1，另一些包满足 91\le b_i \le 100。
满足方程随机（先随 P,x，再随 a_i,b_i 并算出 c_i）。
题解