526互联

AtCoder Beginner Contest(abc) 329

发布时间 2023-11-19 11:46:16作者: mostimali



B - Next

难度: ⭐

题目大意

给定n个数, 输出其去重后的次大值;

解题思路

暴力就行;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
int n, m;
int a = -1, b = -1;
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        if(x > a){
            b = a;
            a = x;
        }
        else if(x > b && x != a){
            b = x;
        }
    }
    cout << b;
    return 0;
}



C - Count xxx

难度: ⭐⭐

题目大意

给定一个字符串, 问其中有多少种由同一个字母组成的连续子串; eg: a bbb cc

解题思路

因为要考虑去重, 我们可以直接记录每种字母最长的连续子串的长度即可, 其数量就是该长度;
注意: 我第一想法是暴力扫一遍然后用set把所有满足条件的子串存起来; 但是我没意识到, set对于字符串的排序和去重也是需要遍历该字符串的, 所以对于string类型的set, 它的所有操作复杂度
是O(nmlogn), m是字符串的长度, 所以会TLE;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
int n, m, idx;
int d[N];
signed main(){
    string s;
    cin >> n >> s;
    string str = "";
    int idx = 1;
    for(int i = 1; i < s.size(); i++){
        if(s[i] == s[i - 1]) idx++;
        else{
            int x = s[i - 1] - 'a';
            d[x] = max(d[x], idx);
            idx = 1;
        }
    }
    d[s[s.size() - 1] - 'a'] = max(d[s[s.size() - 1] - 'a'], idx);
    int res = 0;
    for(int i = 0; i < 26; i++){
        res += d[i];
    }
    cout << res;
    return 0;
}



D - Election Quick Report

难度: ⭐⭐

题目大意

一场选举有n个候选人; 一共有m张选票; 挨个展示每张选票, 并且同步输出当前选票数量最多的候选人是谁, 如果票数相同, 就输出编号小的那位;

解题思路

只需要设置两个变量x和y来维护展示第i张选票前票数最多人是谁, 他的票数是多少; 每次更新时, 如果当前这个人满足条件, 那么就更新x; 否则就还是输出x;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
int n, m, idx;
int maxn = 0, v;
int d[N];
signed main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x;
        cin >> x;
        d[x]++; 
        if(d[x] > maxn){
            maxn = d[x];
            v = x;
        }
        else if(d[x] == maxn){
            if(x < v) v = x;
        }
        cout << v <<endl;
    }
    return 0;
}



E - Stamp

难度: ⭐⭐⭐⭐

题目大意

给定两个字符串S和T, 长度分别为n和m; 以及一个空的字符串C, 长度也是n; 我们可以用字符串T去构造字符串C: 在字符串C中选择m个连续的位置, 然后用字符串T去覆盖这个m个位置; 注意是覆盖, 如果这m个位置之前已经有字符了也会被覆盖为新的; 请问是否可以把C构造为S;

解题思路

待补...

神秘代码

待补...



F - Good Set Query

难度: ⭐⭐⭐

题目大意

现在有n个箱子, 初始每个箱子都有一个颜色为x的球; 现在有m次操作, 每次把a箱子的球倒进b箱子, 然后输出b箱子中有多少种颜色的球;

解题思路

为了去重我们考虑用set来维护每个箱子种球的颜色数量; 本题的关键是要用树上启发式合并来进行两个箱子的合并, 朴素的合并会TLE; 树上启发式合并也很简单, 就是当我们要合并两个箱子时, 我们要选择把球数少的箱子倒进球数多的箱子, 而不是反过来, 这是一种直觉性的算法; 但是题目已经要求了a和b的倒入顺序, 所以如果要进行启发式合并, 那么可能需要互换箱子的编号, 所以我们就得另开一个数组, 表示set[i]的i表示第几个箱子;

神秘代码

#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
int n, m, idx;
set<int> st[N];
int id[N];
signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        st[i].insert(x);
    }
    for(int i = 1; i <= n; i++) id[i] = i;
    while(m--){
        int a, b, a1, b1;
        cin >> a >> b;
        a1 = id[a], b1 = id[b];
        if(st[a1].size() < st[b1].size()){
            for(int x : st[a1]){
                st[b1].insert(x);
            }
            st[a1].clear();
        }
        else {
            for(int x : st[b1]){
                st[a1].insert(x);
            }
            st[b1].clear();
            swap(id[a], id[b]);
        }
        cout << st[id[b]].size() << endl;
    }
    return 0;
}