CSP 2023 游记

Nwayy / 2023-08-15 / 原文

前言

学 OI 的第二年，也是第二次参加 CSP（（

今年是把普及和提高一起报了，~~被 CCF 狂坑 \(100\) RMB 寄。~~

这个赛季期望目标（求稳一点）就是普及一等（\(300\)+ pts）加上提高二等，当然提高如果能冲个一等就起飞了。

7.11-7.19

在石门集训学新算法。老师是klii，是今年石门毕业生，高二打 S 组和 NOIP 时拿下了 \(300\) 多 pts 的辉煌战绩，恐怖如斯。

学了一车提高算法，其中 AC 自动机凭借其逆天的抽象程度被机房骂了 several days。

7.20

石门最后一天模拟赛。

题目如下：

A：给定长为 \(n\) 的序列，每次可以选择相邻两个数合并成他们的和，并插入原位置，求最少的操作次数使得数组回文。\(n \le 10^6\)。

B：给定长为 \(n\) 的序列，再给定质数 \(p\) 和常数 \(k\)，求出满足 \(1 \le i<j \le n\) 并且满足 \((a_{i}+a_{j})(a_{i}^2+a_{j}^2)≡k \pmod p\) 的二元组 \((i,j)\) 的个数。\(n \le 3 \times 10^5\)，\(2 \le p \le 10^9\)，\(0 \le k,a_{i} < p\)。

C：给定 \(n\) 个点 \(m\) 条边的图，图有点权和边权。定义第 \(i\) 条边能被修复当且仅当对于 \((u_{i},v_{i},w_{i})\)，\(u_{i}\) 所在连通块的点权和加上 \(v_{i}\) 所在连通块的点权和不小于 \(w_{i}\)，且 \(u_{i}\) 和 \(v_{i}\) 在不同连通块，初始时点对间互不连通。需要在修复边数尽量多的情况下使得修复边字典序最小。\(1 \le n \le 10^5\)，\(1 \le m \le 2 \times 10^5\)，\(1 \le w_{i},a_{i} \le 10^6\)。