AcWing周赛62-64（选讲）
感觉比较思维
4502. 集合操作
https://www.acwing.com/problem/content/4505/
根据题意，肯定要使得所取的最大值最大，平均值最小。又因为每次放进来的的数字都是递增的，所以最大值必然取的是最新放入的那个 \(x\), 接下来考虑平均值，要使平均值尽可能小的话，就要保证数是从小到大取的，然后我们输入的x恰好满足了不减的性质，所以只需要维护一个前缀和(记录之前输入的x),然后从头依次选取，直到找到最小的平均值。
平均值满足一条性质：先递减后递增（常识，可以多写几项找规律），所以一旦发现平均值变大了，那么代表已经找到了最优答案。
还有一个性质就是当前的平均数是连着往后找的，不会回退，因为满先减后增的性质，严谨的证明可以去看y总的视频
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5;
int m, cnt = 1, sum[N];
signed main () {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> m;
int i = 1;
while (m --) {
int x, op;
cin >> op;
if (op == 1) {
cin >> x;
sum[cnt] = sum[cnt-1] + x;
++ cnt;
}
else {
double ans = x;
//int x = sum[cnt] - sum[cnt-1];
for (; i < cnt; i ++) {
//cout << "sum=" << sum[i] << endl;
double aver = 1.0 * (sum[i] + x) / (i + 1);
//经化简，只需比较x_{k+1}与上一个aver
//cout << "aver=" << aver << endl;
if (aver > ans) break;
ans = min (aver, ans);
}
i--;
cout << fixed << setprecision(6) << x - ans << endl;
}
}
}
//后缀和优化
4501. 收集卡牌
https://www.acwing.com/problem/content/4504/
很简单的小题，但是一开始脑子没转过来，如果是第一次出现，就计入 \(cnt\)，集齐了就一次性 \(erase\)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N];
int main () {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m;
int cnt = 0;
while (m --) {
int x;
cin >> x;
if (a[x] == 0) cnt ++;
a[x] ++;
if (cnt == n) {
cout << 1;
for (int i = 1; i <= n; i ++) {
a[i] --;
if (a[i] == 0) cnt --;
}
}
else cout << 0;
}
}
4504. 字符串消除
https://www.acwing.com/problem/content/4507/
很难不让人想到上场多校的F - Candies
#include <bits/stdc++.h>
using namespace std;
int main () {
string s;
cin >> s;
int n = s.size(), cnt = 0;
stack <char> q;
for (int i = 0; i < n; i ++) {
if (q.empty()) q.push (s[i]);
else {
if (s[i] == q.top ()) {
q.pop(), cnt ++;
}
else q.push (s[i]);
}
}
if (cnt & 1) cout << "Yes\n";
else cout << "No\n";
}
4505. 最大子集
https://www.acwing.com/problem/content/4508/
不懂数学，感觉十分的困难
(懒得打公式，就丑丑的手写)
所以只需枚举数和公差即可。
要注意 \(multiset\) 比手写的 \(hash\) 慢，所以还是乖乖手写把
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5, M = 1999997, INF = 0x3f3f3f3f;
int n, h[M], a[N];
multiset <int> s;
vector <int> ans, tmp;
int find(int x) {
int t = (x % M + M) % M;
while (h[t] != INF && h[t] != x)
if ( ++ t == M)
t = 0;
return t;
}
void print () {
cout << "tmp: ";
for (auto i : tmp) cout << i << ' ';cout << endl;
cout << "ans: ";
for (auto i : ans) cout << i << ' ';cout << endl;
}
int main () {
scanf ("%d", &n);
for (int i = 0; i < n; i ++) scanf ("%d", &a[i]);
sort (a, a + n);
memset(h, 0x3f, sizeof h);
//for (auto i : s) cout << i << ' ';cout << endl;
int cnt = 0;
for (int i = 0; i < n; i++) {//枚举数
for (int j = 0; j <= 30; j++) { //枚举公差
int d = (1 << j);
tmp.push_back (a[i]);
for (int k = 1; k <= 2; k++) { //看看与i相差2^j,2^{j+1}的数是否都存在
int x = a[i] - d * k;
//cout << "x=" << x << endl;
if (h[find(x)] == INF) break;
tmp.push_back(x);
}
//看看放够没
int sz = tmp.size();
//print();
if (cnt < sz) {
cnt = sz;
ans.clear();
for (auto k : tmp) ans.push_back (k);
if (cnt == 3) break; //找到答案了
}
tmp.clear();
//print();
}
if (cnt == 3) break; //找到答案了
h[find(a[i])] = a[i];
}
cout << cnt << endl;
//int x = ans[0], y = ans[1], z = ans[2];
for (auto i : ans) cout << i << ' ';
}
//找到一个该集合的最大子集，
//要求子集内的元素满足任意两元素之差的绝对值都是 2 的整数幂。
这题都整了老半天...
4507. 子数组异或和
https://www.acwing.com/problem/content/4510/
有意思的一道小题
主要是要考虑到异或与加法存在某种相似的关系，然后同理利用前缀和的性质来做
分析：
异或与加法有类似性质，所以可以直接使用前缀和
左半边 \(\bigoplus\) 右半边 \(= 0\)
\([i,j]\) 满足条件即 \(s_j\bigoplus s_{i-1}=0 -> s_j=s_{i-1}\)
hash统计出现过的次数
因为长度是偶数，所以下标分奇偶讨论
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
int n, a[N], ans, sum;
unordered_map <int, int> h[2]; //
signed main () {
cin >> n;
for (int i = 1; i <= n; i ++) cin >> a[i];
h[0][0] = 1;
for (int i = 1; i <= n; i++) {
sum ^= a[i]; //前缀异或和
ans += h[i & 1][sum];
h[i & 1][sum] ++;
}
cout << ans << endl;
}
//异或与加法有类似性质，所以可以直接使用前缀和
//左半边 ^ 右半边 = 0
//[i,j]满足条件即s[j]^s[i-1]=0 -> s[j]=s[i-1]
//hash统计出现过的次数
//因为长度是偶数，所以分奇偶讨论
4508. 移动的点
https://www.acwing.com/problem/content/4511/
因为是匀速，所以 \(a,b\) 能相遇的充要条件是 \(a,b\) 的速度向量为同一方向，且不是相对静止（就算 \(a\) 在 \(b\) 的后面，速度比他小也能相遇，因为时间是 \(-\infty\) 到 \(\infty\)）
那么判断速度向量相等就只需要满足：
\[\frac{v_{y_j}-v_{y_i}}{v_{x_j}-v_{x_i}}=a \]即斜率相等
转化一下就变为
判断不是相对静止可以拿个 \(hash\) 表来存，同理，判斜率相等亦然
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
map<pii, int> V; //相对速度
map<int,int> W; //wi,速度方向
int ans;
signed main () {
int n, a, b;
cin >> n >> a >> b;
for (int i = 1; i <= n; i++) {
int x, vx, vy;
cin >> x >> vx >> vy;
int w = a * vx - vy;
ans += W[w] - V[{vx, vy}];
W[w] ++, V[{vx, vy}] ++;
}
cout << ans * 2; //ab相遇算两次
}
//相遇必须满足:(v_{yj} - v_{yi})/(v_{xj} - v_{xi})=a
//即a*v_{xj} - v_{yj} = a*v_{xi} - v_{yi}且相对速度不为0