迟到两周的总结（一直在补多校...）
过题数：3/3
排名：26/2341
| 过题数 | 罚时 | A(906) | B(533) | C(139) |
|---|---|---|---|---|
| 3 | 0:52:17 | 0:04:17 | 0:11:09 | 0:36:51 |
C我写的是一个三分，调好久，他们写的二分好像也可以，还有其他做法，B我赛中用的线段树...实际上不用这么麻烦。
比赛链接：第 62 场周赛 - AcWing
A.三个元素（签到）
题意：给定一个长度为 $n$ 的数组 $r_1,r_2,…,r_n$。
请你找到其中的三个元素 $r_a,r_b,r_c$，使得 $r_a<r_b<r_c$ 成立。
思路：签到，暴力枚举，不过这里有个技巧是枚举中间的$b$，这样快一些，只需要枚举左右的$a,c$即可。
代码：
inline void Case_Test()
{
cin>>n;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=2;i<n;i++)
{
int ans1 = -1, ans2 = -1;
for (int l = 1;l<=n;l++)
if (a[l]<a[i]) ans1 = l;
for (int r = 1;r<=n;r++)
if (a[r]>a[i]) ans2 = r;
if (ans1!=-1 && ans2!=-1)
{
cout<<ans1<<" "<<i<<" "<<ans2<<endl;
return;
}
}
cout<<-1<<" "<<-1<<" "<<-1<<endl;
}
B.收集卡牌
题意：给你$n$张卡牌，一共有$m$种卡牌，对于按顺序的第$i(1\leq 1\leq n)$询问能够集齐一套进行兑换（1表示能够兑换）
例如：
Input:
3 11
2 3 1 2 2 2 3 2 2 3 1
Output:
00100000001
思路：赛中没有想法...直接用的线段树进行单点加法，区间查询最小值...实际上只需要想象成一个二维的，我用num数组来表示每一种卡牌有多少个（竖着），我用cnt数组来表示每一层，也就是每一套有多少个（横着）。
每次读入一个则对num[x]++，并且记录这一层多了一个，当这一层为m的时候说明集齐一套，进行下一套t++判断并且输出1,否则输出0。
代码：
int num[N],cnt[N];
inline void Case_Test()
{
cin>>m>>n;
int t = 1;
for (int i=1;i<=n;i++)
{
cin>>x;
num[x]++;
cnt[num[x]]++;
if (cnt[t]==m)
{
cout<<1;
t++;
}
else cout<<0;
}
}
C.集合操作（三分）
题意：
给定一个由正整数（最初为空）组成的多重集 $S$。多重集表示可能存在重复元素的集合。
请你对该集合执行 $Q$ 次操作，操作分为两种：
增加操作，格式为 1 x，将一个正整数 $x$ 加入到集合 $S$ 中。数据保证，$x$ 不小于当前 $S$ 中的任何元素。
询问操作，格式为 2，找到一个当前 $S$ 的子集 $s$，要求 $max(s)−mean(s)$ 的值应尽可能大，输出 $max(s)−mean(s)$ 的最大可能值。$max(s)$ 表示 s 中最大元素的值，$mean(s)$ 表示 $s$ 中所有元素的平均值。
思路：每次加入，我想要$max(s)-mean(s)$最大，而每次的$x$又是不递减的，所以它就是当前最大的，然后在前面选择，我前缀和来优化，每次三分选择最大值与前面的答案进行比较并更新。
代码：
inline void Case_Test()
{
cin>>q;
double sum = 0, num = 0;
while (q--)
{
int op;
cin>>op;
if (op==1)
{
cin>>x;
a[++n] = x;
pre[n] = a[n] + pre[n-1];
}
else
{
int l = 0, r = n-1;
double ls,rs;
if (l==r) {cout<<fixed<<setprecision(6)<<0.0<<endl;continue;}
while (l<r)
{
int mid = (l+l+r)/3;
int midmid = (r+r+l+2)/3;
ls = (pre[mid]+a[n])/(double(mid+1));
rs = (pre[midmid]+a[n])/(double(midmid+1));
if (ls<rs) r = midmid-1;
else l = mid+1;
}
ans = Max(ans, a[n]-Min(ls,rs));
cout<<fixed<<setprecision(6)<<ans<<endl;
}
}
}