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