[CF1031E]Triple Flips

题目大意：给你一个长度为$n$的$01$串，一次操作定义为：选取$3$个等距的元素，使其$0$变$1$，$1$变$0$，要求在$\Big\lfloor \dfrac n 3\Big\rfloor+12$次操作内变为全$0$。输出是否可行以及方案

题解：skip1978的博客讲的十分详细。发现给的操作次数很少，基本上一次操作要使得$3$个元素变成$0$

对于区间$[l,r]$，若$a_l=0$，这一位不用翻转，缩小到区间$[l+1,r]$，这样$a_l,a_{l+1},a_{l+2}$有$4$中可能：

$1,1,1：$翻转$a_l,a_{l+1},a_{l+2}$就可以使得这三位变$0$
$1,0,1：$翻转$a_l,a_{l+2},a_{l+4}$就可以使得这三位变$0$
$1,0,0：$翻转$a_l,a_{l+3},a_{l+6}$就可以使得这三位变$0$
$1,1,0：$可以按相同方法收缩右端点，直到右端点也出现这样的情况

- 若$l,r$奇偶性相同，可以翻转$a_l,a_{\frac{l+r}{2}},a_r$和$a_{l+1},a_{\frac{l+r}{2}},a_{r-1}$使得这六位变成$0$
- 若$l,r$奇偶性不同，可以翻转$a_l,a_{\frac{l+r-1}{2}},a_{r-1}$和$a_{l+1},a_{\frac{l+r+1}{2}},a_r$使得这六位变成$0$

然后发现若区间长度大于等于$8$，一定可以翻转成$0$，并且所有合法的翻转只有$12$次，可以暴力枚举每一个操作是否使用即可

卡点：找到答案后忘记退出

C++ Code：

#include <cstdio>

#include <vector>

#define maxn 100010

int n, s[maxn];

struct Step {

	int a, b, c;

	inline Step() {}

	inline Step(int __a, int __b, int __c) {a = __a, b = __b, c = __c;}

};

std::vector<Step> Ans;

bool find_ans = false;

inline void reverse(int a, int b, int c) {

	s[a] ^= 1, s[b] ^= 1, s[c] ^= 1;

	Ans.push_back(Step(a, b, c));

}

inline void reverse(int a, int c) {

	int b = a + c >> 1;

	reverse(a, b, c);

}

std::vector<std::pair<int, int> > V;

int tmp[maxn];

#define rev(x) tmp[x.first] ^= 1, tmp[x.first + x.second >> 1] ^= 1, tmp[x.second] ^= 1

inline bool end(int l, int r) {

	for (int i = l; i <= r; i++) if (tmp[i]) return false;

	return true;

}

void calc(int l, int r) {

	for (int i = l; i <= r - 2; i++) {

		for (int j = i + 2; j <= r; j += 2) {

			V.push_back(std::make_pair(i, j));

		}

	}

	int sz = V.size(), U = 1 << sz;

	for (int i = 0; i < U; i++) {

		for (int i = l; i <= r; i++) tmp[i] = s[i];

		for (int j = 0; j < sz; j++) if (i & 1 << j) rev(V[j]);

		if (end(l, r)) {

			find_ans = true;

			for (int j = 0; j < sz; j++) if (i & 1 << j) reverse(V[j].first, V[j].second);

			return ;

		}

	}

}

#define checkl(x, a, b, c) (s[x] == a && s[x + 1] == b && s[x + 2] == c)

#define work(l, r, L, R) {reverse(l, r), solve(L, R); return ;}

#define checkr(x, a, b, c) (s[x] == a && s[x - 1] == b && s[x - 2] == c)

void solve(int l, int r) {

	if (r - l + 1 <= 8) {

		while (r - l + 1 < 8 && l > 1) l--;

		while (r - l + 1 < 8 && r < n) r++;

		calc(l, r);

		return ;

	}

	if (!s[l]) {solve(l + 1, r); return ;}

	if (!s[r]) {solve(l, r - 1); return ;}

	if (checkl(l, 1, 1, 1)) work(l, l + 2, l + 3, r);

	if (checkl(l, 1, 0, 1)) work(l, l + 4, l + 3, r);

	if (checkl(l, 1, 0, 0)) work(l, l + 6, l + 3, r);

	if (checkr(r, 1, 1, 1)) work(r - 2, r, l, r - 3);

	if (checkr(r, 1, 0, 1)) work(r - 4, r, l, r - 3);

	if (checkr(r, 1, 0, 0)) work(r - 6, r, l, r - 3);

	if (r - l & 1) {

		reverse(l, r - 1), reverse(l + 1, r);

		solve(l + 3, r - 3);

	} else {

		reverse(l, r), reverse(l + 1, r - 1);

		solve(l + 3, r - 3);

	}

}

int main() {

	scanf("%d", &n);

	for (int i = 1; i <= n; i++) scanf("%d", s + i);

	solve(1, n);

	if (find_ans) {

		puts("YES");

		printf("%d\n", Ans.size());

		for (std::vector<Step>::iterator it = Ans.begin(); it != Ans.end(); it++) {

			printf("%d %d %d\n", it -> a, it -> b, it -> c);

		}

	} else puts("NO");

	return 0;

}

巴特西

[CF1031E]Triple Flips

最新文章

热门文章