Codeforces Round #742 (Div. 2)个人题解

比赛链接：Codeforces Round #742 (Div. 2)

A题 Domino Disaster

题目大意：

有一个 $2*n$ 的牌桌，你可以用 $1*2$ 的骨牌来占满它，现在给出第一行，输出第二行

思路解析：

签到题

AC代码：

#include<bits/stdc++.h>
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<n;i++){
            if(s[i]=='L')cout<<"L";
            else if(s[i]=='R')cout<<"R";
            else if(s[i]=='U')cout<<"D";
            else cout<<"U";
        }
        cout<<endl;
    }

}

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<bits/stdc++.h>
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<<n<<endl;
        else if((ans[n-1]^m)==n)cout<<n+2<<endl;
        else cout<<n+1<<endl;
    }

}

C题 Carrying Conundrum

题目大意：

$ALice$ 学加法学错了，他会隔一位进位，给出错误的加法结果，输出有多少种可能的相加方案

思路解析：

我们可以看到过错误的加法进位是奇偶分开的，所以我们可以直接结果的奇偶位分开处理，分别统计方案相乘即可，特别的，因为是正整数，所以要将 $0$ 的情况减去

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> 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<n;i++){
            if(i&1){
                a*=10;
                a+=s[i]-'0';
            }
            else {
                b*=10;
                b+=s[i]-'0';
            }
        }

        cout<<(a+1)*(b+1)-2<<endl;
    }

}

聚聚的数位DP代码（聚聚好强）：

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
  int n;
  cin >> n; 

  vector<int> d;
  while (n > 0) {d.push_back(n % 10); n /= 10;}

  i64 dp[4] = {}; 
  dp[0] = 1; 
  reverse(d.begin(), d.end());

  for (int x : d) {
    i64 g[4] = {};
    for (int i = 0; i < 4; i ++) { 
      for (int c = 0; c < 2; c ++) {
        int s = c * 10 + x - (i & 1);
        g[i] += dp[i >> 1 | c << 1] * (10 - abs(s - 9));
      }
    }
    for (int i = 0; i < 4; i ++) dp[i] = g[i];
  }
  cout << dp[0] - 2 << "\n";
}
int main()
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int tt; cin >> tt;
  while (tt --) solve();

  return 0;
}

推广一波小飞龙博客：戳这里@不会飞的小飞龙