2022牛客多校·第五场

比赛链接："蔚来杯"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;
        }
    }
}