CF1776C题解

IsaacX · 2023-07-24 08:20:49 · 题解

Library game

膜拜 pb 大师 orz。

思路

先考虑 A 和 B 各自的最优策略。

• 对于 A，最优策略很简单，就是从左往右能放就放。此外，放更长的区间不会使答案更劣，所以我们可以把每个区间从长到短排序。
• 对于 B，B 希望卡到某一个时刻 A 放不进去。设 B 想让 A 放不进区间 p，则 B 的最优策略为每隔 a_p 拿一个，也就是拿走 a_p 的倍数，这样就可以确保区间 p 放不进去。

最优策略确定了，考虑如何快速确定胜负情况，这取决于 B 选择的区间 p。通过手玩（抽屉原理可证）可以发现，如果满足 \exists a_i > \lfloor \frac{m}{i} \rfloor，则 B 必胜。如果没有，则 A 必胜。（注意这里的 a 数组是排过序的）

交互时，对于 B，如果 A 选择的区间长度大于 a_p，输出包含在内的 a_p 的倍数。否则随便选一个输出。

确定了胜负，剩下的直接按最优策略和交互库交互即可。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,p,a[105],bk[5005];
bool cmp(int x,int y)
{
    return x>y;
}
void solve_A()
{
    printf("Alessia\n");
    fflush(stdout);
    memset(bk,0,sizeof bk);
    for(int i=1;i<=n;i++)
    {
        int l=1,x;
        for(int r=1;r<=m;r++)
        {
            if(bk[r])//被B拿走了
                l=r+1;
            else if(r-l+1==a[i])//能放进去
            {
                printf("%d %d\n",a[i],l);
                fflush(stdout);
                break;
            }
        }
        scanf("%d",&x);
        bk[x]=1;
    }
}
void solve_B()
{
    printf("Bernardo\n");
    fflush(stdout);
    for(int i=1;i<=n;i++)
    {
        int len,l;
        scanf("%d%d",&len,&l);
        if(a[p]<=len)
            printf("%d\n",(l+a[p]-1)/a[p]*a[p]);//求区间内a[p]的倍数
        else
            printf("%d\n",l);//随便输出一个
        fflush(stdout);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i]>(m/i))//此时B必胜
        {
            p=i;
            break;
        }
    }
    if(!p)
        solve_A();
    else
        solve_B();
}

希望本篇题解可以帮到大家！！！