暑假集训测试（三）题解

题1、散步

　模拟/数学

　　笨办法：用循环逐秒计算行走路程。时间复杂度 O(T)

　　巧办法：算周期数和特判最后一个周期的情况。时间复杂度 O(1)

题2、犬界病毒

　模拟+贪心

　把所有狗的位置由小到大排序。经分析，确定最左边的病狗一定是初始感染者（请思考）。

　1、传染半径的确定：

　　方法1、扫描+查找：

　　从第一只病狗开始，向右扫描每只狗的位置，对于第i只狗，若其有病，则忽略，若其健康，则计算离左右最近的病狗的距离left和right，说明传染半径R不会大于min

(left,right)，所以R=min(R,min(left,right))。

　　扫描+查找时间复杂度为O(n^2);

　　优化：分行左右和从右向左两次扫描，时间复杂度降为O(n)

　　方法2、二分答案：

　　答案范围1..10^6，每二分一个mid，即假设传染半径小mid，当check(mid)为true时，说明mid合适，下次看能否大一点（即右半边二分），否则继续从在左半边猜。
　　check(mid)时，从第一只病狗开始，与其距离小于mid的狗会被感染，如果此时这只狗在输入的数据中健康则返回false；继续下去，每次扫描一只狗都看和左边最近的病狗的

距离是否小于mid，小于则会被传染，否则，从下一只病狗开始继续验证，若所有验证完后，都未发现错误，且病狗数量一致，则返回true。

　　时间复杂度O(nlog(n))

　　2、初始感染的最小数量：

　　知道确切的R值，则用check(mid)的方法，计算最初染病狗的数量。

题3、社区划分

　　把居民点当成图的一个顶点，两个顶点之间的边权就是他们之间距离，一个社区由若干居民点构成，看成一个连通分量

　 算法1、二分答案+求连通分量

　　社区间的距离范围为 0,maxd。因此答案范围就是[0,maxd]，于是我们二分猜最近的社区的距离，当猜得为mid时，则假定图中只存在权值小于mid的边，然后用DFS/BFS/并查集求连通分量数cnt，如果cnt<K，则说明mid小了，下次在右半边猜[mid,r]，否则在左半边猜。

　 算法2、类似Kruskal的贪心算法

　　把所有边权由小到大排序，然后类似Kruskal算法，按权值从小到大向并查集里加边，直到只有K-1个集合为止，则答案就是最后加入边的权值。

题4、观影难题

　题意：要把一个序列变成“不下降序列”或“不上升序列”，最少要修改几个元素。

　 算法1、暴力枚举（1-7个测试点）

　　对于非下降方向，枚举 i 和 j：
　　　设第一段为：a[1]..a[i] 即该段的所有数字都为1；
　　　设第二段为：a[i+1],a[j] 即该段的所有数字都为2；
　　　设第三段为：a[j+1]..a[n] 即该段的所有数字都为3；
　　然后每段计算修改元素个数，最后选一个最优的，

　　对于非上升方向类似。

　 算法2、最长单调子序列（期望得分100分）

　　对于变成“不下降序列”，修改尽量少的元素，意味着不修改的元素要尽量多，所以先求“最长不下降子序列”长度，假设这个长度为len1，则最少修改元素个数为 N-len1。
　　对于变成“不上升序列”，一样的道理，求“最长不上升子序列”长度len2，则此时最少修改的元素个数为N-len2。
　　最后的答案为：min(N-len1,N-len2)。

　　最长单调子序列的算法有两种：动态规划和贪心。

　　DP的时间复杂度为O(n^2)，期望得80分；
　　贪心时间复杂度为O(nlogn)，期望得100分。

　 算法3、另一种状态函数设计（1-20个测试点）

　　因为序列只有1,2,3这三种元素，所以可以据此设状态函数：

　　对于变成“不下降序列”，状态函数设为：
　　　f[i][1] 表示前i个元素，第i个元素为1时，需要修改的最少元素
　　　f[i][2] 表示前i个元素，第i个元素为2时，需要修改的最少元素
　　　f[i][3] 表示前i个元素，第i个元素为3时，需要修改的最少元素

　　则转移为：
　　　f[i][1] = f[i-1][1] + (D[i]!=1)
　　　f[i][2] = min(f[i-1][1] , f[i-1][2]) + (D[i]!=2)
　　　f[i][3] = min(f[i-1][1] , f[i-1][2] , f[i-1][3] ) + (D[i]!=3)

　　边界为：
　　　f[1][1] = D[1]!=1
　　　f[1][2] = D[1]!=2
　　　f[1][3] = D[1]!=3

　　答案为：Ans1 = min(f[N][1] , f[N][2] , f[N][3])

　　对于变成“不上升序列”，类似得到Ans2。

　　最后答案为：Ans = min(Ans1,Ans2)