第七届"图灵杯"NEUQ-ACM程序设计竞赛

Myth丶恋晨 2023-06-18 09:58 11阅读 0赞

### 第七届"图灵杯"NEUQ-ACM程序设计竞赛 ###

*   *   *  Awen的一卡通
         *   *  参考代码
         *  跳格子
         *   *  参考代码
         *  Iris天下第一
         *   *  参考代码
         *  爱做笔记的Awen
         *   *  参考代码
         *  计分板
         *   *  参考代码
         *  我的梦想是世界和平！
         *   *  参考代码
         *  溜圈圈
         *   *  参考代码
         *  Thursday out
         *   *  参考代码

### Awen的一卡通 ###

Awen是个很粗心的人，这天他在买饭的时候，发现他的校园一卡通不见了。虽然他知道自己的一卡通应该落在了综合楼，但因为他实在太饿了，想赶紧吃到饭，所以他也可以去行政楼再补办一张一卡通。但他不知道自己究竟是去行政楼再回到原地更快，还是去综合楼再回到原地更快。不过因为补卡需要时间，如果他去选择行政楼的话，还需要在行政楼额外花费a分钟办理补卡。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]

#### 参考代码 ####

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=105;
    typedef pair<int,int> pa;
    int pos[4][2]={ { 1,0},{ -1,0},{ 0,1},{ 0,-1}};
    int n,m,a;
    char b[maxn][maxn],ch;
    int step[maxn][maxn];
    int sx,sy,xx,xy,zx,zy;
    queue<pa > q;
    
    void bfs(){ 
        int nx,x,y,ny;
        q.push(pa(sx,sy));
        while(!q.empty()){ 
            x=q.front().first;
            y=q.front().second;
            q.pop();
            for(int i=0;i<4;++i){ 
                nx=x+pos[i][0];
                ny=y+pos[i][1];
                if(nx<0||nx>=n||ny<0||ny>=m)continue;
                if(step[nx][ny]==-1&&b[nx][ny]!='*'){ 
                    step[nx][ny]=step[x][y]+1;
                    q.push(pa(nx,ny));
                }
            }
        }
    }   
    
    int main(){ 
        std::ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>n>>m;
        for(int i=0;i<n;++i){ 
            for(int j=0;j<m;++j){ 
                cin>>ch;
                if(ch=='s')sx=i,sy=j;
                else if(ch=='x')xx=i,xy=j;
                else if(ch=='z')zx=i,zy=j;
                b[i][j]=ch;
                step[i][j]=-1;
            }
        }
        bfs();
        cin>>a;
        if(step[xx][xy]*2+a<step[zx][zy]*2)cout<<"ying ying ying\n";
        else if(step[xx][xy]*2+a>step[zx][zy]*2)cout<<"wo tu le\n";
        else cout<<"awennb\n";
    }

### 跳格子 ###

从左到右有N个台阶，每个台阶的高度为Hi，开始你可以随意选择一个台阶作为初始起点  
，每次你可以向右边 移动，当且仅当右边的台阶比你现在所在的台阶高度低，问你最多可以移动多少次  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]

#### 参考代码 ####

//求连续的递减序列最大长度
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn= 200005;
    
    int a[maxn],d[maxn];
    
    int main(){ 
        int n,j=0;
        scanf("%d",&n);
        for(int i=0;i<n;++i){ 
            scanf("%d",&a[i]);
        }
        for(int i=1;i<n;++i){ 
            if(a[i]<a[i-1])d[i]=d[i-1]+1;
        }
        int m = 0;
        for(int i=0;i<n;++i)m=max(m,d[i]);
        printf("%d",m);
    }

### Iris天下第一 ###

Iris今年20岁了，她认为自己有至少20个男朋友是合情合理的。然而世上帅哥千千万，Iris纵有心网罗天下帅哥，可却没有那么多精力去维护她的后宫安宁。因此，Iris为了备战将要到来的面向对象程序设计期末考试，决定抛弃她的一些帅哥。  
已知Iris的后宫中有n个帅哥，而每天可以用来和帅哥聊天的精力为m。对于每个帅哥，有固定的帅气值和每天与其聊天所需要的花费精力值。请你帮Iris算一下，在抛弃掉一些帅哥以保证每天的精力值够用的情况下（也可能精力过剩而没有抛弃），她的后宫的帅气值总和最大时多少。

