牛客小白月赛30 题解

A.黑白边

类似于最小生成树Kruscal算法的思想，用并查集维护当前的连通块直到放入 $n - 1$ 条边则实现了两两联通，因为要白边最少，排个序就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
struct Edge {
    int u, v, w;
    bool operator < (const Edge &s) const {
        return w < s.w;
    }
}edge[N << 1];
int F[N];
int findz(int x) {
    return F[x] = F[x] == x ? x : findz(F[x]);
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= m; i++)    {
        cin >> edge[i].u >> edge[i].v >> edge[i].w;
    }
    sort(edge + 1, edge + 1 + m);
    bool flag = 0;
    for(int i = 1; i <= n; i++) {
        F[i] = i;
    }
    int ans = 0, cnt = 0;
    for(int i = 1; i <= m; i++) {
        int u = edge[i].u, v = edge[i].v;
        int fx = findz(u), fy = findz(v);
        if(fx != fy) {
            F[fx] = fy;
            cnt++;
            if(edge[i].w) ans++;
        }
        if(cnt == n - 1) break;
    }
    if(cnt != n - 1) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}

B. 最好的宝石

太久没写线段树忘了

update: 线段树模板题，多加一个mc表示最大值的个数，然后合并的过程中判断左右子区间的最大值是否相同搞一搞就行了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
typedef long long ll;
struct node {
  int l, r, maxz, mc;
}t[N << 2];
void push_up(int rt) {
  if(t[rt].l == t[rt].r) return ;
  t[rt].maxz = max(t[rt << 1].maxz, t[rt << 1 | 1].maxz);
  t[rt].mc = 0;
  if(t[rt].maxz == t[rt << 1].maxz) {
    t[rt].mc += t[rt << 1].mc;
  }
  if(t[rt].maxz == t[rt << 1 | 1].maxz) {
    t[rt].mc += t[rt << 1 | 1].mc;
  }
}
void build(int rt, int l, int r) {
  t[rt].l = l, t[rt].r = r;
  if(l == r) {
    cin >> t[rt].maxz;
    t[rt].mc = 1;
    return ;
  }
  int mid = l + r >> 1;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid + 1, r);
  push_up(rt);
}
void update(int rt, int x, int y) {
  if(t[rt].l == t[rt].r) {
    t[rt].maxz = y;
    return ;
  }
  int mid = t[rt].l + t[rt].r >> 1;
  if(x <= mid) {
    update(rt << 1, x, y);
  } else {
    update(rt << 1 | 1, x, y);
  }
  push_up(rt);
}
pair<int, int> query(int rt, int ql, int qr) {
  if(ql <= t[rt].l && qr >= t[rt].r) {
    return make_pair(t[rt].maxz, t[rt].mc);
  }
  int mid = t[rt].l + t[rt].r >> 1;
  if(qr <= mid) {
    return query(rt << 1, ql, qr);
  } else if(ql > mid) {
    return query(rt << 1 | 1, ql, qr);
  } else {
    auto p1 = query(rt << 1, ql, mid);
    auto p2 = query(rt << 1 | 1, mid + 1, qr);
    if(p1.first == p2.first) {
      return make_pair(p1.first, p1.second + p2.second);
    } else if(p1.first > p2.first) {
      return make_pair(p1.first, p1.second);
    } else {
      return make_pair(p2.first, p2.second);
    }
  }
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n, m; cin >> n >> m;
  build(1, 1, n);
  while(m--) {
    string s; cin >> s;
    if(s == "Ask") {
      int l, r; cin >> l >> r;
      auto tmp = query(1, l, r);
      cout << tmp.first << ' ' << tmp.second << '\n';
    } else {
      int x, y; cin >> x >> y;
      update(1, x, y);
    }
  }
  return 0;
}

C. 滑板上楼梯

先写一个 $dp$ 找到方案数，然后观察答案，发现分布是 1,2,1,2,3,4,3,4, 其中规律的步长为4, 如果是奇数会比偶数少1, 这样我们可以归纳出答案 $((n - 1) / 4 + 1) * 2$ , 奇数对应减1。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
ll dp[N][2];
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    memset(dp, 0x3f, sizeof(dp));
    // dp[3][1] = 1;
    // dp[3][0] = 3;
    // dp[0][0] = 0;
    // for(int i = 1; i <= 20; i++) {
    //     dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + 1;
    //     if(i - 3 >= 0)
    //         dp[i][1] = dp[i - 3][0] + 1;
    // }
    // for(int i = 0; i <= 20; i++) {
    //     cout << i << ' ' << min(dp[i][0], dp[i][1]) << endl;
    // }
    ll n; cin >> n;
    ll now = ((n - 1) / 4 + 1) * 2;
    if(n & 1) cout << now - 1 << endl;
    else cout << now << endl;
    return 0;
}

D.GCD

