ACM第二周---周赛---题目合集.

超、凢脫俗 2024-03-31 12:23 28阅读 0赞

> 提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

#### 文章目录 ####

*  前言
 *  A - k-LCM (easy version)
 *  B - Base K
 *  C - \[例题\]一维前缀和
 *  D - 最小新整数
 *  E - 验证角谷猜想
 *  F - T-primes
 *  G - Takahashi's Secret
 *  H - 亲和数
 *  I - Alena's Schedule
 *  J - 最少拦截系统
 *  K - Median Maximization
 *  L - 最大子矩阵
 *  总结

--------------------

## 前言 ##

本周的ACM学校的比赛题目放到这里供大家学习与交流，当然，题目适合入门算法并且至少会一种编程语言的同学学习，接下来讲一下整体难度吧，此次比赛难度对我才学完c语言的同学而言还是比较难的，因为我不会数据结构和算法，当时比赛就做出来7道题目，这里经过自己的学习和研究终于把题解写出来了，**第一是便于我自己去复习和巩固，第二就是大家学习和指出可以优化的地方一起进步。蟹蟹。**

## A - k-LCM (easy version) ##

![在这里插入图片描述][06bbf6241d2a4d8baa8e830676062387.png]

#include<stdio.h>
    int t,n,m,k;
    int main()
    {
        	
    	scanf("%d",&t);
    	while(t--)
    	{
        
    		scanf("%d %d",&n,&k);
    		int a,b,c;
    		if(n&1) 
    			a=b=n/2,c=1;
    		else 
    		{
        
    			int tmp=n/2;
    			if(tmp&1)
    				a=b=tmp-1,c=2;
    			else
    				a=b=tmp/2,c=tmp;
    		}
    		printf("%d %d %d\n",a,b,c);
    	}
        return 0;
    }

这个题是来自cf的一道题目，考察了数学知识的掌握，当然我比赛是没写出来的，这里是学习了csdn的一些大佬才自己敲出来了。

## B - Base K ##

![在这里插入图片描述][08c1df191ae9484ea8ee39c7b1d77575.png]

#include<stdio.h>
    #include<math.h>
    int main()
    {
        
    	long long k;
    	scanf("%lld",&k);
    	long long a,b,i=0,j=0,sum=0,count=0;
    	scanf("%lld %lld",&a,&b);
    	while(a>0)
    	{
        
    		sum+=a%10*pow(k,i++);
    		a=a/10;
    	}
    	while(b>0)
    	{
        
    		count+=b%10*pow(k,j++);
    		b=b/10;
    	}
    	long long c=count*sum;
    	printf("%lld",c);
    	return 0;
    }

这个题目是之前周赛考过的进制问题，并且这个题还不是大于十的进制问题可想难度很低了，但是要注意这个题必须注意定义的类型不然会溢出。

## C - \[例题\]一维前缀和 ##

![在这里插入图片描述][d57511f096c1409d9ebb587e81bb8ef0.png]

#include<stdio.h>
    int main()
    {
        
    	long long n,k,arr[100010],sum[100010];
    	scanf("%lld %lld",&n,&k);
    	sum[0]=0;
    	for(int i=1;i<=n;i++)
    	{
        
    		scanf("%lld",&arr[i]);
    		int tmp=arr[i];
    		sum[i]=tmp+sum[i-1];
    	}
    	for(int i=1;i<=k;i++)
    	{
        
    		int f,t;
    		scanf("%d %d",&f,&t);
    		printf("%lld\n",sum[t]-sum[f-1]);
    	}
    	return 0;
    }

基础算法前缀和问题，后面我学到AcWing的算法的时候会详细讲解前缀和的，这里简单聊一聊我所知道的前缀和就是存放到数组里面防止溢出问题的发生其实就是类似于5！=4！\*5这样理解吧。

## D - 最小新整数 ##

![在这里插入图片描述][ffe9bfce0d4248a5b266811a705a8511.png]

#include<stdio.h>
    #include<string.h>
    int main()
    {
        
    	int t;
    	char arr[100010]; 
    	scanf("%d",&t);
    	while(t--)
    	{
        
    		int k=0;
    		scanf("%s %d",arr,&k);
    		int len=strlen(arr);
    		while(k--)
    		{
        
    			for(int i=0;i<len-1;i++)
    			{
        
    				if(arr[i]>arr[i+1])
    				{
        
    					for(int j=i;j<len-1;j++)
    					{
        
    						arr[j]=arr[j+1];
    					}
    				}
    			}
    			len--;
    		}
    		for(int i=0;i<len;i++)
    		{
        
    			printf("%c",arr[i]);
    		}
    		printf("\n");
    	}
    	return 0;
    }

基础的贪心思想，其实我叫他覆盖方法，初学者就是酱紫理解就行，后面咱们会算法了再更正好不好捏？我这里写c语言的方法大家可能看着也舒服，别的地方可能就是c++一大串真的对于小白来说不容易看懂。

## E - 验证角谷猜想 ##

![在这里插入图片描述][ead70e3087554f7ea173a84b4023eef7.png]

