P1356 新解

Summer_Sheep · 2023-11-23 16:56:05 · 个人记录

题意

给定一个长度为 n 的数列，判断是否有添加加号和减号的方案使得最终的和被 k 整除。

分析

蒟蒻没想到背包 dp，于是自创了一个乱搞算法，但正确性好像是对的（

首先一个 trival 的结论是对于数列中的每一个数，我们都只关心其在模 k 意义下的值。

之后我们将原数列的所有数模 k，之后可以得到一个新数列。由题意可知原数列中的数加减后得到的结果等价于新数列中的数加减后得到的结果。

于是考虑这个新结果能被 k 整除。

此时注意到新数列中每个数的最大值是 k-1，而一共有 n 个数，故新数列所有数之和最多是 n(k-1)。

于是容易想到枚举每一个 k 的非负整数倍数，贪心判断是否能够到达此数即可。

时间复杂度 O(n^2)，可以通过此题。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,a[10001],k;
void work(){
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        a[i]=a[i]%k;
        if(a[i]<0){
            a[i]+=k;
        }
    }
    sort(a+1,a+1+n);
    for(int j=0;j<=n;++j){
        int op=j*k;
        int tmp=0;
        for(int i=n;i>=1;--i){
            if(tmp<=op){
                tmp+=a[i];
            }
            else{
                tmp-=a[i];
            }
        }
        if(tmp%k==0){
            cout<<"Divisible\n";
            return;
        }
    }
    cout<<"Not divisible\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        work();
    }
    return 0;
}