2010年7月18日星期六
Question1：n个人围着一个桌子坐，每个人都有一个需求，假如一个人的需求是1，2，就表示他希望1，2坐在他的两边，若每个人的需要都可以满足，则我们需要求出 最少移动几个人可以达到每个人的要求都满足的状态（假定一开始的座位顺序为1，2，3，4，……，n）
分析：我们可以通过dfs找到一条闭合的回路即最终的状态，要想求出最少移动人数实际上就要找出最小的错排数，由于是圆桌旋转会出现另外的最优状态，所以一方面我们可以通过从每一个位置开始做起始点求一遍错排数，然后求出最小的错排数即为结果，但是这样做的复杂度是O(n^2)在题目（10^6）的数据范围下时间是难以承受的。
策略：分析中提到我们需要找出以各个点做起始点不同的错排的数目，事实上我们只要记录每个点它在哪一个位置在起始状态下是正确排的就可以了，这样的话我们就可以得到在不同起始状态下正确点的个数，即可以得到错排数。所以我们只需要扫描一遍，若一个点离它正确位置为k，即它在旋转了k个数的状态下是正确排列的，所以cnt[k]++,最后n-max(cnt[k])即为题目的解。
讲题人：rupxup
Question2：对于a,b,e,f整四个整数求最小的整数c使得存在d满足a/b<c/d<e/f.
分析：由题目可知事实上在c最小的情况下，也可以找到一个最小的d，这两个问题是相通的，我们先看两种特殊的情况：
a：a/b<1<e/f则存在c=1，d=1为题的解。
b：a/b=0，则存在c=1,d=f/e的下取整+1为题的解。
策略：对于上述两种特殊情况可以直接给出解，需要看其它情况可不可能转化成这两种特殊的情况，1.对于1<a/b<e/f,对于这种情况我们可以通过将等式两边同时减去这个整数来转化，可能出现上述a那种特殊状态，则得解c=1+k*d,d=1,即c=1+k;也有可能得到下述情况2.
2.对于a/b<e/f<1的情况可以通过求倒数之后化作1的情况，故1，2两种非特殊情况可以相互转化而且必然会转化到某一个特殊的状态，不断的在减，如果中间没有达到特殊状态a，也一定会达到特殊状态b的。
讲题人：rupxup
Question3:一只蚂蚁在一个木棍上爬，若这个蚂蚁的速度为v，木棍每分钟长长m，（相对的长长，向两端长长，蚂蚁的相对位置会保持，如原先在1/2处长长后蚂蚁还是在木棍1/2处），给出v和m和原始木棍长l，问是否蚂蚁是否有可能从最开始的一端爬到另一端。
题解：蚂蚁在木棍上的比例是不变的，只要蚂蚁在前进的过程中速度大于0，比例总是在增加，它就一定能爬到另一端。
讲题人：Abbie
Question4：给出原来有V升水，淘衣服上的洗衣粉，最多可以把洗衣粉分成n份，每次淘完还会残留b升脏水，问最多淘多少次，可以使得残留最少。
题解：事实上n次的时候残留最少，这是一个不断稀释的过程，用同样多的水稀释溶液，这个次数进行的越多，最后的溶液越稀。
PS：其实洗衣服可以多淘几次少用水的。
讲题人：Abbie
Question5：笔记本放置问题，给你一个方桌，一个矩形，问最少覆盖多少桌面能把这个矩形放到桌面上。
策略：让矩形的中心位于方桌的一个角上所覆盖的面积会最小。
讲题人：Abbie
Question6：一遍dfs求强联通分量。我们在求强联通分量时，一般是把原图做一遍dfs，记录下各个点的访问结束时间，然后以访问结束时间的降序，将反向图做一遍dfs。下面是一种可以一遍dfs求出强联通分量的算法。
相关内容：我们在求一个图中的割点割边时，用一个数组dep表示点的访问时间，数组low表示其儿子可以到达的最浅位置，若low[v]>=dep[u](其实也是low[u]>=dep[u])时该点是割点，这么说实际上割点的low和dep相等，我们考虑一个图，若一个点是割点，则说明其儿子可以到达的最小深度也为它，这么说事实上它的这些儿子是可以通过它相互可达的。所以对于一个割点构成的分量若low值都等于割点的dep值，则这可以构成一个强联通分量。
PS:不是太懂。
讲题人：brent
Question7:单调队列在dp中的运用。
一些时候我们的dp方程中会出现一个值与它之前的多个值相关，这时候很多情况下会出现重复计算问题，比如每个数与它上个状态的它的前面所有状态有关，则我们每次都要从头来枚举这些值，事实上我们进行了比较之后可以记录当前的最优值，下次只需要比较最优值和新增值即可。对于有限定如和它前k个数有关，我们就可以用单调队列，来使用O(1)的时间来随时得到这个最大值。
讲题人：czz