牛客多校1

题目链接 https://ac.nowcoder.com/acm/contest/11166#question

A题

A题是一道博弈，一开始看起来很麻烦，不容易想到，其实还是博弈当中先后手的切换。假设有一对（i，j）使后手胜利，那么先手可以把任意的（i，j+x）通过拿x个变成（i，j），然后对于x<0的情况，先手总能使得他变成i-1对应的后手赢的情况。因此对于每一个i最多只有一个j使他成为后手胜利的情况。
所以代码就出来了，我们用一个二维数组存储所有的（i，j）对应的情况，当（i，j）是对应后手胜利的情况时，我们将所有的（i+s，j+sk）和（i+sk，j+s）都设置成先手胜利。

#include<bits/stdc++.h>
#define  maxn  1000000000 + 7
using namespace std;
typedef long long ll;
bool p[5005][5005];
int main()
{
    int t,m,n;
    for(int i=0;i<=5000;i++)
    {
        for(int j=0;j<=5000;j++)
        {
            if(!p[i][j])
            {
                    for(int s=1;s+j<=5000;s++)for(int k=0;i+s*k<=5000;k++)p[i+s*k][j+s]=1;
                    for(int s=1;s+i<=5000;s++)for(int k=0;j+s*k<=5000;k++)p[i+s][j+s*k]=1;
            }
        }
    }
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        if(p[n][m])puts("Alice");
        else puts("Bob");
    }
    return 0;
}

B题

一道简单的几何题，用相似三角形即可求解，不过由于要求输出小数点后十位，因此要注意运算过程中各个变量的类型要相同不然可能会导致结果不同。

#include<bits/stdc++.h>
#define  maxn  1000000000 + 7
#define x  r*sqrt(h*h+((a-b)*(a-b)/4))/h-b/2
using namespace std;
typedef long long ll;
int main()
{
    double r,a,b,h;
    scanf("%lf%lf%lf%lf",&r,&a,&b,&h);
    if(2*r<b)puts("Drop");
    else
    {
        puts("Stuck");
        printf("%.10lf",h*(x)*2/(a-b));
    }
    return 0;
}

D题

签到题，只需要计算每行有多少个连续的0大于等于m即可。

#include<bits/stdc++.h>
#define  maxn  1000000007
using namespace std;
typedef long long ll;
int main()
{
    int n,m;
    cin>>n>>m;
    char b,a;
    int sum=0;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        sum=0;
        for(int j=1;j<=n;j++)
        {
            cin>>a;
            if(a=='0')sum++;
            else sum=0;
            if(sum>=m)ans++;
            //cout<<sum<<endl;
        }
    }
    for(int i=1;i<=m;i++)
    {
        cin>>b;
    }
    cout<<ans<<'\n';
    return 0;
}

F题

很容易想到前缀和的思想，但是数据范围到了1e18，肯定是会超时，进一步的思考我们会发现大于等于100的数都是3-friendly的，因为对于每一位上的数mod3只有0，1，2三种情况，当有一位mod3为0那一定符合题目要求，除去这个情况外，还有1，2两种情况，不管每一位上的数是哪种情况，总有两位或三位相加的结果为3的倍数，从而符合题目要求。用前缀和思想求解时要注意，当l<=99并且这个数是3-friendly的，这个时候结果要+1，因为题目要我们求的是两边都是闭区间的，这个时候我们要把l这个3-friendly数给加回来。

#include<bits/stdc++.h>
#define  maxn  1000000007
using namespace std;
typedef long long ll;
int a[105];
int main()
{
    a[0]=1;
    for(int i=1;i<100;i++)
    {
        a[i]=a[i-1];
        if(i%3==0)a[i]++;
        else if(i>=10)
        {
            if((i/10)%3==0)a[i]++;
            else if((i%10)%3==0)a[i]++;
        }
    }
    ll t,l,r;
    cin>>t;
    while(t--)
    {
        cin>>l>>r;
        if(l>99&&r>99)
        {
            cout<<r-l+1<<'\n';
        }
        else if(l<=99&&r>99)
        {
            if(a[l]==a[l-1])cout<<r-99+a[99]-a[l]<<'\n';
            else cout<<r-99+a[99]-a[l]+1<<'\n';
        }
        else
        {
            if(a[l]==a[l-1])cout<<a[r]-a[l]<<'\n';
            else cout<<a[r]-a[l]+1<<'\n';
        }
    }
    return 0;
}

G题

这题主要是一个贪心，只要每一次交换的贡献最大，那么就能使结果最大。题目要求是在a数组中操作，但是在a中操作和在b中操作其实是一样的，因为结果是|ai-bi|的和。
我们把每一个i对应的ai,bi中较大的换到a数组中，即对于所有的i有ai>bi，那么一定有(a1>b1&&a2>b2)使得|a1-b1|+|a2-b2|=a1+a2-b1-b2
那么进行交换操作之后的结果为|a1-b2|+|a2-b1|,当a2<b1时，由以上条件可得b2<a2<b1<a1,则交换后的结果为a1-b2-a2+b1,由于我们把ai,bi中较大的数交换到了a数组，那么可能会出现|b2-b1|这样的情况，但按题目要求只能是a数组的元素和b数组的元素的差的绝对值，不要慌，他们其实结果和上面是相同的，因为我们之交换了i对应的ai,bi，因此出现这种情况时一定是交换之后的，我们只要验证他与交换之后的结果是否相同即可，条件与上面相同，|b2-b1|+|a2-a1|=a1-a2+b1-b2=|a1-b2|+|a2-b1|，可以看到结果是相同的，所以我们把ai,bi之中较大的数交换到a数组这种操作并不影响最终结果。然后对应a2>b1时，|a1-b2|+|a2-b1|=a1+a2-b1-b2与交换前相同，贡献差为0，因此我们可以用这种交换来抵消多余的'k'，那么先前的有效操作的贡献再加上原本未进行操作的a,b数组各个元素差的绝对值，即本题答案。那么现在来求一下有效操作的贡献，即交换后的值与交换前的值之差，2*(b1-a1),题目要求我们结果最大，因此我们只需要把大于0的加上即可。

#include<bits/stdc++.h>
#define  maxn  1000000007
using namespace std;
typedef long long ll;
int a[500005],b[500005];
int main()
{
    int n,k;
    cin>>n>>k;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    if(n==2)
    {
        while(k--)
        {
            swap(a[1],a[2]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
        if(b[i]>a[i])swap(b[i],a[i]);
        ans+=a[i]-b[i];
    }
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    ll t;
    for(int i=1;i<=k&&i<=n;i++)
    {
        t=2*(b[n-i+1]-a[i]);
        if(t>0)ans+=t;
        else break;
    }
    cout<<ans<<'\n';
    return 0;
}