HJ93 题解 | #数组分组#

题意分析

• 给你一个数组，数组中所有5的倍数必须在其中一个组中，所有3的倍数在另一个组中（不包括5的倍数），不是5的倍数也不是3的倍数能放在任意一组，可以将数组分为空数组，能满足以上条件，输出$truetrue$；不满足时输出$falsefalse$。

思路分析

• 首先，我们来分析题目，我们先按照题目的要求进行分组，我们可以发现，3的倍数的数和5的倍数的数放的位置是固定了的。那么我们在分完组之后，得到了两个集合，一个是3的倍数的集合,我们把集合的元素的和记为$sum3sum3$，一个是5的倍数的集合,我们把元素的和记为$sum5sum5$，还有就是不是3的倍数和5的倍数的集合，我们把这个集合的数字的和记为$sumsum$。我们发现，如果最后想要两个集合的元素的和一样，那么首先，我们先计算出不是3的倍数和不是5的倍数的元素的和是多少，然后用这个和先弥补两个集合的差距，最后，如果想要两个集合的元素一样，第一个条件就是$sum-abs(sum3-sum5)sum-abs(sum3-sum5)$这个数字一定要是一个偶数，否则一定是不合法的。满足偶数的条件之后，我们的题目就转化为另一个题目了，就是给出一个集合，我们要找出在这个集合里面选择出若干个数字，是否可以拼凑成和刚好为$xx$。这里，这个集合就是我们找到的不是3的倍数和5的倍数的集合，这个$xx$就是$(sum-abs(sum3-sum5))\mathrm{/}2(sum-abs(sum3-sum5))/2$。
• 然后，我们就可以根据题目的数据范围选择合适的算法进行求解了。

暴力模拟法

• 我们可以将所有可能的和求出来，也就是对于每个数，我们有选和不选两种操作，最后可能得到的数的个数就是$2^{n}2^n$。很显然，这种算法的事件复杂度很大。但是似乎可以通过本题。具体的实现过程就是我们遍历每个元素的时候，将目前已经知道的所有元素和这个数进行组合，然后形成一个新的集合，依次类推，最后我们得到了所有可能的数的集合，然后找出最后的集合是否存在我们要求的那个数字就行了。
• 代码如下
  • 选出所有的数字可能组合的和，每个数字有选和不选两种操作，最后的时间复杂度为$O(2^n)O(2^n)$
  • 我们需要存储所有的数组合出来的结果，每个数字有选和不选两种操作，最后的空间复杂度为$O(2^n)O(2^n)$

#include<bits/stdc++.h>

using namespace std;
const int N=30000;
int a[55];
vector<int> v,tmp1,tmp2;
bool f[60000];
int main(){
    int n;
    while(cin>>n){
        tmp1.clear();
        tmp2.clear();
        memset(f,false,sizeof(f));
        v.clear();
        // 每个数组的数字的和是固定的
        int sum=0,sum3=0,sum5=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]%5==0) sum5+=a[i];
            else if(a[i]%3==0) sum3+=a[i];
            else{
                sum+=abs(a[i]); // 为了防止负数的情况，我们都进行取整数操作，这对结果不会有影响
                v.push_back(abs(a[i]));
            }
        }
        int tmp=sum+abs(sum5-sum3); // 5的倍数的数所在的数组的和
        if(tmp&1){
            puts("false");
            continue;
        }
        tmp/=2;
        // 特判为0的情况
        if(tmp==0){
            puts("true");
            continue;
        }
        //cout<<"tmp:"<<tmp<<endl;
        // 剩下不是3和5的倍数的数能否选出几个数字构成和为tmp
        // 我们直接进行暴力模拟，计算出所有可能的值
        for(auto x:v){
            for(auto y:tmp1){
                tmp2.push_back(y);
                tmp2.push_back(y+x);
            }
            tmp2.push_back(x);
            tmp1.clear();
            for(auto y:tmp2){
                tmp1.push_back(y);
            }
        }
        bool flag=false;
        for(auto x:tmp1){
            if(x==tmp){
                flag=true;
                break;
            }
        }
        if(flag){
            puts("true");
        }else{
            puts("false");
        }
    }
    return 0;
}

动态规划

• 我们来进一步考虑，其实这个可以用状态的转移来实现，也算是一个背包问题。首先，最初是的状态肯定是0，然后，我们可以利用元素的位置$ii$作为状态$DPDP$的阶段，在阶段$ii$的时候，$f[i]f[i]$表示前$i-1i-1$组合的数是否可以拼凑成数$ii$，然后进一步做出转移即可。

• 对状态转移的一些简要说明

• 代码如下

  • 这里我们首先遍历集合的元素，然后遍历每个元素的时候，我们有需要遍历所有的数字组合的情况，所以总的时间复杂度为$O(nm)O(nm)$.这里的$nn$为集合里面不是3的倍数和5的倍数的元素的个数，$mm$为集合里面我们需要拼出的和。
  • 我们的状态数组定义的是一个bool类型的数组，状态的数目最多为需要计算的所有的数的和的一半，所以空间复杂度为$O(M)O(M)$.$MM$为不是3的倍数和5的倍数的元素的和的一半。
  • 时间复杂度为$O(nm)O(nm)$.这里的$nn$为集合里面不是3的倍数和5的倍数的元素的个数，$mm$为集合里面我们需要拼出的和。
  • 空间复杂度为$O(M)O(M)$.$MM$为不是3的倍数和5的倍数的元素的和的一半。

#include<bits/stdc++.h>

using namespace std;
const int N=30000;
int a[55];
vector<int> v;
bool f[60000];
int main(){
    int n;
    while(cin>>n){
        memset(f,false,sizeof(f));
        v.clear();
        // 每个数组的数字的和是固定的
        int sum=0,sum3=0,sum5=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]%5==0) sum5+=a[i];
            else if(a[i]%3==0) sum3+=a[i];
            else{
                sum+=abs(a[i]);
                v.push_back(abs(a[i]));
            }
        }
        int tmp=sum+abs(sum5-sum3); // 5的倍数的数所在的数组的和
        if(tmp&1){
            puts("false");
            continue;
        }
        tmp/=2;
        //cout<<"tmp:"<<tmp<<endl;
        // 剩下不是3和5的倍数的数能否选出几个数字构成和为tmp
        // 所以，下面就转化为了01背包问题
        f[0]=true; // 由于可能有负数的情况，所以我们给每个值加上N，这样就可以确保每个数字都是正数，避免段错误
        for(auto x:v){
            for(int j=tmp;j>=x;j--){
                f[j]|=f[j-x];
            }
        }
        if(f[tmp]){
            puts("true");
        }else{
            puts("false");
        }
        
    }
    return 0;
}