牛客周赛 Round 29 (A-E , c++)

比赛地址 :

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

A:小红大战小紫

思路 :?

那个数大就那个赢，相等就是平局；

代码 :?

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;cin >>a>>b;
    if(a>b) cout << "kou";
    else if(a==b) cout <<"draw";
    else cout << "yukari";
}

B.小红的白日梦

思路 :?

直接模拟即可 ， 按照题目意思 ;

代码:

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;

using namespace std;

inline void solve(){
    int n ; cin >> n;
    string a,b;cin >>a>>b;
    int t = 0 ;
    for(int i=0;i<n;i++){
        if(a[i]=='Y'){
            t+=2;
            if(b[i]=='Y') t+=1;
        }
        else{
            if(b[i]=='Y') t+=2;
        }
    }
    cout << t <<endl;
}
 
signed main()
{
    IOS
    int _ = 1;
    // cin >> _;
    while(_ --) solve();
    return 0;
}

C.小红的小小红

思路 :?

模拟题，先把"xiaohong"输出，然后把s中剩余字符输出 ;

代码 :?

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;

using namespace std;

int get(char c){
    return (int)(c-'a');
}

inline void solve(){
    string s ; cin >> s ;
    cout << "xiaohong" ;
    int cnt[26] = {0} ;
    for(int i=0;i<26;i++){
        cnt[i] = 0 ;
    }
    for(char c : s){
        cnt[get(c)]++;
    }
    cnt[get('x')]--;
    cnt[get('i')]--;
    cnt[get('a')]--;
    cnt[get('o')]-=2;
    cnt[get('h')]--;
    cnt[get('n')]--;
    cnt[get('g')]--;
    for(int i=0;i<26;i++){
        int x = cnt[i];
        if(x>0){
            while(x--){
                cout<<(char)(i+'a');
            }
        }
    }
}
 
signed main()
{
    IOS
    int _ = 1;
    // cin >> _;
    while(_ --) solve();
    return 0;
}

D.小红的中位数

思路 :

直接模拟，根据数列长度奇偶性 ， 和? 要删除的位置模拟 ；

( n 表示数组的长度 )

如果n为奇数 :

????????如果i在左半区，选中间和偏右的平均值作为中位数;

????????在中间，那选左边和右边两个数的平均值作为中位数

? ? ? ? 在右边,选中间和偏左的平均值作为中位数;

? n为偶数，依次类推 ;

详情请看代码 ;

代码 :?

#include <iostream>
#include <string>
#include<iomanip>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;


int main() {
    int n;
    double a[100001],pre[100001];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        pre[i]=a[i];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++){
        if(n%2==0){
            if(pre[i]<=a[n/2-1]) printf("%.1f\n",a[n/2]) ;
            else if(pre[i]>=a[n/2])printf("%.1f\n",a[n/2-1]);
        }
        else{
            if(pre[i]==a[n/2])printf("%.1f\n",(a[n/2-1]+a[n/2+1])/2);
            else if(pre[i]>a[n/2])printf("%.1f\n",(a[n/2-1]+a[n/2])/2);
            else if(pre[i]<a[n/2])printf("%.1f\n",(a[n/2]+a[n/2+1])/2);
        }
    }
    return 0;
}

E.小红构造数组

思路 :?

显而易见，先要做的就是分解质因数 ；

然后求出出现次数最多的数的次数(用ma表示,n表示质因数的总个数) ,如果ma > (n+1)/2的话，那么就不能够构造出相邻且不相等的序列了 ；

按照出现次数从大到小排序，对于构造序列，分奇偶位置存放质因数，由于奇数坐标个数总是大于偶数坐标个数(从1开始)，那么可以先从奇数坐标开始放，然后放偶数坐标，先放大的，再放小的；

具体实现请看代码 ;

其它例题推荐 :?

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

代码 :?

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define lowbit(x) (x&(-x))
#define sz(a) (int)a.size()
#define pb push_back
#define all(a) a.begin(), a.end()
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;

int max(int a ,int b){
    return a > b ? a : b ;
}

bool cmp (const pair<int, int>& a, const pair<int, int>& b) {
    return a.second > b.second; // 按照频率从大到小排序
}

inline void solve(){
	int x ; cin >> x ; 
    if(x==1){
        cout << -1 << endl;
        return ;
    }
	map<int,int> mp ;
    int ma = 0 ;
    int n = 0 ; // 质因数 个数
	for (int i = 2; i <= x / i; i ++ )
		if (x % i == 0){
				int s = 0;
				while (x % i == 0) x /= i, s ++ ;
				mp[i] = s ;
                ma = max(ma , mp[i]) ;
                n += mp[i] ;
			}
	if (x > 1){
        mp[x]++;
        n ++ ;
    }
    ma = max(ma , mp[x]) ;
    if(ma > (n+1)/2) {
        cout << -1 << endl ;
        return ;
    }
    vector<pair<int , int>> vc(mp.begin(),mp.end());
    vector<int> ans(n,0);
    sort(vc.begin(),vc.end(),cmp);//将次数从大到小排序
    int idx = 0 ; // 先奇数
    for(int i=0;i<vc.size();i++){
        while(vc[i].second--){
            ans[idx] = vc[i].first ;
            idx += 2 ;
            if(idx >= n) idx = 1 ;
        }
    }
    cout << n << endl;
    for(int i=0;i<n;i++){
        cout << ans[i] << " ";
    }
    return ;
}
 
signed main()
{
    IOS
    int _ = 1;
    // cin >> _;
    while(_ --) solve();
    return 0;
}

F.小红又战小紫

博弈题