这是第11届浙江大学程序设计竞赛(The 11th Zhejiang University Programming Contest)的比赛点评。这不是官方的解题报告,裁判组也将不会提供官方的解题报告和测试数据。不过我可能会在点评中介绍一下我们是如何出题、验题和构造测试数据的。


The 11th Zhejiang University Programming Contest
A ZOJ3477 Akasim Matrix 0.00% (0/21)
B ZOJ3478 Binary Land 50.00% (2/4)
C ZOJ3479 Chinese Zodiac 47.61% (150/315)
D ZOJ3480 Duck Typing 17.28% (14/81)
E ZOJ3481 Expand Tab 8.33% (4/48)
F ZOJ3482 For Loop 0.00% (0/4)
G ZOJ3483 Gaussian Prime 5.32% (60/1127)
H ZOJ3484 How Many Parallelograms on the Grids? 0.00% (0/120)
I ZOJ3485 Identification Number 8.41% (9/107)
J ZOJ3486 Judge Internal Error 32.58% (145/445)

现场赛没有人过AFH,特等奖7题,比较可喜的是Ranklist上百花齐放,比较遗憾的是4题以上的队伍偏少。由于机器存在“时差”,网上同步赛其实只相差十几分钟,最后有4个8题,没有人AC H题实属意外。比赛的时限应该是比较合适的,除了A题,都有10倍TL,其中G和J都是按照比较暴力简单的算法来设置的。测试数据应该是比较强的,经过认真设计和严格测试。


The 11th Zhejiang University Programming Contest (online)
A ZOJ3477 Akasim Matrix 0.00% (0/33)
B ZOJ3478 Binary Land 21.42% (18/84)
C ZOJ3479 Chinese Zodiac 62.41% (382/612)
D ZOJ3480 Duck Typing 14.37% (46/320)
E ZOJ3481 Expand Tab 11.82% (11/93)
F ZOJ3482 For Loop 4.80% (5/104)
G ZOJ3483 Gaussian Prime 14.76% (216/1463)
H ZOJ3484 How Many Parallelograms on the Grids? 0.00% (0/126)
I ZOJ3485 Identification Number 19.77% (70/354)
J ZOJ3486 Judge Internal Error 46.06% (375/814)

校赛和省赛的题目出到一半,突然想整理一套A-J,所以对题目做了一番调整,把原来准备放校赛的题目踢到了省赛,又临时yy了几道题。DEG都是我特意为校赛准备的,可以说没太多算法,比的就是基本功。这次完全没有出那种接触过ACM就秒杀,没接触过就不会的那种没有营养的题目。

ZOJ3477. Akasim Matrix

downloadsource code (ZOJ3477.cpp) [矩形切割, 线段树, parameter search, off-by-1]

坂御矩阵(Misaka.reverse Network Matrix)是学园都市超牛的网格计算平台。里面的姐妹们节点们都有一个唯一的2元组序列号(serial number),她们像矩阵中的元素一样排列。最近魔法少女小◯攻击了坂御矩阵,注入了名为“爱的战士”的治愈系病毒。病毒将在第di天感染序列号(xi, yi)的节点,并以天为单位传播开来。学院都市想要在所有节点被感染前,在某个节点上制作出杀毒程序。题目要求所能争取的最多的时间和对应的字典序最小的节点。

不知道题目里的neta有多少人看出来了。提交此题的基本属于完全无视了规模,直接bfs,这样对规模小得多的CF35C是没有问题的,但对于这题自然要TLE。估计还是有不少人想到了正确的思路,但即便如此,离AC恐怕还是有一点距离的。可能有很多边界需要考虑,不拿个暴力的程序(ZOJ3477bf.cpp)对拍一下是不容易发现的。首先想到可以二分答案,其后算法很多,如果n或m小一点,那么按行列扫描,如果这题v的规模继续加大,可能就不得不离散化加线段树了。标程是矩形切割,注意到每个源最后所扩散的区域最后是一个菱形,转45度之后就是正方形,所以用矩形切割后就可以求得剩下的区域。比较恶心的是,转45度以后,新坐标系的点和原坐标系的点不是一一对应的,有一半的点在原坐标系不存在,所以还要处理这种问题。总之这是一道想起来不难,但写起来比较吐血的题吧。顺便附上我有这个算法做CF35C的Ruby程序(CF35C.rb)。

ZOJ3478. Binary Land

downloadsource code (ZOJ3478.cpp) [shortest path]

很显然的最短路,每次需要考虑:

  • 移动:注意到2+3=5,所以可以单独处理两只企鹅的移动,也不需要分情况讨论;
  • 救人:如果一只企鹅在蛛网中,另一只企鹅在它旁边,那么花11秒,它可以从蛛网中移到另一只企鹅所在位置。

注意蛛网不会消失,虽然我一开始打算这么出来着。还要注意的一点是,你要枚举一开始选择控制Gurin还是Malon,Sample故意设计得没有体现这一点。此外Sample非常强,应该过了Sample就能AC了。数据一共74组,完全人肉,包含了Binary Land中所有光卡的地图。人肉74组10×15数据的你伤不起!

