Codeforces Round #742 (Div. 2)个人题解
Codeforces Round #742 (Div. 2)个人题解
比赛链接：Codeforces Round #742 (Div. 2)
A题 Domino Disaster
题目大意：
有一个 \(2*n\) 的牌桌，你可以用 \(1*2\) 的骨牌来占满它，现在给出第一行，输出第二行
思路解析：
签到题
AC代码：
#include
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int vis[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
for(int i=0;i B题 MEXor Mixup
题目大意：
定义两个运算：
- \(MEX\) 在序列中从 \(0\) 开始第一个未出现的数
- \(XOR\) 序列中所有数的异或
现在给出 \(a，b\)，求出元素最少的序列使 \(MEX=a，XOR=b\)
思路解析：
首先考虑 \(MEX\)，很直接的我们可以想到，序列中一定存在 \(0\sim a-1\)，一定不存在a
其次，我们考虑 \(XOR\) ，因为一定有 \(0\sim a-1\) ，所以我们可以先求出 \(0\sim a-1\) 的 \(XOR\) 我们假设为 \(X\) ,如果 \(X=b\) 的话，答案就为 \(0\sim a-1\) 的长度即为 \(a\) ，如果 \(X^a==b\) 即 \(X^b==a\) 时，我们不能加入 \(a\)， 所以我们至少需要加入两个比 \(a\) 大的数来异或凑出 \(a\) ，此时答案为 \(a+2\) ，否则我们就可以至少加入一个来达到 \(XOR=b\)，答案为 \(a+1\)
AC代码：
#include
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
int ans[maxn];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
for(int i=0;i<3e5+7;i++){
ans[i]=ans[i-1]^i;
}
int t;
cin>>t;
while(t--){
int n,m;
cin>>n>>m;
if(ans[n-1]==m)cout< C题 Carrying Conundrum
题目大意：
\(ALice\) 学加法学错了，他会隔一位进位，给出错误的加法结果，输出有多少种可能的相加方案
思路解析：
我们可以看到过错误的加法进位是奇偶分开的，所以我们可以直接结果的奇偶位分开处理，分别统计方案相乘即可，特别的，因为是正整数，所以要将 \(0\) 的情况减去
AC代码：
#include
using namespace std;
typedef pair pii;
typedef long long ll;
const int maxn=1e5+5;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
string s;
cin>>s;
int n=s.size();
int a=0,b=0;
for(int i=0;i