CSU-ACM Home Page

中南大学第七届大学生程序设计竞赛-解题报告【简略版】

Update Time: 2017-03-31 19:27:24     Recent Editor: CSGrandeur     Create Time: 2013-04-15 20:47:58     Creator: CSGrandeur    


A. Pingpang Balls

依次读入每个球的重量,用if语句判断球的重量在哪个星级范围内并使对应的计数器+1,最后输出结果即可。

B. Morse Code Wristwatch

将数字或字母翻译成摩斯码并用点阵的形式输出出来即可。为了程序写起来方便,可以先用数组打一张表,描述每个数字和APM对应的点阵,这样需要用到哪个数字或字母的时候直接打印对应的数组即可。

C. Swap Digits

一个贪心的思路就是我们要保证最高位尽可能大,如果同时有多种方案保证最高位尽可能大,那么就应选择交换次数尽量少的方案。

于是我们可以从高位向低位遍历数组,假设当前还剩余k次交换机会,那么就从当前位开始,向后找k个数字,因为这k个数字都可能通过交换移到当前位置,然后包括当前位数字在内选择最大的一个数字交换到当前位置,如果有多个最大的数字,则选择离当前位置最近的那个数字交换过来,因为这样可以保证交换的次数尽可能少。

D. Brackets Sequence

这个题目如果熟悉判断一个括号序列是否合法的方法的话,应该还比较容易想到解法,所以先提一下判断括号序列是否合法的一个方法。

我们将一个括号序列中的左括号当成1,右括号当成-1,然后从左至右依次累加,就可以得到一个整数序列,比如()(()())对应的整数序列就是1 0 1 2 1 2 1 0,如果整数序列中不存在负数,且最后一个数是0,那么这个括号序列就是合法的。

接下来我们考虑此题的解法。由于题目说了答案至少是1,那么也就是说这个序列相比合法的括号序列而言只是少了一个括号,至于少的是左括号还是右括号,我们根据括号的数量是很容易判断出来的。

不妨先讨论缺少一个左括号的情况。比如(()))()这个序列,对应的整数序列就是1 2 1 0 -1 0 -1。接着我们考虑在哪里插入一个左括号可以使其变成一个合法的括号序列,其实也就是考虑在哪里插入一个左括号后使这个整数序列所有的值都是非负的。考虑到插入一个左括号的效果是插入一个整数,并且让插入位置右边的所有整数都+1,因此左括号可以插入的最右的位置应该是最左的-1的左边,同时这个位置左边的任何一个位置都可以作为插入位置。这样我们只要遍历一下这个整数序列找到第一个-1出现的位置就可以知道有多少个位置可以插入左括号了。

至于缺少一个右括号的情况,比如()((())这个序列,我们可以将其翻转一下,就变成了(()))(),这样就又变成了缺少一个左括号的情况了。

E. Karma

其实karma每走过一条线段,灵魂连接扫过的区域就是一个三角形(也可能退化成线段),因此在karma走的全程中,实际上就是扫过了若干个三角形,对于每个三角形,都判断一下哪个点在三角形中并标记一下。最后统计一下有多少个点至少在一个三角形中即可。

F. Two Edge-disjoint Paths

这个题目主要卡一些错误的算法,时间上倒没有刻意卡什么,大多数数据都是随机+筛选得到的。

首先提一些错误的一些思想:

  1. 费用流。直接建立超级源点和超级汇点做费用流,或者先做s1->t1的费用流,如果有解再做s2->t2的费用流等。
  2. 贪心。先求一条s1->t1的最短路,再求一条s2->t2的最短路。

标程是用搜索做的,整体的思路是先搜s1->t1的可行路,当搜到可行路后做s2->t2的最短路。不过裸着搜会TLE的,需要考虑加一些剪枝(但是下面的剪枝不一定需要全要有):

  1. 搜可行路的过程中没必要经过重复的点。因为经过重复的点就会形成环,而砍掉这个环后不会使结果变得更差。现场赛和semilive的时候如果有这个剪枝就可以过的,因为那时的数据没有人为构造的,都是随机+筛选的,后来[HDU]夏天的风又提供了几组强力测试数据,所以单纯有这个剪枝也过不了了。
  2. 搜可行路时,如果两点之间有多条边时,只选最小的,其他的不用考虑。
  3. A*剪枝,在搜的过程中,假设之前已经走了pre_dis,当前节点为cur,目前最优的结果是opt_dis,那么如果pre_dis + dis(cur, t1) + dis(t1, cur) >= opt_dis,就直接return,其中dis(x, y)表示在当前图(不能经过一些之前搜索的时候已经经过的边)中,xy的最短路。
  4. ...(under construction)

