类似题目:[BalticOI 2014 Day 1] Sequence。
然而暑假模拟赛没做出来,现在照样做不出来捏。场上不知道为啥一直想高位前缀和描述限制。
考虑按位填,每次填完以后限制会有一定变化,具体来说,设原来的限制是 \(lmt_T\),那么:
- 填 \(0\):变成 \(lmt'_T=lmt_{T*2}\&lmt_{T*2+1}\)。
- 填 \(1\):变成 \(lmt'_T = lmt_{T*2}\&(lmt_{T*2+1}>>1)\)。
(\(\LaTeX\) 格式懒得标准写了,反正都能看懂,就这样吧。)
dfs 即可。时间复杂度 \(\mathcal O(n2^n)\)。
#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second
using i64 = long long;
using pii = std::pair<int, int>;
constexpr int maxn = 20;
int n, S;
std::vector<int> ans;
void dfs(int bit, int cur, std::vector<int> lmt) {
if (bit == n) {
int x = lmt.back();
if (x == 1) ans.pb(cur);
return;
}
std::vector<int> nw(lmt.size() / 2, 0);
std::fill(nw.begin(), nw.end(), S);
for (int i = 0; i < lmt.size(); ++i)
nw[i >> 1] &= lmt[i];
dfs(bit + 1, cur, nw);
std::fill(nw.begin(), nw.end(), S);
for (int i = 0; i < lmt.size(); ++i) {
if (i & 1) {
nw[i >> 1] &= lmt[i] >> 1;
} else {
nw[i >> 1] &= lmt[i];
}
}
dfs(bit + 1, cur | (1 << bit), nw);
return;
}
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin >> n; S = (1 << n + 1) - 1;
std::vector<int> b(1 << n, 0);
for (int i = 1; i < (1 << n); ++i)
std::cin >> b[i];
b[0] = 1;
dfs(0, 0, b);
std::cout << ans.size() << '\n';
std::sort(ans.begin(), ans.end());
for (auto& v : ans)
std::cout << v << '\n';
return 0;
}
标签:std,int,lmt,dfs,CF1975F,bit,nw
From: https://www.cnblogs.com/663B/p/18214147