Codeforces Round 941 (Div. 2)(A-D)

补题

2301_80299496

804人浏览 · 2025-03-07 15:37:13

2301_80299496 · 2025-03-07 15:37:13 发布

题目链接：Dashboard - Codeforces Round 941 (Div. 2) - Codeforces

A. Card Exchange

思路

只要数出现次数有大于k的数，那么我们就可以把数变到k-1，没有那就只能是n

代码

void solve(){
    int n,k;
    cin>>n>>k;
    vi a(n+10);
    map<int,int> mp;
    int mx=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]]++;
        mx=max(mx,mp[a[i]]);
    }
    if(mx>=k){
        cout<<k-1<<"\n";
    }else{
        cout<<n<<"\n";
    }
}

B. Rectangle Filling

思路

很明显如果四个角的两个对角如果有相同的那么就一定能转成一个颜色，剩下的就剩以下四种情况：

1.B....W 2.W....B 3.B....B 4.W....W

........ ........ ....... .........

B......W W....B W.....W B....B

可以发现如果在两个相同字符之间出现一个不同的就可以将这个角上的字符转换颜色，然后使之对角的字符相同，进而转成一个颜色

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

void solve(){
    int n,m;
    cin>>n>>m;
    string s[n+1];
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]=" "+s[i];
    }
    if((s[1][1]==s[n][m])||(s[1][m]==s[n][1])){
        cout<<"YES\n";return;
    }
    
    if(s[1][1]==s[1][m]){
        for(int i=2;i<m;i++){
            if(s[1][i]!=s[1][1]){
                cout<<"YES\n";return;
            }
        }
        for(int i=2;i<m;i++){
            if(s[n][i]==s[1][1]){
                cout<<"YES\n";return;
            }
        }
    }

    if(s[1][1]==s[n][1]){
        for(int i=2;i<n;i++){
            if(s[i][1]!=s[1][1]){
                cout<<"YES\n";return;
            }
        }
        for(int i=2;i<n;i++){
            if(s[i][m]==s[1][1]){
                cout<<"YES\n";return;
            }
        }
    }

    cout<<"NO\n";
}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

C. Everything Nim

思路

感觉来说是个贪心+博弈，首先肯定先进行排序我们从小到大来进行游戏

首先A先手，我们让A把当前最小的数取到只剩下1，下一次B只能取1，那么A便会在取下一个数时占先手，显而易见会有特殊情况就是有连续的几个数相差为1时A不能这么取，如果这么取的话就会让B在接下来的数中取到先手

例如 3 4 5 100 A这么取的话A也能先手取100那么A就会赢

如果 3 4 5 6 100 这么取的话就会让B先手取100，那么B就会赢，假如A先手把3全拿走，那么取100时A还是先手，那么A还是可以赢

综上的分析来看，先手一定会赢，只有在开始时出现1 2 3 4.... A无法进行操作，最后将先手转换成了B这样B才会胜出

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

void solve(){
    int n;cin>>n;
    vi a(n+1);
    map<int,bool> mp;
    vi b;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!mp[a[i]]){
            mp[a[i]]=true;
            b.push_back(a[i]);
        }
    }
    sort(b.begin(),b.end());
    if(b[0]==1){
        int ct=0;
        for(int i=0;i<b.size();i++){
            if(b[i]!=i+1) break;
            ct++;
        }
        if(ct==b.size()){
            if(ct%2){
                cout<<"Alice\n";
            }else{
                cout<<"Bob\n";
            }
        }else{
            if(ct%2){
                cout<<"Bob\n";
            }else{
                cout<<"Alice\n";
            }
        }
        
    }else{
        cout<<"Alice\n";
    }
    
}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}

D. Missing Subsequence Sum

思路

这道题倒是比较吃做题的经验

首先我们观察数据范围发现要用最多25个数构造1e6，那么 $2^{20}\approx 1e6$ 那么我们就能用二进制思想来构造，解决了如何构造1~n的数之后我们再看剩下的条件，

要求不能构造出k，那我们就构造出 $[1,k-1]$ 和 $[k+1,n]$

我们用p表示二进制下k的最高位1的位置

1. $[1,k-1]$

按照上面方法我们先构造出 $[1,2^{p}-1]$

然后再加上 $k-2^{p}$ 这个数 ( $(2^{p}-1)+(k-2^{p})=k-1$ ) 这样我们就能使能构造的范围为 $[1,k-1]$

2. $[k+1,n]$

我们配合上先前构造的 $[1,k-1]$ 的数，再加上 $k+1$ 我们就能再构造出 $[k+1,2*k]$ 的数，再把除了 $2^{p}$ 之外的 $2^{i}$ 加进去，然后观察发现我们有一类数是不能构造的就是 $2^{p}+k+1$ ，我们将这个数加进去即可

代码

#include<bits/stdc++.h>
using namespace std;

#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;

const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;

void solve(){
    int n,k;
    cin>>n>>k;
    int p=31-__builtin_clz(k);

    vi ans;
    ans.push_back(k-(1ll<<p));
    ans.push_back(k+1);
    ans.push_back(k+1+(1ll<<p));

    for(int i=0;i<=20;i++){
        if(i!=p)
        ans.push_back((1ll<<i));
    }

    cout<<ans.size()<<"\n";
    for(auto x:ans){
        cout<<x<<" ";
    }
    cout<<"\n";

}
signed main() {
    vcoistnt
    cout<<fixed<<setprecision(2);
    int _=1;
    cin>>_;
    while(_--) solve();
    return 0;
}