2020.04.18【NOIP普及组】模拟赛C组27 总结

$2020.04.18$2020.04.18【$NOIP$NOIP普及组】模拟赛$C$C组$27$27 总结

这次比赛我$AK$AK了，拿了$300$300分。说实话，这次比赛的题目真的很水，很水，很水。

第一题：$Mixing$Mixing $Milk$Milk

题目

题目描述
农业，尤其是生产牛奶，是一个竞争激烈的行业。Farmer John发现如果他不在牛奶生产工艺上有所创新，他的乳制品生意可能就会受到重创！
幸运的是，Farmer John想出了一个好主意。他的三头获奖的乳牛，Bessie、Elsie和Mildred，各自产奶的口味有些许不同，他打算混合这三种牛奶调制出完美的口味。
为了混合这三种不同的牛奶，他拿来三个桶，其中分别装有三头奶牛所产的奶。这些桶可能有不同的容积，也可能并没有完全装满。然后他将桶1的牛奶倒入桶2，然后将桶2中的牛奶倒入桶3，然后将桶3中的牛奶倒入桶1，然后再将桶1的牛奶倒入桶2，如此周期性地操作，共计进行100次（所以第100次操作会是桶1倒入桶2）。当Farmer John将桶a中的牛奶倒入桶b时，他会倒出尽可能多的牛奶，直到桶a被倒空或是桶b被倒满。
请告诉Farmer John当他倒了100次之后每个桶里将会有多少牛奶。

输入
输入文件的第一行包含两个空格分隔的整数：第一个桶的容积c1，以及第一个桶里的牛奶量m1。c1和m1均为正，并且不超过10^9。第二和第三行类似地包含第二和第三个桶的容积和牛奶量。

输出
输出三行，给出倒了100次之后每个桶里的牛奶量。

样例输入
10 3
11 4
12 5

样例输出
0
10
2

数据范围限制

提示
在这个例子中，每倒一次之后每个桶里的牛奶量如下：
初始状态：   3   4   5
1. 桶1->2：  0   7   5
2. 桶2->3：  0   0   12
3. 桶3->1：  10  0   2
4. 桶1->2：  0   10  2
5. 桶2->3：  0   0   12
（之后最后三个状态循环出现……）

解题方法

这道题非常简单，直接模拟就可以了，真不明白为什么很多人这题都会错。
我们可以定义一个函数来进行倒奶。
如果倒过去之后没倒满，就不用管了；否则就与它的容量取一个最小值。
程序如下：

void ck(int a,int b)
{
	int x,y;
	x=min(c[b],m[a]+m[b]);
	y=m[a]-(x-m[b]);
	m[a]=y;
	m[b]=x;
}

那么我们就可以循环$1$1到$100$100进行模拟，可以发现如果当前的操作次数模$3$3等于$1$1，就代表从$1\rightarrow2$1→2；如果等于$2$2，就代表从$2\rightarrow3$2→3；如果等于$0$0，就代表从$3\rightarrow1$3→1。
程序如下：

for(int i=1;i<=100;i++)
{
	int j=i%3+1,k;
	k=j-1;
	if(k==0)
	{
		k=3;
	}
	ck(k,j);
}

时间复杂度只是一个常数，$100$100。

得分情况

比赛时满分。

第二题：$The$The $Bucket$Bucket $List$List

题目

题目描述
Farmer John正在考虑改变他给奶牛挤奶的时候分配牛奶桶的方式。他认为这最终能使得他使用数量更少的桶，然而他不清楚具体是多少。请帮助他！
Farmer John有N头奶牛（1≤N≤100），方便起见编号为1…N。第i头奶牛需要从时间si到时间ti之间挤奶，并且挤奶过程中需要用到bi个桶。于是多头奶牛可能在同一时刻都在挤奶；如果这样，她们不能使用相同的桶。也就是说，一个在第i头奶牛挤奶时用的桶不可以被任何在时间si到时间ti之间挤奶的其他奶牛使用。当然，这个桶在这段时间之外可以被其他奶牛所使用。为了简化他的工作，FJ保证在任一时刻，至多只有一头奶牛开始或是结束挤奶（也就是说，所有的si和ti各不相同）。
FJ有一个储藏室，里面有依次编号为1、2、3、……的桶。在他的挤奶策略中，当某一头奶牛（比如说，奶牛i）开始挤奶（在时间si），FJ就跑到储藏室取出编号最小的bi个桶分配给第i头奶牛用来挤奶。
请求出FJ需要在储藏室中存放多少个桶才能使得他能够顺利地给所有奶牛挤奶。

输入
输入的第一行包含N。以下N行，每行描述了一头奶牛，包含三个空格分隔的数si，ti，和bi。其中si和ti均为1…1000之间的整数，bi为1…10之间的整数。

输出
输出一个整数，为FJ需要的桶的数量。

