周赛好题推荐

这周周赛很有质量的，上了一个很有意思的数学题目，推了半天.....

给定一个区间[l,r]，求出区间内所有满足x mod  2^i !=k的所有正整数（最后全部进行异或）

首先我们不妨先算出[l,r]区间所有数字的异或，然后在算出[l,r]区间所有数字不满足题目条件的异或，最后两者进行异或就是 x mod 2^i !=k所有数字的答案。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cun(int n){//计算从1到n所有整数的按位异或（XOR）结果//利用了模4的周期性规律来快速计算结果：//如果n ≡ 0 mod 4，结果为n。//如果n ≡ 1 mod 4，结果为1。//如果n ≡ 2 mod 4，结果为n + 1。//如果n ≡ 3 mod 4，结果为0。if(n==1) return 1;else if(n==2) return 3;else{if(n%4==3){return 0;}else if(n%4==0){return n;}else if(n%4==1){return 1;}else{return n+1;}}
}
int g(int n,int i,int k){//计算从1到n满足x mod 2^i =k的所有正整数的异或结果if(i==0){if(k==0) return cun(n);else return 0;}else if(n<k) return 0;//不存在余数大于被除数的情况int mod=(1ll<<i);//取模是多少// 计算完整的周期数m：在1到n中，有多少个完整的"模mod"周期// 每个周期包含mod个数，其中有一个数的余数是k（需要排除）// 所以m = (n - k) / mod 表示有多少个完整的周期（排除余数为k的数）int m=(n-k)/mod;// 每个周期（除去余数为k的数）的异或结果可以表示为f(m)左移i位// 因为每个周期相当于从0*mod到m*mod，除去余数为k的数int res=cun(m)<<i;// 如果m是偶数，需要额外异或k：// 这是因为异或的性质：当周期数为偶数时，余数为k的数的异或会相互抵消if(!(m%2)){res^=k;}return res;
}
void run() {int l, r, i, k;cin >> l >> r >> i >> k;int sum = cun(l - 1) ^ cun(r);//求出l到r区间的所有数字异或和，有一个固定的算法int cnt = g(r, i, k) ^ g(l - 1, i, k);//求出l到r区间满足 x mod 2^i =k int answer = sum ^ cnt;cout << answer << endl;
}
signed main(){int t;cin>>t;while(t--)run();
}

给定一个字符串，并且可以做出任意操作对1变成0，0变成1

求最小操作可以将字符串分成偶数长度，且子字符串内所有数字都相同

解法：每两个相邻的作为一组，两者不同（10或者01）就对其中一个进行改变，最小字段数就是在排除了01字串后对剩下的字符串进行分组，相邻且不同算成一组

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline void solve(){int t;cin>>t;string ac;cin>>ac;int ans=0;int sum=1;//最少字段数是1string answer="";for(int i=0;i<ac.size();i+=2){ans+=ac[i]!=ac[i+1]?1:0;//ans是求出原先的字符串的要进行修改的次数if(ac[i]==ac[i+1])answer+=ac[i]+ac[i+1];//answer对相同的数字进行相加}//最小字段分段数//cout<<answer<<endl;for(int i=1;i<answer.size();i++){if(answer[i]!=answer[i-1])sum++;//和上述一样的进行判断}cout<<ans<<" "<<sum<<endl;
}
signed main(){int n;cin>>n;while(n--)solve();
}