显然 $[1, n]$ 里所有的素数都要包含在 $k$ 里面，于是答案就是 $num_{prime} + 1$ ，因为除了素数其他数字都会跟素数组合满足 $gcd(i, j) > 1$
特判 $n \leq 3$ 为 -1，因为全是素数
注意本题把1也认为是素数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int prime[N];
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n; cin >> n;
    if(n <= 3) {
        cout << -1 << endl;
        return 0;
    }
    for(int i = 2; i <= n; i++) {
        if(!prime[i]) {
            for(int j = 2 * i; j <= n; j += i) {
                prime[j] = 1;
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        ans += (!prime[i]);
    }
    cout << ans + 1 << endl;
    return 0;
}

E.牛牛的加法

没什么好说的，一开始用 $long \ long$ 读入了，卡了很久改成 $string$ 就行了
读入后记得把长度短的前面补0，然后对应位相加取模即可
注意00000、0001的情况，要分别输出0和1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
ll ans[N];
int main() {
    //cout << (80 ^ 34) << endl;
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    string a, b; cin >> a >> b;
    while(a.size() < b.size()) a = '0' + a;
    while(a.size() > b.size()) b = '0' + b;
    vector<int> v1, v2;
    for(auto &x : a) {
        v1.push_back(x - '0');
    }
    for(auto &x : b) {
        v2.push_back(x - '0');
    }
    for(int i = 0; i < v1.size(); i++) {
        ans[i] = (v1[i] + v2[i]) % 10;
        //cout << v1[i] << ' ' << v2[i] << endl;
    }
    int cnt = 0;
    while(ans[cnt] == 0 && cnt < v1.size()) ++cnt;
    //cout << cnt << endl;
    if(cnt == v1.size()) {
        cout << 0 << endl;
        return 0;
    }
    //reverse(ans, ans + max(v1.size(), v2.size()));
    for(int i = cnt; i < v1.size(); i++) {
        cout << ans[i];
    }
    cout << endl;
    return 0;
}

F.石子合并

每次保留一个最大数字用来合并其他数字，这个最大数字可以有 $n - 1$ 次贡献( $n - 1$ 次合并), 其他的数字分别都有一次贡献，答案为 $(n - 1) * maxz + (sum - maxz)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
ll a[N];
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    //memset(dp, 0x3f, sizeof(dp));
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];    
    ll sum = 0, maxz = *max_element(a + 1, a + 1 + n);
    ll cnt = 0;
    for(int i = 1; i <= n; i++) {
        sum += a[i];
    }
    sum -= maxz;
    cout << sum + (n - 1) * maxz << endl;
    return 0;
}

G.滑板比赛

贪心一下，对 $m$ 个数字排序，从小到大每次在 $n$ 个数字里 $upper_bound$ 找即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int a[N];
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m; cin >> n >> m;
    multiset<int> st;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        st.insert(a[i]);
    }
    for(int i = 1; i <= m; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + m);
    int ans = 0;
    for(int i = 1; i <= m; i++) {
        auto pos = st.upper_bound(a[i]);
        if(pos == st.end()) continue;
        ans++;
        st.erase(pos);
    }
    cout << ans << endl;
    return 0;
}

H.第k小

以为是主席树，但是其实用两个优先队列就能做了，一个大根堆一个小根堆，大根堆里存 $k - 1$ 个数字，那么小根堆里的堆顶元素就是第 $k$ 小。注意到插入操作可能会小于小根堆的堆顶，此时的操作是放到大根堆，再从大根堆取出堆顶放入小根堆。
注意元素不够输出-1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int a[N];
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m, k; cin >> n >> m >> k;
    priority_queue<int, vector<int>, greater<int> > q1;
    priority_queue<int> q2;
    for(int i = 1; i <= n; i++) cin >> a[i], q1.push(a[i]);
    while(q2.size() < k - 1 && !q1.empty()) {
        q2.push(q1.top()), q1.pop();
    }
    for(int i = 1; i <= m; i++) {
        int op; cin >> op;
        if(op == 1) {
            int x; cin >> x;
            if(q2.size() < k - 1) {
                q1.push(x);
                while(q2.size() < k - 1 && !q1.empty()) {
                    q2.push(q1.top()), q1.pop();
                }
            } else if(q1.empty() || q1.top() > x) {
                q2.push(x);
                auto tmp = q2.top(); q2.pop();
                q1.push(tmp);
            } 
        } else {
            while(q2.size() < k - 1 && !q1.empty()) {
                q2.push(q1.top()), q1.pop();
            }
            if(q1.size() && q2.size() == k - 1)
                cout << q1.top() << endl;
            else cout << -1 << endl;
        }
    }
    return 0;
}

I.区间异或

观察数据范围，先 $O(n^2)$ 预处理一下每一个长度异或的最大值
最后每次查询的时候二分查找即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int a[N], ans[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] ^= a[i - 1];
    }
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            ans[j - i + 1] = max(ans[j - i + 1], a[j] ^ a[i - 1]);
        }
    }
    for(int i = 1; i <= n; i++) {
        ans[i] = max(ans[i], ans[i - 1]);
    }
    for(int i = 1; i <= m; i++) {
        int x; cin >> x;
        int p = lower_bound(ans + 1, ans + 1 + n, x) - ans;
        if(p == n + 1) {
                cout << "-1\n";
        }
        else {
                cout << p << "\n";
        }
    }
    return 0;
}

J.小游戏

简单 $dp$ , 取和不取用0/1表示，显然有转移方程

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])，
dp[i][1] = dp[i - 1][0] + 1LL * i * vis[i]，其中vis[i]是该数字出现的次数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
int a[N], vis[N];
ll dp[N][2];
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        vis[a[i]]++;
    }
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= a[n]; i++) {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        dp[i][1] = dp[i - 1][0] + 1LL * i * vis[i]; 
    }
    cout << max(dp[a[n]][0], dp[a[n]][1]) << endl;
    return 0;
}