$2020.05.23$2020.05.23【$NOIP$NOIP普及组】模拟赛$C$C组$34$34 总结

这次比赛我考了$330$330分，第$5$5名，还可以。

第一题：$read$read

题目

解题方法

这道题目的解题方法是直接模拟。
题目要求出$\begin{aligned}\min_{i=1}^n{\sum_{j=1}^{i}{86400-a_j}\geq t}\end{aligned}$i=1minn​j=1∑i​86400−aj​≥t​。
我们直接每一次减去$86400-a_j$86400−aj​就行了。
或者可以设$s_i$si​表示$\begin{aligned}\sum_{j=1}^{i}{86400-a_j}\end{aligned}$j=1∑i​86400−aj​​，则$s_i=s_{i-1}+86400-a_i$si​=si−1​+86400−ai​或$\begin{aligned}s_i=86400i-\sum_{j=1}^{i}{a_j}\end{aligned}$si​=86400i−j=1∑i​aj​​。
其中$\begin{aligned}\sum_{j=1}^{i}{a_j}\end{aligned}$j=1∑i​aj​​可以用前缀和维护。

得分情况

比赛时满分。

第二题：$gun$gun

题目

解题方法

这道题目的解题方法是斜率和贪心。
我们知道一个直线的斜率为$\frac{y_i-y_j}{x_i-x_j}$xi​−xj​yi​−yj​​，这里我们用$a_i$ai​表示斜率，$a_i=\frac{y_i-y_0}{x_i-x_0}$ai​=xi​−x0​yi​−y0​​。
其实在同一条直线的所有*可以直接消灭。
那么每一次我们就对$a$a进行排序并找到有多少个不同的斜率即可。
不懂斜率的可以看这里。

得分情况

比赛时$30$30分。
改题后满分。

第三题：$peanuts$peanuts

题目

解题方法

这道题的解题方法是贪心。

贪心策略

每一次我们选择数量大的进行采摘，然后看一下是否可以摘，如果可以就摘掉，不可以则不摘。

具体实现

把所有花生存到一个数组里边，然后以数量为关键字排序，这里设$a_i$ai​为行，$b_i$bi​为列，$c_i$ci​为数量。
然后用一个$s$s数组存最少时间，则
$s_i=\begin{cases} a_i+1&i=1\\ s_{i-1}+|a_i-{a_{i-1}}|+|b_i-b_{i-1}|+1&i>1 \end{cases}$si​={ai​+1si−1​+∣ai​−ai−1​∣+∣bi​−bi−1​∣+1​i=1i>1​
接着我们看一下$s_i+a_i$si​+ai​（加上回去的时间）是否小于等于$k$k，如果小于等于，则答案加上数量，否则不加。

得分情况

比赛时满分。

第四题：$love$love

题目

解题方法

这道题的方法是动态规划。
设$f_{i,j}$fi,j​表示一种颜色用了$i$i，另一种颜色用了$j$j的方案。
则
$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}\times j$fi,j​=fi−1,j​+fi−1,j−1​×j
初始化$f_{0,i}=1,f_{i,0}=1$f0,i​=1,fi,0​=1。
然后我们可以发现答案为$f_{a,b}\times f_{b,c}\times f_{a,c}$fa,b​×fb,c​×fa,c​。
注意要开$long\:long$longlong，然后要边乘边模。

得分情况

比赛时满分。