码蹄杯 2024 初赛第一场

在这里插入图片描述

MC0301

求个最大值

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

int n;

void solve(){
    cin >> n;
    int mx = -1;
    for(int i = 0;i < n;i ++){
        int x; cin >> x;
        mx = max(mx,x);
    }
    cout << mx << endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}

MC0302

sort一下

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

int n;

void solve(){
    vector<int> a(3);
    for(int i = 0;i < 3;i ++) cin >> a[i];
    sort(a.begin(),a.end());
    for(int i = 0;i < 3;i ++) cout << a[i] << " "; 
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}

MC0303

看一下范围内有多少质数

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 7;
int n;
int st[N]; 

int get_prime(){
    int cnt = 0;
    for(int i = 2;i <= n;i ++){
        if(st[i]) continue;
        cnt ++;
        for(int j = i + i;j <= n;j += i) st[j] = 1; 
    }
    return cnt;
}

void solve(){
    cin >> n;
    cout << get_prime() << endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}

MC0304

二分答案然后check里去将每个 $a_i$ 减去二分的答案看长度 $f - n$ 的区间和
大于零更新 l 小于零更新 r

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 7;
int n,f;
int a[N];

int check(double x){
    vector<double> b(n + 1);
    for(int i = 1;i <= n;i ++) b[i] = a[i] - x;
    vector<double> pre(n + 1);
    for(int i = 1;i <= n;i ++) pre[i] = pre[i - 1] + b[i];
    double mn = 1e18;
    for(int i = f;i <= n;i ++){
        mn = min(mn,pre[i - f]);
        if(pre[i] - mn >= 0) return 1; 
    }
    return 0;
}

void solve(){
    cin >> n >> f;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    double l = 1,r = 2000;
    while(r - l > 1e-6){
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid; 
    }
    cout << floor(r * 1000) << endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}

MC0305

模拟一下排名

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 7;
int n;
int a[N];

void solve(){
    cin >> n;
    for(int i = 0;i < n;i ++) cin >> a[i];
    sort(a,a + n,greater<int>());
    map<int,int> mp;
    int pos = 1;
    for(int i = 0;i < n;i ++){
        if(!mp[a[i]]) mp[a[i]] = pos ++;
        else pos ++;
    }
    int x; cin >> x;
    cout << mp[x] << endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}

MC0306

转化一下类型即可

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 7;
int n;
int a[N];

void solve(){
    char x; cin >> x;
    cout << (int)x << endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}

MC0307

存一下路径跑一遍bfs即可

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e6 + 7;
vector<int> g[N];
int n,x,y;

int bfs(){
    queue<int> q;
    q.push(x);
    vector<int> st(n + 1);
    vector<int> d(n + 1,1e9);
    d[x] = 0;
    st[x] = 1;
    while(q.size()){
        int t = q.front();
        q.pop();
        for(auto root : g[t]){
            if(st[root]) continue;
            d[root] = min(d[t] + 1,d[root]);
            if(root == y) return d[y];
            q.push(root);
            st[root] = 1;  
        }
    }
    return -1;
}

void solve(){
    cin >> n >> x >> y;
    for(int i = 1;i <= n;i ++){
        int len; cin >> len;
        int u = i;
        int v1 = i + len,v2 = i - len;
        if(v1 <= n) g[u].push_back(v1);
        if(v2 >= 1) g[u].push_back(v2); 
    }
    cout << bfs();
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}

MC0308

统计一遍大写字符

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

void solve(){
    string s; getline(cin,s);
    int ans = 0;
    for(int i = 0;i < s.size();i ++){
        if(s[i] >= 'A' && s[i] <= 'Z') ans ++;
    }
    cout << ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}

MC0309

拆位统计每位的个数
然后分别算一下按位与和按位或的贡献

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 7;
int a[N];
int n;

void solve(){
    cin >> n;
    for(int i = 0;i < n;i ++) cin >> a[i];
    map<int,int> mp;
    int ans = 0;
    for(int i = 0;i < n;i ++) ans += a[i];
    for(int i = 0;i < 32;i ++){
        for(int j = 0;j < n;j ++){
            int cnt = a[j] >> i;
            if(cnt & 1) mp[i] ++;
        }
        ans += mp[i] * (n - 1 + n - mp[i]) / 2 * ((int)1 << i);
        if(mp[i] > 1) ans += mp[i] * (mp[i] - 1) / 2 * ((int)1 << i);
    }
    cout << ans << endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}

MC0310

reverse一下

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 7;
int a[N];
int n;

void solve(){
    string s; cin >> s;
    reverse(s.begin(),s.end());
    cout << s;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}

MC0311

模拟

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

void solve(){
    map<int,int> mp;
    int space = 0;
    for(int i = 0;i < 8;i ++){
        int x; cin >> x;
        mp[x] ++;
        if(mp[x] == 3){
            space += 2;
            mp[x] = 0;
            mp[x * 10] ++;
        }
    }
    int n; cin >> n;
    for(int i = 0;i < n;i ++){
        int x; cin >> x;
        if(mp[x] == 2){
            mp[x] = 0;
            mp[x * 10] ++;
            space += 1;
            if(mp[x * 10] == 3){
                mp[x * 10] = 0;
                mp[x * 100] ++;
                space += 1;
                if(mp[x * 100] == 3){
                    mp[x * 100] = 0;
                    mp[x * 1000] ++;
                    space += 1;
                }
            }
        } else if(space){
            mp[x] ++;
            space --;
        }
    }
    int op; cin >> op;
    if(mp.rbegin()->first >= op) cout << "YES YES YES";
    else cout << "NO NO NO";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}

MC0312

直接erase 或者更新删除位置开始以后的数组的值为他之后的值复杂度也是可以的

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

int n,m; 

void solve(){
    cin >> n;
    vector<int> a;
    for(int i = 1;i <= n;i ++){
        int x; cin >> x;
        a.push_back(x); 
    }
    cin >> m;
    for(int i = 1;i <= m;i ++){
        int pos; cin >> pos;
        a.erase(a.begin() + pos - 1);
    }
    for(auto x : a) cout << x << " ";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}

MC0313

暴力枚举

code:

#include<bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int N = 1e5 + 7; 
int n,m; 
int a[N];

void solve(){
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    a[n + 1] = a[1],a[n + 2] = a[2],a[n + 3] = a[3];
    int pos = 0,sum = 0;
    int mx = -1;
    for(int i = 1;i <= n;i ++){
        sum = a[i] + a[i + 1] + a[i + 2] + a[i + 3];
        if(sum > mx) mx = sum,pos = i;
    }
    cout << mx << endl << pos << endl; 
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int _ = 1; 
    while(_ --){
        solve();
    }
    return 0;
}