G. Balls in the Boxes

如果设初始时刻球一共有sum个,球最少的那个盒子中有min个球,球最多的那个盒子中有max个球,经过了x次操作,每个盒子中球的数量变成了y,那么就会有sum + x * N = y * M。如果这个方程不存在整数解,那么显然题目一定无解。而如果题目无解,那么这个方程是否就一定不存在整数解呢?这个等解决了下面的问题自然就明了了。

如果方程sum + x * N = y * M有整数解的话,那么解出来的最小的x是否就是最后结果呢?当然不一定,因为最起码x可能是负的。实际上最后解至少还需满足几个不等式:

  1. x >= max - min。意思是这x次操作,至少得弥补maxmin之间的差距。
  2. y >= max。最后每个盒子中球的个数显然要比max大。
  3. x >= y - min。意思是一开始球最少的盒子中一共被添加了y - min球,那么操作次数x就肯定不能小于y - min

其中1这个不等式可以由2和3推得,所以1就没什么用了,我们只考虑2和3。那么现在我们有一个大胆的猜想——在满足2、3的条件下方程中x的最小整数解就是最后的答案。

而这个猜想是不是对的呢?我们接下来就证实一下。

假设题目有解,那么解必然要满足上面的不等式。于是我们可以说,对于在满足上面不等式的条件下解出的x的最小整数解ans,如果ans是可行解,那么一定是最优解。于是,只要我们能证明ans是可行解,那么就能说明我们的猜想是正确的。

我们不妨用构造的方式去证明ans是可行解,也就是说,我们人为安排一种操作的过程,使得经过ans次操作之后,每个盒子中球的数量都是相等的。接下来我们通过一个例子来说明,如果人为安排操作的过程。

4 3
0 2 2 2

这组样例的答案是6。我们得到的方程是6 + 3 * x = 4 * y,需要满足的不等式是y >= 5x >= y,在满足这个不等式的条件下,解出的x的最小整数解ans是6,对应的y也是6。也就是说一共经过了6次操作,第一个盒子要放6个球,第二、三、四个盒子分别要放4个球。如果每个盒子要放多少个球就用多少个空方块代替,我们就能得到下面的图。

balls_and_boxes_1

我们从第一列开始,从下向上依次填1, 2, ..., ans, 1, 2..., ans, 1, 2...,第一列填完就继续第二列,第二列填完就填第三列...,然后就能得到下面这样的图。

balls_and_boxes_2

于是我们的操作过程就是这样的——第一次在所有标有1的盒子中各添加一个球,第二次在所有标有2的盒子中各添加一个球,...,第k次在所有标有k的盒子中各添一个球,...

由于满足x >= y - min,所以同一个盒子中不会有相同的数字,而且最后各个盒子中的球数一定是y(因为每个盒子所缺的球我们都放进去了)。

于是,到此为止,我们证明了满足上述不等式的条件下解出的x的最小解ans是可行解,也就证明了我们猜想是正确的。

现在还剩前面的一个问题没有解释——如果题目无解,那么方程sum + x * N = y * M是否就一定不存在整数解呢?这个我们用反正法解决。首先假设题目无解的情况下这个方程存在一组整数解。而实际上存在一组整数解就存在无数组整数解,而且随着x的增大,y也是在增大的,所以y >= max随着y的增大总会有一刻满足的。那么x >= y - min随着x的增大是不是也一定会满足呢?当x趋于正无穷时有x * N = y * M,此时由于N < M所以有x > y,自然就有x >= y - min。这样两个不等式随着x的增大总会满足的,于是题目就一定有解了,而这就与之前的假设就矛盾了。因此题目无解和方程没有整数解是等价的。

