Subsequence Addition

ダ月 · 2023-03-23 17:09:42 · 题解

题意概要：

给定长度为 n 的序列 a_i。现在有一个初始序列 \{1\}。每次操作可以选择当前序列的任意一个子序列，然后进行求和，求和后的数字可以加入任何一个位置。问初始序列是否可以经过有限次操作变成 a_i。

题目分析：

将 a_i 从小到大排序。先考虑暴力，当前集合已经有 x 个元素，进行搜索，看是否存在一个子序列和为 a_{x+1}。时间复杂度：O(n2^n)。显然任何一个任务都不能通过。

我们可以把题目抽象成如下：对于当前集合已经有了 a_i 的前 x 的数，当前集合中每个数最多使用一次，可以不使用。是否取其中一部分数字，和为 a_{x+1}。显然，这是一个经典的 01 背包问题。即 f_i 表示当前 i 这个数字是否取得到，考虑转移 f_{i}=\operatorname{or}f_{i-a_j},1\le j\le x 且 i\ge a_j。对于每个 x 都重新转移的话，时间复杂度：O(n^3)。(a_i 与 n 同阶)

我们对于每个 x，我们只用重新对 a_x 转移一遍 f_i 即可，因为前面能够取到的，当前也能取得到。时间复杂度：O(n^2)。能通过 Easy Version。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int T;
int n;
const int N=5e3+10;
int a[N];
bool w[N];
int main(){
    cin>>T;
    while(T--){
        cin>>n;int tem=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]==1)tem++;
        }
        sort(a+1,a+n+1);
        memset(w,false,sizeof(w));
        if(n==1){puts(a[1]==1?"YES":"NO");continue;}
        if(n==2){puts(tem==2?"YES":"NO");continue;}
        if(tem<2){puts("NO");continue;}
        w[1]=true;bool flag=true;
        for(int i=2;i<=n;i++){
            if(!w[a[i]]){
                flag=false;
                break;
            }
            for(int j=5000;j>=a[i];j--)
                w[j]|=w[j-a[i]];
        }puts(flag?"YES":"NO");
    }return 0;
}

注意到能取到的元素容易被转移很多次。这里只需要一个打表，或者有敏锐的直觉，你可以猜到一个结论：对于任意正整数 x，如果满足 \sum_{i=1}^{x-1}a_i\ge a_x，那么初始序列能够经过若干次操作变成 a_i。

证明先咕一下，打表结果如下：

上面是 n=4,a=\{1,1,2,4\} 的情况，下面是 n=5,a=\{1,1,2,3,7\} 的情况。

所以有了这个代码以后，只要求出 a_i 的前缀和就行。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int T;
typedef long long ll;
int n;
const int N=2e5+10;
ll a[N],s[N];
int main(){
    cin>>T;
    while(T--){
        cin>>n;int tem=0;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
        if(a[1]!=1){puts("NO");continue;}
        bool flag=true;
        for(int i=2;i<=n;i++)
            if(s[i-1]<a[i]){
                flag=false;
                break;
            }
        puts(flag?"YES":"NO");
    }return 0;
}

时间复杂度：O(n)。