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)

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)

### ZOJ3477. Akasim Matrix

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

### ZOJ3478. Binary Land

source code (ZOJ3478.cpp) [shortest path]

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

### ZOJ3479. Chinese Zodiac

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

### ZOJ3480. Duck Typing

source code (ZOJ3480.cpp) [simulation]

### ZOJ3481. Expand Tab

source code (ZOJ3481.cpp) [string manipulation]

### ZOJ3482. For Loop

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

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

### ZOJ3483. Gaussian Prime

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

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

### ZOJ3484. How Many Parallelograms on the Grids?

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

### ZOJ3485. Identification Number

source code (ZOJ3485.cpp) [enumeration]

### ZOJ3486. Judge Internal Error

source code (ZOJ3486.cpp) [counting]

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:

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

• watashi 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

• guinao says:

==是我有点想偏了，枚举一遍确实神马都不会落下

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久到最后还是没弄出来……看了报告发现想法竟然是对的，就是没写出来。。。

• watashi says:

momo 这种事常有的，多练练码代码吧

9. 猛犸也钻地 says:

不过唯独Akasim这词真没看出来 – -

• watashi says:

navi也没看出来，其实这是一种常用的避嫌技术

10. Navi says:

每年我的题都在省赛…

• watashi says:

快出题！

• Navi says:

等我配好电脑 (=w=)

11. VeegtableB says:

G我说过要加case的……

12. lxyxynt says:

orz

13. vout says:

sf

14.