2024常州day5（8.16）

Posted on By 林 珂涵 2024常州day5（8.16）无评论

1.比赛

今天的比赛，我的成绩实在是太“理想”了
很难想象，我是怎么做到，
打了4题，4题全四十分的，真的太平均了

1.paint

这道题很简单
但是我当时不知道哪根筋搭错了
题目说：最中间的是第一个字符
我自动转化成了最外圈的是第一个字符（不知道我的脑回路是怎么长的，成功痛失40分
还有，前面竟然有两个样例是n=1的情况
我根本没判断，有没了20分
代码如下：

#include
using namespace std;
int n;
char a,b;
int 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%4==3) swap(a,b);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if((i==1 && j==1) || (i==n && j==1) || (i==1 && j==n) || (i==n && j==n)) cout<<" ";
            else if((i==1 || i==n) || (j==1 || j==n)) cout<<a; 
            else if((i%2==1 && i=i && j<=n-i+1) cout<=(n+1)/2) && j>=n-i+1 && j<=i) cout<<a;
            else if((j%2==1 && j=j && i<=n-j+1) cout<=(n+1)/2) && i>=n-j+1 && i<=j) cout<<a;
            else cout<<b; 
        }
        cout<<endl;
    }
    return 0;
}

2.study

不知道又哪根筋搭错了，很成功的又拿了40分
怎么说，思路接近答案，但是又有点问题
代码如下：

#include
using namespace std;
int t,n,a[10005],b[10005];
int main()
{
    freopen("study.in","r",stdin);
    freopen("study.out","w",stdout);
    cin>>t;
    while(t--)
    {
        int f=0;
        memset(b,0,sizeof(b));
        cin>>n;
        for(int i=1;i>a[i];
            b[a[i]]++;
        }
        for(int i=1;in/2+n%2) f=1;
        }
    //  cout<<f<<endl;
        if(f==1) cout<<"N"<<endl;
        else cout<<"Y"<<endl;
    }
    return 0;
}

3.cat

这题我用了不像dp的dp打的
可以拿40分：
dp[i]表示在i之前（包括i）的猫咪最大快乐值
f表示选了多少只猫咪，sum_b是选择了猫咪的b[i]总和
转移方程：dp[i]=max(dp[i-1],dp[i-1]+a[i]-f*b[i]-sum_b)
但是它很明显的错了，
正解用贪心 + 枚举
枚举猫咪个数，然后用一个数组c[i]
记录如果选了x只猫，第i只猫的快乐度
然后再sort排序一下（用降序
然后把快乐度最高的x只猫咪加在一起为sum
每一次枚举：maxn=max(maxn,sum),并记录x
代码如下：

