CSP 2019 提高组第一轮

杂谈

5题
不换成int是一位也不舍弃的

6题
分类讨论+组合数学
9题
分类谈论+一点点耐心

11题

极限情况

(A_1<B_1<A_2<b_2)······

14题
一点小小的计算·····
16题

最后两问对应的就是单调第增和递减的情况
第五问似乎合并的顺序不影响答案。

17题
朴素的并查集复杂度是(n^2)

18题

任务:计算s最多可以删去几个字符,使t仍为s的子序列

suf,pre存的是从后往前和从前往后匹配最远可行的位置
(1)错误

显然suf[i+1]其实就是没到if时的j
j唯一的变化就是--,所以说小于等于成立

(2)错误 两个都是空串时为0

(3)错误 如果没有任何公共子串,输出就是一个负数

(4)错误 反例 a和b相等时

(5) 1因为怎么说,只要t不是s子序列就行,但是s不能输入空啊

(6) 12输出2表示删去两个还是,那么最小肯定就是t加上两个字符

19

unlock[i]表示i还有多少未解开限制
1,2 就是解开一门课需要有足够的point和可解锁(==0)
已解锁的定位-1
3问就是得分
4问减少限制

20
博弈论可知
记f[i]表示剩下i个石子时先手能不能必胜

显然只有所有的f[i-b[i]]先手必败,才会必胜

本题中b[i]小于64,那么用status记录i个石子时,i-1,i-2,1····i-64能否必胜

若为一则先手必胜

1 初始化,一开始只有0个石子,那么先手必败,所以第一位为0,剩下的就是1了

2 毕竟随着石子增多,可以由上面的转移过来,所以只在相等的时候转移

3trans记录的是可行的转移方式,所以说|一下(这与b[i]范围有很大关系)

4后手必败才会先手必胜,所以说需要~,只有必胜且存在这个转移方式(trans)才能先手必胜,所以&

5考虑一下status是干啥的,那么多了一个石子就左移一位,然后异或一下,重叠的是肯定不行的(怎么可能呢,多了一个石子还能取到)

原文地址:https://www.cnblogs.com/For-Miku/p/13736552.html