大家好，又见面了，我是你们的朋友全栈君。
近来做了一些题目和异或运算有关的题目，总结一下
Xor
按位异或
符号在编程语言中通常是 ^或xor
数学符号通常用⊕表示
X = 0101B
Y = 1011B
| X | Y | X⊕B |
|---|---|---|
| 1 | 0 | 1 |
| 1 | 1 | 0 |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
X^Y = 1110B
性质
1. 0 ^ 0 = 0
2.a ^ a = 0
3.0 ^ 1 ^ 2 … ^ n的性质
先观察一下如下的 序列
我们暴力计算出前50项的异或和,观察规律
1 3 0 4 1 7 0 8 1 11 0 12 1 15 0 16 1 19 0 20 1 23 0 24 1 27 0 28 1 31 0 32 1 35 0 36 1
不难得出每隔四项的异或和都为0
并且每四项都是以1 N-1 0 N这四项为规律
这里N取第一个大于等于n且是4的倍数的数
所以我们想要求得第1项到第n项的异或和的结果
只需要异或
n - n % 4 ^ (n - n % 4 + 1) ^... ^ n
while (n % 4 != 3 && n >= 0) {
ans ^= n; n --;
}
4.[l,r]区间的异或和
l ^ l + 1 ^ l + 2^… ^ r = (1 ^ 2… ^ l ) ^ (1 ^ 2 ^ 3… ^ r)
所以如果我们要求一个区间段的异或和，只需要求(1-l) 的异或和 ^ (1-r)的异或和
证明
1 ^ 2 ^ 3 ... ^ l
1 ^ 2 ^ 3... ^l ^ l+1 ^l+2 ....^ r-1 ^ r
很容易发现1^2^3...l相同,则异或和为0
传送门
XOR Sum
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
ll a,b;
cin >> a >> b;
int kk = a % 4;
a -= kk;
ll ans = 0;
for(ll i = a + kk;i < a + 4;i++)
{
ans ^= i;
}
int ss = b % 4;
b -= ss;
for(ll i = b;i <= b + ss;i++)
{
ans ^= i;
}
cout << ans;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
void solved()
{
ll ans = 0,n;
cin >> n;
while (n % 4 != 3 && n >= 0) {
ans ^= n;
n --;
}
}
int main() {
cin >> t;
while (t --)
solved();
return 0;
}
#include <bits/stdc++.h>
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
using namespace std;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
string t;
int n;
cin >> n >> t;
for (char c : {
'W', 'B'}) {
string s = t;
vector<int> v;
for (int i = 0; i < n - 1; i++) {
if (s[i] != c) {
v.push_back(i);
s[i] = (s[i] == 'W' ? 'B' : 'W');
s[i + 1] = (s[i + 1] == 'W' ? 'B' : 'W');
}
}
if (s[n - 1] == c) {
cout << v.size() << "\n";
for (int x : v)
cout << x + 1 << " ";
cout << "\n";
return 0;
}
}
cout << -1;
return 0;
}
#include <bits/stdc++.h>
#define N 100010
#define CINSPEED std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
using namespace std;
typedef long long ll;
int n;
int dfs(vector<int> t,int i)
{
vector<int>one,zero;
if(i < 0 || t.size() == 0)return 0;
for(auto & j : t)
{
if(j >> i & 1)
one.push_back(j);
else zero.push_back(j);
}
if(!zero.size())return dfs(one,i - 1);
if(!one.size())return dfs(zero,i - 1);
return min(dfs(one,i - 1),dfs(zero,i - 1))|(1 << i);
}
int main()
{
cin >> n;
vector<int> k(n);
for(int i = 0;i < n;i++)cin >> k[i];
cout << dfs(k,30);
#ifdef LOCAL
system("pause");
#endif
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/160202.html原文链接：https://javaforall.net
