【题解】[初一编程社暑假集训前难题复习]

A. 扩散

法一：二分时间+并查集判连通性

法二：直接floyd

*B. 赶牛入圈

解析：大概是二维前缀和+离散化 发现题目中未出现的行和列都对答案不会产生影响，可以直接略过，于是将数（每个坐标的行和列）一起离散化，每个数变成了对应数组中的下标，这样保持了大小关系，对二维前缀和无影响

然后二分边长。

int get(int x) { return lower_bound(c+1,c+1+cnt,x)-c; } map<int,int> mp; for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); if(!mp[a[i]]) mp[a[i]]=1,c[++cnt]=a[i]; if(!mp[b[i]]) mp[b[i]]=1,c[++cnt]=b[i]; } sort(c+1,c+1+cnt); for(int i=1;i<=n;i++) { int x=get(a[i]),y=get(b[i]); sum[x][y]++; }

C. 老鼠与猫的交易

解析：贪心，$a[i].s=a[i].p/a[i].v$，从大到小排序即可

*D. 火柴排队

解析：不难想到贪心算法，每个数列最大与最大，次大与次大相对应就是最小答案。由于每个数列没有重复的数，我们可以把每个序列分别离散化，拿到每个数的排序后的位置。 然后说白了就是求两个序列之间的逆序对。逆序对，说白了就是求一个随机序列排序成从小到大的序列的最小步数。

如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j]，则 这个有序对称为 A 的一个逆序对，也称作逆序数。

关键来了：对a中的每个数，找到b中该数的下标（由于离散化后数为[1,n],可保证一一映射），得到num数组，求num数组中的逆序对，就是答案。

E. 旅行家的预算

忘了。。找时间再看一下

F. [NOIP2004]虫食算

咕咕咕

G. 马里奥的梯子

解析：二分梯子长度，然后BFS，没难度，简单的跑图，边权也没有

H. 抓住那头牛

解析：BFS即可，边权为1，没难度

I. 神奇的通道

法一：搜索 法二：并查集

*J. 水池

*K. 观光公交

背景：晚上和WGY上机房，然后写对了

解析：首先发现每个人的旅行时间=到达终点站时间-出发时间，我们只需要求出最后的$a[i]$ 数组即可 然后经过一系列分析： 设$c[i]$表示i站台最晚出发时间，$d[i]$表示终点为i站台的人数 考虑$k=0$，不难写出：$a[i]=max(a[i-1],c[i-1])+t[i]$ $k>0$时，考虑加速i，若$a[i]<=c[i]$,显然只会$a[i]--$，对后续无影响。贡献：$d[i]$ 若$a[i]>c[i]$，则$a[i+1]--$，继续考虑$a[i+1]>c[i+1]$,又对$a[i+2]--$，…… 贡献:$d[i]+d[i+1]+...+d[i+k](a[i+k]<=c[i+k])$

我们用$sum[i]$表示对i使用加速器的价值，然后逆序遍历，得到价值最高的点，$t[i]--$

时间复杂度：O(N*K)