题目链接

题目大意：

给你两个字符串只有01组成，你可以选取区间[l, r]，对字符串a在区间里面进行异或操作，对字符串b非区间值进行异或操作，问能否将两个字符串变为全0串。如果可以输出YES，操作次数，操作区间。

思路：

将他们全部变成0，等价于将全0变成a, b串。经归纳法可以发现，在进行基数次操作后a,b串每个对应字符都不同,偶数次操作他们每个对应字符都相同。那么我们可以进行的操作方案是将a串上的1全部变为0，如果b[1]=1，那代表b串全部是1，a串全部为0，那么我们可以进行操作（1，1），（1， 2），（2，2）。这样就结束了。

注意：

cout << endl; //速度很慢，不推荐使用

ios :: sync_with_stdio(false);

cin.tie(0);

cout.tie(0); //使用该流解除后将不能使用puts(""), 和scanf(), printf();

AC代码：

#include<bits/stdc++.h>

#define L(i, j, k) for(int i = (j); i <= (k); ++i)

#define R(i, j, k) for(int i = (j); i <= (k); --i)

#define ll long long

#define sz(a) ((int) (a).size())

#define vi vector< int >

#define me(a, x) memset(a, x, sizeof(a))

#define ull unsigned long long

#define ld __float128

using namespace std;

const int N = 1e6 + 7;

int n, m, t;

char s[N], p[N];

int a[N], b[N];

void Main() {

	cin >> n;

	cin >> (s + 1) >> (p + 1);

	for (int i = 1; i <= n; i ++ ) {

		a[i] = s[i] - '0';

		b[i] = p[i] - '0';

	}

	for (int i = 1; i <= n; i ++ ) {

		b[i] ^= a[i];

		if (b[i] != b[1]) {

			cout << "NO\n";

			return ;

		}

	}

	vector< pair<int, int> > vc;

	for (int i = 1; i <= n; i ++ ) {

		if (a[i]) {

			vc.emplace_back(i, i);

			b[1] ^= 1;

		}

	}

	if (b[1]) {

		vc.emplace_back(1, 1);

		vc.emplace_back(1, 2);

		vc.emplace_back(2, 2);

	}

	cout << "YES\n";

	cout << sz(vc) << '\n';

	for (auto i : vc)

		cout << i.first << ' ' << i.second << '\n';

}

int main() {

	ios :: sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	int t;

	cin >> t;

	while (t--) Main();

	return 0;

}

/* stuff you should look for 你应该寻找的东西

 * int overflow, array bounds (int)溢出，数组边界

 * special cases (n=1?) 特殊情况(n=1?)

 * do smth instead of nothing and stay organized 做一些事情而不是什么也不做，保证效率

 * WRITE STUFF DOWN 将东西写下

 * DON'T GET STUCK ON ONE APPROACH 不要在一个地方死磕

 */

巴特西

Complementary XOR

题目链接

题目大意：

思路：

注意：

AC代码：

最新文章

热门文章