CF1807G2 - Subsequence Addition (Hard Version)

· · 题解

bitset

最开始序列 a 中仅有一个 1。

由于可以在 a 中任意选择任意数量的数、拼出的数可以插入任何位置，考虑贪心，对序列 c 从小到大排序，判断首位是否为 1，不为 1 显然无法从 a 获得。

初步检查之后将 bitset 下标为 1 的位赋 1，其余置 0。

从小到大枚举 c 中元素，判断其在 bitset 中的对应的位是否为 1，若不为 1 则无法从 a 中获得该元素，也就说明 c 序列无法从 a 获得。

若其值为 1，需要将所有能够拼出的值加上这个数，此时 bitset 中所有可以被拼出的值下标处为 1，不可被拼出的值下标处为 0。

从小到大枚举 c 中元素，若当前枚举到的元素为 c_i，将 bitset 与其自身左移 c_i 位后的值进行按位或运算即可更新所有能够被拼出的数。

由于序列长度 n 与值域 V 同阶，时间复杂度 O(n^2/w)，其中 w=32。

可以使用 CodeForces 语言选项中的 GNU C++20 (64) 来加速 bitset，使 w=64，但由于 CF 的 64 位机自带大常数，总体效率仍然比 32 位机慢，运算量大或需要卡常的情况下不建议使用。

bitset 的效率非常好，一秒内跑完 n=10^5 是没有问题的，本题的时限为 2000ms 且最坏情况下 n=2\times10^5，跑满的情况下有可能超时。

下面的代码在赛后 18h 左右被 hack(TLE)，但最终 System Test 时通过了所有 hack 数据，同样是本题的 AC 代码。

bitset 能否通过一定程度上取决于评测机发挥，存在风险，但它仍然是一种值得学习的解法。

#include<bits/stdc++.h>
using namespace std;
int T,n,c[200005];
bitset<200004> s;
void deal(){
    cin>>n,s.reset();
    for(int i=1;i<=n;i++) cin>>c[i];
    s[1]=1,sort(c+1,c+n+1);
    if(c[1]!=1) return cout<<"NO\n",void();
    for(int i=2;i<=n;i++)
        if(s[c[i]]) s|=s<<c[i];
        else return cout<<"NO\n",void();
    cout<<"YES\n";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    for(cin>>T;T;T--) deal();
    return 0;
}