24.9.21

距离 CSP-J/S 2024 第一轮 还有 0 天。

距离 停课集训 还有 1 天。

集训日子加载中……

24.9.22

距离 CSP-J/S 2024 第二轮 还有 33 天。

初赛成绩已出 J:86 S: 68.5。

今日份模拟赛初中联考 期望：90 + 30 + 0 + 0 = 120，实际：90 + 30 + 0 + 0 = 120，大众分: 100 + 40 + 40 + 20 = 200，最高分：100 + 100 + 85 + 100 = 385。

考试时策略

T1想到大致思路后，认为T2能写，认为是线段树模拟，写了 2.5h 发现算法假，后写 T1 90pts写法和 T2 30pts 写法。

集合set

题目传送门

考场思路：考虑如何从 \(n - 1\) 转移，使用 map 维护出现次数。

正解：对于每一个 \(x\) 出现次数，使用背包DP进行维护出现次数。

很睿智的发现自己并不会使用DP维护次数：枚举每一个 \(i\)，有选和不选两种情况进行转移。

本题次数会超过 long long 范围，考虑取模，对于质数 \(Mod\)，\(x^y\equiv x ^ {y\ mod\ (k - 1)} (mod\ p)\)（费马小定理）。

code

出租hire

题目传送门

考场思路：认为可以使用线段树维护区间和，提供 HACK， 使用线段树硬模拟会挂。

input:

4 3 2 1
1 2
3 2
2 4

output:

YES
YES
YES

正解：考虑无解情况 \(\exists l, r(l,r \in [1, n], l \le r), \sum_{i = l}^{r} a_i > (r - l + 1 + d) * k\)， 展开右边，得到 \(d * k + (r - l + 1) * k\), \(d * k\) 显然与 l, r 无关。 考虑将每个楼初始化为 \(-k\)，那么因该找到最大的 \(\sum_{i = l}^{r}a_i\)， 使用线段树维护最大字段和。

code

跳棋checkers

题目传送门

考场思路：没看

正解：DP

对于棋子去跳，类似从110变为011可以抽象的认为是11和0交换位置。

\(f[i][j][k][x][y]\) 为选前i个有j个0，k个11，当前选0/1，有连续奇/偶数个1结束时构造出的方案。

放一下转移式吧，很好推的这个。

f[op][j][k][0][0] = f[op ^ 1][j - 1][k][0][0] + f[op ^ 1][j - 1][k][1][0] + f[op ^ 1][j - 1][k][1][1]

f[op][j][k][1][0] = f[op ^ 1][j][k - 1][1][1]
f[op][j][k][1][1] = f[op ^ 1][j][k][0][0] + f[op ^ 1][j][k][1][0]

结算答案：对于现在的方案，考虑有多少情况转移过来，由于单个 1 不会产生贡献（0不能穿过它），所以不考虑，将 11 看成为一个。\(i\) 个 1，\(j\) 个 0，有 \((i + j)!\) 种方案，由于1,0都不考虑顺序，所以除以 \(i! * j!\)。由于题目取模，注意需要逆元。

code

连通块block

题目传送门

考场思路：没看。

正解：树形DP

对于子树 \(x\)，满足要求需要前一个子树的最后一个不与 \(x\) 矛盾。考虑状态设计。

\(f[i][j]\) 选 \(i\) 的子树中，其中 dfn 最大值为 \(j\)。

如果要加一个子树，则要从不冲突的子树转移过来。

看似复杂度 \(O(n ^ 2)\)，实则 \(m\) 很小，所以离散化后复杂度 \(O(n m)\)。

code

总结

分数远低于大众分，分析主要原因是在安排时间不够合理， DP欠缺，以至于知道是 DP 仍然不会写，要加以训练。

下班收工！！！

24.9.23

距离 CSP-J/S 2024 第二轮 还有 32 天。

有且仅有晚自习，改题.png

24.9.24

距离 CSP-J/S 2024 第二轮 还有 31 天。

可爱的模拟赛捏，期望：100 + 50 + 0 + 0 = 120，实际：0 + 50 + 0 + 0 = 50，大众分: 未知，最高分：100 + 100 + 100 + 70 = 370。

考试时策略

写 1.5h T1，大样例过了，挂的一分不剩。后推 T2 式子，失败，怒拿 50pts。

依依寺yiyi

题目传送门

考场思路 & 正解：0的作用使先后手交换，然后选取只能 2 2 1 2 1 2...... 或 1 1 2 1 2 1.......

想到了，但是没有完全想到，判错了QwQ……

code

武义寺wuyi

题目传送门

放一下写的好的 TJ 吧，分解 + 证明确实不好写。BlueMoon | PikachuQAQ。

考场思路：选取 \(i\) 作为 \(val_p\)，去求方案数。枚举 \(i\) 的值，然后暴力去算。（其实是因为式子推了很久没退出来。

正解：同上，将式子化简。

列出式子：\(v_i=\displaystyle\sum_{j=0}^{i-2}(n-i+1)^j(n-i+2)^{i-j-2}\)。

但是这样还是 \(O(n^2)\) 的做法，考虑 \((n-i+1)+1=n-i+2\)，令 \(a=n-i+1\)。

证明 \(\displaystyle\sum_{i=0}^{k}a^i(a+1)^{k-i}=(a+1)^{k+1}-a^{k+1}\)

code

依久依久yijiu

题目传送门

考场思路：没看

对于区间，考虑使用前缀优化。 \(f(x)\) 表示从 \(1\) 到 \(x\) 的异或和。

令斐波那契数列数组为 \(a\)，当 \(x\) 处于 \(a_i\) 到 \(a_{i+1}\) 之间时，每个 \(x\) 都能分出 \(a_i\)，那么整个区间会分为两部分，能减 \(a_i\) 和 不能减去 \(a_i\) 的，同时 \(a_i\) 对答案的影响取决于 \(a_i\) 的数量是奇数还是偶数。

考虑分治解决问题。

code

补幺梨pear

题目传送门

考场思路：推出为完全背包，但是没时间写了QwQ

正歪解：考虑优化剪枝，由于为随机，肯定跑不满。

大优化：考虑如果有连续 \(Min\) 个可行方案，可以将每个值多增加一个 \(Min\)，使得后面的方案全部可行。

小优化：当 \(f_i\) 已经可以被转移，则不必继续循环。

然后加一点常数优化，就愉快的 AC 了！

code

总结

考到一半心态炸了，T2一直没有推出来，最后暴力拿分，没有时间留给 T4，有点可惜。还需要调整时间和心态。

下班收工！！！