CF Goodbye 2022 题解

2023/6/22 C++ 算法竞赛 题解 CodeForce

A-D

A. Koxia and Whiteboards

题面

每次操作都把最小的换掉

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<int,vector<int>,greater<int>>q;
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            q.push(x);
        }
        for(int i=1;i<=m;i++)
        {
            int x;
            cin>>x;
            q.pop();
            q.push(x);
        }
        ll sum=0;
        while(!q.empty())
        {
            sum+=q.top();
            q.pop();
        }
        cout<<sum<<'\n';
    }
    return 0;
}

B. Koxia and Permutation

题面

考虑 这个数，如果 从n这个数开始，那么最小是

可以想到 这样下去是最小的， 始终不超过

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n,k;
        cin>>n>>k;
        int x=1,j=0;
        for(int i=1;i<=n;i++)
        {
            if(!x)
                cout<<j<<' ';
            else
                cout<<n-++j+1<<' ';
            x^=1;
        }
        cout<<'\n';
    }
    return 0;
}

C. Koxia and Number Theory

题面

首先是如果有两个相同的是不可能的，因为这两个相同的数比如 ,

如果对于一个模数 ，在模 的意义下 中所有数都出现超过 次，那么加上的数 无论模 为几，都会有两个数同时被 整除。即若 ，那么

同时模 下只需要计算模 的完全剩余系的出现次数，即只需计算 个数，所以当 时，就不需要考虑了，因为 个数必然填不满模 的完全剩余系

虽然这个条件的充分性还没有证明(不一定能找到对应的 )，但是交了一发过了，那可以不用证了XD

(看了题解发现充分性是因为对所有的 ，可以列出一个同余方程组，由中国剩余定理，解 一定存在)

所以只需要从 到 遍历 ，检查是否会有模 下的完全剩余系内出现次数小于等于1的即可

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
ll a[N];
int cnt[N];
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        bool Flag=false;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            for(int j=1;j<i;j++)
            {
                if(a[i]==a[j])
                {
                    Flag=true;
                    break;
                }
            }
        }
        if(Flag)
        {
            cout<<"NO"<<'\n';
            continue;
        }
        for(int j=2;j<=n;j++)
        {
            memset(cnt,0,sizeof(cnt));
            bool flag=false;
            for(int i=1;i<=n;i++)
                cnt[a[i]%j]++;
            for(int i=0;i<j;i++)
            {
                if(cnt[i]<2)
                {
                    flag=true;
                    break;
                }
            }
            if(!flag)
            {
                Flag=true;
                break;
            }
        }
        if(Flag)
            cout<<"NO"<<'\n';
        else
            cout<<"YES"<<'\n';
    }
    return 0;
}

D. Koxia and Game

题面

首先可以看出Mahiru不可能去选 ，因为 是我们构造的，而我们构造的 要让Koxia赢，而如果积极游戏的Mahiru选了我们给的 ，说明我们给的 对Mahiru有帮助，所以我们肯定不能这么选

所以Mahiru相当于只能从 中选一个

而构造合适的 可以操纵Mahiru的选择，比如构造 ，再拿走 ，那么相当于Mahiru只能选择

现在只需要考虑所有的 能否构成一个排列，如果不能，那么无论怎么给 都没用，如果有用，那么我们才能计数

这里尝试去写dfs，但是烂掉了，于是看了看题解..

发现题解的思路很巧妙

题解

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N],b[N];
int fa[N];
int cnt_v[N],cnt_e[N],selfloop[N];
bool vis[N];
const int mod=998244353;
void init(int n)
{
    for(int i=1;i<=n;i++)
        fa[i]=i;
    fill(cnt_v+1,cnt_v+1+n,1);
    fill(cnt_e+1,cnt_e+1+n,0);
    fill(selfloop+1,selfloop+1+n,0);
    fill(vis+1,vis+1+n,false);
}
int find(int x)
{
    return x==fa[x]?fa[x]:fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    x=find(x);y=find(y);
    if(x==y)
        return;
    cnt_v[y]+=cnt_v[x];
    cnt_e[y]+=cnt_e[x];
    selfloop[y]|=selfloop[x];
    fa[x]=y;
}
int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            cin>>b[i];
        init(n);
        for(int i=1;i<=n;i++)
        {
            merge(a[i],b[i]);
            cnt_e[find(a[i])]++;
            if(a[i]==b[i])
                selfloop[find(a[i])]=1;
        }
        ll ans=1;
        bool flag=false;
        for(int i=1;i<=n;i++)
        {
            int x=find(i);
            if(!vis[x])
            {
                vis[x]=true;
                if(cnt_e[x]!=cnt_v[x])
                {
                    flag=true;
                    break;
                }
                if(selfloop[x])
                    ans=(ans*n)%mod;
                else
                    ans=(ans*2)%mod;
            }
        }
        if(flag)
            cout<<0<<'\n';
        else
            cout<<ans<<'\n';
    }
    return 0;
}
img_show