竞赛讨论区 > 牛客小白月赛31 题解

牛客小白月赛31 题解

头像
喵渺淼妙的死忠粉
编辑于 2021-01-11 12:34:33 APP内打开
赞 3 | 收藏 0 | 回复0 | 浏览298

我是个小菜鸡...只是从今天开始是我认真学习的第一天)不想当划水怪了.赛后感觉和赛时真不一样...

A.A|B

我写的是数位dp...第一次自己写出数位dp也挺激动的,虽然挺水的..
首先我们开个f[2][31]数组来记忆化一下,然后就是模拟这个过程了,看这位是不是已经比x小了,小了下一位可以任意选...然后模拟下去就好了,代码写的虽然长点,但是思路很清晰,最后减去0的情况.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+6;
const int mod=1e9+7;
int x,a;
int f[2][31];
int dfs(int u,int k,bool limit)
{
    int res=0;
    if(!limit&&f[k][u]!=-1)    return f[k][u];
    if(u==0)
    {
        if(a&(1<<u)&&k==1)    return 0;
        else                  return 1;
    }
    if(limit)
    {
        if(x&(1<<(u-1)))//下一位是1.
        {
            if(a&(1<<(u-1)))
            {
                res+=dfs(u-1,0,0);
            }
            else
            {
                res+=dfs(u-1,0,0);
                res+=dfs(u-1,1,1);
            }
        }
        else//下一位是0. 
        {
            if(a&(1<<(u-1)))
            {
                res+=dfs(u-1,0,1);
            }
            else
            {
                res+=dfs(u-1,0,1);
            }
        }
    }
    else
    {
        if(x&(1<<(u-1)))//下一位是1. 
        {
            if(a&(1<<(u-1)))
            {
                res+=dfs(u-1,0,0);
            }
            else
            {
                res+=dfs(u-1,0,0);
                res+=dfs(u-1,1,0);
            }
        }
        else//下一位是0. 
        {
            if(a&(1<<(u-1)))
            {
                res+=dfs(u-1,0,0);
            }
            else
            {
                res+=dfs(u-1,0,0);
                res+=dfs(u-1,1,0);
            }
        }
    }if(!limit)    f[k][u]=res;
    return res;
}

int main()
{
    int T;cin>>T;
    while(T--)
    {
        cin>>a>>x;
        memset(f,-1,sizeof f);int dep=0;
        for(int i=30;i>=0;i--)
        {
            if(x>>i&1)    dep=max(dep,i);
        }
        if(a&(1<<dep))
        {
            printf("%d\n",dfs(dep,0,0)-1);
        }
        else
        {
            printf("%d\n",dfs(dep,0,0)+dfs(dep,1,1)-1);
        }
    }
    return 0;
}

B.A + B

模拟..

#include <bits/stdc++.h>
using namespace std;
char res[6][1000];
map<string,int>mp = {
    {"..#..#..#..#..#",1},
    {"###..#####..###",2},
    {"###..####..####",3},
    {"#.##.####..#..#",4},
    {"####..###..####",5},
    {"####..####.####",6},
    {"####.##.#..#..#",7},
    {"####.#####.####",8},
    {"####.####..####",9},
    {"####.##.##.####",0},
    {"....#.###.#....",-1}
};
map<int,string>mp2;
int main()
{
    ios; 
    for(auto it:mp)
    {
        mp2[it.second] = it.first;
    }
    int t;
    for(cin>>t;t;t--)
    {
        int n=5;
        string raw[6]={};
        for(int i = 1;i<=n;i++)cin>>raw[i];
        n=raw[1].size();
        int cnt=1+(n-3)/4;
        ll ans=0,tmp=0;
        for(int i=1;i<=cnt;i++)
        {
            string que = "";
            for(int y = 1;y <= 5;y++)
                for(int j = 1;j <= 3;j++)
                {
                    int x = (i - 1)*4 + j;
                    que += raw[y][x-1];
                }
            if(mp[que]==-1)
            {
                ans+=tmp;
                tmp=0;
            }
            else
            {
                tmp*=10;
                tmp+=mp[que];
            }
        }
        ans+=tmp;
        cnt=0;
        ll ans2=ans;
        vector<int>tmp3 = {};
        while(ans2)
        {
            cnt++;
            tmp3.push_back(ans2%10);
            ans2 /= 10;

        }
        reverse(tmp3.begin(),tmp3.end());
        memset(res,0,sizeof res);
        for(int i = 1;i <= cnt;i++)
        {
            string u = mp2[tmp3[i-1]];
            for(int y = 1;y <= 5;y++)
            {
                for(int j = 1;j <= 3;j++)
                {
                    int x = (i-1)*4+j;
                    char now = u[(y-1)*3 + j - 1];
                    res[y][x] = now;
                }
            }
            for(int y = 1;y <= 5;y++)
            {
                res[y][i*4] = '.';
            }
        }
        n=(cnt-1)*4+3;
        for(int y=1;y<=5;y++)
        {
            for(int i=1;i<=n;i++)    cout<<res[y][i];
            cout << endl;
        }
        if(t)    cout<<'\n';
    }
    return 0;
}

C.图像存储

把dfs序当成哈希值,然后随便选个base和mod都能过.

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
char s[N][N];
int n,m;
bool vis[N][N];
int hx=0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
const int base=131;
const int mod=1e9+7;
void dfs(int x,int y)
{
    if(x>n||x<1||y>m||y<1||vis[x][y]||s[x][y]=='0')    return;
    vis[x][y]=true;
    for(int i=0;i<4;i++)
    {
        dfs(x+dx[i],y+dy[i]);
        hx=(hx*base%mod+5)%mod;
    }hx=(hx*base%mod+13)%mod;
}
map<int,bool>mp;
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0&&m==0)    break;
        mp.clear();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                vis[i][j]=false;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",s[i]+1);
        }int res=0,ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(s[i][j]=='1'&&!vis[i][j])
                {
                    res++;
                    hx=0;
                    dfs(i,j);
                    if(!mp[hx])    ans++,mp[hx]=true;
                }    
            }
        }    
        printf("%d %d\n",res,ans);
    }
    return 0;
}