#### 参考代码 ####

//背包
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn= 100005;
    
    int w[maxn],v[maxn],dp[maxn];
    
    int main(){ 
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;++i)scanf("%d%d",&w[i],&v[i]);
        for(int i=0; i<n; i++)
        for(int j=k; j>=w[i]; j--)
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        printf("%d\n",dp[k]);
    }

### 爱做笔记的Awen ###

众所周知，Awen非常喜欢写一些心得笔记。这一天他又在写笔记了。已知他可进行如下操作：

Add x y\[1\]y\[2\]y\[3\]…y\[n\]  
在笔记最后添加x个字符，它们分别是y\[1\]y\[2\]y\[3\]…y\[n\] (每一个y\[i\]都是一个小写英文字母)；  
Del x  
删除掉笔记中最后写的x个字符；  
Copy  
复制当前写的所有笔记；  
Paste  
将当前复制的所有文字粘贴在笔记最后。

在写完笔记之后，Awen想知道自己究竟写下了什么，你能帮帮他吗？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 2]

#### 参考代码 ####

//直接字符串模拟即可
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn= 100005;
    
    char c[maxn];
    char d[200];
    char op[10];
    char co[maxn];
    
    int main(){ 
        int n,a,j=0,cj=0;
        scanf("%d",&n);
        for(int i=0;i<n;++i){ 
            scanf("%s",op);
            if(op[0]=='A'){ 
                scanf("%d %s",&a,d);
                for(int t=0;t<a;++t)c[j++]=d[t];
            }else if(op[0]=='C'){ 
                for(int t=0;t<j;++t)co[t]=c[t];
                cj=j;
            }else if(op[0]=='D'){ 
                scanf("%d",&a);j-=a;
            }else if(op[0]=='P'){ 
                for(int t=0;t<cj;++t)c[j++]=co[t];
            }
        }
        c[j]=0;
        printf("%s\n",c);
    }

### 计分板 ###

一个游戏由N个玩家玩，编号从1到N。在游戏开始时，每个玩家初始分数都为K。 当一个玩家正确地回答了一 个问题，其他N-1个玩家每人都会-1分。 在游戏结束时，得分为0分或更低的玩家将被淘汰，剩下的玩家存活下来。 在一场游戏中，玩家总共给出Q个正确答案，其中第i个答案由玩家Ai给出。 请你编写一个程序来确定这N 个玩家是否能在游戏中幸存下来。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 3]

#### 参考代码 ####

//这题的输出数据案例有误，最后有一个空格
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 300005;
    int a[maxn]={ 0};
    
    int main(){ 
       int n,k,q,d;
       scanf("%d%d%d",&n,&k,&q);
       for(int i=0;i<q;++i){ 
           scanf("%d",&d);
           a[d]++;
       }
       for(int i=1;i<=n;++i){ 
           if(k>q-a[i]){ 
               printf("Yes ");
           }else printf("No ");
       };
    }

### 我的梦想是世界和平！ ###

恭喜FPX获得S9全球总决赛冠军！

虽然在征战S9的各大战队中，蓝公主被公认为技术最差的辅助，但是蓝公主凭借姣好的外型，仍然拥有数量可观的妈妈粉。所谓道不同，不相为谋，真正的LPL粉丝并不愿意和妈妈粉一同观看比赛。所幸，梅赛德斯奔驰会展中心提供了三个观战坐席区域，避免双方见面引发冲突。

已知今天前往观战的妈妈粉有a人，普通LPL粉丝b人，好斗的LPL粉丝c人，妈妈粉与好斗的LPL粉丝在同一个观战坐席区域相遇会引发冲突，而普通的LPL粉丝无论与妈妈粉还是与好斗的LPL粉丝在一起均可以和平共处。请你帮助主办方计算在不发生冲突的情况下，人数最多的观战坐席区域最少有多少人。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 4]

#### 参考代码 ####

输入数据：

5
    3 5 7
    4 8 4
    13 10 13
    1000 1000 1000
    13 22 7