至此,这个问题就完美的解决了。总结一下算法——首先判断方程sum + x * N = y * M是否整数解,如果没有那么最后一定无解,如果有那么就求满足y >= maxx >= y - min这两个条件的x的最小整数解ansans就是最后的答案。

H. Happy Number

这个题目可以用dp去做,一位一位地考虑,先dp出小于B+1的Happy Number有多少个,再dp出小于A的Happy Number有多少个,然后作差就是最后的结果。

但是直接dp出小于x的Happy Number有多少个不大好办,我们不妨先dp出小于x的各位数字的平方和为j的数有多少个,因为根据各位数的平方和实际上也就可以断定是否是Happy Number了。

虽然数很大,但是其实各位数字的平方和并不大,18*9*9才1000多,因此我们在dp的时候可以用一维表示各位数字的平方和这个状态。这样我们可以用f[i][j]表示递推到第i位的时候,数字平方和为j,且小于x的数有多少个,i要从高位向低位dp。f[i][j]的一部分来源于在前面就已经确定了会比x小的那些数,那么第i位是0-9均可,另一部分来源于前面各位均是和x相等的,只有这一位比x的对应位要小的数。

最后我们实际上dp出的是小于x的,且各位数字平方和为j的数各有多少个,那么这些数中哪些是Happy Number呢?这当然取决于j的值了。因为j的范围不大,1000多,我们可以预处理出来每个j都是否是Happy Number。这样最后我们把是Happy Number的j对应的dp出来的数量累加起来,就是小于x的所有Happy Number的数量了。

I. Counting Route Sequence

不同的路径序列的个数可以由下面这个式子计算得到,其中a[i]表示点ii+1之间的边数。

route_sequence_1

至于这个式子是怎么来的,就要费一番口舌来解释了。

由于按题意来看,两点之间的边是相同的,所以我们不妨指定经过这些的顺序,默认由上向下依次经过地这些边,这样我们就可以对这些边定向了。

考虑下面这个图,我们不妨把1和2之间的边由上到下依次记为H1、H2、H3(黑1、黑2、黑3),2和3之间的边由上到下依次记为L1、L2、L3、L4、L5。

route_sequence_2

假设我们先走完所有黑边,再走完所有蓝边,再像这样的形式走完剩下所有相邻两点间的边,那么显然最后只有一种序列。而为什么会产生多种序列呢?关键就在于可能会交替经过黑边和蓝边,比如走完H1不立刻去走H2,而是去走L1,等等。这样一旦黑边和蓝边是交替过的,就会产生多种情况,那么黑边和蓝边之间有多少种可能的交替情况呢?这个可以用组合数算出来,也就是我们上面的那个式子所展示的组合数。而且,不同的交替情况都绝对会对应着不同的路径序列。

这样我们只是考虑了1和2以及2和3之间的边交替的情况对最后结果带来的影响,那么2和3以及3和4之间的边交替情况对结果又有怎样的影响呢?其实计算方式是一样的,而且更重要的是,在计算2和3以及3和4之间的边的交替情况时,与1和2以及2和3之间的边的交替情况是没有任何关系的,也就是说是相互独立的。既然是相互独立的,那么在计算最后结果的时候把两部分影响乘起来就可以了。同样的,我们就会依次乘起来很多项,也就得到了上面那个式子。

J. Real Numbers Magic Square

我们可以用S来代替幻和,并列出2*N的等式,即S=第一行各个数的和,S=第二行各个数的和,...,S=第一列各个数的和,S=第二列各个数的和,...至于某行或者某列的和的表达式,如果那个位置已经填了数,那么就对应着一个常数,如果还没有填数,那么就对应着一个未知数。最后就是求S的最小值。

由于一个等式可以用两个不等式来替代,比如x=y,那么就可以写成x>=y,且x<=y,这样我们把上面的等式都转化成这样的不等式之后,再用线性规划求解S的最小值即可。

K. Eat the Bean

方法应该不难想,就是直接BFS+坐标变换即可,然后判断点是否在凸多面体内,只不过代码嘛...反正我不会写...这个题也不是我出的...