个人技术分享

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;
}