这是我们队周一在218秘密做成都赛区赛题的比赛小结,这场比赛是作为检验题目质量的内部测试,成都正赛的题目又有细微变化。ZOJ将在下周日举办The 2010 ACM-ICPC Asia Chengdu Regional Contest的Practice,所以对题解和算法的剧透没有兴趣的您就此打住了吧。代码附。(正式比赛题号有调整,H插到了原来的F(现在的G)的前面。)

cd-9-1490

原定的比赛环境是ZOJ@acm127,vls在比赛开始前5min发来了地址、用户名和密码,居然还是https的。不过我们迟到了一会,所以比赛推迟了一个小时才开始,并且为了更好的测试,改到了pc^2,由hhanger做judge。不过没有纸质题目,所以还是用ZOJ看题。一看居然是11道题,moondy前面,欧阳后面,我中间。比赛开始moondy就准备写C这道签名题,写完交发现交不上去,大概是acm127机器的问题,所以hhanger重启acm127。最后C一共Yes了三次。


我是剧透的分割线


我一开始没看E,先看了F,这个全场最大的悲剧。F题很简单,题目里那个C++的函数里有奇怪的空格,不过影响不大,题目理解费了点劲,不过理解了就很简单。但我一开始居然想错了,跑上去写了才发现过不了sample。然后换欧阳早就想好的J,J其实就是一个二分图最优匹配,写好之后很顺利的就J1y(51)

我继续上去写F,F题其实就是要求最大的m,使得存在数组x满足前m条规则。由于x只有0或1,而c都是0, 1, 2,所以就是一个2-SAT问题:

  • c = 0: x[a]=0 => x[b]=1; x[b]=0 => x[a]=1;
  • c = 0: x[a]=0 => x[b]=0; x[b]=0 => x[a]=0; x[a]=1 => x[b]=1; x[b]=1 => x[a]=1;
  • c = 2: x[a]=1 => x[b]=0; x[b]=1 => x[a]=0;

只要二分m后构图,求有向图强连通分量判断是否可满足就可以了。不过悲剧的就是我写错了n个地方,于是改了n次,交了n次,还WA了n次。现在想起来真实要多白痴有多白痴。而且那天acm127上的打印服务又挂掉了,于是我们只能通过ssh看WA掉的代码。

然后换欧阳上去写E,E就是简单的DP,不过由于要输出字典序最小的解,所以从后往前DP是比较好的方法。然后我和moondy看已经WA了n次的F都看不出问题了,然后我和moondy讨论了决定先写H。H的描述很裸,由于a≥0的二次函数是凸函数,凸函数的max还是凸函数(这个我ms在大妈题解题报告里说过),要求目标凸函数的最小值只要三分就可以了。所以H短短5min就写好过smaple,一提交居然WA了。结果被来捣乱的LCLL无限bs……moondy和我一起看H,结果moondy发现了bug,又被moondy无限bs……原来我输出的是自变量x,而不是函数值S(x),脑残啊,xe的sample最小值都取在不动点!改过以后H2y(108)。欧阳的E在debug一段时间以后过了sample,sample的output看起来那么强,于是提交,居然WA了。然后发现原来程序取的不是ABCD的字典序最小,而是求了下标顺序0123的最小,sample难道是唯一解的么……好xe。改过之后E2y(124)

关于A题首先考虑如何判断一个数是balanced的,O(l^2)的暴力很显然,其实很容易优化成O(l)的扫描,然后就会发现一个数最多关于一个digit是balanced的(一个严格单调函数最多有一个零点)。注意到了这一点就会知道,这题是不存在重复计算这种问题的。所以只要通过DP预处理出不同长度的力矩和,然后通过枚举就可以求出不超过某个数的balanced number的个数了。不过我们做的时候这题的数据只有1e9,所以我们用了更容易写的方法,打表+布鲁特—福斯。用O(l)的判断方法打表,记录每10w个数的区间内有多少个balanced number,这个表只要1min就能跑出来,大小才50k。然后对于每个test case,就只需要读表后再用相同的O(l)算法判断不超过2*10w个数就好了。这个sqrt(n)的打表方法是从quark那里学来的。测试了几个case没有问题后提交,A1y(148)

然后再回过头来看悲催的F,欧阳和moondy也帮慢看了,又是好长好长的时间过去了,最后moondy指出了一个模块敲错的纱布错误,改过之后F5y(158),我想撞墙啊。而我在机器上写I,I题很容易想到先二分p,然后由于每次施法只对j≤i有效,所以就需要从大到小贪心,关键在于如何O(n)的贪心。而其关键就是如何快速计算出到第j个石头的时候,它已经受到了多少的破坏,破坏次数c很容易得到,注意到(i-j)*(i-j)=i*i+j*j-2*i*j由三部分组成,\sum{i*i}和\sum{-2*i}也很容易统计,所以这个问题也解决了。最后还要注意要和0取max,所以可以用一个deque来维护能产生破坏的施法。程序很快写好,测了几个比较有意义的sample都过了,以为终于能1y了,结果WA >_< 我马上醒悟到二分的上界我加了n*n,而n是50000的时候溢出了,肉牛满面改过后I2y(180)。于是我写了一个三分,两个二分,都写得惨不忍睹,对于这场比赛里我糟糕透顶的表现,我也只好赛后bg麻辣烫谢罪了。

