JZTXT

10.5 Codeforces Round 638 (Div. 2)

发布时间 2023-10-05 19:29:00作者: bible_w

Codeforces Round 638 (Div. 2)

A - Phoenix and Balance

思路：加的数成等比关系，且第n项大于前n-1项的和，那么最大的一项加上最小的几个即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[110];
deque<int>q;

int32_t main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int d=n/2;
        int ans=2;
        int sum1=0,sum2=0;
        for(int i=1;i<=n;i++){
            if(i<=d-1||i==n){
                sum1+=ans;
            }
            else{
                sum2+=ans;
            }
            ans*=2;
        }
        cout<<abs(sum1-sum2)<<endl;
    }
    return 0;
}
View Code

 

 B - Phoenix and Beauty

思路：可以发现有循环节的数列，且k恰好是循环节的长度一定是成立的

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[110];
deque<int>q;

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        set<int>s;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            s.insert(a[i]);
        }
        if(s.size()>k){
            cout<<"-1\n";
            continue;
        }
        for(int i=1;;i++){

            if(s.size()==k)
                break;
            s.insert(i);
        }
        cout<<n*k<<"\n";
        for(int i=1;i<=n;i++){
            for(auto e:s)
                cout<<e<<" ";
        }
        cout<<"\n";
    }
    return 0;
}
View Code

 

C - Phoenix and Distribution

思路：将原串排序后，若s[k-1]不等于s[0]，那么答案为s[k-1]，否则，若之后的字符都相等，那均分成k份，s[0]加上最多的那份为答案，否则将之后的所有字符都加在s[0]后为答案；

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n,k;string s;
    cin>>n>>k>>s;
    sort(s.begin(),s.end());
    if(s[0]!=s[k-1]){
        cout<<s[k-1]<<'\n';
    }else{
        if(s[n-1]!=s[k]){
            string ans=s.substr(k-1);
            cout<<ans<<'\n';
        }else{
            int c=(n-1)/k;
            string ans;ans.push_back(s[0]);
            while(c--)ans.push_back(s[n-1]);
            cout<<ans<<'\n';
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

D - Phoenix and Science

思路：由于要尽可能少的天数，贪心地分裂更多的细胞，每天细胞数为2、4、8...，若最后还剩下细胞为x个，那么可以在某一天后通过增加一天的分裂来得到x（可以发现是一定可以的）；那么将所有天数排序后的差分即为每天分裂的细胞数。

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e3+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve(){
    int n;cin>>n;
    vector<int>ans;
    for(int i=1;i<=n;i*=2){
        ans.push_back(i);
        n-=i;
    }
    if(n)ans.push_back(n);
    sort(ans.begin(),ans.end());
    cout<<ans.size()-1<<'\n';
    for(int i=1;i<ans.size();++i)cout<<ans[i]-ans[i-1]<<' ';cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code