2022牛客寒假算法基础集训营

前言A 智乃的Hello XXXX

题解代码 B 智乃买瓜

题解/思路代码 D 智乃的01串打乱

题解/思路代码 E智乃的数字积木(easy version)

题解/思路代码 G智乃的树旋转(easy version)

题解/思路代码 I 智乃的密码

题解/思路代码 L 智乃的数据库

题解/思路代码
题目链接

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

没啥说的直接输出

print("hello ")

使用的算法：简单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 
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< 
（滚动数组优化）
 
#include 
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< 
D 智乃的01串打乱 
题解/思路 
直接找到第一个0和第一个1交换位置即可
 
代码 
#include 
using namespace std;
#define int long long
signed main()
{
    int n;
    string s;
    cin>>n>>s;
    int x,y;
    for(int i=0;i 
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 
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; ib;
}
signed main()
{
    int n,m,k;
    cin>>n>>m>>k;
    cin>>s;
    for(int i=0;i>col[i];
    for(int i=0;i>p>>q;
        for(int i=0;i 
G智乃的树旋转(easy version) 
题解/思路 
看题看题看题，题里有答案(看了n遍才明白的我是真的fw)
 如果你看懂了的话你就会发现
 当两棵树的两个节点互为父子关系的时候，输出父亲节点即可
 
代码 
#include
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"< 
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 
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<
    }
    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>1;
            if(check(i,mid))
                r=mid;
            else
                l=mid+1;
        }
        if(!check(i,l))continue;//没有满足题意的
        ans+=y-l+1;
    }
    cout< 
L 智乃的数据库 
题解/思路 
因为题目的数据范围很小
 所以我直接手写排序+去重(代码很丑，我自己都不想看，建议别看)
 
代码 
#include 
using namespace std;
#define int long long
const int N=1e5+10;
string s[1010];
int a[1010][1010];
char sql[50010],len;
map q;
bool vis[1010];
struct xx
{
    int a[1010],len;
}p[1010];
bool cmp(xx a,xx b)
{
    for(int i=0;i>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]='';
            string ss=sql;
            vis[q[ss]]=1;
            len=0;
            o++;
            continue;
        }
        if(sql[len]==';')
        {
            sql[len]='';
            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<