题解：P17124 [ICPC 2025 Shanghai R] Not a subset sum
Genshigros
·
·
题解
一、 分析和思路
1. 暴力搜索
此处需要两个深搜函数。
复杂度分析：$\text{dfs1}(s)$ 遍历 $3^n$ 个状态， $dfs2$ 对每个状态转化所有 $?$，最坏 $O(6^n)$。
### 2. 记忆化搜索
可以发现，$\text{dfs2}$ 函数在将某一状态中出现 $?$ 的位置被填上 $0$ 或 $1$ 后，$\text{dfs2}$ 所求的子问题同样可以定义为“给定一个含 $?$ 的字符串（$?$ 的数量可为 $0$），求所有展开结果的权值之和”，该结果仅与字符串本身有关，因此可对 $\text{dfs2}$ 做记忆化。
比如 $1?01$ 会被转化为 $1001$ 和 $1101$，结果为 $\text{dfs2( }1001 \text{ )}$ 与 $\text{dfs2( }1101 \text{ )}$ 的和，而这两个转化后的字符串也是 $\text{dfs1}$ 搜索过程中会到达的状态。自然就可以对 $\text{dfs2}$ 函数进行记忆化搜索。以 $\text{string}$ 为键，就需要使用 $\text{unordered\_map}$ 或 $\text{map}$ 进行记忆化的记录。
但由于 $a_i$ 的值可能为 $0$，而 $\text{unordered\_map}$ 或 $\text{map}$ 的默认初始值都是 $0$，所以不能够只用一个 $mem$ 数组用于记录该状态的答案，还需要 $vis$ 数组标记该状态是否已被访问。
复杂度分析：时间复杂度已经降至 $O(3^n)$，但由于 $\text{unordered\_map}$ 和 $\text{map}$ 使用 $\text{string}$ 时常数极大，导致在所有可能的状态数为 $3^{16} \approx 4.3 \times 10^7$ 的情况下一定会超时，所以仍需要优化。
### 3. 将字符串替换为整数进行编码
为了解决字符串作为 $\text{unordered\_map}$ 和 $\text{map}$ 的键时的极大的常数所带来的问题，此处需要改用整数编码状态，使用三进制，将 $?$ 编码为 $2$。
在 $\text{dfs1}$ 函数中，若该状态为整数 $s$，那么将下一个状态 $s'$ 记为 $s \times 3 + k$，$k \in \{0,1,2\}$。
在 $\text{dfs2}$ 函数中，从低位到高位遍历每一位，位的索引是 $[0,n-1]$。设此时传入的状态整数为 $s$，该 $?$ 所在位的索引为 $k$，那么下一次需要递归搜索 $s-3^k \times 2$ 和 $s-3^k$，前一个是转换为 $0$ 的状态，后一个是转换为 $1$ 的状态。记忆化数组可相应地改用普通数组实现，初始化时将未搜索的状态记为 $-1$。
最终时间复杂度为 $O(3^n)$，空间复杂度为 $O(3^n)$。
## 二、 代码
```cpp
#include<stdio.h>
#include<string.h>
int a[214514];
int n;
int p3[1145];//3^k预处理
int *vis;
int dfs2(int s){
if(vis[s]!=-1){
return vis[s];
}
int p3n=1,tmp=s;
for(int i=0;i<n;i++){
if(tmp%3==2){//找到含有?的位置
int go0=dfs2(s-p3n*2);
int go1=dfs2(s-p3n);
int tas=go0+go1;
return vis[s]=tas;
}
tmp/=3;
p3n*=3;
}
//若该状态没有?符号
int tas=0;
tmp=s;
for(int i=0;i<n;i++){
tas+=(tmp%3)<<i;//回到二进制编码
tmp/=3;
}
vis[s]=a[tas];
return a[tas];
}
int dfs1(int s,int len){
if(len==n){
return dfs2(s);
}else{
int tas=0;
tas^=dfs1(s*3+1,len+1);
tas^=dfs1(s*3+0,len+1);
tas^=dfs1(s*3+2,len+1);
return tas;
}
}
int main(){
scanf("%d",&n);
int m=(1<<n);
for(int i=0;i<m;i++){
scanf("%d",a+i);
}
p3[0]=1;
for(int i=1;i<=n;i++){
p3[i]=p3[i-1]*3;
}
vis=new int [p3[n]+1];
memset(vis,-1,sizeof(int)*(p3[n]+1));
printf("%d",dfs1(0,0));
return 0;
}
```