Atcoder ABC 459
A 签到
删除string的第i个字符，用s.erase(i - 1, 1)
B 签到
要把每个字母映射成一个值，很方便的写法：
C 树状数组
不使用树状数组的做法
void solve() {
int n, q;
cin>>n>>q;
vector<int>cnt(n+1,0);
unordered_map<int,int>p;
p[0]=n;
int ans = 0;
while(q --) {
int a, x;
cin >> a >> x;
if (a == 1) {
cnt[x] ++;
if(cnt[x] == 1) {
ans++;
}
}
}
p[cnt[x]]++;
if (ans == n) {
for (int i = 1; i <= n; i ++) {
if (--cnt[i] == 0) {
ans--;
}
}
p[cnt[i] + 1] --;
}
else {
cout << p[x] << endl;
}
}
不用树状数组我还有一种做法，用到了二分，或许本质和树状数组比较接近
void solve() {
int n, q;
cin >> n >> q;
vector<int> cnt(n + 1); // 以单元格为维度，记录1-n个单元格的砖块数量
vector<int> arr(n); // 维护n个格子的block数量，维护时使用upper_bound - 1保证其为有序的，从而实现可以二分查询
int op, x;
int zero = 0; // 记录当前消到了第几层
while (q --) {
cin >> op >> x;
if (op == 1) {
// 给第x块加1
int v = cnt[x];
cnt[x] ++;
arr[upper_bound(arr.begin(), arr.end(), v) - arr.begin() - 1] ++;
// 如果满了一层，则全体基准0 ++
if (arr[0] - zero >= 1) zero ++;
} else {
// 查询 >= y 的个数
// x - zero >= y
auto iter = lower_bound(arr.begin(), arr.end(), x + zero) - arr.begin();
cout << n - iter << endl;
}
}
}
乍一看，在Q次查询中嵌套一个O(N)的for 循环，最坏时间复杂度似乎是O(NxQ)。但实际上它的总时间开销是O(Q)。
- 要触发一次这个O(N)的for 循环，前提是 ans==n(即盘面上至少增加了N个积木)。
- 每次触发循环，会从盘面上消除N个积木。
- 因为每次查询最多只添加1个积木，总共只有Q次查询，这意味着最多只能触发Q/N次全局消除。
- 所以这个for 循环在整个程序运行期间，最多只会执行(Q/N)xN=Q次。这种“平时攒着，偶尔爆发”的时间计算方式就叫均摊复杂度分析。
在这个位置肯定是有不用树状数组的做法，但使用数据结构可以降低思维含量，借此机会复习一下树状数组
俄罗斯方块，消掉的动作转换成已经有多少层铺满了（这个想到了）
维护使用权值树状数组最方便
- 下标记录第几层
- 值记录恰好有几层位于这一层
一开始所有层有位于第0格，修改就改变当前这一格的层数
- 由于树状数组不能有0下标，所以偏移一位
- 树状数组可能会超m或n所以开大一点
template <typename T>
struct BIT {
int n;
vector<T> a;
BIT(int _n) {
init(_n);
}
void init(int _n) {
n = _n;
a.assign(n + 1, T{});
}
void update(int x, const T &v) {
for (; x <= n; x += x & -x) {
a[x] += v;
}
}
T sum(int x) {
T res = 0;
for (; x; x -= x & -x) {
res += a[x];
}
return res;
}
T query(int l, int r) {
return sum(r) - sum(l - 1);
}
};
void solve2() {
int n, q;
cin >> n >> q;
vector<int> cnt(n + 1, 1);
BIT<int> bit(1e6 + 1);
bit.update(1, n);
int zero = 1;
while (q --) {
int op, x;
cin >> op >> x;
if (op == 1) {
bit.update(cnt[x], -1);
cnt[x] ++;
bit.update(cnt[x], 1);
if (bit.query(zero, zero) == 0) zero ++;
} else {
cout << n - bit.query(1, zero + x - 1) << endl;
}
}
}
D 贪心
每次选择最大的及次大的
第一次pop出来的要根据当前末尾的字符多做一点策略
void solve2() {
string s;
cin >> s;
int n = s.size();
vector<int> cnt(26);
for (char c : s) cnt[c - 'a'] ++;
int mx = *max_element(cnt.begin(), cnt.end());
if (mx > (n + 1) / 2) {
cout << "No\n";
return;
}
priority_queue<pair<int, char>> pq;
for (int i = 0; i < 26; i ++) {
if (cnt[i] > 0) pq.push({cnt[i], i + 'a'});
}
string ans;
while (!pq.empty()) {
auto [c1, ch1] = pq.top();
pq.pop();
if (ans.empty() || ans.back() != ch1) {
ans += ch1;
c1 --;
if (c1 > 0) pq.push({c1, ch1});
} else {
if (pq.empty()) {
cout << "No\n";
return;
}
auto [c2, ch2] = pq.top();
pq.pop();
ans += ch2;
c2 --;
pq.push({c1, ch1});
if (c2 > 0) {
pq.push({c2, ch2});
}
}
}
cout << "Yes\n";
cout << ans << "\n";
}