题解 P1356 【数列的整数性】

这是一个真正的暴力算法,不知道有没有和我一样的人,看到这题,正常人应该都会想到枚举放‘+’、‘-’,但看到数据较大,便知道枚举决对会超时,但是,你们可能忘了c++的一个函数——rand (c++大法好),我们可以随机生成数,来判断是该+还是-,只要多随机几次,就可以AC(说白了还是骗)

#include<cstdio>
#include<cstdlib>//rand所在的库,我有一本书上说在cmath,害的我搞了好久才过编译= =
using namespace std;
int a[10010];//存数
int main()
{
    int i,j,n,m,k,p,s;
    scanf("%d",&m);
    while(m)
    {
        m--;
        scanf("%d%d",&n,&k);
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        j=250;//这个j代表我们要随机+-j次,我不知道这个j最小是多少(应该看脸,我脸比较黑),反正我调到250就A了
        while(j)//开始我们的随机化暴力之路
        {
            j--;
            s=0;
            for(i=1;i<=n;i++)
            {
                p=rand();//随机判断变量p
                if(p%2)//如果是奇数就+,偶数就-,当然你搞别的乱七八糟的判断也是没问题的,不过最好应该把概率定在五五分
                    s+=a[i];
                else
                    s-=a[i];
            }
            if(!(s%k))//每次随机结束后判断是否整除,能就直接break掉循环
            {
                printf("Divisible\n",k=0);
                break;
            }
        }
        if(k)//如果在循环中k没有被改为0,那么就说明不能被整除
            printf("Not divisible\n");
    }
    return 0;
}

ps:蒟蒻表示不会题解里dalao的dp……


发表于 2017-11-01 08:55:26 in 题解