题解
By.tqr
感谢大家参加这次比赛
若有任何疑问，欢迎加QQ735748368讨论，加好友时备注好牛客id
std在每题分析的最后
A-「水」滔天巨浪
100分：
因为数据保证严格单调递增，所以显然只需要找到一个最大的区间，使得其左右两个元素的差值等于其长度即可
直接递推就好了，唯一需要注意的就是两边的边界需要初始化。
复杂度
B-「木」迷雾森林
由小学数学题改编而来......
30分：
dfs即可，因为没有刻意造数据，所以具体多少不好说...
100分：
显然一个点只能从下面和左边走过来，所以可以直接dp
设dp[i][j]是走到坐标(i,j)可行的方案数，dp[i][j]=dp[i+1][j]+dp[i][j-1]
当一个地方有障碍时，dp值为0
复杂度
C-「土」秘法地震
选取区间，使得其中没有建筑
30分：
直接枚举所有区间，check计数
100分：
如果没有规定区间的大小的话，需要使用数据结构和dp来优化
但现在已经规定了区间的大小，因此我们求二位前缀和来统计区域内建筑数
num[i][j]=num[i-1][j]+num[i][j-1]-num[i-1][j-1]+a[i][j];
复杂度
D-「金」初心如金
30分：
对于每次询问，暴力判断其是不是质数，然后记录答案，下一次询问的时候还原出本来的数字，再继续判断，复杂度 【数据加强后没有这部分分了】
80分（左右）：
使用miller-rabin素数探测，可以得80分左右
100分：
因为给出的是一个奇数，lastans又只可能是1或0，因此可以直接根据后面询问的奇偶性判断上一次的答案
复杂度
是一道披着数论皮的乱搞题
E-「火」烈火燎原
100分：
如果知道一棵树的小树中每个点的度数，就可以知道其小树的小树的边数
而小树的点的度数就是原树中每条边邻接的边数
所以读入的时候统计一下的度数就可以了
F-「水」悠悠碧波
60分：
暴力枚举子串，暴力分给得很高......
100分：
使用hash判断即可
标程加了几个优化:
1.一个从首字母开始的，长度为l的字符串，如果从尾字母向前推l个字母不是首字母，说明不合法
2.记录所有首字母出现的位置，如果往后l个不是尾字母，说明没有在中间出现过，不合法
(当然此题也可以kmp来做，但因为没打这个做法所以不做讲解)
G-「金」点石成金
观察到数据范围很小，所以直接dfs
但因为如果数值小于0的时候会修正数据，所以记录一下选取之前的状态，回溯的时候回溯回来就行了
H-「土」巨石滚滚
100分：
很显然的贪心
如果土球碰到障碍不会碎的话，那么尽量先选取 回复-消耗 更大的障碍
如果可以回血，那么优先选择消耗最小的；
如果回血小于了消耗，那么先选择回血最多的
在上述操作过程中，一旦遇到无法选取的，就可以判断无法满足条件了
代码很有意思可以琢磨一下，证明也很有趣，自己想一想
（其实有部分分的，但是审题人说这题不需要，所以就没在数据范围中体现出来）
I-「木」揠苗助长
给两个序列，这两个序列与真实序列都有一个数字有差异，问是否能还原出真实的序列
100分：
大模拟，通过多个条件判断是否可行（如，如果一个数字出现了三次，就一定不可行等），码量较大
但我们机房内互测的时候，神仙搞出了一个很巧妙的方法，就是两个序列分别向可能的合法序列转换，比较两个序列转换出的序列，如果有重合的就代表有解，否则无解
每个人代码不同，分数可能会很多样
J-「火」皇家烈焰
相当于给出一个一维的扫雷地图，已知里面的一些格子的情况，问有多少种情况符合初始条件
30分：
枚举所有情况，check是否合法，计数
100分：
dp[i][j][k]表示现在在第i格，前一格是否有皇家烈焰，后一个是否有皇家烈焰
然后分情况转移即可，注意处理细节，考虑清楚是否有情况没有讨论到
全部评论
(8) 回帖