D保证了不会全放射,所以只会折射0次或2次,直接计算几何就好了,不过写起来还是费点劲的。(不幸的是好像刚结束的NEERC 2010, Eastern subregional contest中I. Chapaev at the Planet Ocean也是折射,所以有点撞题了。)队里的计算几何都是欧阳写得,所以欧阳上机。而作为队里肉最多的moondy负责看Fire的超自然蘑菇题K。我则想剩余的两题B和G。D无论是写还是调都花了不少时间,最后……没有过sample。然后换moondy写K。我想了很久B,完全没有想法;然后再仔细看了下G,这不是简单的记忆化搜索么,如果在现场的话应该很早就有人过,然后跟风了吧。

moondy的K写了一段时间后放弃,于是让欧阳继续调试D。我让moondy帮我确认一下G的题意,然后我就去想G怎么写了。我的记录方法是dp[N][A][C][W][T],五维分别记录高度,111的个数,110的个数,轮到谁,和最高层的个数,记录的是对应最优决策下的胜率(标程似乎记的是dp[A][B][C+D][W][T]),转移就是取后继状态的max,写成记忆话搜索比较简单。考虑清楚以后,我上机,只花了10min就写完过sample,然后终于G1y(247),本场比赛我写第4道题的时候,终于1y了,肉牛满面。

B毫无头绪,K挑战不能,于是只有三人强攻D了。怎么说呢,这题很难在纸上吧sample话出来,所以也很难知道错哪里了,所以只能一点一点调,一点一点assert+把每步中间结果打出来。看了n遍都找不到错误,最后我猛然发现两个最后一步中间结果冥冥之中与sample的输出有某种联系。似乎把最后一段光线的终点x2,减去起点x1就是sample output,而按题意应该输出x2才是。叫来vb,结果一看标程果然是输出答案的地方错了。于是我们先交了一个和vls错的一样的,又交了一个正确的,如果sample没问题的话,这题应该老早AC了。然后得知这题是唯一没有验过的题,是从根本没人想验的三维版本简化来的,vls比赛的时候还和hhanger说sample可能有错,把比赛延长5h也一定要我们做出来。

K题就是典型的Fire式蘑菇题,一步一步模拟没有算法,但是测试数据强而猥琐,现场一个不小心就不知道死在什么地方了。B题算法不明,我比完赛刚要谈到B,vls就直接笑道:“算法,比完赛再说”……听说要很多数据结构,而且vls写了200+行,换我的风格起码得写300+吧。

小结。嗯……我是zhua……被vls, hhanger和LCLL给bs到死了,要有危机感了。对题目的评价。有B和K在基本是可以防止AK了吧,然后各种题型也差不多有了,不过比较悲剧的就是大部分题代码量都非常非常小,所以顺的话,早早的就能9题,于是最后会有很多9题吧,而10题也不容易的样子,rank上前面题数拉不开也不太好看……我和LCLL和vb也说过,如果给所有题都加上输出方案的话会好不少,像H还能藏到某个背景里去。不过似乎主办方不希望有spj,最后时间有限,也不适合做大的改动了。

27 Responses to “[ネタバレ注意]成都赛区验题比赛小结 by watashi@ArcOfDream”
  1. XxX_Stu says:

    会不会有点过期…求教B题。谢谢。

  2. AekdyCoin says:

    后排仰慕

  3. jj says:

    请问大神,为什么曹鹏的别名是彩票哥,难道曹鹏神牛还经常买彩票?

  4. ZAFU_Lx says:

    请问E题Double Maze用搜索可行吗?用visi[6][6][6][6]标记掉两张图的状态。

  5. Yuan says:

    请问A题的dp要怎么设计状态呢?

  6. watashi says:

    The 2010 ACM-ICPC Asia Chengdu Regional Contest
    题目已加ZOJ Problem Set
    3417 Battle over Cities
    3418 Binary Number
    3419 Detector Placement
    3420 Double Maze
    3421 Error Curves
    3422 Go Deeper
    3423 Jenga
    3424 Rescue
    3425 Similarity
    3426 Snooker Referee

  7. LuGuo~ says:

    B似乎是杭州的G+可并堆+最小生成树?

    • watashi says:

      听说标程是

      int top(int k)
      void uu(int t1,int t2)
      int MST()
      void dfs(int k,int hh)
      void buildRMQ()
      int RMQquery(int t1,int t2)
      int MST1(int n,int m)
      bool cmp(const pair<int,int> &a,const pair<int,int> &b)
      void update(int t,int l,int r,int a,int val)
      int query(int t,int l,int r,int a,int b)
      void seginit(int t,int l,int r)
      void buildQ()
      void deque(int idx,int height)
      int bf(int a[],int n,int val)
      void gao(int k)
      void init()
      

      还不知道~

  8. VegetableB says:

    bs要放比赛还提前剧透的

  9. vout says:

    前排仰慕

  10. LCLL says:

    想不到我的题还可以成为扎实的炮灰和坚实的屏障,哈哈

  11. Ufotalent says:

    前排仰慕

  12. Navi says:

    前排仰慕

  13. Fancy says:

    前排仰慕

  14. watashi says:

    oops 看来我的预言不太准……
    看来和xgy/Fire/hhanger/LCLL一起集训过对他们的题比较熟悉了么
    而且校赛省赛也做了很多vb和彩票哥的题

  15.  
Leave a Reply