辽宁省大学生程序设计竞赛赛后记录

发布于 2023-04-25  565 次阅读


A 伟大奋斗(签到题)

应该是响应20大,所以一道非常简单的签到题

B 可莉的五子棋(签到题,模拟)

链接:https://ac.nowcoder.com/acm/contest/43937/B

可莉最近沉迷于蒙德五子棋,她在棋盘上放了一些棋子。

蒙德五子棋的规则如下。

给定一个n*m的棋盘。棋盘上有两种棋子“1”和“2”,其中每种棋子分别计算得分。

假如相同种类的五个棋子连成相邻的一行,一列,或斜对角线的情况,每有五个这样的棋子,该种类棋子加1分。

可莉已经把她的棋子都摆在了棋盘上。

但是可莉不太聪明的样子,她希望你,聪明的旅行者,告诉她,她两种棋子的得分。

解析:

一道正常逻辑的模拟,有人用搜索做,但我个人觉得搜索不是很合适,

直接模拟各个方向凑成五个就算一分,然后遍历矩阵,重点在于,该棋子向右成五连等于第五个棋子向左成五连所以最后,每个棋子只需要判断,上,右,左上,右上,四个方向就可以或者你也可以判断下,左,左下,右下这里需要注意一点就是,不要越界,要限制好范围,暴力模拟直接过。

#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[1005][1005];
bool shang(int i,int j){
//cout<<endl<<s[i][j]<<s[i-1][j]<<s[i-2][j]<<s[i-3][j]<<s[i-4][j]<<endl;
if(s[i][j]==s[i-1][j]&&s[i][j]==s[i-2][j]&&s[i][j]==s[i-3][j]&&s[i][j]==s[i-4][j]){
// cout<<"成功一次"<<endl;
return true;
}
return false;
}
bool zuoshang(int i,int j){
if(s[i][j]==s[i-1][j-1]&&s[i][j]==s[i-2][j-2]&&s[i][j]==s[i-3][j-3]&&s[i][j]==s[i-4][j-4]){
return true;
}
return false;
}
bool youshang(int i,int j){
if(s[i][j]==s[i-1][j+1]&&s[i][j]==s[i-2][j+2]&&s[i][j]==s[i-3][j+3]&&s[i][j]==s[i-4][j+4]){
return true;
}
return false;
}
bool you(int i,int j){
if(s[i][j]==s[i][j+1]&&s[i][j]==s[i][j+2]&&s[i][j]==s[i][j+3]&&s[i][j]==s[i][j+4]){
return true;
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
int result1=0;
int result2=0;
for(int i=0;i<n;i++){
cin>>s[i];
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i>=4){
if(shang(i,j)){
if(s[i][j]=='1'){
result1++;
}else if(s[i][j]=='2'){
result2++;
}
}
if(j>=4){
if(zuoshang(i,j)){
if(s[i][j]=='1'){
result1++;
}else if(s[i][j]=='2'){
result2++;
}
}
}
}
if(m-j>=5){
if(you(i,j)){
if(s[i][j]=='1'){
result1++;
}else if(s[i][j]=='2'){
result2++;
}
}
if(i>=4)
if(youshang(i,j)){
if(s[i][j]=='1'){
result1++;
}else if(s[i][j]=='2'){
result2++;
}
}

}
}
}
printf("%d %d",result1,result2);
return 0;
}

E 病毒危机(模拟)

链接:https://ac.nowcoder.com/acm/contest/43937/E

你是旅行者,由于未知原因,你穿越到了提瓦特,遇到了各种各样的角色,游历了风格各异的地方,成为了战力第一。但可怕的是,你为这个世界带来了一种本不属于这个世界的L病毒,这种L病毒传染性强,一旦这种病毒散播开来,后果不堪设想。

我们可以认为,如果旅行者去过一个地点,则到过该地点的人们全部都会被感染L病毒。现在找到了n个人(其中第1个人是旅行者,是初始感染了L病毒的人),分别得知了n个人到过的地方。注意,被旅行者感染的人没有感染别人的能力。你需要计算出最坏情况下,也就是最后的感染L病毒人数。

解析:

这题wa了两次不太都是细节格式问题,不太应该QAQ

第一个是感染者,他去过的地方,别人再去都会被感染,但是别人没有感染其他人的能力,所以也是一个非常简单的模拟,记录第一个人去过的地方,然后遍历其他人去过的地方,当检测到其他人去过第一个人去过的地方时,就记录一下,然后退出循环,因为此人已经被感染了,无需再往下判断,节省时间,就ac了

#include<bits/stdc++.h>
using namespace std;
map<int,int> p;
int main(){
int n,m;
scanf("%d%d",&n,&m);
int result=1;
int t;
scanf("%d",&t);
for(int i=0;i<t;i++){
int temp;
scanf("%d",&temp);
p[temp]++;
}
if(n==1){
printf("%d",result);
return 0;
}
n--;
while(n--){
int t2;
scanf("%d",&t2);
int s[t2];
//cout<<"t值"<<t2<<endl;
for(int i=0;i<t2;i++){
scanf("%d",&s[i]);
}
for(int i=0;i<t2;i++){
if(p[s[i]]>0){
// cout<<temp2<<"被感染"<<endl;
result++;
break;
}
}
}
printf("%d",result);
return 0;
}

F 互质(找规律)

链接:https://ac.nowcoder.com/acm/contest/43937/F 来源:牛客网

