牛客小白月赛88 (A~E)

A

题目要求投喂可口值超过 且总零食不超过 ,贪心的喂 个可口值最大的

int x, n, mx=0;
char res;
void solve(){
    cin >> x >> n;
    for(int i = 1; i <= n; i ++){
        char a;
        int b;
        cin >> a >> b;
        if(b > mx){
            mx = b;
            res = a;
        }
    }
    for(int i = 1; i <= 1000; i ++){
        cout << res;
    }
}

B

与门中有 , 或门中有 , 剩下的是非门

#include<bits/stdc++.h>
using namespace std;
#define int long long
string a[5];
void solve() {
    for(int i = 0; i < 5; i++){
        getline(cin, a[i]);
    }
    if(a[2].find("&") != string::npos){
        int x = a[1][0] - '0';
        int y = a[3][0] - '0';
        cout << (x&y);
    }
    else if(a[2].find(">") != string::npos){
        int x = a[1][0] - '0';
        int y = a[3][0] - '0';
        cout << (x|y);
    }
    else{
        int x = a[2][0] - '0';
        cout << (!x);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T --) {
        solve();
    }

    return 0;
}

C

根据题意模拟，用 去重

int n;
int judge[3] = {1, 3, 5};
set<pair<int, int> > res;
void solve() {
    cin >> n;
    for(int i = 1; i <= n; i ++){
        int x, y;
        cin >> x >> y;
        for(int i = 0; i < 3; i ++){
            int tx = x, ty = y;
            if(y < judge[i]){
                ty += 60;
                tx --;
            }
            res.insert({tx, ty - judge[i]});
        }
    }
    cout << res.size() << '\n';
    for(auto [x, y] : res){
        cout << x << ' ' << y << '\n';
    }
}

D

我们用 表示第 个数是否能到达

每次用 数组记录从 可以向 转移哪些数字, 然后用 更新

int n, m;
int a[5100];
void solve(){
    cin >> n >> m;
    vector<int> dp(n);
    for(int i = 1; i <= m; i ++){
        cin >> a[i];
    }
    dp[0] = 1;
    for(int i = 1; i <= m; i ++){
        vector<int> tmp(n);
        a[i] %= n;
        for(int j = 0; j < n; j ++){
            if(dp[j] == 1){
                tmp[(j + a[i]) % n] = 1;
                tmp[(j - a[i] + n) % n] = 1;
            }
        }
        dp.swap(tmp);
    }
    cout << (dp[0] == 1 ? "YES" : "NO") << '\n';
}

E

并查集维护 , 祖宗节点表示原数组 应该变为 , 维护的是位置信息

维护某个数 的位置, 且通过并查集保证 唯一 (具体见代码)

那么 就表示 应该变成的数

int n, m;
int find(int x, vector<int> &p){
    if(x != p[x]) p[x] = find(p[x], p);
    return p[x];
}
void solve(){
    cin >> n >> m;
    vector<int> p(n), w(n);
    map<int, int> mp;
    iota(p.begin(), p.end(), 0); // 初始化并查集 
    for(int i = 0; i < n; i ++){
        cin >> w[i];
        if(mp.count(w[i]) == true){
            int pi = find(mp[w[i]], p);
            p[i] = pi; // 重复的数应该变为之前的数 
        }
        mp[w[i]] = i;
    }
    for(int i = 0; i < m; i ++){
        int x, y;
        cin >> x >> y;
        if(x == y || mp.count(x) == false){
            continue;
        }
        if(mp.count(y) == true){
            int px = find(mp[x], p);
            int py = find(mp[y], p);
            p[px] = py;
            mp.erase(x);
        }
        else{ // y 不存在 
            int px = find(mp[x], p); // 注意此时, w[px] = x
            w[px] = y; 
            mp[y] = px;
            mp.erase(x);
        }
    }
    for(int i = 0; i < n; i ++){
        cout << w[find(i, p)] << " \n"[i==n-1];
    }
}

• iota(st, ed, x) 表示将 分别赋值为

参考代码 : @ https://ac.nowcoder.com/acm/contest/profile/268088354