P1356 数列的整数性题解

like1 · 2019-11-05 21:53:25 · 题解

看到很多大佬都是用dp切的这一题，其实这道题的运算符只有‘+’和‘-’，要么加要么减，其概率各位1/2，那我们可以尝试乱搞大法，直接用rand（）函数；randomm=rand( ),如果randdomm%2==1,则让ans加上a[i]，反之则减去a[i]；

为了让答案更加准确，我们可以多rand几次，但具体还是要看数据范围

放上代码

#include<cstdio>
#include<cstdlib>
using namespace std;

int a[10001];
int i,n,T,k,randomm,ans;

int main( )
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
        int tot=500,flag=0;
        while(tot)
        {
            tot--;
            ans=0;
            for(i=1;i<=n;i++)
            {
                randomm=rand(); 
                if(randomm%2)
                    ans+=a[i];
                else
                    ans-=a[i];
            }
            if(ans%k==0)
            {
                printf("Divisible\n");
                flag=1;
                break;
            }
        }
        if(!flag) printf("Not divisible\n");
    }
    return 0;
}

其实有很多题在我们无法想出正解时，我们可以采取随机的方法，虽然这样单次的正确率很低，但随机法通常是O(n)的，我们可以重复多次，并且事实证对于有些题目其实有很多题在我们无法想出正解时，我们可以采取随机的方法，虽然这样单次的正确率很低，但随机法通常是O(n)的，我们可以重复多次，并且事实证对于有些题目随机法的正确性还是很高的；特别是在考场对于一些难题，如果能用随机法并能获得较高得分比我们去死磕正解要划算的多。

最后祝大家CSP2019rp++,score++;