琴团长提出了T次询问,每次询问给出一个正整数n,询问雷泽是否存在一个正整数x,满足x大于等于n/4向上取整,小于等于n/2向下取整,且x与n互质。

雷泽并不会数学,于是便向你求助。

解析:

这道题看别人wa了那么多次就能看出来不是暴力能过的,我个人当场分析是,因为他超时了,所以说明肯定找到最后那个数字了,又因为,只要输出一个就行,所以我从后面判断,然后判断区间发现如果是偶数的话,右区间肯定不行,那就右区间减一,然后举例子10以内的就有减一也不可以的,有一个6,他只能做到减一,所以特殊判断下,其他的那就再减二,判断一下。试了好多次没找到不符合条件的,然后一狠心试了下就过了,主要还是在能看出这道题肯定是一道规律题,不可能是从头到尾找,又因为肯定是有人从头到尾超时,所以从尾开始往前找。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
   ll t,n;
   scanf("%lld",&t);
   while(t--){
       scanf("%lld",&n);
       if(n==4){
           printf("1\n");
           continue;
      }
       if(n==6){
           printf("-1\n");
           continue;
      }
       if(__gcd(n/2,n)==1){
           printf("%lld\n",n/2);
      }else if(__gcd(n/2-1,n)==1){
           printf("%lld\n",n/2-1);
      }else if(__gcd(n/2-2,n)==1){
           printf("%lld\n",n/2-2);
      }else{
           printf("-1\n");
      }
  }
}

G 栈与公约数(模拟剪枝)

链接:https://ac.nowcoder.com/acm/contest/43937/G

初始有一个为空的栈,进行q次操作,操作分为以下四种:

1.在栈顶放入一个元素x

2.删除栈顶元素(数据保证此时栈内至少有一个元素)

3.查询栈顶元素

4.将栈顶的k个元素修改成他们的最大公约数(数据保证k不超过栈中元素数量)(比如栈内元素是4,2,将栈顶的2个元素修改成他们的最大公约数,栈内元素是2,2)

解析:

这道题开始暴力超时,但是找公约数实在没能力再优化,又过了那么多,所以我开始想的是把k存一下,只真正改一个数,如果他弹栈了,那就检测K,是否在他弹出前让他的后一个等于他,感觉思路没问题,但交了试了下还是超时,就没办法了,已经想放弃了,然后队员学弟比较Nice,他发现只要求出最大公约数是1了,那么所有的最大公约数只能是1,就没有必要再求下去了,然后加了个1的优化,就过了......(这时候已经封榜了,说实话这道题卡这么久,我心态已经有点崩了,但队员给力这道题过了,瞬间就活了,然后我就把F互质过了,封榜又过了两题)

#include<bits/stdc++.h>
using namespace std;
int s[200000];
int indext=-1;
int gcd(int a,int b){
   return b==0 ? a:gcd(b,a%b);
}
int main(){
   int q;
   scanf("%d",&q);
   while(q--){
       int op;
       scanf("%d",&op);
       if(op==1){
           int temp;
           scanf("%d",&temp);
           //cout<<"sda:"<<temp<<endl;
           s[++indext]=temp;
      }else if(op==2){
           s[indext--];
      }else if(op==3){
           printf("%d\n",s[indext]);
      }else if(op==4){
           int k;
           scanf("%d",&k);
           int temp;
           temp=s[indext];
           for(int i=1;i<k;i++){
               temp=gcd(temp,s[indext-i]);
               if(temp==1)break;
          }
           for(int i=0;i<k;i++){
               s[indext-i]=temp;
          }
      }
  }
   return 0;
}

M 画画(矩阵找规律)

链接:https://ac.nowcoder.com/acm/contest/43937/M

小筱有一块画布,画布是一个N×NN \times NN×N的网格。最先开始画布上的每个格子都是白色,小筱想要把一些格子涂黑,完成一幅黑白的画。由于小筱很喜欢黑色,所以她希望使得尽量多的格子变成黑色。同时她希望对于第i行/列上的黑色格子数量与i的奇偶性相同(行与列编号为[0...N−1])。 现在请你帮助小筱画出一幅符合要求的画,其中黑色用1表示,白色用0表示。

解析:

这道题的话,看完题发现是一个正方形矩阵,然后奇偶行列分别都要满足要求,就说明0的位置肯定不是随便的,然后其实能感觉出来是一道找规律的题,开始就可以画着试试看能不能找到规律

答案解析给的是:首先把矩阵全赋1,然后把对角线上的元素间隔改0就行

但我们当时画了几次,开始拿小数字试,发现0的位置好像有规律和对角线有关,然后我们发现的规律是:如果n是偶数,那么0就在i,j相等且为奇数的位置,如果n是奇数,那么就是i+j等于n-1且i,j都为偶数的位置(这里注意一点就是编号是从0到n-1),可能有一点绕,但其实和答案应该是一样的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
   int t;
   cin>>t;
   while(t--)
  {
       int n;
       scanf("%d",&n);
       for(int i=0;i<n;i++)  
      {
           for(int j=0;j<n;j++)
          {
               if(n%2==0)
              {
                   if(i%2!=0&&j%2!=0&&i==j) printf("0");
                   else printf("1");
              }
               else
              {
                   if(i+j==n-1&&i%2==0&&j%2==0) printf("0");
                   else  printf("1");
              }            
          }
            printf("\n");        
      }
  }
   return 0;
}

星星温柔泛滥,人间至善