本文主要是介绍2022牛客寒假算法基础集训营，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

@

• 前言
• A 智乃的Hello XXXX
  • 题解
  • 代码
• B 智乃买瓜
  • 题解/思路
  • 代码
• D 智乃的01串打乱
  • 题解/思路
  • 代码
• E智乃的数字积木(easy version)
  • 题解/思路
  • 代码
• G智乃的树旋转(easy version)
  • 题解/思路
  • 代码
• I 智乃的密码
  • 题解/思路
  • 代码
• L 智乃的数据库
  • 题解/思路
  • 代码

前言

本人菜鸡一个，写到一半吃饭去了(不吃饭后面的题也写不出来...),后续会补题
另附官方题解

A 智乃的Hello XXXX

题解

没啥说的直接输出

代码

print("hello ")

B 智乃买瓜

题解/思路

使用的算法：简单dp，类似于01背包（跟第一场的类似）。
定义状态：f(i,j)代表前i种瓜组成重量为j的方案数
状态转移方程

f(i,j)=f(i-1,j)+f(i-1,j-a[i]/2)+f(i,j-a[i])

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
const int p=1e9+7;
int a[N],dp[N][N];
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(j>=a[i])
                dp[i][j]=(dp[i-1][j-a[i]]+dp[i-1][j-a[i]/2]+dp[i-1][j])%p;
            else if(j>=a[i]/2)
                dp[i][j]=(dp[i-1][j-a[i]/2]+dp[i-1][j])%p;
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    for(int i=1;i<=m;i++)
        cout<<dp[n][i]<<" ";
    return 0;
}

（滚动数组优化）

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
const int p=1e9+7;
int a[N],dp[N];
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dp[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=a[i]/2;j--)
        {
            //dp[j]=(dp[j-a[i]]+dp[j-a[i]/2]+dp[j])%p;
            if(j>=a[i])
                dp[j]=(dp[j-a[i]]+dp[j-a[i]/2]+dp[j])%p;
            else if(j>=a[i]/2)
                dp[j]=(dp[j-a[i]/2]+dp[j])%p;
        }
    }
    for(int i=1;i<=m;i++)
        cout<<dp[i]<<" ";
    return 0;
}

D 智乃的01串打乱

题解/思路

直接找到第一个0和第一个1交换位置即可

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n;
    string s;
    cin>>n>>s;
    int x,y;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='0'){x=i;break;}
    }
    for(int i=0;i<n;i++)
    {
        if(s[i]=='1'){y=i;break;}
    }
    swap(s[x],s[y]);
    cout<<s<<endl;
    return 0;
}

E智乃的数字积木(easy version)

题解/思路

简单题，直接分段排序，找到相同颜色的块然后排序
因为段与段之间不相交，则每次排序复杂度为O(nlog n)
还有一点就是大数取模的思路：
设x=abcd(分别是千，百，十，个位上的数)
x%p=a1000%p+b100%p+c10%p+d%p
=(((((a%p)10+b)%p10+c)%p*10)+d)%10

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int col[N];
char s[N];
const int p=1e9+7;
int MOD(string str)
{
    int len=str.length();
    int s=0;
    for(int i=0; i<len; i++)
    {
        s=s*10+str[i]-'0';
        s=s%p;
    }
    return s;
}
bool cmp(char a,char b)
{
    return a>b;
}
signed main()
{
    int n,m,k;
    cin>>n>>m>>k;
    cin>>s;
    for(int i=0;i<n;i++)
        cin>>col[i];
    for(int i=0;i<n;i++)
    {
        int j=i+1;
        while(col[j]==col[i])
        {
            j++;
            if(j==n){break;}
        }
        //cout<<i<<" "<<j<<endl;
        sort(s+i,s+j,cmp);
        i=j-1;
    }
    cout<<MOD(s)<<endl;
    while(k--)
    {
        int p,q;
        cin>>p>>q;
        for(int i=0;i<n;i++)
            if(col[i]==p)col[i]=q;
        for(int i=0;i<n;i++)
        {
            int j=i+1;
            while(col[j]==col[i])
            {
                j++;
                if(j==n){break;}
            }
            sort(s+i,s+j,cmp);
            i=j-1;
        }
        cout<<MOD(s)<<endl;
    }
    return 0;
}

G智乃的树旋转(easy version)

题解/思路

