ZOJ在建站105个月之后迎来了第一百场比赛。

””\\( ̄ー ̄) ( ̄ー ̄)//””

办一场比赛来庆祝一下,这个想法最先是姐姐在邮件中提出的:

所谓求人不如求己,我自己的记录里是有序号的,所以知道我们目前有98场原创比赛和10场Practice了!喂,要不要庆祝一下第100场呀??!^_^

而我们在ZOJ2.1提供了几个脚本语言的支持后,也一直想办一场“非主流”的比赛。所以便有了今天的 Let’s Celebrate the 100th Contest on ZOJ! — An Unusual Contest powered by ZOJ Staff 这场9道非同寻常的题组成的9小时9分9秒的比赛。题目的准备还是比较匆忙的,事实上除了hhanger的一道题以外,所有题都是最近几天出的。感谢参与出题和验题的navi, hhanger, quark, hsys猛犸也钻地等童鞋,也感谢大家的捧场和支持。


Let’s Celebrate the 100th Contest on ZOJ!
100A ZOJ3437 Very Hard Problem 6.89% (28/406)
100B ZOJ3438 Tripartite Graph 62.28% (71/114)
100C ZOJ3439 Substitution Cipher 7.86% (36/458)
100D ZOJ3440 Detect the Virus II 0.00% (0/26)
100E ZOJ3441 Crack Me II 2.06% (2/97)
100F ZOJ3442 Complex Calculator 0.00% (0/1)
100G ZOJ3443 Bessel Function II 0.00% (0/0)
100H ZOJ3444 An Unusual Problem 5.12% (2/39)
100I ZOJ3445 1KB 9.09% (4/44)

下面是解题报告:


剧透的分割线,看题解之前建议您自己先思考一下


ZOJ3437. Very Hard Problem

[C (programming language), yet-another-easy-problem]

我的idea,navi出的题。题目要求对一个b进制的64位有符号整数,按要求输出它的相反数,逻辑非或按位取反后的10进制结果。

此题唯一一个需要注意的地方就是,C/C++的long long和Java中的long,即[LLONG_MIN=-9223372036854775808, LLONG_MAX=9223372036854775807]对于!和~运算都是封闭的,能得到正确的结果,而对于-运算却不是,-LLONG_MIN=LLONG_MAX+1会溢出,得到的结果会是-LLONG_MIN=LLONG_MIN,所以特判之。顺带一提,36进制以内的数,C/C++的库函数strtol/strtoll就能搞定。

ZOJ3438. Tripartite Graph

[yet-another-easy-problem]

题目要求构造一个V个点,E条边的简单三分图。其中V不超过50,E不小于1000。

注意V和E的范围,满足题目要求的图,根本不存在。所以完全不用读输入数据,直接提交一个什么也不输出的程序就好了。事实上对于python, perl和scheme,提交一段空的代码就能AC了。

ZOJ3439. Substitution Cipher

[C (programming language), puzzle, yet-another-easy-problem]

This is a problem about Substitution Cipher. All letters from a to z are mapped to a permutation of themselves, which means that it is a bijection. You should try to decrypt the description. But what you should submit is the program that encrypt this descrption. The test input just contains all one-byte characters.

To make it easier to decrypt, part of wiki page of Substitution Cipher is quoted.

In cryptography, a substitution cipher is a method of encryption …

“看懂”题目是成功的一半。其实标题的提示性就很强了,而且加密也很弱。不过这只是一半而已,首先要注意的第一个地方是 what you should submit is the program that encrypt this descrption,sample特别选得对加密和解密是对称的。然后就是 The test input just contains all one-byte characters,所以0-255的字符都出现了。需要注意的是,如果你是

for (int i = 0; i < 256; ++i) charmap[i] = i;

这么写的,并通过char类型的下标访问charmap,那么可能会WA或者RE。因为C/C++中,char可能是signed的或unsigned的,事实上大多环境下char的取值是[-128, 127],而不是[0, 255]。还需要注意的是,如果你是

char ch;
while ((ch = getchar()) != EOF) {
}

这么写的,也会WA。注意255是一个合法的字符,但转成char后变成了-1,即EOF。正因为EOF不在char的表示范围内,所以getchar被设计为返回一个int。

fgetc(), getc() and getchar() return the character read as an unsigned char cast to an int or EOF on end of file or error.

ZOJ3445. 1KB

[BigInt]

原本不太难的一个大数运算题,加上了xe的1kb代码提交限制后就不简单了。首先可以看看作者华丽丽的C语言标程,我觉得都可以出成Crack Me III了。至于数据,我们至少用了C, Java, Perl和Python四种语言取不同精度验证过。

大数计算中,最复杂的就是sqrt开根号运算了。标程用了非常快的大数开方算法(参考SGU111. Very simple problem),速度也是最快的。Java如果用二分,即使利用bitLength选择比较好的上下界也有可能超时,更好的算法是用牛顿迭代y’=y+x/y。quark的程序就运用了这种方法,不过他还加了一个很重要的优化才没有TLE:用浮点运算sqrt得到的结果作为牛顿迭代的初值。

quark-qmd

Perl的Math::BigInt中直接提供有bsqrt函数,所以是最省事的,不过我的程序也是最慢的。顺带一提,Math::BigInt还提供了bnok函数直接求c[n][k],可惜这个函数有bug

There is a bug in Math::BigInt’s implementation of n over k:
Math::BigInt->new($n)->bnok(0) is $n+1, should be 1.
Math::BigInt->new($n)->bnok($n-1) is 1, should be $n.

TO BE CONTINUED …

11 Responses to “[题解]Let’s Celebrate the 100th Contest on ZOJ!”
  1. LambdaTT says:

    请问ZOJ里用Scheme提交的格式是什么样的?
    或者能给出A+B Problem的Scheme代码吗?

    • watashi says:
      (define gao
        (lambda (a b)
          (if (eof-object? a)
            0
            (begin
              (display (+ a b))
              (newline)
              (gao (read) (read))
            )
            )
          )
        )
      
      (gao (read) (read))
      
  2. jing says:

    1kb那个也太夸张了吧,居然还加个1kb,够非主流的

  3. LCLL says:

    char ch;
    while ((char = getchar()) != EOF) {
    }

    打错了吧~
    ch = getchar() ?

  4. 小媛 says:

    表示压力很大啊压力很大。。。不过感觉这次题很有意思。。。对解密那题很有兴趣。。。BTW:这次比赛的题真是太灰主流了 = =

  5.  
Leave a Reply