【DP】：CF #319 (Div. 2) B. Modulo Sum

【题目链接】：http://codeforces.com/contest/577/problem/B

【相似题目】：http://swjtuoj.cn/problem/2383/

【题意】：给出n个数，问是否能从中选出一些数，使得这些数的和是m的倍数。

【题解】：

首先，先明白这样一个事实：

设：sum%dend=rem;

（sum：一些数的和，dend：被除数，rem：余数）

则有：(rem+n)%dend=(sum+n)%dend;

（n为一个新的数）

知道了上面的等式之后，题目就好做了：

设：est[rem]=1 表示存在余数rem，它是通过一些数的和sum%dend得到的。

对于每一个给定的n，

考察 1<=rem<=dend-1 范围内的est[rem]，即考察是否存在之前一些数的和sum%dend=rem（不管sum是之前的数是怎么相加得来的）

若存在，即est[rem]=1，则可以通过(rem+n)%dend来求出新的余数，即令est[(rem+n)%dend]=1；

此外，n%dend也是新的余数，即est[n%dend]=1；

若在上面的余数中有一个等于0，即est[0]=1，则说明存在dend的倍数，直接中断循环。

【注意】

在对每一个n的循环中，不能立刻更新est数组，原因是某些情况会导致出错。

出错例子：

设：已有est[1]=1，此时n=1，dend=100；

若令est[(1+n)%dend]=1，即est[2]=1，

则又有est[(2+n)%dend]=1，即est[3]=1，

又有est[(3+n)%dend]=1，即est[4]=1......

最后整个est数组都为1，显然这是错误的。

所以，要一个 i_est 数组来临时更新est数组，最后再更新est数组（详见代码）。

 #include<stdio.h>

 int num,dend,t,i,n[];

 char est[],i_est[];

 int main(){

     scanf("%d%d",&num,&dend);

     for(t=;t<num;t++){

         scanf("%d",&n[t]);

     }

     for(t=;t<num;t++){

         for(i=;i<dend;i++){

             if(!est[i]) continue;

             i_est[(i+n[t])%dend]=;

         }

         i_est[n[t]%dend]=;

         for(i=;i<dend;i++){

             est[i]=i_est[i];

         }

         if(est[]) break;

     }

     if(est[]){

         printf("YES\n");

     }

     else{

         printf("NO\n");

     }

     return ;

 }

巴特西

【DP】：CF #319 (Div. 2) B. Modulo Sum

最新文章

热门文章