求教,为什么输入时预处理不先模上m会导致WA on #34
查看原帖
求教,为什么输入时预处理不先模上m会导致WA on #34
422684
M1saka16I72楼主2024/1/23 09:55

AC 代码如下,有没有大佬能够讲解一下

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define mp_ make_pair
#define pb_ push_back
#define pob_ pop_back
#define fst first
#define snd second
#define debug cout<<"********\n";
#define reset(x,y) memset(x,y,sizeof(x))
#define fi(x) freopen(x,"r",stdin)
#define fo(x) freopen(x,"w",stdout)
#define iosf ios::sync_with_stdio(0);cin.tie(0);
#define prec(x) cout<<setprecision(x);
#define prec0(x) cout<<fixed<<setprecision(x);
#define s(x,y) x[y-1]
#define Misaka16172 sb

using ll = long long;
using ld = long double;
using db = double;
using ull = unsigned long long;

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

using namespace std;

template <class T>
inline void read(T &x){
    x = 0;T w = 1;
    char c = 0;
    while(c<'0' || c>'9'){
        if(c=='-')	w = -1;
        c = getchar();
    }
    while(c>='0' && c<='9'){
        x = ((x<<3)+(x<<1))+c-'0';
        c = getchar();
    }
    x = x*w;
}
bool vis[2005];
bool f[2005];
int t[2005];
int d[2005];
ll a[1000005];
int n,m;
int fix(ll x){
    if(x>=0 && x<m)	return x;
    else if(x<0)	return ((m-1-x)/m)*m+x;
    else return x-(x/m)*m;
}
void solve(){
    read(n);read(m);
    if(n>m) puts("YES");
    else {
        for (int i = 1; i <= n; i++){
            read(a[i]);
            a[i]%=m;	//这一行去掉就会wa on #34
        }
        for (int i = 1; i <= n; i++) {
            vector<int> sol;
            for (int j = 0; j < m; j++) {
                if (j == a[i] || f[fix(j - a[i])]) sol.push_back(j);
            }
            for (auto j: sol) f[j] = 1;
        }
        if (f[0]) puts("YES");
        else puts("NO");
    }
}

int main(){
    int t = 1;
//	read(t);
    for(int tt=1;tt<=t;tt++){
        solve();
    }
}
//
2024/1/23 09:55
加载中...