#include
using namespace std;
int n,a[1005],b[1005],c[1005],f,sum,maxn;
int cmp(int x,int y)
{
    return x>y;
}
int main()
{
    freopen("cat.in","r",stdin);
    freopen("cat.out","w",stdout);
    cin>>n;
    for(int i=1;i>a[i];
    for(int i=1;i>b[i];
    for(int i=1;i<=n;i++)
    {
        sum=0;
        for(int j=1;j<=n;j++) c[j]=a[j]-b[j]*(i-1);
        sort(c+1,c+n+1,cmp);
    //  for(int j=1;j<=n;j++) cout<<c[j]<<" ";
        for(int j=1;j=maxn) 
        {
            maxn=sum;
            f=i;
        }
    } 
    cout<<maxn<<endl<<f;
    return 0;
}

4.way
我用的是dfs
赛时d数组开太小了，RE了
还有忘记判断它没有回到家要输出No什么什么的
改完后就70了，但是还有一个，他可以通过传送门在回去的我没写
dfs 70分代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,tj[30],d[110][110],ans;//tj是统计字母个数,csm是传送门
struct csm
{
    int x1,y1,x2,y2;
}csm[30];
char a[110][110];
int xi[5]={0,0,0,1,-1};
int yi[5]={0,1,-1,0,0};
void dfs(int x,int y,int k)
{
    int new_x,new_y;
    d[x][y]=k;
    for(int i=1;i<=4;i++)
    {
        new_x=x+xi[i];
        new_y=y+yi[i];
        if(a[new_x][new_y]==&#039;0&#039; && new_x>=1 && new_x<=n && new_y>=1 && new_y<=m && k+1<d[new_x][new_y]) dfs(new_x,new_y,k+1);
        else if(a[new_x][new_y]>=&#039;A&#039; && a[new_x][new_y]<=&#039;Z&#039; && k+1<d[new_x][new_y])
        {  
            ans=a[new_x][new_y]-&#039;A&#039;+1;
            d[new_x][new_y]=k+1;
            if(csm[ans].x1==new_x && csm[ans].y1==new_y) dfs(csm[ans].x2,csm[ans].y2,k+1);
            else dfs(csm[ans].x1,csm[ans].y1,k+1);
        }
    }
}
int main()
{
    freopen("way.in","r",stdin);
    freopen("way.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            if(a[i][j]>=&#039;A&#039; && a[i][j]<=&#039;Z&#039;)
            {
                if(tj[a[i][j]-&#039;A&#039;+1]==1) csm[a[i][j]-&#039;A&#039;+1].x2=i,csm[a[i][j]-&#039;A&#039;+1].y2=j;
                else tj[a[i][j]-&#039;A&#039;+1]++,csm[a[i][j]-&#039;A&#039;+1].x1=i,csm[a[i][j]-&#039;A&#039;+1].y1=j;
            }
            d[i][j]=INT_MAX;
        } 
    }
    if((a[n-1][m]==&#039;1&#039; && a[m-1][n]==&#039;1&#039; && a[n][m]==&#039;0&#039;) || a[n][m]==&#039;1&#039; || a[1][1]==&#039;1&#039;){
        cout<<"No Solution.";
        return 0;
    } 
    if(a[1][1]>=&#039;A&#039; && a[1][1]<=&#039;Z&#039;)
    {
        ans=a[1][1]-&#039;A&#039;+1;
        dfs(csm[ans].x2,csm[ans].y2,0);
    }
    dfs(1,1,0);
    if(d[n][m]==INT_MAX)cout<<"No Solution.";
    else cout<<d[n][m];
    return 0;
}

BFS(不知道为什么只有20分：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[110][110],tj[30];
struct node
{
    int x,y,k;
}csm[30][3];
queue<node> q; 
int xi[5]={0,0,0,1,-1};
int yi[5]={0,1,-1,0,0};
int main()
{
    freopen("way.in","r",stdin);
    freoepn("way.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            if(a[i][j]>=&#039;A&#039; && a[i][j]<=&#039;Z&#039;)
            {
                tj[a[i][j]-&#039;A&#039;+1]++;
                csm[a[i][j]-&#039;A&#039;+1][tj[a[i][j]-&#039;A&#039;+1]].x=i,csm[a[i][j]-&#039;A&#039;+1][tj[a[i][j]-&#039;A&#039;+1]].y=j;
            }
        }
    }
    q.push((node){1,1,0});
    while(!q.empty())
    {
        node t=q.front();
        if(a[t.x][t.y]>=&#039;A&#039; && a[t.x][t.y]<=&#039;Z&#039;)
        {
            int ans=a[t.x][t.y]-&#039;A&#039;+1;
            if(t.x==csm[ans][1].x && t.y==csm[ans][1].y)
               t.x=csm[ans][2].x,t.y=csm[ans][2].y;
            if(t.x==csm[ans][2].x && t.y==csm[ans][2].y)
               t.x=csm[ans][1].x,t.y=csm[ans][1].y;
        }
        if(t.x==n && t.y==m)
        {
            cout<<q.front().k;
            return 0;
        }
        for(int i=1;i<=4;i++)
        {
            int tx=t.x+xi[i];
            int ty=t.y+yi[i];
            if(a[tx][ty]!=&#039;1&#039; && tx>=1 && tx<=n && ty>=1 && ty<=m)
            {
                q.push((node){tx,ty,q.front().k+1});
                a[tx][ty]=&#039;1&#039;;
            }
        }
        q.pop();
    }
    cout<<"No Solution.";
    return 0;
}

2.贪心

我不知道该写点什么（so就不写了）

训练日志

发表回复