#include<stdio.h>
    int main()
    {
        
    	int n;
    	scanf("%d",&n);
    	while(n--)
    	{
        
    		int m,flag=0,i=0,j=0,arr[100010];
    		scanf("%d",&m);
    		while(m!=1)
    		{
        
    			if(m%2==1)
    			{
        
    				flag=1;
    				arr[i++]=m;
    				m=m*3+1;
    			}
    			if(m%2==0)
    			{
        
    				m=m/2;
    			}
    		}
    		if(flag==0)
    		{
        
    			printf("No number can be output !");
    		}
    		else
    		{
        
    			for(j=0;j<i;j++)
    			{
        
    				if(j!=i-1)
    				printf("%d ",arr[j]);
    				else
    				printf("%d",arr[j]);
    			}
    		}
    		printf("\n");
    	}
    	return 0;
    }

这一道题真的就是语法题目捏，所以我想说的就是1.简单的大家不要骄傲，2.flag标记法对于printf这种yes or no 的真的好用大家快学习用起来吧hhh~

## F - T-primes ##

![在这里插入图片描述][dba2df7f94fb4514adb160994c51bb8c.png]

#include<stdio.h>
    #include<math.h>
    int arr[100010]={
        0};
    void init()
    {
        
    	for(int i=2;i<100005;i++)
    	{
        
    		if(arr[i]==0)
    		{
        
    			for(int j=i*2;j<100005;j+=i)
    			{
        
    				arr[j]=1;
    			}
    		}
    	}
    }
    int main()
    {
        
    	int t;
    	init();
    	scanf("%d",&t);
    	while(t--)
    	{
        
    		long long n;
    		scanf("%lld",&n);
    		long long x=sqrt(n);
    		if(x*x==n&&x>1&&arr[x]==0)
    		{
        
    			printf("YES\n");
    		}
    		else printf("NO\n");
    	}
    	return 0;
    }

emm埃式筛选法，上一期讲过了，好好看看，对素数也算是一种技巧上的提高对吧？不仅仅要会暴力求解也要会一些小技巧。

## G - Takahashi’s Secret ##

![在这里插入图片描述][0681807312aa4d659fafcc532bb97a4b.png]

**题意：我有N个朋友，我跟X有小秘密，但是X会告诉a\[X\]，a\[X\]，会告诉a\[a\[X\]\]，问最后一共能有多少个人知道这个秘密。**  
**思路:定义两个数组，一个是谁告诉谁的数组，一个数组用来记录谁知道了，循环的条件就是告诉下一个人，但是下一个人的标志数组为1，代表已经知道了，循环就结束，最后再遍历标志数组，记录为1的，就代表知道了，最后输出cnt；**

#include<stdio.h>
    int main()
    {
        
    	int n,x,arr[100010]={
        0},book[100010]={
        0};
    	scanf("%d %d",&n,&x);
    	for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    	while(book[x]==0)
    	{
        
    		book[x]=1;
    		x=arr[x];
    	}
    	int cnt=0;
    	for(int i=1;i<=n;i++)
    	{
        
    		if(book[i]==1)
    		{
        
    			cnt++;
    		}
    	}
    	printf("%d\n",cnt);
    	return 0;
    }

## H - 亲和数 ##

![在这里插入图片描述][3cfa4ed69b1d4ac988b9b03ec7211b3e.png]

#include<stdio.h>
    int main()
    {
        
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
        
    		int flag=0,n,m,i=0,j=0,sum=0;
    		scanf("%d %d",&n,&m);
    		for(i=1;i<n;i++)
    		{
        
    			if(n%i==0)
    			{
        
    				sum+=i;
    			}
    		}
    		if(sum!=m) flag=1;
    		sum=0;
    		for(j=1;j<m;j++)
    		{
        
    			if(m%j==0)
    			{
        
    				sum+=j;
    			}
    		}
    		if(sum!=n) flag=1;
    		if(flag==1)
    		{
        
    			printf("NO\n");
    		}
    		else 
    		{
        
    			printf("YES\n");
    		}
    	}
    	return 0;
    }

简单语法题。

## I - Alena’s Schedule ##

![d1340c47f1d1481c8534596b740bcdb2.png][]

真是大家好好学习英语吧，这么长我都自闭了，大家看看题意和思路吧

**题意：  
有人要去上课，1代表有课，0代表没课  
这个人在有两个及以上连续的没课的时候，才会回家  
然后问你这个人得在学校呆多**

**题解：**

**直接暴力扫一遍就好了  
有课会呆在学校，没课但是，上下都是课的，也会呆在学校**

#include<stdio.h>
    int main()
    {
        
    	int n,arr[100010];
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    	int count=0;
    	for(int i=1;i<=n;i++)
    	{
        
    		if(arr[i]==1) 
    			count++;
    		if(arr[i]==0&&arr[i-1]==1&&arr[i+1]==1)
    			count++;
    	}
    	printf("%d\n",count);
    	return 0;
    }

## J - 最少拦截系统 ##

![在这里插入图片描述][dfb4822811644e4eb15114936120add0.png]  
**题意描述：本题就是给你多个数，统计里面的单调递减子序列最少有几个，大概就是先找第一个最长的递减子序列(第一个拦截系统)，然后在剩下的序列里面接着找最长的递减子序列，看一共有多少个递减子序列**  
这题可不敢像我一样直接遍历傻傻的错了还不知道哪里错了。

