CS109 考前复习
回顾
基本数据类型
888 个,String 不是哦!
变量名命名规则
只能包含字母、数字、下划线、美元符号,且不能以数字开头。
编译
Java 源代码(.java 文件)-> 字节码(.class 文件)。字节码(bytecode)是一种中间代码,与平台(操作系统)无关,能被 Java 虚拟机(JVM)执行。
编译并运行:java Main.java arg0 arg1 arg2 ...,其中 arg0 arg1 arg2 ... 是 main 方法的参数,也就是 public static void main(String[] args) 中的 args 数组。
编译:javac Main.java。
运行:java Main arg0 arg1 arg2 ...。
printf 方法
switch-case
case 后的值必须是编译期已知的常量,不能使用变量或表达式。
如果省略 break,代码会继续执行下一个 case,称为贯穿(fall through)。而 default 可以没有 break,因为碰到大括号 ...
CF1476F. Lanterns
Statement
nnn 个灯笼排成一排,第 iii 个灯笼具有 pip_ipi 的亮度。每个灯笼要么朝向左,照亮左边编号为 [i−pi,i−1][i − p_i, i − 1][i−pi,i−1] 的灯笼;要么朝向右,照亮右边编号为 [i+1,i+pi][i + 1, i + p_i][i+1,i+pi] 的灯笼。
请你为所有的灯笼确定朝向,使得每一个灯笼至少被另外一个灯笼照亮,或判断无解。
数据范围:n≤3×105n \le 3 \times 10^5n≤3×105。
Solution
神仙 DP。
把可行性问题转化为最优性问题,设 f(i)f(i)f(i) 表示前 iii 个灯笼能覆盖的最长前缀。
转移考虑第 iii 个灯笼的朝向。如果向右,那么
f(i)={f(i−1),f(i−1)<imax{f(i−1),i+pi},f(i−1)≥if(i) = \begin{cases}
f(i - 1), &f(i - 1) < i \\
\max\{f(i - 1), i + p_i\}, &f(i - 1) \ge i
\en ...
CF840C. On the Bench
Statement
给你一个长度为 nnn 的序列 aia_iai。问有多少 1∼n1 \sim n1∼n 的排列 pip_ipi,满足 ∀i∈[2..n]\forall i \in [2.. n]∀i∈[2..n],有 api−1×apia_{p_i − 1} \times a_{p_i}api−1×api 不为完全平方数。答案对 109+710 ^ 9 + 7109+7 取模。
数据范围:n≤300n \le 300n≤300,1≤ai≤1091 \le a_i \le 10 ^ 91≤ai≤109。
Solution
每个数去掉平方因子后,条件等价于没有两个相等的数相邻。
Algorithm 1
把相同的数分类,假设共 mmm 种不同的数,其中第 iii 种有 cic_ici 个。记 f(i,j)f(i, j)f(i,j) 表示填入前 iii 种数,有 jjj 对相同的数相邻的方案数;g(i,j)g(i, j)g(i,j) 表示将第 iii 种数拆分成块内块间均有序的 jjj 块的方案数。下面设 si=∑j=1icjs_i = \sum_{j = 1} ^ ...
CF888F. Connecting Vertices
Statement
有一个正 nnn 边形,顶点顺时针编号为 1∼n1\sim n1∼n。问用 n−1n-1n−1 条边连接这 nnn 个顶点,使它们连成一棵树,有多少种方法。
连边时有以下限制:
给出一个 n×nn\times nn×n 的 01 矩阵 AAA,Ai,j=1A_{i,j}=1Ai,j=1 表示顶点 iii 和顶点 jjj 可以直接相连,而 Ai,j=0A_{i,j}=0Ai,j=0 时则不能。保证 Ai,i=0A_{i,i}=0Ai,i=0,Ai,j=Aj,iA_{i,j}=A_{j,i}Ai,j=Aj,i。
两条线段不能在顶点之外的地方相交,如不能同时连 (1,3)(1,3)(1,3) 和 (2,4)(2,4)(2,4)。
数据范围:n≤500n\le500n≤500。
Solution
计数 DP 的一般套路是要构造一个“不可划分的整体”。—— sol1
考虑区间 DP,因为如果 iii 和 jjj 有边,则 i+1∼j−1i+1\sim j-1i+1∼j−1 中不可能有连出去的边。
记 f(i,j)f(i,j)f(i,j) 表示 iii 和 ...
P7044. [MCOI-03] 括号
Statement
定义一个括号串的 000 级偏值为将该括号串修改为合法括号串需要的最小操作数。一次操作你可以在一个位置添加一个括号或删除一个位置的括号。
定义一个括号串的 iii(1≤i≤n1 \le i \le n1≤i≤n)级偏值为该串所有子串的 i−1i - 1i−1 级偏值之和。
给你一个长度为 nnn 的括号串 sss 和一个正整数 kkk,求 sss 的 kkk 级偏值。答案对 998244353998244353998244353 取模。
数据范围:1≤n,k≤1061 \le n, k \le 10 ^ 61≤n,k≤106。
Solution
下面的 kkk 在题面的基础上 −1-1−1。
将一个括号串修改为合法括号串需要的最小操作数,等于它不匹配的括号个数。
一个子串的 000 级偏值中,一个左括号有贡献,一定是没有与之匹配的右括号。右括号同理。
那么一个子串 s[l:r]s[l : r]s[l:r] 的贡献就是 (l−1+kk)⋅(n−r+kk)⋅f(s[l:r])\binom{l - 1 + k} k \cdot \binom{n - r + k} k ...
CF765F. Souvenirs
Statement
给你一个长为 nnn 的序列 aia_iai,mmm 次询问,每次询问给出 l,rl,rl,r,求
mini,j∈[l..r]∧i≠j{∣ai−aj∣}\min_{i, j \in [l.. r] \land i \ne j}\{|a_i - a_j|\}
i,j∈[l..r]∧i=jmin{∣ai−aj∣}
数据范围:n≤105n \le 10^5n≤105,m≤3×105m \le 3 \times 10^5m≤3×105,0≤ai≤1090 \le a_i \le 10^90≤ai≤109。
Solution
离线询问并按右端点升序排序,在 rrr 右移的过程中维护每个 lll 的答案。每次 r−1→rr - 1 \rightarrow rr−1→r 时,要加入 ara_rar 和前面的数的贡献。
下面考虑 ax≥ara_x \ge a_rax≥ar 的情况,ax<ara_x < a_rax<ar 的情况同理。
用主席树找到 [1..r−1][1.. r - 1][1..r−1] 中最大的 xxx 满足 ax≥a ...
CSP-S2 2022
T1. 假期计划
枚举 B, C 就行,预处理前三大的 A / D。时间复杂度 O(nm+n2)O(nm + n^2)O(nm+n2)。
T2. 策略游戏
按照 B 中是否有正负数分讨即可。
T3. 星战
判断的条件就是每个点出度都为 111。
给每个点随机一个权值 vali\text{val}_ivali,对于每个点 vvv 维护 sv=∑(u,v)∈Evalus_v = \sum_{(u, v) \in E} \text{val}_usv=∑(u,v)∈Evalu,并维护 ∑sv\sum s_v∑sv。每次检查 ∑sv\sum s_v∑sv 是否等于 ∑vali\sum \text{val}_i∑vali 即可。
感觉不稳的话就多随几次。
T4. 数据传输
k=2k = 2k=2 的时候中途的点不会跳出 sis_isi 到 tit_iti 的链上。矩乘加速是显然的。
k=3k = 3k=3 的时候中途的点可能会跳出 sis_isi 到 tit_iti 的链上,但是可以发现出去的点一定是这条链某个点的邻居。进一步可以发现,这个点一定是链上某个点所有 ...
CF505E. Mr. Kitayuta vs. Bamboos
Statement
有 nnn 根竹子,第 iii 根初始时高度为 hih_ihi。你需要依次进行如下操作 mmm 轮:
重复 kkk 次,从 nnn 根竹子中选出一根,将它的高度减少 ppp。若当前 hi<ph_i<phi<p,则将 hih_ihi 改为 000。
对于 ∀i∈[1..n]\forall i\in[1..n]∀i∈[1..n],将第 iii 根竹子的高度增加 aia_iai。
请你最小化所有操作结束时,最高的竹子的高度。
数据范围:n≤105n\le10^5n≤105,m≤5000m\le5000m≤5000,k≤10k\le10k≤10。
Solution
考虑二分答案后如何 check。不好做的是 hih_ihi 会改成 max{hi−p,0}\max\{h_i-p,0\}max{hi−p,0}。
尝试将整个函数向上平移,函数就变成了 hi+Δh_i+\Deltahi+Δ 出发到 mid\text{mid}mid,一路上 hih_ihi 均 ≥0\ge0≥0。
因为最后时刻是确定的,因此倒序考虑,变成了『有 nnn 根 ...
CF1408G. Clusterization Counting
Statement
给你一张 nnn 个点的完全图,边 (i,j)(i,j)(i,j) 的边权是 w(i,j)w(i,j)w(i,j)。保证所有边权形成一个 1∼n(n−1)21\sim\frac{n(n-1)}21∼2n(n−1) 的排列。
请你对每个 k∈[1..n]k\in[1..n]k∈[1..n],求出把 nnn 个点划分成 kkk 个点集的方案数,满足:
对于任意四个点 a,b,c,da,b,c,da,b,c,d 满足 a,b,ca,b,ca,b,c 同组但 ddd 不同组,有 w(a,b)<w(c,d)w(a,b)<w(c,d)w(a,b)<w(c,d)。
数据范围:n≤1500n\le1500n≤1500。
Solution
条件就是组内边小于组间边,也就是组内边的最大值小于组间边的最小值。
所以按边权从小到大加边,可以发现一个结论:一个连通块可以单分为一组,当且仅当这个连通块在加边的时候,变成了一个团。
因此按照 Kruskal 的过程,维护当前连通块是否是团。到这里应该可以得到指数级的 DP。
比较显然的是,合法连通块一定是 Krusk ...
NOIP 2020
T1. 排水系统
拓扑排序 + 高精。
T2. 字符串匹配
题意:给你一个长度为字符串 SSS,求对 SSS 的划分个数,使得 S=(AB)iCS=(AB)^iCS=(AB)iC,其中 (s)i(s)^i(s)i 表示将 sss 复制 iii 遍拼接,A,B,CA,B,CA,B,C 均为非空字符串。
多组数据。T≤5T\le5T≤5,∣S∣≤220|S|\le2^{20}∣S∣≤220。
枚举倍数调和级数是 O(nlnn+26n)O(n\ln n+26n)O(nlnn+26n) 或者 O(nlnnlog26)O(n\ln n\log 26)O(nlnnlog26) 的。
扩展 KMP 可以做到 O(n)O(n)O(n)。
T3. 移球游戏
题意:有 n+1n+1n+1 根柱子,前 nnn 根柱子上每根有 mmm 个球。所有 n×mn\times mn×m 个球共 nnn 种颜色,每种颜色 mmm 个。
你可以对当前局面进行以下操作若干次:
将某柱子顶端的球移到另一个柱子的顶端。
最后使得将相同颜色的球最后全部放置在相同柱子上。操作过程中需要满足:
原来的柱 ...