ZOJ3479. Chinese Zodiac

downloadsource code (ZOJ3479.cpp) [签名题]

Given the traditional age (Xusui) of someone, you are requested to answer his zodiac sign (Shengxiao).

输入虚岁,输出生肖。

这道题作为校赛签名题出色的完成了自己的使命。不过现场赛的AC Ratio居然不到一半。怎么说呢,yes的程序都是一样的,no的程序却各有各的bug。

ZOJ3480. Duck Typing

downloadsource code (ZOJ3480.cpp) [simulation]

模拟动态语言中的类型定义,函数定义和调用。

中规中矩的模拟吧,用上STL应该是相当简单才是,不过Sample不怎么强。人肉了几组特殊测试数据,然后用程序(ZOJ3480gen.rb)生成了一些大数据,最后还在标程里计算了一下这些数据的代码覆盖率。

ZOJ3481. Expand Tab

downloadsource code (ZOJ3481.cpp) [string manipulation]

题目中top stop和heredoc什么的似乎有些人不知道是啥玩意。题目比较麻烦之处在于有两类情况需要处理,分别是只有一个ts和给定一个ts list的情况。给定的ts list不保证升序,而且可能有重复,这个在第一个sample中就体现了。还有,可能有人和我一样用set来存储ts list,这样就要小心”expand 4,4″这样的case了。还有一点,题目虽然保证输入长度不超过1000,但输出长度可能很长很长的哦,亲~

ZOJ3482. For Loop

downloadsource code (ZOJ3482.cpp) [DP, eps, BigInteger]

N个数中,选出一个M可重复排列,目标是使product{max(0, 相邻两个数的差)}最大。要求输出最大的counter模BASE和对应的方案。

很显然的动态规划,对于要求字典序最小的动态规划,通常使用反向来做。dp[m - 1][j]表示b[i]=j时的最优解,那么初始dp[0][j]=1,转移dp[i][j]=max{dp[i-1][k]*max(0,a[j]-a[k])}。DP的空间复杂度O(n2),时间复杂度O(n3)。显然counter会溢出,所以可以用大数或浮点数,用浮点数还要考虑eps,否则输出的方案可能不是字典序最小的,测试数据中特别增加了这类case。标程是用浮点数写的,不过测试数据的输出则是用python生成的(ZOJ3482py.py)。还有一个需要注意的是,如果最大的counter是0,那么对应的方案也应该是全0。这题现场居然没有人过,难以理解……

ZOJ3483. Gaussian Prime

downloadsource code (ZOJ3483.cpp) [prime, gcd]

一个高斯整数a+bi是高斯素数,当且仅当:

  • a和b中一个是0,另一个是±(4n+3)形式的素数;
  • a和b均不为0,且a2+b2是素数。

要求平面[x1,x2]×[y1,y2]的区域内的素数的密度。

这题原来规模是1000,case数是10000,要求用线性筛法处理素数,再用部分和预处理,O(1) per case求出高斯素数的个数。后来考虑到整体难度和与H题的部分重叠,降低了难度,现在只要O(\sqrt n)判断素数,暴力二重循环求高斯素数个数就可以了。需要注意的是答案要以即约真分数形式输出,所以还要对分子和分母求一个gcd,sample没有体现这一点,算是一个失误。全场第三简单的题,只要C语言学得扎实都没问题的一道题,不过也有几个过D或E的队伍没有过G。

ZOJ3484. How Many Parallelograms on the Grids?

downloadsource code (ZOJ3484.cpp) [geometry, counting]

求两边边长满足给定限制,且顶点都在格点上的平行四边形的个数。全等的平行四边形只算一个。

这题中间经过了较多变化,最初的题目只要求两边长度不超过n,n是整数,这样打表就可以了。后来我push了vls三天,才终于改成了现在这样,卡掉了打表,并且要O(1) per case。也就是把G题改简单,把H题改难。一开始的比较容易想到的方法就是通过容斥把全等的平行四边形减掉,不过我们都没有想到可行的算法,如果有的话,数据范围应该可以出到更大吧。事实上题目的规模只有50,这个规模下的平行四边形是不多的,所以我们完全可以枚举他们,再把重复的去掉。事实上我们先枚举长边的长度\sqrt x,再枚举短边的长度\sqrt y,并要求它们的夹角是锐角或直角(点积非负),那么它们的叉积(即面积)唯一确定平行四边形。所以只要把所有叉积塞到一个set里,最后这个set的size就是两边分别为\sqrt x和\sqrt y的平行四边形的个数,记为a[x][y],预处理出a。最后为了做到O(1) per case,只要求出部分和,加加减减就得到了。注意不要多算,也不要漏算。

ZOJ3485. Identification Number

downloadsource code (ZOJ3485.cpp) [enumeration]

改变最少的位,使得身份证号合法。

原本寒mm告诉我,他有一个idea,给一个身份证号,问是否合法。我说,好啊,挺简单的,就作为校赛的I题吧。谁知道结果出出来的是这题,哪像校赛的简单题啊,幸亏还不要求字典序最小。其实算法很简单,只要暴力枚举所有日期就好了,TL也给得比较松,像我一样实现得很黄很暴力也不会超时。校验码是不需要枚举的。尽量把15位和18位省份证的逻辑合并起来吧,如果做不到,也可以考虑干脆写两个程序。

