首页 > 其他分享 >CF1975F

CF1975F

时间:2024-05-26 19:00:10浏览次数:20  
标签:std int lmt dfs CF1975F bit nw

类似题目:[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

相关文章