2024常州暑假集训Day5——8.16

早上8：00整，我们又又又来到了这与我们“亲爱”的Quanzhou No.1 High School有长达20个英文字符的最长公共子序列的Changzhou No.1 High School。

上午

220/400(第九)

考试分析（见下）

下午

讲了贪心，之前也学过了。（具体就不在此说了）

考试

第一题：图案计划 (paint)

思路

O(n^2)：

a[i][j]的圈数是min(i,j,n+1-i,n+1-j)(具体见螺旋方阵）
所以只需判断一下圈数的奇偶性就好了。

核心代码

signed main(){
    freopen("paint.in", "r", stdin);
    freopen("paint.out", "w", stdout);
    cin>>n;
    cin>>a>>b;
    if(n==1)
    {
        cout<<a;
        return 0;
    }
    if(((n-1)/2+1)%2==0)
    {
        swap(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if((i==1 && (j==1 || j==n)) || (i==n && (j==1 || j==n)))
            {
                cout<<" ";
                continue;
            }
            if(min(min(i,j),min(n+1-i,n+1-j))%2==1)
            {
                cout<<a;
            }
            else
            {
                cout<<b;
            }
        }
        cout<<endl;
    }
    return 0;
}

第二题：学习计划 (study）

思路

将数组a进行桶排，在判断一下没个数字有没有 （超过剩下的数字+n%2），超过了就输出N，都没超就输出Y

核心代码

signed main(){
    freopen("study.in", "r", stdin);
    freopen("study.out", "w", stdout);
    t=read();
    while(t--)
    {
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        n=read();
        bool f=true;
        for(int i=1;i<<=n;i++)
        {
            a[i]=read();
            b[a[i]]++;
        }
        int s=n%2;
        for(int i=1;in-b[i]+s)
            {
                f=false;
                break;
            }
        }
        if(f)
        {
            cout<<"Y"<<endl;
        }
        else
        {
            cout<<"N"<<endl;
        }
    }
    return 0;
}

第三题：猫咪计划 (cat)

思路

对取i[1,n]只猫进行求解，在取最大值就好了

核心代码

signed main(){
    freopen("cat.in", "r", stdin);
    freopen("cat.out", "w", stdout);
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=read();
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j=n-i+1;k--)
        {
            sum=sum+c[k];
        }
        if(sum>=ans)
        {
            ans=sum;
            x=i;
        }
    }
    cout<<ans<<endl<<x;
    return 0;
}

第四题：回家计划 (way)

思路

宽搜模板题，只需要注意细节就可以了。

核心代码

输入

signed main(){
    freopen("way.in", "r", stdin);
    freopen("way.out", "w", stdout);
    n=read(),m=read();
    for(int i=1;ia[i][j];
            if(a[i][j]>='A' && a[i][j]<='Z')
            {
                int x=a[i][j]-'A'+1;
                if(zb[x].a.x==0)
                {
                    zb[x].a.x=i;
                    zb[x].a.y=j;
                }
                else
                {
                    zb[x].b.x=i;
                    zb[x].b.y=j;
                }
            }
        }
    }

宽搜

   node x;
    x.x=1;
    x.y=1;
    x.bu=0;
    q.push(x);
    f[1][1]=true;
    while(!q.empty())
    {
        node y=q.front();
        q.pop();
        for(int i=1;i<=4;i++)
        {
            int tx=y.x+fx[i];
            int ty=y.y+fy[i];
            if(!f[tx][ty] && a[tx][ty]!='1' && tx=1 && ty=1)
            {
                f[tx][ty]=true;
                if(a[tx][ty]=='0')
                {
                    node xx;
                    xx.bu=y.bu+1;
                    xx.x=tx;
                    xx.y=ty;
                    q.push(xx); 
                    if(tx==n && ty==m)
                    {
                        cout<<xx.bu;
                        return 0;
                    }
                }
                else
                {
                    int b=a[tx][ty]-'A'+1;
                    if(tx==zb[b].a.x && ty==zb[b].a.y)
                    {
                        tx=zb[b].b.x;
                        ty=zb[b].b.y;
                    }
                    else
                    {
                        tx=zb[b].a.x;
                        ty=zb[b].a.y;
                    }
                    zb[b].n++;
                    f[tx][ty]=(bool)zb[b].n;
                    node xx;
                    xx.bu=y.bu+1;
                    xx.x=tx;
                    xx.y=ty;
                    q.push(xx);
                    if(tx==n && ty==m)
                    {
                        cout<<xx.bu;
                        return 0;
                    }
                }
            }
        }
    }
    cout<<"No Solution.";
    return 0;
}