ZOJ3486. Judge Internal Error

downloadsource code (ZOJ3486.cpp) [counting]

由于I题太难,所以临时加了一道J题简单题。原本我出了一道,结果姐姐看过觉得还是太难(事实上也是),于是也毙掉了。最后出来的就是quark的这道确实简单的题了。怎么做都可以吧,要注意次数相同的时候要取题号大的。

27 Responses to “第11届浙江大学校赛比赛点评beta
  1. Hello_Kitty says:

    请问 problem A, ( 1 ,1 ) –》( r,c) 这个矩形 旋转 45度 后 然后被一系列的 正方形切割, 而 ( 1 ,1 ) –》( r,c) 剩下的部分就可能为各种形式的图形了, ms还可能为三角形, 这感觉实在不好处理啊,ms 矩形切割那篇论文都木有讲这种情况,请问这应该如何处理呢?

  2. tn pas cher says:

    都好难,我一个都做不出来,怎么办?

  3. CrazyCow says:

    大神什么时候写省赛比赛报告呀,好生期待呀

  4. chenzhe says:

    解决了~~

  5. chenzhe says:

    你好,3483那题我一直过不了,但是把大牛你的程序结果和我的做了大量比较,找不到问题所在,请问能不能帮我看下。非常感谢!
    #include
    #include
    #include
    #include
    #include
    #include

    using namespace std;

    int gcd(int a, int b) {

    return b == 0 ? a : gcd(b, a % b);

    }

    int is_prime(int a)
    {
    if(a==1||a==-1)return 0;
    if(a<0) a=-a;
    for(int i=2;i*i<=a;i++)
    if(a%i==0) return 0;
    return 1;
    }

    int is_form(int a)
    {
    if(a0)
    {
    if((a-3)%4==0) return 1;
    else return 0;
    }
    }

    int main()
    {
    int n;
    scanf(“%d”,&n);
    int t[4];
    while(n–)
    {
    scanf(“%d%d%d%d”, &t[0],&t[1],&t[2],&t[3]);
    int total = (t[1]-t[0]+1)*(t[3]-t[2]+1) ;
    int count =0;
    for(int i=t[0];i<=t[1];i++)
    {
    for(int j = t[2];j<=t[3];j++)
    {
    if(i!=0&&j!=0&&is_prime(i*i+j*j)) count++;
    else if(i==0&&is_prime(j)&&is_form(j)) count++;
    else if(j==0&&is_prime(i)&&is_form(i)) count++;
    }
    }
    int tmp=gcd(count,total);

    printf("%d/%d\n",count/tmp,total/tmp);
    }
    return 0;
    }

  6. guinao says:

    I题有没有可能出现在日期中有多个修改都是最优但是其中一个不需要修改checksum而其他的会修改checksum的情况?

    • watashi says:

      不需要考虑枚举checksum,因为checksum只有一位,所以如果最后checksum不对则修改之,否则省一位
      解总不会比枚举checksum得到的来得差

      • guinao says:

        比如说有一个IDNumber 123456199103418882,我可以把它修改成 123456199103018882、123456199103118883、123456199103218884、123456199103318885,第一种是最优的因为只改了一个数字,而其它的多修改了checksum,这种情况怎么求出最优解?

        • watashi says:

          你枚举日期1991-03-01的时候不就把最优解求出来了吗?

          • guinao says:

            这样的啊~那就是说先要把所有可能的最优解求出来,然后看看是不是有不用改checksum就正确的解,如果没有就任取了?

            • watashi says:

              看不懂你的回复 @,@
              简单来讲就是枚举整个解空间的一个子空间,并保证这个子空间的最优解不比整个解空间的最优解差
              前者是为了不TLE,后者是为了不WA

  7. stariy says:

    感觉G题超诡异啊…
    1. 约分原则没有说,当分子是0时,为什么一定要0/1不能0/2吧?这个该不该在题中或case中说明的?
    2. “±(4n+3)形式的素数” 有歧义啊,应该是+(4n+3)的素数,或为这个素数的负数…

    555 >_<

    • littlefish says:

      分子為0的話就不需要約了

    • watashi says:

      即约真分数by definition就应该是0/1吧,就像n>0,那么gcd(0, n) = n一样
      有case的话当然很多人就不会没注意到要约分了,这只能算个美中不足

      后面这个是我简写了吧,英文版的写的很清楚的,我抄wiki的……

  8. littlefish says:

    好伤感啊~I题弄了N久到最后还是没弄出来……看了报告发现想法竟然是对的,就是没写出来。。。

  9. 猛犸也钻地 says:

    A题一看到Academic City和魔法少女就懂了,出题出成这样的,题目必然邪恶啊,果断不做
    不过唯独Akasim这词真没看出来 – -

  10. Navi says:

    每年我的题都在省赛…

  11. VeegtableB says:

    G我说过要加case的……

  12. lxyxynt says:

    orz

  13.  
Leave a Reply