526互联

Codeforces Round 742 Div2 A-D题解

发布时间 2023-09-27 11:54:31作者: tiany7

Codeforces Round 742 Div2 A-D题解

A. Domino Disaster

这题就是说给出一些2x1 tile，然后给出2xn的第一行构造，问第二行

这个刚开始想着是啥dp，一看那么多人过了果断改思路，发现这题就是个模拟题，就是把U换成D，D换成U，L和R不影响，然后输出就行了

代码 
#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (2e5  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
int n, m;
int a[limit];
void solve() {
    cin>>n;
    string str;
    cin>>str;
    str = " " + str;
    string ans;
    rep(i,1,n){
        char c;
        if(str[i] == 'L'){
            c = 'L';
        }
        if(str[i] == 'R'){
            c = 'R';
        }
        if(str[i] == 'U'){
            c = 'D';
        }
        if(str[i] == 'D'){
            c = 'U';
        }
        ans += c;
    }
    cout<<ans<<endl;


}
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    int kase;
    cin>>kase;
    while (kase--)
        invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

B. MEXor Mixup

这个题思路很好想，就是有些trick，首先出现要出现mex我们至少要有mex - 1个数字。 然后我们需要讨论一下mex - 1个能否满足。什么情况下能够满足？
因为xor的前缀和和交换律性质，所以我们如果mex - 1个数字bitxor前缀和等于pb，我们直接就满足了。如果不满足，那么我们可以用b bitxor一下mex - 1的前缀和就好了，所以分别是 + 1 和 + 2

代码 
#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (3e5  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
int n, m;
int a[limit];
// 0 1 2 3
void solve() {
    int pa, pb;
    cin>>pa>>pb;
    ll ans = pa + 1;
    if(pa > 0){
        if(a[pa - 1] == pb){ // 如果pa - 1刚好是，那么只需要pa个
            cout<<ans - 1<<endl;
            return;
        }
    }
    if((pb ^ a[pa - 1]) == pa){
        ans++;
    }
    cout<<ans<<endl;
}
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    rep(i,1,3e5){
        a[i] = i ^ a[i - 1];
    }
    int kase;
    cin>>kase;
    while (kase--)
        invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

思路不集中，所以写了不少时间

C. Carrying Conundrum

这题是做加法，然后进位不是相邻位置进位，而是隔着两位进位，问给出一个数字有多少ordered pair在错误条件下加起来等于这个数字。

首先我们观察到，隔一位进位，只和前两位有关系，让我们想到马尔可夫链。

然后我们可以dp出来每个地方进位 + 不进位的情况，其实后面意识到这个过程是求奇数和偶数上的方案数，哎昨天看了那个交互题说要对奇偶性敏感，自己还是不太敏感。然后找了stack overflow上一个很有意思的题目的一个类似解法。把奇偶位置上的方案数 + 1代表全是0的情况，然后相乘， -2去除有一半是0的情况就行了。

代码 
#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (3e5  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
int n, m;
int a[limit];
// 0 1 2 3
int dp[15]; // 代表第i位是j的是否carry
void solve() {
    cin>>n;
    string str = to_string(n);
//    reverse(str.begin(), str.end()); //先反转
    n = str.length();
    str = " " + str;
    ll ans = 0;
    auto st = str | ranges::views::transform([](char c) { if(c == ' ') return 0; return c - '0'; });
    auto get_plan = [](ll x){
        ll ans = 0;
        rep(i,0,10){
            rep(j,i, 10){
                if(i + j == x)ans++;
            }
        }
        return ans / 2;
    };
    auto get_big_plan = [](ll x){
        ll ans = 0;
        rep(i,0,10){
            rep(j,0,10){
                if(i + j >= 10 and (i + j) % 10 == x){
                    ans++;
                }
            }
        }
        return ans /  2;
    };
    // for(auto it : st){
    //     cout<<it;
    // }
    // cout<<endl;
    memset(dp, 0, sizeof dp);
    dp[1] = st[1];
    dp[2] = st[2];
    rep(i,3,n){
        int x = st[i];
        dp[i] = dp[i - 2] * 10 + st[i];
    }
    ll res = dp[n];
    res++;
    res *= dp[n - 1] + 1;
    res -= 2; //special case
    cout<<res<<endl;
}
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    rep(i,1,3e5){
        a[i] = i ^ a[i - 1];
    }
    int kase;
    cin>>kase;
    while (kase--)
        invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

D. Expression Evaluation Error

这题是给出一个和s，拆成n个正整数，要求11进制下和最大。
首先我们枚举一下11 - 10进制映射，然后然后我们发现，在11进制末尾位9 - 0的变化中，我们的10进制加了2，如果有更多的后缀0那么收益更大，所以我们想到先贪心。

然后写了一版除了不够的放1，其他平均分10的，不对，发现100的收益比拆成若干个10更大，后缀0位置上的数字对于答案的收益和两个数字单独拿出来是一样的。所以我们贪心地选择当前后缀0长度最大的那个进行拆分，最后拆不动了全放在第n位上就好。

可惜，这题vp的时候wa了4发才发现是我忘记删第一版代码导致的。吐了

代码 
#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (3e5  + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define pi(a, b) pair<a,b>
#define rep(i, a, b) for(ll i = a; i <= b ; ++i)
#define per(i, a, b) for(ll i = b ; i >= a  ; --i)
#define MOD 998244353
#define traverse(u) for(int i = head[u]; ~i ; i = edge[i].next)
#define FOPEN freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\data.txt", "rt", stdin)
#define FOUT freopen("C:\\Users\\tiany\\CLionProjects\\akioi\\dabiao.txt", "wt", stdout)
typedef long long ll;
typedef unsigned long long ull;
char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;
inline ll read() {
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    ll sign = 1, x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {
        if (s == '-')sign = -1;
        s = getchar();
    }
    while (s >= '0' && s <= '9') {
        x = (x << 3) + (x << 1) + s - '0';
        s = getchar();
    }
    return x * sign;
#undef getchar
}//快读
void print(ll x) {
    if (x / 10) print(x / 10);
    *O++ = x % 10 + '0';
}

void write(ll x, char c = 't') {
    if (x < 0)putchar('-'), x = -x;
    print(x);
    if (!isalpha(c))*O++ = c;
    fwrite(obuf, O - obuf, 1, stdout);
    O = obuf;
}
#define int ll
int n, m;
ll a[limit];
void solve() {
    ll s;
    cin>>s>>n;
    rep(i,1,n) a[i] = 0;
    ll num[] = {1ll, 10ll, 100ll, 1000ll, 10000ll, 100000ll, 1000000ll, 10000000ll, 100000000ll, 100000000ll};
    rep(i,1,n){
        // 现在安排到第几位了
        ll cur = 1;
        ll rem = n - i;
        for(auto it : num | views::reverse){
            if(s >= it and it + rem <= s){
                cur = it;
                break;
            }
        }
        s -= cur;
        a[i] += cur;
    }
    a[n] += s;
    rep(i,1,n){
        cout<<a[i]<<" ";
    }
    cout<<endl;
}
int32_t main() {
#ifdef LOCAL
    FOPEN;
//    FOUT;
#endif
    FASTIO
    rep(i,1,3e5){
        a[i] = i ^ a[i - 1];
    }
    int kase;
    cin>>kase;
    while (kase--)
        invoke(solve);
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s";
    return 0;
}

总结

稳中向好吧，工作还在搞，不过感觉经过两三周的康复训练，今天明显思路快了很多，第一次一眼出D的思路，不过开始的时候还是卡卡的。这个月还得加油才行呢。