牛客周赛 26_牛客博客

A题：相当于每个数都可以对应到一个%k意义下的一个数 这些%k相同的数都可以通过加一些k变得相同，所以统计%k哪个最多即可

#include "bits/stdc++.h"
using namespace std;
#define int long long

const int maxn=1e5+10;
int a[maxn];
int n,k;
map<int,int >mp;
signed main()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
        mp[a[i]%k]++;
    }
    int maxx=0;
    for (auto i:mp)
    {
        maxx=max(maxx,i.second);
    }
    cout<<maxx;
}


B题：根据题意可得 当s.size()为奇数时，那么0 1的个数分别是奇数，偶数 （或是偶数，奇数）那么例如这种010100111串，可以先直接把相邻的00变成11 然后0101部分也可变换一下得到11111111 所以 一定是yes，
当s.size()为偶数时，并且0 1的个数都为偶数时，11001010 可以直接类似上面的变换 变成 全1或全0 ，当其中一个是奇数另一个一定也是奇数，那么通过上面的变换最后会多一个0或1 例如110111一定会多一个0
#include "bits/stdc++.h"
using namespace std;
#define int long long

const int maxn=1e5+10;
int a[maxn];
int T;
signed main()
{
    cin>>T;
    while (T--)
    {
        string s;
        cin>>s;
        int num=0;
        for (int i=0;i<s.size();i++)
        {
            if (s[i]=='0')
            {
                num++;
            }
        }
        if (s.size()%2==1) cout<<"Yes"<<endl;
        else
        {
            if (num%2==1) cout<<"No"<<endl;
            else cout<<"Yes"<<endl;
        }
    }
}

C题：直接跑一个堆优化dij

#include "bits/stdc++.h"
using namespace std;
#define int long long

const int maxn=1e5+10;
int n,m;
int a[2020][2020];
int f(int x,int y)
{
    return x>=1 && y>=1 && x<=n && y<=m;
}
int dx[3]={0,0,1};
int dy[3]={-1,1,0};
struct node{
    int x,y,val,dis;
    bool operator> (const node &t) const
    {
        return dis>t.dis;
    }
};
bool st[2020][2020];
int dis[2020][2020];
signed main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }
    priority_queue<node,vector<node>,greater<node> >q;
    memset(dis,0x3f,sizeof dis);
    q.push({1,1,a[1][1],0});

    dis[1][1]=0;
    while (q.size())
    {
        auto t=q.top();
        if (t.x==n && t.y==m)
        {
            cout<<t.dis;
            return 0;
        }
        q.pop();
        if (st[t.x][t.y]) continue;
        st[t.x][t.y]=1;
        for (int i=0;i<=2;i++)
        {
            int xx = dx[i];
            int yy = dy[i];
            if (f(t.x + xx, t.y + yy))
            {
                int vall;
                if (a[t.x + xx][t.y + yy] == a[t.x][t.y])
                {
                    vall = 1;
                } else vall = 2;
                if (dis[t.x+xx][t.y+yy]>vall+dis[t.x][t.y])
                {
                    dis[t.x+xx][t.y+yy]=vall+dis[t.x][t.y];
                    q.push({t.x+xx,t.y+yy,a[t.x+xx][t.y+yy],t.dis+vall});
                }
            }
        }
    }
}

D题：

类似小白赛82 C题的状态机模型有点麻烦但是也算是比较清楚状态定义和转移在注释内注意每个状态需要有26个出边这样检查能保证不重不漏

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int mod=1e9+7;
int n;
const int maxn=1e6+10;
int dp[maxn][10];
signed main()
{
    cin>>n;

    dp[1][6]=25;
    dp[1][5]=1;
    for (int i=2;i<=n;i++)
    {
        //dp[n][0]表示包含两个red子串的数量
        //dp[n][0]=dp[n-1][0]*26+dp[n-1][1]
        //dp[n][1]表示有一个red子串且结尾是re的数量
        //dp[n][1]=dp[n-1][2];
        //dp[n][2]表示有一个red子串且结尾是r的数量
        //dp[n][2]=dp[n-1][3]+dp[n-1][2]+dp[n-1][1];
        //dp[n][3]表示有一个red子串的数量且结尾是""的数量
        //dp[n][3]=(dp[n-1][3])*25+24*(dp[n-1][1]+dp[n-1][2])+dp[n-1][4];
        //dp[n][4]表示一个red子串都没有且结尾是re的数量
        //dp[n][4]=dp[n-1][5]
        //dp[n][5]表示一个red子串都没有且结尾是r的数量
        //dp[n][5]=dp[n-1][6]+dp[n-1][5]+dp[n-1][4];
        //dp[n][6]表示一个red子串都没有且结尾是""的数量
        //dp[n][6]=24*(dp[n-1][5]+dp[n-1][4])+25*dp[n-1][6]
        dp[i][0]=dp[i-1][0]*26+dp[i-1][1];
        dp[i][1]=dp[i-1][2];
        dp[i][2]=dp[i-1][3]+dp[i-1][2]+dp[i-1][1];
        dp[i][3]=(dp[i-1][3])*25+24*(dp[i-1][1]+dp[i-1][2])+dp[i-1][4];
        dp[i][4]=dp[i-1][5];
        dp[i][5]=dp[i-1][6]+dp[i-1][5]+dp[i-1][4];
        dp[i][6]=24*(dp[i-1][5]+dp[i-1][4])+25*dp[i-1][6];
        for (int j=0;j<=6;j++)
        {
            dp[i][j]%=mod;
        }
    }
    cout<<(dp[n][0]+mod)%mod;

}