上一年的最后一次训练赛被卡了AK...
一开始天真的认为每个数字都进行取模 然后认为它是一个vol为取模后的数 val为0的01背包 去计算dp[m]能否被装满
只想到了其中的一点..简直天真
后来看百度学习了一下vector的部分用法
头文件是queue 可以从0向q.size()遍历 for(int i=0;i<len;i++)
push_back() 往最后面放数
size（）大小
再加个数组来判断某个数字是否出现过 把每次的东西都遍历一遍
如果每次输入x后不进行ok的判断会超时 最多是O（n*n）吧貌似。。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<queue>
using namespace std;
int main(){
int n,m;
while(~scanf("%d%d",&n,&m))
{
map<int ,int >f;
f.clear();
bool ok=false;
vector<int >q;
int x;
for(int i=0;i<n;i++)
{
scanf("%d",&x);
x%=m;
int len=q.size();
if(ok==false)
{ for(int k=0;k<len;k++)
{
int e=(q[k]+x)%m;
if(e==0)
ok=true;
if(f[e]==0)
{
q.push_back(e);
f[e]=1;
}
}
if(f[x]==0)
{
q.push_back(x);
f[x]=1;
}
if(x==0)
ok=true;
}
}
if(ok==true)
{
printf("YES\n");
}
else printf("NO\n");
}
}
嗯...acm真正进行半年了(其实是从九月多到二月多 五个月左右...)
嗯 以后也要努力!