看题看题看题，题里有答案(看了n遍才明白的我是真的fw)
如果你看懂了的话你就会发现
当两棵树的两个节点互为父子关系的时候，输出父亲节点即可

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
struct tree
{
    int fa;
    int l,r;
}t1[N],t2[N];
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        t1[i].l=l;
        t1[i],r=r;
        t1[l].fa=i;
        t1[r].fa=i;
    }
    for(int i=1;i<=n;i++)
    {
        int l,r;
        cin>>l>>r;
        t2[i].l=l;
        t2[i],r=r;
        t2[l].fa=i;
        t2[r].fa=i;
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(t1[i].fa==j&&t2[j].fa==i)
            {
                cout<<"1"<<endl;
                cout<<j<<endl;
                return 0;
            }
        }
    }
    cout<<0<<endl;
    return 0;
}

I 智乃的密码

题解/思路

题目要求我们找到包含三种类型的串，且长度∈[L,R]
设f(x)是每一个x位置上对应的f(x),区间[x,f(x)]满足题目要求，且区间[x,f(x)-1]不满足要求，(即每一个i对应的最小满足条件的j)
可以发现对于每一个j>i都有f(j)>=f(i)，具有单调性
这思路不就来了，二分分分~~~~
当然双指针(尺取)的方法更简单
但个人总想写二分(感觉更高端，bug更多....)
尺取和的思路都是找到每一个x位置对应的f(x)，然后算方案数

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
char s[N];
int a[N],b[N],c[N],d[N];
bool check(int l,int r)
{
    int x=a[r]-a[l-1],y=b[r]-b[l-1],z=c[r]-c[l-1],p=d[r]-d[l-1];
    if((x>=1&&y>=1&&z>=1)||(x>=1&&y>=1&&p>=1)||(y>=1&&z>=1&&p>=1)||(x>=1&&p>=1&&z>=1))
        return 1;
    return 0;
}
signed main()
{
    int n,L,R;
    cin>>n>>L>>R>>s+1;
    for(int i=1;i<=n;i++)
    {
        a[i]=a[i-1];
        b[i]=b[i-1];
        c[i]=c[i-1];
        d[i]=d[i-1];
        if(s[i]>='A'&&s[i]<='Z')
            a[i]++;
        else if(s[i]>='a'&&s[i]<='z')
            b[i]++;
        else if(s[i]>='0'&&s[i]<='9')
            c[i]++;
        else 
            d[i]++;
        //cout<<a[i]<<" "<<b[i]<<' '<<c[i]<<' '<<d[i]<<endl;
    }
    int ans=0;
    for(int i=1;i<=n-L+1;i++)
    {
        int l=min(i+L-1,n),r=min(n,i+R-1);
        int y=r;
        while(l<r)
        {
            int mid=l+r>>1;
            if(check(i,mid))
                r=mid;
            else
                l=mid+1;
        }
        if(!check(i,l))continue;//没有满足题意的
        ans+=y-l+1;
    }
    cout<<ans<<endl;
    return 0;
}

L 智乃的数据库

题解/思路

因为题目的数据范围很小
所以我直接手写排序+去重(代码很丑，我自己都不想看，建议别看)

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
string s[1010];
int a[1010][1010];
char sql[50010],len;
map<string,int> q;
bool vis[1010];
struct xx
{
    int a[1010],len;
}p[1010];
bool cmp(xx a,xx b)
{
    for(int i=0;i<a.len;i++)
    {
        if(a.a[i]==b.a[i])continue;
        return a.a[i]<b.a[i];
    }
    return 0;
}
bool xx(xx a,xx b)
{
    for(int i=0;i<a.len;i++)
    {
        if(a.a[i]!=b.a[i])return 0;
    }
    return 1;
}
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>s[i];
        q[s[i]]=i;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    getchar();
    scanf("SELECT COUNT(*) FROM Table GROUP BY ");
    len=0;
    int o=0;
    while(cin>>sql[len])
    {
        if(sql[len]==',')
        {
            sql[len]='\0';
            string ss=sql;
            vis[q[ss]]=1;
            len=0;
            o++;
            continue;
        }
        if(sql[len]==';')
        {
            sql[len]='\0';
            string ss=sql;
            vis[q[ss]]=1;
            len=0;
            o++;
            break;
        }
        len++;
    }
    len=0;
    for(int i=1;i<=n;i++)
    {
        int len=0;
        for(int j=1;j<=m;j++)
        {
            if(vis[j])
            {
                p[i].a[len++]=a[i][j];
            }
        }
        p[i].len=o;
    }
    sort(p+1,p+n+1,cmp);
    int ans=1,x=1;
    for(int i=2;i<=n;i++)
    {
        if(!xx(p[i],p[i-1]))
        {
            ans++;
        }
    }
    cout<<ans<<endl;
    for(int i=2;i<=n;i++)
    {
        if(xx(p[i],p[i-1]))//相等
        {
            x++;
        }
        else
        {
            cout<<x<<" ";
            x=1;
        }
    }
    cout<<x<<endl;
    return 0;
}

这篇关于2022牛客寒假算法基础集训营的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！