ACM第二周训练题目合集

布满荆棘的人生 2024-03-31 08:05 77阅读 0赞

![dbf0e3b6e4684b4a9883d0679ebf5d03.png][]已经写过了这个题目，所以不再赘述

![2deb5bc5d0a34b568dd40bb21225c7d5.png][]

1.这个题目就是学长让学习的本周算法题目，给了个基本概念，这个题也是非常简单。代码如下所示：

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

![6b9bf047837d431a907049ee3702d332.png][]

这就是一道语法题目很简单，代码如下所示：（本人可能写的不是最牛的或者最简洁的代码）

#include<stdio.h>
    int main()
    {
    	int y,m,d,i;
    	int arr[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
    	while(~scanf("%d/%d/%d",&y,&m,&d))
    	{
    		int sum=0;
    		if((y%100!=0 && y%4==0)||(y%400==0))
    		{
    			arr[2]=29;
    		}
    		else arr[2]=28;
    		if(m==1)
    		{
    			sum=d;
    		}
    		else if(m>1)
    		{
    			for(i=1;i<m;i++)
    			{
    				sum=sum+arr[i];
    			}
    			if(i==m)
    			{
    				sum=sum+d;
    			}
    		}
    		printf("%d\n",sum);
    	}
    	return 0;
    }

![51d8f053427b45f79de1fb9e57a7521a.png][]

这个题目其实就是前缀和算法我后面会出一期关于我学习AcWing算法课程的内容，里面还是会讲解我学习算法的心得和收获，这里我不过多讲述算法内容，代码如下：

#include<cstdio>
    int main()
    {
    	int N,Q;
    	scanf("%d %d",&N,&Q);
    	long long int sum[N+1],temp=0;
    	sum[0]=0;
    	for(int i=1;i<=N;i++)
    	{
    		long long int a;
    		scanf("%lld",&a);
    		temp+=a;
    		sum[i]=temp;
    	}
    	for(int i=1;i<=Q;i++)
    	{
    		int f,t;
    		scanf("%d%d",&f,&t);
    		printf("%lld\n",sum[t]-sum[f-1]);
    	}
    	return 0;
    }

![1bea1ff2e7b24980a5e1b9a072e8b0eb.png][]

目前做过几次这样的题目了，没啥难度，语法题目，看代码吧：

#include<stdio.h>
    int fen(int n,int m)
    {
    	int r;
    	if(n>m)
    	{
    		int temp=n;
    		n=m;
    		m=temp;
    	}
    	while((r=m%n)!=0)
    	{
    		m=n;
    		n=r;
    	}
    	return n;
    }
    int main()
    {
    	int n,a,b,c,d,z,m;
    	scanf("%d",&n);
    	while(n>0)
    	{
    		scanf("%d %d %d %d",&a,&b,&c,&d);
    		m=b*d;
    		z=a*d+c*b;
    		int c=fen(z,m);
    		printf("%d %d\n",z/c,m/c);
    		n--;
    	}
    	return 0;
    }

![05fb142edd2540889dbf2eb1f942eb93.png][]

这个题目学长们安排其实就是考察我们的思维，如果看透了非常easy,代码如下所示：

#include<stdio.h>
    #include<math.h>
    int main()
    {
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		int a,b,n;
    		int i=0,j=0,count=0;
    		scanf("%d %d %d",&a,&b,&n);
    		while(a%2==0)
    		{
    			i++; a=a/2;
    		}
    		while(b%2==0)
    		{
    			j++; b=b/2;
    		}
    		count=pow(2,i+j);
    		if(count>=n) printf("YES\n");
    		else printf("NO\n");
    	}
    	return 0;
    }

![d84cfce3894c414aa198cb72cab28dc4.png][]

我估计是因为学长们害怕我们不会，一直放这个题，代码如下所示：

#include<stdio.h>
    int main()
    {
    	int n,r,i=0,j=0;
    	char arr[1000];
    	while(~scanf("%d %d",&n,&r))
    	{
    		if(n<0){
    			printf("-");
    			n=n-2*n;
    		} 
    		while(n>0)
    		{
    			++i;
    			arr[i]=n%r;
    			n=n/r;
    		}
    		for(j=i;j>0;j--)
    		{
    			if(arr[j]>=10&&arr[j]<=16)
    			{
    				if(j!=1) printf("%c",arr[j]+55);
    				else{
    					printf("%c\n",arr[j]+55);
    				} 
    				i=0;
    			}
    			else
    			{
    				if(j!=1) printf("%d",arr[j]);
    				else {
    					printf("%d\n",arr[j]);
    				}
    				i=0;
    			}
    		}
    	}
    	return 0;
    }

