【题解】牛客NOIP暑期七天营-普及组5
T1:手术等级？？？
定位：本场签到题。
题意：给你一个数组，你需要将其切成两部分，每部分的权值等于各自从1开始的下标乘以相应的数组元素。求最小权值和。
0pts
数组越界RE，或者写的错的非常离谱....不然一般会不0分。
10-20pts
看了一眼，100000，好像可以nlog，然后盲狙一个单调写了个二分/三分。如果写了个二分那么一般是10分，运气好一点20分。如果写了个三分就是20分。
50pts
写了n方暴力或者，爆int了，就是50分。
实际上本场比赛有不少人爆了int。
100pts
仔细思考一下
对于第一部分的数组，永远都是1*a[1]+2*a[2]+..+k*a[k],k是断开的位置。那么对于这个东西很明显可以预处理前缀和。
而第二部分的数组为(i-k+1)*a[i]+(i-k+2)*a[i+1]+...+(n-k)*a[n]，我们不妨提取出-k*(a[i]+a[i+1]+...a[n])，发现和上面相同，都是下标乘以数组元素的前缀和。
所以两个前缀和做减法就可以O（1）的求出断在每个位置的权值和。所以for过去O（n）枚举断点求最小解即可。
其他情况
写了一些假贪心骗分，或者没有处理好边界问题，导致WA掉一些测试点。
T2小混沌的RYB树
0pts
dfs的时候没有判断是否为父亲，导致dfs不能达到叶子，而是在转圈圈导致死循环或者递归爆栈，或者直接写了假贪心。
30pts
直接dfs处理，不做记忆化。
50pts
看了下选手的代码，除了爆int以外，还有例如双向边边表数组没有开两倍额外空间导致的RE。
100pts
状态转移方程
dp[x][0]=Σmax(dp[ch][1],dp[ch][2])
dp[x][1]=Σmax(dp[ch][0],dp[ch][2])
dp[x][2]=Σmax(dp[ch][0],dp[ch][1])
做树形DP即可。
T3所以，然后是几点呢？
0pts
没交，或者盲狙数据直接输出还猜错。
10pts
输入什么，直接进行输出。
20pts
输入之后判断AM或者PM，以及是否需要转化。
60pts
能过样例（能过样例就是60，但是数据中不含样例），但是部分数字无法识别。
100pts
大模拟，最好把输入和输出封装成不同的函数，进行函数化的编程。如果都写在主函数里面，往往由于逻辑不够清晰导致各种问题。
T4小w的Fibonacci数列
定位：本场防AK题。
0pts
有人想不开不是递推求斐波那契，而是递归求斐波那契...而且没加记忆化搜索..20项都会TLE
10pts
啥都不写，直接提交一个return 0的程序，白给点。
不是因为特判有锅，而是有一个点（白送）的答案是0 0，选手不输出的话，特判程序读进来的选手答案默认是0 0。所以能得到10pts。
20pts
暴力枚举前两项，做斐波那契数列。
30pts
在20的基础上，特判掉x=1,y=3的情况就是30
50pts
不是for过去进行验证，而是使用矩阵快速幂进行验证，就是50pts。
60pts
第5个测试点是提示正解的测试点，若想通过这个点，需要设第一项为Ax，第二项为Bx，因为x=1所以显然Ax已知就是valx。
那么我们按照斐波那契数列的规则进行递推
Ax,Bx,Ax+Bx,Ax+2Bx,2Ax+3Bx,3Ax+5Bx,5Ax+8Bx,8Ax+13Bx....
不知道你有没有发现规律
假设类斐波那契数列的第一项为A,第二项为B，那么第p项就为fib[p-2]*A+fib[p-1]*B，fib为首项为1 1的斐波那契数列。
由于测试点的特殊性，A是已知的。所以这个方程列出来进行移项变形之后，就是一个形如
的形式，也就是解一次同余方程。
这个问题的话很早以前的NOIP题目中是有涉及的，这里不再展开详讲，如果不懂想学的话可以百度：NOIP2012D2T1 同余方程
牛客网上面也有真题训练：https://ac.nowcoder.com/acm/contest/260/A
100pts
有了60pts的结论，我们可以列方程组
别被同余等号吓住，这就是个普通的二元一次方程组，加减消元之后变成了的一般形式，求出AB即可。
至于项很大的时候如何求斐波那契数列，可以使用矩阵快速幂，或者斐波那契数列的log递推式。这是一个比较常见的问题，不在赘述，如果不清楚怎么做的话可以百度：斐波那契数列取模数。
花絮：
我以为是中午开始比赛...然后昨天才得知是早上，然而我今早在飞机上，叫了同学帮忙答疑。题目可能有不清楚的地方或者各种笔误手滑...向各位同学道歉。
t4可能人认为一定有解并且是唯一解，这个看上去好像是这样，实际上随机出来也是这样。
但是实际上t4是有无解和无穷解这两种情况的。
若)
,|fib|表示斐波那契数列在该模条件下的循环节长度，此时不是无穷解就是无解。
若此时)
则为无穷多解，反之则为无解。
当然...讨论斐波那契数列循环节这个问题，可能已经远超过普及组，甚至NOIP提高组了，这里并没有这么毒瘤，而是降低了难度，只让选手解方程。
本场第一名：星夜201907132011908，这位同学是最后5分钟发现自己t2没开双倍空间进行修改，50->100完成绝杀。
本场第二名：ethan_zhou
本场第三名：Guoyh06
本场第四名：RobertLuo
本场第五名：偶尔刷刷题
像我们这种二本仔秋招没有实习也是白忙活