//最大上升子序列模板题
    #include<stdio.h>
    #include<math.h>
    int main()
    {
        
    	int n,i,j,arr[5000]={
        0},f[5000]={
        0};
    	while(~scanf("%d",&n))
    	{
        
    		for(i=1;i<=n;i++) scanf("%d",&arr[i]);
    		int max=1;
    		for(i=1;i<=n;i++)
    		{
        
    			f[i]=1;
    			for(j=1;j<=i;j++)
    			{
        
    				if(arr[i]>arr[j])
    				{
        
    					f[i]=fmax(f[i],f[j]+1);
    				}
    			}
    			max=fmax(f[i],max);
    		}
    		printf("%d\n",max);
    	}
    	return 0;
    }

## K - Median Maximization ##

这里没图了发送链接给大家  
[添加链接描述][Link 1]

这个题目目前我还不会,大家如果会可以call我,感谢你啦蟹蟹.

## L - 最大子矩阵 ##

这里没图了发送链接给大家

[添加链接描述][Link 2]  
题目来自杭电,

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    int t,m,n,x,y,a;
    long long sum[1005][1005];
    long long arr[1005][1005];
    int main()
    {
        
    	scanf("%d",&t);
    	while(t--)
    	{
        
    		scanf("%d%d%d%d",&n,&m,&x,&y);
    		long long res=0;
    		memset(sum,0,sizeof sum);
    		memset(arr,0,sizeof arr);
    		for(int i=1;i<=n;i++)
    			for(int j=1;j<=m;j++)
    			{
        
    				scanf("%lld",&arr[i][j]);	
    				sum[i][j]=sum[i][j-1]+arr[i][j];
    			}
    		for(int i=1;i<=n;i++) 
    			for(int j=1;j<=m;j++)
    			{
        
    				sum[i][j]+=sum[i-1][j]; 
    				if(i>=x&&j>=y)
    					res=fmax(res,sum[i][j]-sum[i][j-y]-sum[i-x][j]+sum[i-x][j-y]);
    			}			
    		printf("%lld\n",res);
    	}
    	return 0;
    }

这里就是前缀和和差分模板,后面我会在我的算法学习当中详细讲解,希望大家到时候给我指点和方向蟹蟹.

## 总结 ##

1.打完这场周赛我自己的编程能力是有提升的这是确确实实感受到了,我在学校的蓝桥杯选拔赛当中也获得了补助的最大力度的奖金,我的意思是说我希望大家未来不管这个比赛是否是学校组织的 或者 省组织的,更或者国家组织的大家都要以最最最好的心态和状态去准备他去打好这场比赛,因为即使一题也写不出来,但只要知道不足了,方可寻找下一步的方向,才可以去成长,进步  
2.后面也感觉到了题难嘛,所有就是学习数据结构和算法是目前最最最重要和需要的事情,但是出发之前都需要检验自己目前的实力是否真的配去学习这些更加高级的知识呢?我想我是不够的,因为c语言我只考了90分,并且我没有把这些知识做成博客去方便自己去复习和巩固,所以下面就要根据这些缺陷去打补漏洞战.  
3.比赛后一定要去把错题和不会的题去csdn这些网站上找题解去学习,因为编程题需要语言+数据结构+算法+积累题型的多少+天赋+努力(当然错了大家可以指正)来决定,所以积累是必不可少的.

最后感谢看到这里的小伙伴,原编程路上有馥陪你,一起度过难关,学习进步,祝所有热爱的人都能心想事成,加油吧! 曹子馥.

[06bbf6241d2a4d8baa8e830676062387.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6b18c1dbb40a406db62ef76ee58f0e7d.png
[08c1df191ae9484ea8ee39c7b1d77575.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f9b7adbc3f394f13851c259ec735c95f.png
[d57511f096c1409d9ebb587e81bb8ef0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3802db709fca467baa9d4526bde81069.png
[ffe9bfce0d4248a5b266811a705a8511.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f6ce0537ab324035bd02f907fad4079e.png
[ead70e3087554f7ea173a84b4023eef7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/38a2b66092f54ffa8116cc6899bf5f1f.png
[dba2df7f94fb4514adb160994c51bb8c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/2344bea781a446cbbdb2e21afe1a5682.png
[0681807312aa4d659fafcc532bb97a4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/8ed5d842e6f04fa9b39a2c7cee706f14.png
[3cfa4ed69b1d4ac988b9b03ec7211b3e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/22dd7a5e36e84ad5a17fc73022ce905d.png
[d1340c47f1d1481c8534596b740bcdb2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a875d6e7027c40c4b7252881030c89ee.png
[dfb4822811644e4eb15114936120add0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/6a2b635ddc52439baad13f4636615649.png
[Link 1]: https://codeforces.com/contest/1566?f0a28=1
[Link 2]: https://acm.hdu.edu.cn/search.php?field=problem&key=HDU%202006-12%20Programming%20Contest%20&source=1&searchmode=source