比赛链接："蔚来杯"2022牛客暑期多校训练营5
这场出题人大锅，大家都乱玩了，不过有些题还是挺不错的，其他题就随便写一点就行。
因为时间关系，这里有两个好题暂时没补，先放在这里2022牛客暑期多校训练营5 A(DP) D(树上DP) - 知乎 (zhihu.com)，感谢ygg
B.Watches（二分）
题意：一共有$n$个手表，价值分别是$a_i$，你有$m$枚金币，求能够买的最大的手表数量。每个手表有一个“税收”，也就是如果你买了$k$个手表，原列表中的第$i$个手表的价格就是$a_i+k\times i$。
例如我现在有手表$a_i=\lbrace 1,3,2,5,4\rbrace$，我选择买其中的$1,3,5$三块手表，那么这个时候$k=3$，价格加上税收之后变成了$\lbrace 1+3\times 1\ ,\ 2+3\times 3\ ,\ 4+3\times 5 \rbrace$。
思路：这个时候每个$k$是不一样的，所以我们需要二分答案，我们可以买$mid$块手表，这样$k$就确定了，我们就可以对其新的价格进行更新，然后sort一遍之后就可以得到从小到大的新价格。这个时候我们选出前面的$k$块手表计算价格之和之后比较一下我们的钱$m$。
代码：
inline bool check(int k)
{
for (int i=1;i<=n;i++)
b[i] = a[i] + i*k;
sort(b+1,b+1+n);
int res = 0;
for (int i=1;i<=k;i++)
res += b[i];
return (res<=m);
}
inline void Case_Test()
{
while(cin>>n>>m)
{
for (int i=1;i<=n;i++)
cin>>a[i];
int l = 0, r = n;
while (l<r)
{
int mid = (l+r+1)>>1;
if (check(mid)) l = mid;
else r = mid-1;
}//二分答案
cout<<l<<endl;
}
}
G.KFC Crazy Thursday（PAM回文自动机/manacher）
马拉车算法签到
K.Headphones（签到）
注意题目意思。
F.A Stack of CDs（计算几何）
BZOJ1043 下落的圆盘
H.Cutting Papers
输出n*n*3.0/4+n*acos(-1.0)/4-n/2.0即可
C.Bit Transmission（签到）
统计错误
代码：
inline void Case_Test()
{
while (cin>>n)
{
vector<int> ans(n);
for (int i=1;i<=3*n;i++)
{
cin>>x>>s;
if (s=="YES") num[x][1]++;
else num[x][0]++;
}
int res = 0;
for (int i=0;i<n;i++)
{
if (num[i][0] == num[i][1]) res+=2;
else if (num[i][0]>num[i][1]) ans[i] = 0, res += num[i][1];
else ans[i] = 1, res += num[i][0];
}
if (res>1) cout<<-1<<endl;
else
{
for (int i=0;i<n;i++)
{
cout<<ans[i];
num[i][0] = num[i][1] = 0;
}
cout<<endl;
}
}
}