位运算#蓝桥杯

文章目录

位运算#蓝桥杯
- 1、小蓝学位运算
- 2、异或森林
- 3、位移
- 4、笨笨的机器人
- 5、博弈论

1、小蓝学位运算

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const LL N = 1e9+7; 
template<int kcz>
struct ModInt {
#define T (*this)
    int x;
    ModInt() : x(0) {}
    ModInt(int y) : x(y >= 0 ? y : y + kcz) {}

    ModInt(LL y) : x(y >= 0 ? y % kcz : (kcz - (-y) % kcz) % kcz) {}

    inline int inc(const int &v) {
        return v >= kcz ? v - kcz : v;
    }

    inline int dec(const int &v) {
        return v < 0 ? v + kcz : v;
    }

    inline ModInt &operator+=(const ModInt &p) {
        x = inc(x + p.x);
        return T;
    }

    inline ModInt &operator-=(const ModInt &p) {
        x = dec(x - p.x);
        return T;
    }

    inline ModInt &operator*=(const ModInt &p) {
        x = (int) ((LL) x * p.x % kcz);
        return T;
    }

    inline ModInt inverse() const {
        int a = x, b = kcz, u = 1, v = 0, t;
        while (b > 0)t = a / b, std::swap(a -= t * b, b), std::swap(u -= t * v, v);
        return u;
    }

    inline ModInt &operator/=(const ModInt &p) {
        T *= p.inverse();
        return T;
    }

    inline ModInt operator-() const {
        return -x;
    }

    inline friend ModInt operator+(const ModInt &lhs, const ModInt &rhs) {
        return ModInt(lhs) += rhs;
    }

    inline friend ModInt operator-(const ModInt &lhs, const ModInt &rhs) {
        return ModInt(lhs) -= rhs;
    }

    inline friend ModInt operator*(const ModInt &lhs, const ModInt &rhs) {
        return ModInt(lhs) *= rhs;
    }

    inline friend ModInt operator/(const ModInt &lhs, const ModInt &rhs) {
        return ModInt(lhs) /= rhs;
    }

    inline bool operator==(const ModInt &p) const {
        return x == p.x;
    }

    inline bool operator!=(const ModInt &p) const {
        return x != p.x;
    }

    inline ModInt qpow(LL n) const {
        ModInt ret(1), mul(x);
        while (n > 0) {
            if (n & 1)ret *= mul;
            mul *= mul, n >>= 1;
        }
        return ret;
    }

    inline friend std::ostream &operator<<(std::ostream &os, const ModInt &p) {
        return os << p.x;
    }

    inline friend std::istream &operator>>(std::istream &is, ModInt &a) {
        LL t;
        is >> t, a = ModInt<kcz>(t);
        return is;
    }

    static int get_mod() {
        return kcz;
    }

    inline bool operator<(const ModInt &A) const {
        return x > A.x;
    }

    inline bool operator>(const ModInt &A) const {
        return x < A.x;
    }
#undef T
};
using Z=ModInt<N>;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;cin>>n;
	if(n>8192){
		cout<<"0\n";return 0;
	}
	vector<int> a(n),sum_xor(n+1,0);
	for(auto &x:a)cin>>x;
	/*
		为什么使用前缀异或和？ 
		快速计算任意区间的异或结果
		有了前缀异或和，如果要计算区间 [l, r] 的异或结果
		只需要通过 sum_xor[r+1] ^ sum_xor[l] 即可得到结果
		因为在l之前的数据包都是一样的，异或结果都是0 
	*/
	Z ans = 1;
	for(int i=1;i<=n;i++)sum_xor[i]=sum_xor[i-1]^a[i-1];
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			ans*=sum_xor[i-1]^sum_xor[j];
		}
	} 
	cout<<ans;
 	return 0;
}

2、异或森林

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;cin>>n;
	vector<int> a(n),sum_xor(n+1,0);
	for(auto &x:a)cin>>x;
	for(int i=1;i<=n;i++)sum_xor[i]=sum_xor[i-1]^a[i-1];
	/*
		是需要咱们找到连续子数组的数量
		n * (n + 1) / 2 表示长度为1的子数组有 n 个
		长度为2的子数组有 n-1 个，以此类推
		最终得到总共 n * (n + 1) / 2 个子数组
		所以，
		n(n+1)/2 = 连续子数组个数 
	*/
    int ans = n * (n + 1) / 2;
    // 记录每个前缀异或和的次数 
    vector<int> cnt(4 * n + 1);
    cnt[0] = 1;
    /*
    	n  x|n  n/x|n 
		if x=n/x，那么说明这个n的因数就是奇数个了，因为这两个数一样
		所以·判断条件就是 x^2=n
		因为 奇数 个好判断，所以我们列举出来所有可能的数量就是ans
		让 ans 减去奇数个的就行了 
	*/ 
    for (int r = 1; r <= n; r++) {
        for (int i = 0; i * i <= 2 * n; i++) {
            ans -= cnt[sum_xor[r] ^ (i * i)];
        }
        cnt[sum_xor[r]]++;
    }
    cout << ans << '\n';
 	return 0;
}

3、位移

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;cin>>n;
	while(n--){
		unsigned int a,b;cin>>a>>b;
		while(!(a&1))a>>1;
		while(!(b&1))b>>1;
		if(a<b){
			cout<<"No\n";return 0;
		} 
		// 因为输入的是10进制，所以我们要转化这两个数的二进制状态
		vector<int> A,B;
		while(a>0){
			A.push_back(a&1);a=>>1;
		}
		while(b>0){
			B.push_back(b&1);b=>>1;
		}  
		//判断 b 是否在 a 里面
		int n = (int) A.size(), m = (int) B.size();
		// 字符串匹配 
    	for (int i = 0; i + m - 1 < n; i++) {
        	int fl = 0;
        	for (int j = 0; j < m; j++) {
        		// 对于 A 来讲 肯定是 每次移动，B 从头开始的 
            	if (A[i + j] != B[j]) {
                	fl = 1;
                	break;
                }
            }
        }
        if (!fl) {
            cout << "Yes\n";
            return 0;
        }
    	cout << "No\n";
	} 
 	return 0;
}

4、笨笨的机器人

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    int n;cin>>n;
	vector<int> a(n);
	for(auto &x:a)cin>>x; 
    int cnt = 0;
    // 枚举集合，此时 S 的每一位表示第 i 个数是加还是减
	// 为了生成长度为 n 的二进制数的所有可能情况
	// 通过这种方法来穷举所有的子集合
    for (int S = 0; S < 1 << n; S++) {
        int p = 0;
        // 求第 i 位是加还是减
        for (int i = 0; i < n; i++) {
            // S >> i & 1 的意思是先做 S >> i，再 & 1，含义是 S 的第 i 位是不是 1
            // S >> i 等价于 S / 2 ^ i 下取整，意味着去除了最后的 i 位，此时个位数 (二进制) 是原数第 i 位
            // x & 1 等价于与 1 取 and，也就是只有 x 的个位与 1 做了 and，即 x 的个位数是不是 1
            if (S >> i & 1)p += a[i];
            else p -= a[i];
        }
        if (p % 7 == 0)cnt++;
    }
    double ans = (double)cnt/(1<<n);
    ans = round(ans * 1e4) / 1e4;
    cout<<fixed<<setprecision(4)<<ans;
 	return 0;
}