题解：P17124 [ICPC 2025 Shanghai R] Not a subset sum

Bobi2014 · 2026-07-19 21:40:52 · 题解

这是一道签到题。

我才不告诉你我最开始使用字典树加线段树合并吃了七发罚时。

思路

考虑暴力枚举字符串 q，时间复杂度完全可以接受，再思考如何快速查询答案，对于 0 和 1 的情况可以直接将数组切成前后两个部分递归，对于问号我们考虑将数组对齐，即去掉这一位后后面都一样的数相加，可以结合代码理解：

int mid = len >> 1;
int* merge = tmp[dep];
for(int i = 0;i < mid;i ++){
    merge[i] = dat[i] + dat[i + mid];
}

这样就可以快速查询答案了，递归函数需要 3 个参数，dfs(int dep,int len,const int* dat)，dep 表示深度，len 表示当前区间长度，dat 表示需要处理的数据的指针，我们可以静态存储指针，即先对于每个深度创建数组，每次合并时再调用，递归函数代码：

int tmp[N][1 << (N - 1)];
void dfs(int dep,int len,const int* dat){
    if(len == 1){
        ans ^= dat[0];
        return;
    }
    int mid = len >> 1;
    dfs(dep + 1,mid,dat);
    dfs(dep + 1,mid,dat + mid);
    int* merge = tmp[dep];
    for(int i = 0;i < mid;i ++){
        merge[i] = dat[i] + dat[i + mid];
    }
    dfs(dep + 1,mid,merge);
}

然后就可以 AC 本题了。

Code

#include<bits/stdc++.h>
#define N 16
using namespace std;
int n,dat[1 << N],tmp[N][1 << (N - 1)],ans;
void dfs(int dep,int len,const int* dat){
    if(len == 1){
        ans ^= dat[0];
        return;
    }
    int mid = len >> 1;
    dfs(dep + 1,mid,dat);
    dfs(dep + 1,mid,dat + mid);
    int* merge = tmp[dep];
    for(int i = 0;i < mid;i ++){
        merge[i] = dat[i] + dat[i + mid];
    }
    dfs(dep + 1,mid,merge);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 0;i < (1 << n);i ++){
        cin >> dat[i];
    }
    dfs(0,1 << n,dat);
    cout << ans;
    return 0;
}