/* 人数最多的观战坐席区域最少有多少人: 在各种的情况下，三个区域中人数最少 且大于其他种情况下 区域中人数最少数，的这种情况下，区域中人数最多 */
    #include<bits/stdc++.h>
    using namespace std;
    
    int main(){ 
        int t,a,b,c,j,d;
        int Min[3];
        scanf("%d",&d);
        while(d--){ 
            scanf("%d%d%d",&a,&b,&c);
            if(c>a)swap(a,c);
            Min[0]=a/2;Min[1]=a-a/2;Min[2]=c;
            for(int i=1;i<=b;++i){ 
                for( t=1,j=0;t<3;++t)if(Min[t]<Min[j])j=t;
                Min[j]++;
            }
            for(t=1,j=0;t<3;++t)if(Min[t]>Min[j])j=t;
            printf("%d\n",Min[j]);
        }
    }

### 溜圈圈 ###

BigSheep总是喜欢溜圈，但是他有几个原则：

只能向左转，且不能在同一个地方多次左转。  
每次只走不同的圈。  
每次走圈走遍整个区域，同一个点只去一次，起点不一定需要等于终点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 6]

样例输入

1
    2 2

样例输出

#### 参考代码 ####

/* 这题属于找规律： 很容易看出当只有1行或者1列的时候 情况为2，（1*1时才为1）； 如果是2*x(x>=2)的话，那么意味着，这个图每个点出发都可以满足条件。 其他情况，除去四个角之外，还可以从中间开始到其他节点结束。 */
    #include<bits/stdc++.h>
    using namespace std;
    
    int main(){ 
        int t,n,m;
        cin>>t;
        while(t--){ 
            cin>>n>>m;
            if(n<m) swap(n,m);
            if(m==1){ 
                if(n==1)cout<<"1\n";
                else cout<<"2\n";
            }else if(m==2) cout<<n*m<<"\n";
            else cout<<2*(n+m-2)<<"\n";
        }
    }

### Thursday out ###

11月17日，Zsmj，BigSheep和PerpEternal决定退役了，但是生活需要仪式感，所以他们决定一起去吃顿好的，作为纪念。

三个人在街头找到了一家自助餐厅，刚进餐厅，PerpEternal和Zsmj就摊在椅子上，并指使BigSheep去拿吃的，BigSheep也想摊在椅子上，但是因为队内地位实在是太低，所以只能屈服于淫威，老老实实的去拿吃的，餐厅提供的食物可以当做一个序列，每个食物拥有一个营养值ai ，BigSheep知道仨人的食量至少需要营养值为x的食物才能吃饱，但是BigSheep也不想多次去拿食物，所以他打算一次拿把一个区间的食物全部拿了，当BigSheep把食物带回到位置上时，PerpEternal突然发问：你俩曾经身为一个ACM选手，能不能算出有多少种方案能够让咱们仨吃饱。但是BigSheep和Zsmj太饿了，所以只好打电话求助亲爱的参赛选手，你能帮帮他俩吗，PerpEternal说了，算不出来不让他俩吃饭。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 7]  
样例输入

2
    5 5
    1 1 1 1 1
    5 2
    1 1 1 1 1

样例输出

1
    10

参考官方解法  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 8]

#### 参考代码 ####

#include<bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5+4;
    const int mod = 1e9+7;
    int a[maxn],sum[maxn]={ 0};
    int main(){ 
        int t,n,x;
        scanf("%d",&t);
        while(t--){ 
            scanf("%d%d",&n,&x);
            for(int i=1;i<=n;++i){ 
                scanf("%d",&a[i]);
                sum[i]=sum[i-1]+a[i];
            }
            int ans=0;
            for(int i=1;i<=n;++i){ 
                int l=i,r=n+1,tmp=n+1,mid;
                while(l<r){ 
                    mid=(l+r)>>1;
                    if(sum[mid]-sum[i-1]>=x)r=mid,tmp=mid;
                    else l=mid+1;
                }
                ans=(n-tmp+1+ans)%mod;
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191203173623409.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191201213840315.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191201214349219.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191201215150694.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191205161454732.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2019120516191043.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191205161938630.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2019120516373255.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20191205164350822.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMTQ2NjUw,size_16,color_FFFFFF,t_70