首页 > 其他分享 >Codeforces 732 Div2 A-D题解

Codeforces 732 Div2 A-D题解

时间：2023-01-15 04:33:53浏览次数：50  
标签：int 题解 rep Codeforces long 732 str ll define

感觉做过这场啊，要不就是看过

A题 AquaMoon and Two Arrays

问前加后减能不能把A变成B，首先这个貌似是经典老题了，无论怎么操作数列总和不变，如果和不相同，变不了，其他情况暴力判断即可

#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (2000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#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].nxt)
#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;
}
constexpr ll mod = 1e9 + 7;
ll quick_pow(ll base, ll expo){
    ll ans = 1;
    while(expo){
        if(expo & 1) ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans;
}
int n,m;
int a[limit];
int b[limit];
void solve(){
    cin>>n;
    rep(i,1,n) cin>>a[i];
    rep(i,1,n) cin>>b[i];
    vector<pi(int, int)>p;
    int sum1 = accumulate(a + 1, a + n + 1, 0);
    int sum2 = accumulate(b + 1, b + n + 1, 0);
    if(sum1 != sum2){
        cout<<-1<<endl;
        return;
    }
    int tot = 0;
    rep(i,1,n){
        tot += abs(a[i] - b[i]);
        a[i] -= b[i];
    }
    rep(i,1, tot / 2){
        int fst,scd;
        rep(j,1, n){
            if(a[j] > 0){
                a[j]--;
                fst = j;
                break;
            }
        }
        per(j,1, n){
            if(a[j] < 0){
                a[j]++;
                scd = j;
                break;
            }
        }
        p.push_back({fst, scd});
    }
    cout<<p.size()<<endl;
    for(auto && [k, v] : p){
        cout<<k<<' '<<v<<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\n";
    return 0;
}
AC Code

B题 AquaMoon and Stolen String

这题是给n个string，n为奇数，两两配对，其中一些相同index字母互相交换，给出n-1个交换之后的结果，其中有一个不参与配对，问这个string是什么

这。。。绕了半天，让我想起来了矩阵内每个东西出现两遍，有一个出现一遍。char本质也是int，好，异或！

#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (2000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#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].nxt)
#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;
}
constexpr ll mod = 1e9 + 7;
ll quick_pow(ll base, ll expo){
    ll ans = 1;
    while(expo){
        if(expo & 1) ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans;
}
int n,m;
int a[limit];
string str[limit];
void solve(){
    cin>>n>>m;
    rep(i,1,m){
        a[i] = 0;
    }
    rep(i,1,n){
        cin>>str[i];
        str[i] = " " + str[i];
        rep(j,1,m){
            a[j] ^= str[i][j] - 'a';
        }
    }
    rep(i,1, (n - 1) ){
        cin>>str[i + n];
        str[i + n] = " " + str[i + n];
        rep(j,1,m){
            a[j] ^= str[i + n][j] - 'a';
        }
    }
    rep(i,1,m){
        cout<<(char)(a[i] + 'a');
    }
    cout<<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\n";
    return 0;
}
AC Code

C题 AquaMoon and Strange Sort

这题是给一个序列，然后我们可以两两交换，初始位置上全是1，那么每次交换只能交换相邻的，把交换过后的0变成1，1变成0，问有没有办法把序列排序，然后所有位置上还是1

这道题冒泡排序，首先想到了逆序对数量。后来发现没卵用啊，假如我们出现了2 2 2 2 1 1 1，逆序对怎么知道我们可以交换几次呢？毕竟同一值内部还是可以交换的，显然逆序对没有考虑到这种情况。

然后我们手动模拟下，比如3 2 1

第一次交换 之后是 

3 2 1

1 1 1

3 1 2

1 0 0

1 3 2

1 0 0

1 2 3

1 1 1

那么我们再来看看

3 1 2

1 1 1

1 3 2

0 0 1

我们多模拟几组数据，可以发现，当我们距离目标位置距离是偶数的时候，路径上所有的不相干的位置都不受影响，否则奇偶性将发生改变。

那也就意味着，奇数位置的东西，最后在升序序列中，必须也在奇数位置上，偶数亦然。

所以我们只需要统计下奇数位置上和偶数位置上同元素分别出现的次数好了，有区别则说明一定不可行

#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (2000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#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].nxt)
#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;
}
constexpr ll mod = 1e9 + 7;
ll quick_pow(ll base, ll expo){
    ll ans = 1;
    while(expo){
        if(expo & 1) ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans;
}
int n,m;
int a[limit];
//mergesort get inversions
int tree[limit];
void add(int pos, int val){
    while(pos <= n){
        tree[pos] += val;
        pos += lowbit(pos);
    }
}
int query(int pos){
    int ans = 0;
    while(pos){
        ans += tree[pos];
        pos -= lowbit(pos);
    }
    return ans;
}
int b[limit];
int c[limit];
void solve(){
    cin>>n;
    rep(i,1,n) cin>>a[i],b[i] = a[i], tree[i] = 0;
    sort(b + 1,b + 1 +  n);
    map<int, int>mp[2];
    rep(i,1,n){
        mp[0][b[i]] += (i & 1);
    }
    rep(i,1,n){
        mp[1][a[i]] += (i & 1);
    }
    for(auto[k, v] : mp[0]){
        if(v != mp[1][k]){
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<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\n";
    return 0;
}
AC Code

D.  AquaMoon and Chess

这题是给一个01串，对于所有的当前为1的位置，只要i + 1也为1，那么可以走到i + 2

同样，只要i - 1为1，那么i - 2也可以走到，问有多少种走法

本身看上去像是环和并查集的题，我还以为又是个带权并查集，但是看了半天似乎不是

因为给出题目要求，我们发现一组11是可以走到任何地方去的，所以我们只需要统计所有的11数量，然后所有的0数量，这样的话就变成了一个隔板法模板题

总数为11总数 + 0的总数选11总数个位置

为什么是11个啊，明明算两个，因为对于每个位置，比如011和110，第二位都是合法的，所以要/2

#include <bits/stdc++.h>
using namespace std;
constexpr int limit =  (2000000 + 5);//防止溢出
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f
#define lowbit(i) i&(-i)//一步两步
#define EPS 1e-9
#define FASTIO  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ff(a) printf("%d\n",a );
#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].nxt)
#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;
}
constexpr ll mod = MOD;
ll quick_pow(ll base, ll expo){
    ll ans = 1;
    while(expo){
        if(expo & 1) ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans;
}
ll inv(ll x){
    return quick_pow(x, mod - 2);
}
ll C(ll n, ll m){
    ll ans = 1;
    for(ll i = 1; i <= m; i++){
        ans = ans * (n - i + 1) % mod;
        ans = ans * inv(i) % mod;
    }
    return ans;
}
int n,m;
int a[limit];
int fa[limit];
int sizes[limit];
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y){
    int fx = find(x);
    int fy = find(y);
    if(fx == fy) return;
    fa[fx] = fy;
    sizes[fy] += sizes[fx];
}
#define int ll
void solve(){
    cin>>n;
    string str;
    cin>>str;
    str = " " + str;
    //如果碰到11对的话，应该是可以把所有的地方走完的
    rep(i,1,n){
        a[i] = str[i] - '0';
    }
    rep(i,1,n){
        fa[i] = i;
        sizes[i] = 1;
    }
    int tot = 0;
    int zero = 0;
    vector<pi(int, int)> v;
    rep(i,1,n){
        if(v.empty() or v.back().first != a[i]){
            v.push_back({a[i], 1});
        }else{
            v.back().second++;
        }
    }
    for(auto [k, val] : v){
        k == 1 ? tot += val / 2 : zero += val;
    }
    ll ans = C(zero + tot, tot);
    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\n";
    return 0;
}
AC Code

 

标签：int,题解,rep,Codeforces,long,732,str,ll,define
From： https://www.cnblogs.com/tiany7/p/17053016.html

相关文章

  • ARC153 ABC 题解
    A【题意】给定\(N\)，求第\(N\)个满足以下条件的数：它是一个\(9\)位数，没有前导\(0\)。它的第一位等于它的第二位。它的第五位等于它的第六位。它的第七位等于它......
  • XMU 2023.1.14 题解汇总
    A、CF1779A原题B、https://www.cnblogs.com/wondering-world/p/17038860.htmlC、https://www.luogu.com.cn/problem/solution/P4305D、快速幂模板点击查看代码#incl......
  • Educational Codeforces Round 119 (Rated for Div. 2)
    EducationalCodeforcesRound119(RatedforDiv.2)我真是越来越菜了，现在竟然连a都做不出来了，o(╥﹏╥)oAA这个题是对于每一个ai和ai+1,（an和a1)都有一个判断，判断这两......
  • Codeforces Round #843 (Div. 2)
    C.InterestingSequence(二进制)题目大意给定两个大于等于0的数\(n,\x\)，求满足\(n\&(n+1)\&(n+2)\cdotsm=x\)的最小\(m\)，若不存在输出-1。解题思路首先若\(n<x\)肯......
  • DTOJ-2023-01-02-测试-题解
    （2023省选模拟Round#4）之前感冒了一阵子，错过了两场省选模拟，不过我不打算补（乐成绩：0+42+0（就是说T1写挂了）A题目链接题目大意小\(\omega\)最近学习了分治\(\text{......
  • Educational Codeforces Round 108 (D记忆化搜索)
    D.MaximumSumofProducts题目大意：给定两个长度为n(n<=5000)的整型数组a,b可以对数组a进行至多一次以下操作：选择l,r并对l到r进行翻转求\(\sum\)a\(_i\)*b\(_i\)的......
  • Codeforces Round #839 F
    F.CopyofaCopyofaCopy题链我们发现这个操作是将中间不一样周围四个一样的形如1010101010变成全部都一样的显然这样变之后是不可还原的就是说这......
  • 【题解】P4565 [CTSC2018]暴力写挂
    能写点分为什么要写这种玄学东西。思路边分树合并。首先考虑点分，发现只会T飞的做法。但是答案的形式有点意思，换一下写法：\(ans=\frac{1}{2}\max(\operatorname{dis......
  • Codeforces Round #843 (Div. 2) A1A2BCE(D待补)
    url:Dashboard-CodeforcesRound#843(Div.2)-CodeforcesA1&&A2.GardenerandtheCapybaras题意:给你一个只由$a$和$b$两个字符组成的字符串现在要你把这个字......
  • Codeforces Round #834 (Div. 3) D. Make It Round（贪心/数论）
    https://codeforces.com/contest/1759/problem/D题目大意：给定一个数字n，要求扩大至多m倍，求最大的并且最多0的数字。input106115431354161005012345264......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99