2020.05.06【NOIP普及组】模拟赛C组32 总结

$2020.05.06$2020.05.06【$NOIP$NOIP普及组】模拟赛$C$C组$32$32 总结

这次比赛我拿了$400$400分，$AK$AK了。

第一题：移动奶牛

题目

题目描述
Farmer John的三头获奖奶牛Bessie、Elsie和Mildred，总是会迷路走到农场上遥远的地方去！他需要你帮助将她们一起赶回来。
农场的草地大体是一块狭长的区域——我们可以将其想象成一条数轴，奶牛可以占据数轴上的任意整数位置。这3头奶牛现在正位于不同的整数位置，Farmer John想要移动她们，使得她们占据三个相邻的位置（例如，位置6、7、8）。
不幸的是，奶牛们现在很困，Farmer John要让她们集中精力听从命令移动并不容易。任意时刻，他只能使得一头处在“端点”（在所有奶牛中位置最小或最大）位置的奶牛移动。当他移动奶牛时，他可以命令她走到任意一个未被占用的整数位置，只要在新的位置上她不再是一个端点。可以看到随着时间的推移，这样的移动可以使奶牛们趋向越来越近。
请求出使得奶牛们集中到相邻位置所进行的移动次数的最小和最大可能值。

输入
输入包含一行，包括三个空格分隔的整数，为Bessie、Elsie和Mildred的位置。每个位置均为一个范围1…10^9内的整数。

输出
输出的第一行包含Farmer John需要将奶牛们聚集起来所需进行的最小移动次数。第二行包含他将奶牛聚集起来能够进行的最大移动次数。

样例输入
4 7 9

样例输出
1
2

数据范围限制

提示
最小移动次数为1——如果Farmer John将位置4的奶牛移动到位置8，那么奶牛们就处在连续的位置7、8、9。最大移动次数为2。例如，位置9的奶牛可以被移动到位置6，然后位置7的奶牛可以被移动到位置5。

解题方法

首先我们先把三个数排序。

第一个答案

我们分类考虑三种情况：

1. 三个是连续的：答案为$0$0。
2. 三个的差有一个是$2$2：答案为$1$1（因为两个牛中间的位置是空的，所以另一个牛可以直接填入中间）。
3. 除了上面的其他情况：答案为$2$2。

第二个答案

我们可以发现最大值的移动方法是一步一步移，所以答案为最大差值减一。

第二题：电压放大器

题目

题目描述
西西需要把输入的电压1伏通过一系列电压放大器放大成原来的N倍，然后输出。
西西现在手上有两种放大器： 
第一种能够把X伏的电压放大成2X-1伏 
第二种能够把X伏的电压放大成2X+1伏 
放大器是串联（即按顺序放在一条线路上）的。
现在西西手上有用不完的放大器，他希望能组出一个电路，使用数量最少的放大器，使得电压被放大了刚好N倍。  

输入
一行一个正整数N(1<=N<=2*10^9)  

输出
如果无法组成电路则输出一行No solution 
否则输出两行，第一行一个整数表示最少的放大器个数K，第二行K个用空格隔开的1或2，表示放大器序列。1表示第一种，2表示第二种，其中左边为输入端。如果有多解输出任意一组。  

样例输入
5

样例输出
2
2 1

数据范围限制
20%的数据中  N<=1000

50%的数据中，N<=1000000

100%的数据如题。

提示
先经过放大器2，1*2+1=3，然后经过1，3*2-1=5。满足要求 

解题方法

这道题的方法是找规律。
我们先用$dfs$dfs找一下规律，可以发现，当$n$n为偶数时，没有答案。
那么当$n$n为奇数时是怎么样的呢？
我们继续找规律，可以发现它的最少步数是$\lfloor\log_{2}^{n}\rfloor$⌊log2n​⌋。
那么它的方案是什么呢？
我还是找规律。
注：下面只考虑$n>1$n>1且是奇数的情况。
可以发现每一个方案的第一个数都是$2$2。
然后后面的数也有规律，如下：