![aa1c25f29c9b4d59b2d45e7b4bc1581c.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;
    }

![029602781b30431f9cb321cebbda09a6.png][]

这是一道找规律问题 ，不难。

暴力递归完了

#include<stdio.h>
    int fun(int n)
    {
    	if(n<=4)
    	return n;
    	else
    	return fun(n-1)+fun(n-3);
    } 
     int main()
     {
     	int n;
     	while(~scanf("%d",&n)&&n!=0)
     	{
    		printf("%d\n",fun(n));
    	}
     	return 0;
     }

![2adab41ed07145d2b75ec13294e8f471.png][]

这个我一开始想的思路是把每一个数都放到数组里面然后快速排序，然后从最小值输出，后来发现这种方法是不行的，于是求助了一下csdn

### **题解：** ###

将要删除的数字从头开始，让第一个与第二个比较大小，如果第一个大于第二个，则将第二个的值赋给第一个，第三个付给第二个，依次类推。第一个与第二个比完后，如果第一个大于第二个，则赋值后记一次数，然后退出复制的循环，再从头开始比较；否则，继续进行第三个与第二个的比较，依次类推，其实一句话就是贪心算法这个题目。

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

![d3ca06c6c3f442eab39312d298ea2a81.png][]

做了好几次了这个题目，不说了看代码：

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

![32500e01fda748b4a27cb48b9fc4767c.png][]

这一道题目收获颇丰，我学到了判断素数的新的方法埃式筛选法：

#include<stdio.h>
    #include<math.h>
    int a[1000005];
    //1-10^6范围内的素数筛
    void init()//埃氏筛求1-10^6内的所有素数
    {
    	//a[i]=0代表是素数 a[i]=1代表不为素数
    	for(int i=2;i<1000005;i++)
    	{
    		if(a[i]==0)//意味着当前数为素数
    		{
    			for(int j=i*2;j<=1000005;j+=i)
    			{
    				a[j]=1;//j代表 i的整数倍，因为j是i的整数倍
    					   //因此j一定不是素数 标记为1
    			}
    		}
    	}
    }
    int main()
    {
    	int t;
    	init();
    	scanf("%d",&t);
    	for(int i=0;i<t;i++)
    	{
    		long long n;
    		scanf("%lld",&n);
    		long long x=sqrt(n);
    		if(x*x==n&&x>1&&a[x]==0)
    		{
    			printf("YES\n");
    		}
    		else 
    		{
    			printf("NO\n");
    		}
    	}
    	return 0;
    }
    //注释是学长教的

本周训练总结：

1.收获：学习到了前缀和算法，以及了解了贪心算法，知道了埃式筛选法。

2.规划：继续学习acwing算法和数据结构，坚持在x-mind上边打卡。

[dbf0e3b6e4684b4a9883d0679ebf5d03.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/7d7550a895ff424fa17bf9cf1b1f5aa3.png
[2deb5bc5d0a34b568dd40bb21225c7d5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/079e81e2f7d54a81a56da7086e326d24.png
[6b9bf047837d431a907049ee3702d332.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f2df056ecdfb409ba25c4e63e97468e3.png
[51d8f053427b45f79de1fb9e57a7521a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/02f56d04d32f41ce9f64efa2d27c212e.png
[1bea1ff2e7b24980a5e1b9a072e8b0eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/d26ef033384a4fa1942dac7d55c55794.png
[05fb142edd2540889dbf2eb1f942eb93.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/fb6c62b0776c486bbca86ce602fd051f.png
[d84cfce3894c414aa198cb72cab28dc4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a8d0a2b863c54c20ba8e7af30234bc03.png
[aa1c25f29c9b4d59b2d45e7b4bc1581c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/10c3bcc04fa243ffb6a7d2985c7c1de0.png
[029602781b30431f9cb321cebbda09a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/951f7a7ffd044e3b855a2b7e95a3eebd.png
[2adab41ed07145d2b75ec13294e8f471.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/71aa36700e264f91aee3be2a9c22929d.png
[d3ca06c6c3f442eab39312d298ea2a81.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/13d43eff6429447fae2fda7df96a854a.png
[32500e01fda748b4a27cb48b9fc4767c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e4671767b0f34d4c80ae466f476e61c0.png