荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: 长春赛区网络预赛试题报告
发信站: 荔园晨风BBS站 (Thu Oct 11 09:07:31 2007), 站内
长春赛区网络预赛试题报告
By skywind
长春赛区网络预选赛已经结束了，首先恭贺那些取得现场决赛资格的学校和队伍，并且希望
没有出线的队伍能够再接再厉，在北京或者以后的比赛中取得更好成绩
在比赛刚刚开始的时候，由于各种突发情况，造成诸如网页中缺少图案、压缩文件有毛病等
问题，在此一并向大家致歉。好在后来还比较顺利。我们使用3台服务器，都不停的运算，
特别是在比赛的最后阶段，有时服务器都在waiting，得等一段时间才能响应。但这些都不
影响判题和成绩的计算。
本次比赛，共有130所院校，698个队，34支女队参加（还有一个账户是我们内部测试的，所
以看到699个），我们的账户是随机产生的，所以序号和报名等次序无关，这些也是为了增
大比赛的悬念。
本次比赛，共有9个题目，其中有7个题目有队伍解答出来，第一名的队伍解答出6道。比赛
过程中，提交了6353次，正确570次，有490支队伍参与提交，86所学校，236支队伍至少做
出一个题目。
下面说一下各个题目：
A：2450：Is it possible?
足球这个题目，是尝试次数最多的。因为描述比较简单，一般也能想到一定的解决方案。不
过看看前面几个队伍的提交就能发现，高手并不先作这个题目。因为实际上这个问题比较复
杂，需要考虑情况较多，因此比较容易出错。下面仔细说一说。
这个题目，一方面考虑是否可能时，要判断总场次的奇偶性、判断每支队伍分数是否可能，
并计算出总的平局数和胜局数。并且还要进行搜索，计算这种情况是否可能。搜索时从每支
队伍最少的可能平局数直到最大的可能平局数计算，看总的得分和平局数能否满足；并且每
队胜利数不能大于其他队失败数和，每队失败数不能大于其他队胜利数和，每队平局数不能
大于其他队平局数和。
另一方面，还考察处理输入和字符串的能力。因为题目中说，一行只有最后两个整数是需要
的，前面可以是任意符号。一个可行的做法是先读一行到字符串中，从后往前找整数；或者
从字符串中读每个token，直到最后两个，一定是整数。这件事情也需要仔细处理。
总的来说，我觉得这是一个考察编程基本功力的题目。
B：2451：Fatmouse and JavaBean
题目描述比较复杂，其实读懂了就知道，这就是一个最短路径问题。分别求出老鼠、猫到各
房间的最短时间即可。可用单源最短路的dijkstra算法或其他算法。
C：2452：Transportation Power Augmentation
这是一个约束最大流（constrained maximum flow）问题，其解法类似于最小费用流。注意
本题边的耗费是分段线性函数(convex function)。出题者给出了最坏复杂度O(min{d, mu}
m log n)的算法，其核心为含负权图上的successive shortest path(SSP)算法。详细方法
可搜索相关论文。
D：2453：Candy
每颗糖对应每个人只有两种状态，故可将糖表示为2^M种状态，可转换为网络流求解，每种
糖对应一个顶点，每个人对应一个顶点，另建立源点汇点，人到汇点的路容量为
floor(Bi/2)，源点到每种糖的路容量为无穷，每种糖与每个人之间的喜好度为2则该种糖的
个数为1，否则为0，直接求最大流 ans，判断 (ans+N)与(B1+B2+..+BM)大小。
E：2454: Hyper-Calculator
相信有很多人对这个题目很头疼，从通过率来说也能看出来。这个题目就是一个大数计算器
，没有太多复杂的东西。题目里面对运算符的结合性没有明确说明，不过惯例都是左结合的
。主要注意以下几点：计算指数要用二分法，不能直接算；计算阶乘时，大于200的阶乘模
10^40都是0。有人提问，是先计算最终结果再求模，还是每次计算都求模，我无法回答他。
按照题意当然是最终求模，但计算者可以简化为每一步求模。
不过注意，这个题目的主要陷阱就在此处，举个例子，0!=1；而 (10**40)! = 0；
F：2455: Credit hour
50门课程的搜索。算法分为两步:
1.确定最小可行学分: 在[C, 2*C)范围内二分枚举学分值，DFS验证。DFS验证时亦可同时缩
小当前二分上限。
2.找出字典序最小的解：可以证明只要选中的选修课字典序最小，总的课程字典序也最小。
这个出题者的数据量很大，没有很好的搜索优化就要超时。
G：2456：Stampeding
动态规划题目，x[i]表示第i个时间段的任务数，cost(i,j)为i个进程j个任务时惊醒进程的
系统耗费，dp[i][j]表示第i+1个时间段开始前进程数为j的最小耗费。
状态转移为：
dp[i][x[i]]=dp[i-1][j]+cost(x[i],x[i])
当i>x[i]时dp[i][j]=min( dp[i-1][j]+cost(j,x[i-1]) , dp[i][j-1]+Y )
当i<x[i]时dp[i][j]=dp[i][x[i]]
H：2457: Sailboat
这是一个高数题目。说题目之前先说一个物理问题，有同学对本题中速度与力成正比不理解
，是不是以为作者是亚里士多德的学生了。实际上，任何一本流体力学中都有这样一个基本
公式，由1851年英国数学和物理学家Stokes提出（场论中著名的斯托克斯环流量与旋度公式
也是他提出的）。即
在流体中作匀速运动的（球形）物体所受的阻力为 F=6πη R V，其中η为粘滞系数，R为
球体半径，V为物体速度。
可参见《新概念物理教程－力学》赵凯华等著。1995年版，第247页。
根据本题可以列出一个一阶微分方程，此方程可以积分求解，不过我想几乎没有人会积分来
作吧，因为这个积分太复杂了，一般的数学书上都不会有。可以用数值积分的方法算出来。
I：2458: Pestiferous
最后这个题目，掀起外衣，就是一个有向图的强联通分量、加上一个中国邮路问题。这两个
算法很多地方都有相应描述，不过都是比较复杂的算法。相信在比赛时间内写完也不是一件
容易的事情。
总的来说，题目可以分为三个难度等级，A、B、G、H是一个级别；C、D、E比较难；F和I又
是一个等级。
另外，感谢所有为本次比赛出题和测试题目的朋友们，由于正式赛还没有结束，有些人的名
字ID不能公布，一并感谢。
ps ，我原来说，10号帖解题报告，现在不算超时吧。
No Tags
本文归类于 有教无类, 程序设计. You can follow any responses to this entry
through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging
is currently not allowed.
3 留言
1
guest says:
十月 10th, 2007 at 11:57 pm
C：费用都是线性函数，没有“分段”的说法。
D：乘方的惯例是右结合。
2
guest says:
十月 11th, 2007 at 12:58 am
A题，由于没有剪枝，碰上无解的情况不超时么？或者因为数据弱？并且“每队胜利数不能
大于其他队失败数和，每队失败数不能大于其他队胜利数和”，能给出证明么？如果不能，
这部分要用匹配在能判定。
I题，题目中没有说是“最小”费用。
3
skywind says:
十月 11th, 2007 at 1:27 am
A: 当然得有剪枝了。“每队胜利数不能大于其他队失败数和，每队失败数不能大于其他队
胜利数和”是搜索结果的检查规则，不是条件。
C：为什么没有分段线性的说法？
D：Fortran里面乘方是右结合，C语言一般的运算符都是左结合的。
I：确实没说最小费用。
其实我真没必要和大家较真。比如说I，是没说最小费用，让你求一个任意费用，有意义么
？
--
Science is what we understand well enough to explain to a computer.
Art is everything else we do.
———— Donald E. Knuth
※ 修改:·kaman 于 Oct 11 09:07:34 修改本文·[FROM: 192.168.14.224]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.14.224]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店