2020.09.26【普及组】模拟赛C组总结
总结
这次比赛感觉还可以，没有丢太多分，公认的难题第三题也在考试时做对了。
T1 INSTRUKCIJE（100）
题目大意：给你一个序列，让你求 a a a~ b b b之间的那些数之和。序列：
1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,6,6,6,6,6,6,......
其中 a,b<=1000
思路：这不就一道模拟题吗？用了个双重循环和前缀和数组，分分钟搞定。
T2 LAGNO（100）
题目大意：给你一个 8 8 8* 8 8 8的棋盘，上面有黑白棋子，让你放一颗黑子，使得吃掉白子的数量最多。吃掉的规则：
.B.. | B... | ....
.W.. | .W.. | BWB.
.B.. | ..B. | ....
.... | .... | ....
思路：这题就是一道暴力题，直接枚举棋盘上的所有点，取一个 m a x max max就行了。
T3 NIKOLA（100）
题目大意：给你 n n n个数，表示 n n n个格子的费用，让你从 1 1 1开始跳，跳到第 n n n个格子上，第一次必须跳到第 2 2 2个格子。求最少花费。跳的规则：
//设x代表上一次跳的格子数
往前跳：x+1格
往后跳：x格
思路：一开始想的是搜索，发现搜索做不了，极限数据不能过，怎么办呢？
想了想，对呀，可以用记忆化！
设
f
i
,
j
f_{i,j}
fi,j表示当前为第
i
i
i格，上一次跳了
j
j
j格的最少花费，显然除了
f
2
,
1
f_{2,1}
f2,1为
a
2
a_2
a2，其他都是无穷大。然后，就可以套进搜索里进行优化了。可是，还是过不去啊QAQ
没关系，失败是成功之母。我们已经打出了记忆化，能不能再优化呢？没错，动态规划！
我们发现，
n
2
n^2
n2仅仅只有
1000000
1000000
1000000那么大，我们就可以枚举
i
,
j
{i,j}
i,j，然后推公式带进去。公式是什么呢？
f i , j = m i n ( f i , j , m i n ( f i − j , j − 1 , f i + j , j ) + a i ) f_{i,j}=min(f_{i,j},min(f_{i-j,j-1},f_{i+j,j})+a_i) fi,j=min(fi,j,min(fi−j,j−1,fi+j,j)+ai)
这个公式第一条表示从前面跳过来，第二条表示从后面跳过来。这个时候，我们只需要枚举 j , i j,i j,i最后在 f n , i , i f_{n,i},i fn,i,i<= n n n中取最小值就行了。
T4 pjesma（11.1）
题目大意：给你 n n n个字符串，让你在另 m m m个串中找，求找到第几个串后找到的不重复串个数至少为 n n n的一半？
思路：这一题一开始理解错了，以为是连续的，然后就没有然后了……
正解为分开找，加个标记，然后到一半时输出就行了。
完成情况
- T1
- T2
- T3
- T4