题解 P1537 【弹珠】

· · 题解

首先声明。。这不是自创题解。。第二。。这道题原题名字叫Dividing。。。出题者只是搬砖。。。

我只讲怎么 0ms 过这题好不好？？？

举个栗子：“1 0 2 0 1 0” ：一个人拿走价值为 3 的大理石块，其余归另一个人；而“2 1 1 1 1 1” ：一个人只拿一种大理石就不行了，需要拿到多种大理石。这两组数据，对任意价值的大理石块，无论增加多少个 2，仍然是可以平分的，只要他们平分这个 2 就可以了。。

因此我们不需要对每种价值的大理石，按多达20000块进行平分，而只需要对一个最低限度的大理石块数 n （0 <= n <= a[i]）进行平分，

其余的部分，他们直接平分就好。显然 n 是偶数，经过测试。n = 6；

关键代码：

if(a[i] != 0 && a[i] %6 == 0) a[i] = 6;
else a[i] %= 6;
其中：1<= i <= 6

好了。。这样就大大压缩了原始数据的范围。。。就算枚举都没问题了。。

给出核心代码（虽然我知道没有人不会写枚举。。就是不给DP，，虽然都是0ms。。）：

void calc(int sum) {
    int mid;
    for(int i=0;i<=a[1];++i)
    for(int b=0;b<=a[2];++b)
    for(int c=0;c<=a[3];++c)
    for(int d=0;d<=a[4];++d)
    for(int e=0;e<=a[5];++e)
    for(int f=0;f<=a[6];++f)
    {
        mid = 1*i+2*b+3*c+4*d+5*e+6*f;
        if(mid == sum/2) {puts("Can be divided.\n");return;}
    }
    puts("Can't be divided.\n");
}