【题解】牛客CSP-J入门组赛前集训营4
T1从NOIP到CSP
tag，字符串模拟，签到题
10pts
输入什么，直接输出。100pts
按题意模拟即可…T2可持久化变量
tag，思维，数组，模拟，定位：第二签到题，题意题
30pts
*暴力模拟（一个一个back）100pts
做一个真正的“可持久化变量”，什么是可持久化，可持久化就是保留所有的历史版本，所以可持久化变量就是数组。然后对于back操作就可以O(1)回退了。T3doge的取数博弈
tag，博弈，区间DP，定位：中等偏简单题
20pts
if,else判一下30pts
暴搜一下，或者胡乱贪心都可以。40pts
因为所有数字都相同，所以最优操作显然是每次去掉中间那个和直接取一半。递归dfs计算一下即可。100pts
区间DP，考虑两个人在一轮中的操作，先手（删除操作的人）想要让得分最小化，后手（取数操作的人）想要让得分最大化，所以显然有如下的转移方程：
边界条件为dp(i,i)=0，非法的dp与sum可直接置零。
T4Modulus
tag，整除分块（或找规律），RMQ，二分法，定位：中等题偏难题
30pts
暴力for50pts
先暴力计算出每个位置的数组元素，然后套一个线段树或者RMQ都行。70pts
在写出正解的情况下爆int了，不过题目中已经提示好几次了，理论应该不会有人爆int。100pts
首先考虑n/i这个式子。我们知道对于一个整数n，它的因子数目是根号数量级的。这也就是为什么在质因数分解或者判断质数合数的时候只用枚举到√n。对于除法，我们可以将商相同的运算归为一类。 例如在n=20时候 n/i的商跟余数为{(20,0),(10,0),(6,2),(5,0),(4,0),(3,2),(2,6),(2,4),(2,2),(2,0),(1,9),(1,8),(1,7),(1,6),(1,5),(1,4),(1,3),(1,2),(1,1),(1,0)}
我们发现，对于商相同的除数，它的余数是单调递减的。 如果你懂得整除分块的原理，那么这个事情其实很好理解。
因为a=k*i+b，其中a是被除数k是商，b是余数，当商固定的时候，随着i的单调递增，余数b显然会单调递减。
那么要做的事情就很显然了。首先整除分块预处理出所有的单调递减段。
整除分块也是分块，分块对于一个区间查询l，r要特判掉两个端点，中间的部分才能利用分块加速。这个就当成普通的分块做嘛，当然，本题只有左边界是需要特殊处理的，右边界是不用管的。
对于一个询问l,r，其最大值要么来自于整个查询的l点，要么来自这段区间覆盖整除分块的左端点值。用线段树或者RMQ维护这个离散后的整除分块左端点值即可。
因为a=k*i+b，其中a是被除数k是商，b是余数，当商固定的时候，随着i的单调递增，余数b显然会单调递减。
那么要做的事情就很显然了。首先整除分块预处理出所有的单调递减段。
整除分块也是分块，分块对于一个区间查询l，r要特判掉两个端点，中间的部分才能利用分块加速。这个就当成普通的分块做嘛，当然，本题只有左边界是需要特殊处理的，右边界是不用管的。
对于一个询问l,r，其最大值要么来自于整个查询的l点，要么来自这段区间覆盖整除分块的左端点值。用线段树或者RMQ维护这个离散后的整除分块左端点值即可。
update:
前几天出提高组数据水了一波...赶紧检查了一下普及的数据。
这个T4，有好几个70分的都写出了正确的整除分块部分，甚至还有一人是整除分块存起来然后二分左右边界（离正解真的只差一个区间RMQ）...然后他暴力for过去T了。
可能就是想到都用二分了，就没意识到后面for过去是)
的...
所谓整除分块...其实就是利用了一个数字至多有
个因子，也就是素数判定的时候for根号的性质找规律，但是这个题你打个表还真看不出来规律，因为你觉得它不单调，但是一旦按照商相同的分组却又单调，我认为这个很巧妙。
我们下次出题再见~
