题解 P1356 【数列的整数性】

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