D. 坐标计数

看下样例就知道是面积了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        ll x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<(y2-y1+1)*(x2-x1+1)<<'\n';
    }
    return 0;
}

E.解方程

ax+by=xy->y=ax/(x-b)=(a(x-b)+ab)/(x-b)->y=a+ab/(x-b).然后x,y要是正整数,所以x-b>0的,然后就是看a*b的因子数了.
然后就是质因子数量+1的乘积,可以理解为选0-n个.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    for(cin>>T;T;T--)
    {
        int ansa,ansb;
        int a,b;cin>>a>>b;
        map<int,int>cnt;
        for(int i=2;i*i<=a;i++)
        {
            while(a%i==0)    cnt[i]++,a/=i;
        }if(a!=1)    cnt[a]++;
        for(int i=2;i*i<=b;i++)
        {
            while(b%i==0)    cnt[i]++,b/=i;
        }if(b!=1)    cnt[b]++;
        int ans=1;
        for(auto x:cnt)
        {
            ans*=(x.second+1);
        }cout<<ans<<'\n';
    }
    return 0;
}

F.消减整数

开始看这题的时候就读错了,读对了之后...emmm.暴力算一下就好了.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    for(cin>>T;T;T--)
    {
        int n;int x=1;cin>>n;
        while(n-x>=0)    n-=x,x++;
        for(int i=1;;i++)
        {
            if(i*n%x==0)
            {
                cout<<i<<'\n';break;
            }
        }
    }
    return 0;
}

G.简单题的逆袭

注意爆ll(可以开int128),然后卡精度,不能直接log2之类的,只能模拟取log的过程.我被这题wa傻了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+65;
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        if(x<=1||!y)
        {
            puts("-1");
        }
        else 
        {
            int Ans=0;
            while(y)
            {
                y/=x;
                Ans++;
            }
            cout<<Ans-1<<endl;
        }
    }    
    return 0;
}

H.对称之美

遍历这个串以及和它对称的那个串是不是存在相同的即可.

#include <bits/stdc++.h>
using namespace std;
const int N=105,M=27;
bool f[M];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        string s[N];
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++)    cin>>s[i];
        bool flag=true;
        for(int i=1;i<=n/2;i++)
        {
            memset(f,false,sizeof f);
            for(int k=0;k<s[i].size();k++)
            {
                f[s[i][k]-'a']=true;
            }
            int j=n-i+1;bool fl=false;
            for(int k=0;k<s[j].size();k++)
            {
                if(f[s[j][k]-'a'])    fl=true;
            }if(!fl)    flag=false;
        }
        if(flag)    puts("Yes");
        else        puts("No");
    }
    return 0;
}

I.非对称之美

注意aaaaa这种情况就好了.

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+65;
char s[N];
int main()
{
    bool flag=true;int n;
    scanf("%s",s+1);n=strlen(s+1);
    for(int i=1;i<=n/2;i++)
    {
        if(s[i]!=s[n-i+1])    flag=false;
    }int len=0;
    if(flag)
    {
        bool f=true;
        for(int i=2;i<=n;i++)
            if(s[i]!=s[i-1])    f=false;
        if(f)    cout<<0<<endl;
        else    cout<<n-1<<endl;    
    }
    else        cout<<n<<endl;
    return 0;
}

J.排列算式

贪心的消就可以了...理性的把-3,3消完之后,其他一定是可以消掉的.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int cnt[8];//-3 -2 -1 1 2 3
        memset(cnt,0,sizeof cnt);
        int sum=0;int n;scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int x;cin>>x;
            if(x==-3)         cnt[1]++,sum-=3;//-3
            else if(x==-2)    cnt[2]++,sum-=2;//-2
            else if(x==-1)    cnt[3]++,sum-=1;//-1
            else if(x==1)     cnt[4]++,sum+=1;//1
            else if(x==2)     cnt[5]++,sum+=2;//2
            else if(x==3)     cnt[6]++,sum+=3;//3
        }
        if(sum>3||sum<0)    puts("No");
        else
        {
            //先把-3消掉.
            //3 22-1 12 111
            int num=cnt[1];
            for(int i=1;i<=num;i++)
            {
                if(cnt[6])                    cnt[1]--,cnt[6]--;
                else if(cnt[5]>=2&&cnt[3])    cnt[1]--,cnt[3]--,cnt[5]-=2;
                else if(cnt[4]&&cnt[5])       cnt[1]--,cnt[4]--,cnt[5]--;
                else if(cnt[4]>=3)            cnt[1]--,cnt[4]-=3;
            }
            //再把3消掉.
            //-3 -2-21 -1-2 -1-1-1
           // cout<<cnt[2]<<' '<<cnt[3]<<endl;
            num=cnt[6];
            for(int i=1;i<=num;i++)
            {
                if(cnt[1])                      cnt[6]--,cnt[1]--;
                else if(cnt[2]>=2&&cnt[4])    cnt[6]--,cnt[2]-=2,cnt[4]--;
                else if(cnt[2]&&cnt[3])       cnt[6]--,cnt[2]--,cnt[3]--;
                else if(cnt[3]>=3)            cnt[6]--,cnt[3]-=3;
            }
            if(cnt[1]||cnt[6]>1)    puts("No");
            else                    puts("Yes");
        }
    }
    return 0;
}

0条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