我们可以发现如果把上面的方案的每个数减一，则按二进制来说，前一个数加一就是后一个数。
然而我们一次加它们的差就行了。
我们直接模拟二进制加法就行了。
时间复杂度为$O(\log_{2}^{n})$O(log2n​)。

第三题：步行

题目

题目描述
ftiasch 又开发了一个奇怪的游戏，这个游戏是这样的：有N 个格子排成一列，每个格子上有一个数字，第i 个格子的数字记为Ai。这个游戏有2 种操作：

1. 如果现在在第i 个格子，则可以跳到第Ai 个格子。

2. 把某个Ai 增加或减少1。

nm 开始在第1 个格子，他需要走到第N 个格子才能通关。现在他已经头昏脑涨啦，需要你帮助他求出，从起点到终点最少需要多少次操作。

输入
第1 行，1 个整数N。
第2 行，N 个整数Ai。

输出
1 行，1 个整数，表示最少的操作次数。

样例输入
5
3 4 2 5 3

样例输出
3

数据范围限制
对于30% 的数据，1<= N<=10。

对于60% 的数据，1<= N<= 1 000。

对于100% 的数据，1 <=N<=100000，1 <=Ai<=N。

解题方法

这道题的方法是$bfs$bfs。
我们每一次只要$bfs$bfs就行了，注意要标记。
每一次有三种情况：

1. 直接去下一个点。
2. 将$a$a加上$1$1。
3. 将$a$a减去$1$1。

时间复杂度为$O(n)$O(n)。

第四题：数数

题目

题目描述
ftiasch 开发了一个奇怪的游戏，这个游戏的是这样的：一个长方形，被分成N 行M 列的格子，第i 行第j 列的格子记为(i, j)，就是说，左上角的格子是(1,1)，右下角的格子是(N,M)。开始的时候，nm 在(1,1)，他需要走到(N,M)。每一步，nm 可以走到正右方或者正下方的一个格子。具体地说，如果nm 现在在(x, y)，那么他可以走到(x,y + 1) 或(x + 1,y)。当然，nm 不能走出离开这个长方形。
每个格子有积分，用一个1—10 的整数表示。经过这个格子，就会获取这个格子的积分（起点和终点的积分也计算）。通过的方法是：到达(N,M) 的时候，积分恰好为P。
现在给出这个长方形每个格子的积分，你需要帮助nm，求出从起点走到终点，积分为P的线路有多少条。

输入
第1 行，3 个整数N, M, P。接下来N 行，每行M 个整数Aij，表示格子(i, j) 的积分。

输出
1 行，1 个整数，表示积分为P 线路的数量。因为数值太大，你只需要输出结果除以(10^9 +7) 的余数。

样例输入
3 3 9
2 2 1
2 2 2
1 2 2

样例输出
2

数据范围限制
对于50% 的数据，1<= N,M<=10。

对于100% 的数据，1<=N,M<=100，0 <= Aij<=10。

解题方法

这道题的方法是$dp$dp。
设$dp_{i,j,k}$dpi,j,k​表示到了$(i,j)$(i,j)这个点，和为$k$k的方案数。
我们发现$(i,j)$(i,j)这个点可以从$(i-1,j)$(i−1,j)和$(i,j-1)$(i,j−1)这两个点转移。
则
$f_{i,j,k}=f_{i-1,j,k-a_{i,j}}+f_{i,j-1,k-a_{i,j}}(a_{i,j}\leq k\leq p)$fi,j,k​=fi−1,j,k−ai,j​​+fi,j−1,k−ai,j​​(ai,j​≤k≤p)
注意：$f_{1,1,a_{1,1}}=1$f1,1,a1,1​​=1。
答案为$f_{n,m,p}$fn,m,p​。
时间复杂度为$O(nmp)$O(nmp)