样例输入
3
4 10 1
8 13 3
2 6 2

样例输出
4

数据范围限制

提示
在这个例子中，FJ需要4个桶：他用桶1和桶2来给奶牛3挤奶（从时间2开始）。他用桶3给奶牛1挤奶（从时间4开始）。当奶牛2在时间8开始挤奶时，桶1和桶2可以再次利用，然而桶3不可以，所以他会使用桶1、桶2和桶4。

解题思路

这道题目的方法是拆分或者暴力，都可以过。
我用的是暴力$+$+线段树优化。

• 暴力
  我们可以直接把$s$s到$t$t区间的标记加上$b$b，最后只要看最大的那个就行了——因为只有最大的才能符合所有要求。
  时间复杂度为$O(\sum_{i=1}^{n}{t_i-s_i})$O(∑i=1n​ti​−si​)，可以过。
  注：上面的式子表示所有$t_i-s_i$ti​−si​的和。
• 暴力$+$+线段树
  我们可以用线段树来维护区间的最大值，从而把时间复杂度降到$O(n\log_{1000}^{2})$O(nlog10002​)，大概是$O(10n)$O(10n)，可以过。
  不会线段树的可以自己学一下。
• 拆分
  直接将$s-1$s−1和$t$t都标记一下，最后用前缀和来处理。
  时间复杂度为$O(n)$O(n)。

得分情况

比赛时没有想到拆分，用了暴力$+$+线段树，还是满分。

第三题：$Back$Back $and$and $Forth$Forth

题目

题目描述
Farmer John有两个挤奶棚，每个挤奶棚里各有一个奶罐和一个装有10个各种尺寸的桶的储物柜。他喜欢将在两个挤奶棚之间来回运送牛奶作为一种锻炼方式。
周一，Farmer John量了恰好1000加仑的牛奶放在第一个挤奶棚的奶罐里，又量了恰好1000加仑的牛奶放在第二个挤奶棚的奶罐里。
周二，他从第一个挤奶棚里取出一个桶，并装满牛奶，然后将牛奶运到第二个挤奶棚，并将牛奶倒进奶罐。他把这个桶留在了第二个挤奶棚。
周三，他从第二个挤奶棚里取出一个桶（可能是周二留在这里的），并装满牛奶，然后将牛奶运到第一个挤奶棚，并将牛奶倒进奶罐。他把这个桶留在了第一个挤奶棚。
周四，他从第一个挤奶棚里取出一个桶（可能是周三留在这里的），并装满牛奶，然后将牛奶运到第二个挤奶棚，并将牛奶倒进奶罐。他把这个桶留在了第二个挤奶棚。
周五，他从第二个挤奶棚里取出一个桶（可能是周二或周四留在这里的），并装满牛奶，然后将牛奶运到第一个挤奶棚，并将牛奶倒进奶罐。他把这个桶留在了第一个挤奶棚。
此时Farmer John测量了第一个挤奶棚的奶罐里的牛奶。他总共可能得到多少种不同的读数？

输入
输入的第一行包含10个整数，为第一个挤奶棚里初始的桶的容积。输入的第二行也包含10个整数，为第二个挤奶棚里初始的桶的容积。所有桶的容积均在1…100的范围内。

输出
输出Farmer John在周五之后测量第一个挤奶棚里的奶罐的牛奶时可能得到的读数的数量。

样例输入
1 1 1 1 1 1 1 1 1 2
5 5 5 5 5 5 5 5 5 5

样例输出
5

数据范围限制

提示
在这个例子中，最后第一个挤奶棚的奶罐中的牛奶量总共有5种可能的结果：
1000：FJ可以在每次往返的时候都携带同一个桶，从而不会改变第一个挤奶棚的奶罐的牛奶量。
1003：FJ可以在周二运送2个单位，周三5个单位，周四1个单位，周五1个单位。
1004：FJ可以在周二运送1个单位，周三5个单位，周四1个单位，周五1个单位。
1007：FJ可以在周二运送1个单位，周三5个单位，周四2个单位，周五5个单位。
1008：FJ可以在周二运送1个单位，周三5个单位，周四1个单位，周五5个单位。

解题方法

直接$dfs$dfs或者暴力枚举，其实都是一样的。
我们只要枚举出所有情况，然后用一个标记数组来存（我怕会爆，所以没有用这种方法），最后统计。
我的方法：
把所有情况列出来并排序。
接下来设$f_i$fi​表示$i$i之前（包括$i$i）一共有多少种类型，则
$f_i=\begin{cases} f_{i-1}+1 & a_i\not=a_{i-1}\\ f_{i-1} & a_i=a_{i-1} \end{cases}$fi​={fi−1​+1fi−1​​ai​​=ai−1​ai​=ai−1​​
答案就是$f_n$fn​。
注：$a$a表示排完序的序列，$n$n表示$a$a的元素个数。

得分情况

比赛时满分。