牛客练习赛88

A 活着的证据

题意：

给了 的个数为 个， 的个数为 个，最大数位个数为 ，现在问能表示出来的最大的数是多少。
其中罗马字母与数学字母对应的关系如下：

Solution：

按照贪心策略分类讨论：
若是两种字母的数量之和大于所要求的位数，那么按照如下顺序优先构造数字 8、7、6、5、3、2、1，否则先构造 5 ，最后再构造 1
其中 4 和 6 的罗马字符对称，因此只需构造 6 即可。

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ls i<<1
#define rs i<<1|1
typedef long long ll;
typedef pair<int,int>P;
int t,a,b,c;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&b,&a,&c);
        while(c)
        {
            if(a+b>=c)
            {
                if(a>=3&&b>=1&&a+b-4>=c-1)
                {
                    printf("8");
                    a-=3;
                    b--;
                }
                else if(a>=2&&b>=1&&a+b-3>=c-1)
                {
                    printf("7");
                    a-=2;
                    b--;
                }
                else if(a>=1&&b>=1&&a+b-2>=c-1)
                {
                    printf("6");
                    a--;
                    b--;
                }
                else if(b>=1&&a+b-1>=c-1)
                {
                    printf("5");
                    b--;
                }
                else if(a>=3&&a-3>=c-1)
                {
                    printf("3");
                    a-=3;
                }
                else if(a>=2&&a-2>=c-1)
                {
                    printf("2");
                    a-=2;
                }
                else if(a>=1&&a-1>=c-1)
                {
                    printf("1");
                    a-=1;
                }
            }
            else if(b)
            {
                b--;
                printf("5");
            }
            else if(a)
            {
                a--;
                printf("1");
            }
            c--;
        }
        printf("\n");
    }
    return 0;
}

B 寻寻觅觅寻不到

题意：

组样例，给了两个字符串 和 ,一个数字 , 判断 中是否能截取 个连续字符串放到末尾后，与字符串 相同，若存在输出 YES，否则输出 NO。

Solution：

这道题暴力可能是可以写的，但是我用了哈希。
这样就能 判断两个字符串是否一致。
先记录一下字符串哈希的前缀和，可以将 字符串大致分为三段，第一段哈希只需取出，无需其他操作，第二段为截取的 个字符的哈希值需乘上哈希种子，计算出其放在最后的哈希值，第三段哈希值需乘上哈希种子的逆元，到达第二段开始的位置。判断哈希值是否相等，若相等则 YES,否则 NO

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
int T;
const int mod=1e9+7;
const int p=233;
char s[300005];
ll a[300005];
char t[300005];
int k;
ll _pow[300005];
ll sum[300005];
ll inv[10];
ll fpow(ll x,int power)
{
    ll ans=1;
    while(power)
    {
        if(power&1)ans=ans*x%mod;
        power>>=1;
        x=x*x%mod;
    }
    return ans;
}
int main()
{
    scanf("%d",&T);
    inv[1]=fpow(p,mod-2);
    for(int i=2;i<=6;i++)inv[i]=inv[i-1]*inv[1]%mod;
    _pow[0]=1;
    for(int i=1;i<=300000;i++)_pow[i]=_pow[i-1]*p%mod;
    while(T--)
    {
        scanf("%s%s%d",s+1,t+1,&k);
        int n=strlen(s+1);
        int m=strlen(t+1);
        if(n!=m){printf("NO\n");continue;}
        for(int i=1;i<=n;i++)
        {
            a[i]=(a[i-1]+(s[i]-'A')*_pow[i])%mod;
            sum[i]=(sum[i-1]+(t[i]-'A')*_pow[i])%mod;
        }
        a[n+1]=0;
        bool flag=false;
        for(int i=1;i+k-1<=n;i++)
        {
            ll tem=(a[i-1]+(a[i+k-1]-a[i-1]+mod)*_pow[n-i-k+1])%mod;
            tem=(tem+(a[n]-a[i+k-1]+mod)*inv[k])%mod;
            if(sum[n]==tem)flag=true;
            if(flag)break;
        }
        if(flag)printf("YES\n");
        else printf("NO\n");

    }
    return 0;
}

C 踩不出足迹

题意：

Solution：

代码：

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
int n,k;
int main()
{
    scanf("%d%d",&n,&k);
    ull sum1=0,sum2=0;
    for(int i=1;i<=n;i++)
    {
        ull x;
        scanf("%llu",&x);
        sum1^=x;
    }
    ull x=sum1;
    for(int i=0;i<k;i++)
    {
        if(x&(((ull)1)<<i));
        else sum2|=((ull)1)<<i;
    }
    if(n==1)printf("%llu",sum1);
    else 
    printf("%llu",max(sum1,sum2));
    return 0;
}