2020.06.01——习题训练四

2024-02-02 18:21:16

A - Dreamoon and Ranking Collection

题意：在一串数字中添加x个数，使得从1开始到某个数连续，求这个数。

思路：从1开始遍历到出现的最大值，如果没有这个数，就增添上；直到x用没；然后再依次遍历直到某个数没出现

代码：

/*
  \\               //
   \\             //
    \\           //
##DDDDDDDDDDDDDDDDDDDDDD##
## DDDDDDDDDDDDDDDDDDDD ##
## hh   /\     ***** hh ##
## hh  //\\   **     hh ##
## hh //__\\  **     hh ##
## hh//    \\  ***** hh ##
## hh      wwww      hh ##
## hh                hh ##
## MMMMMMMMMMMMMMMMMMMM ##
##MMMMMMMMMMMMMMMMMMMMMM##
     \/            \/
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<math.h>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fora(i,a,b) for (int i = (a); i < (b); i++)
#define fors(i,a,b,s) for (int i = (a); i < (b); i=i+(s))
int main(){
	int a,n,t,x;
	cin>>t;
	while(t--){
		map<int,int>mp;
		scanf("%d%d",&n,&x);
		int ans=0,mmax=0;
		for(int i=1;i<=n;i++){
			scanf("%d",&a);
			mp[a]=1;
			mmax=max(mmax,a);
		}
		for(int i=1;i<=mmax+1000;i++){
			if(mp[i]==0&&x){
				x--;
				mp[i]=1;
			}
			else if(mp[i]==0&&x==0){
				ans=i;
				break;
			}
		}
		for(int i=1;i<=mmax+1000;i++){
			if(mp[i]!=1){
				break;	
			}
			ans=i;
		}
		printf("%d\n",ans);
	}
	return 0;
}

C - Exercising Walk

题意：给定一个矩形，左下角顶点坐标为(x_1,y_1)，右上角顶点坐标为(x_2,y_2))。现在有一个起点(x,y)(x,y),以及四个数a,b,c,d,问能否从起点开始走若干步（向左，向右，向上或向下），使向左、右、下、上分别共走了a,b,c,d步。

思路：无论怎么走，水平方向上一定向右走了(b-a)步，竖直方向上向上走了(d-c)步，即最终位置为 (x+b-a, y+d-c)，只要判断这个位置在不在 x_1,y_1,x_2,y_2 的范围内就可以了.需要注意的是，即使 b-a=0(或 d-c=0)，如果 x_1=x_2或y_1=y_2，依然无路可走.

代码：

/*
  \\               //
   \\             //
    \\           //
##DDDDDDDDDDDDDDDDDDDDDD##
## DDDDDDDDDDDDDDDDDDDD ##
## hh   /\     ***** hh ##
## hh  //\\   **     hh ##
## hh //__\\  **     hh ##
## hh//    \\  ***** hh ##
## hh      wwww      hh ##
## hh                hh ##
## MMMMMMMMMMMMMMMMMMMM ##
##MMMMMMMMMMMMMMMMMMMMMM##
     \/            \/
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<math.h>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fora(i,a,b) for (int i = (a); i < (b); i++)
#define fors(i,a,b,s) for (int i = (a); i < (b); i=i+(s))
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		int x,y,x1,y1,x2,y2;
		scanf("%d%d%d%d%d%d",&x,&y,&x1,&y1,&x2,&y2);
		int right=x+b-a,up=y+d-c;
		if(right<x1||right>x2||up<y1||up>y2
					||x1==x2&&a||y1==y2&&c){
			cout<<"No"<<endl;
                        continue;
		}
		cout<<"Yes"<<endl;
	}
	return 0;
}

D - Composite Coloring

题意：分组，把有相同公约数的数字分成一组

思路：1000以内的质因数共有11个，遍历他们能整除同一个数的就是在一组里的。

代码：

/*
  \\               //
   \\             //
    \\           //
##DDDDDDDDDDDDDDDDDDDDDD##
## DDDDDDDDDDDDDDDDDDDD ##
## hh   /\     ***** hh ##
## hh  //\\   **     hh ##
## hh //__\\  **     hh ##
## hh//    \\  ***** hh ##
## hh      wwww      hh ##
## hh                hh ##
## MMMMMMMMMMMMMMMMMMMM ##
##MMMMMMMMMMMMMMMMMMMMMM##
     \/            \/
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<math.h>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fora(i,a,b) for (int i = (a); i < (b); i++)
#define fors(i,a,b,s) for (int i = (a); i < (b); i=i+(s))
const int c[15]={1,2,3,5,7,11,13,17,19,23,29,31,33};
int id[15],a[1005],b[1005],cnt,t,n;

int main()
{
	scanf("%d",&t);
	while(t--)
	{
		for(int i=1;i<=11;++i)
			id[i]=0;
		cnt=0;
		scanf("%d",&n);
		for(int i=1;i<=n;++i)
			scanf("%d",&a[i]);
		for(int i=1;i<=n;++i){
			for(int j=1;j<=11;++j){
				if(a[i]%c[j]==0){
					if(id[j]==0)
						id[j]=++cnt;
					b[i]=id[j];
					break;
				}
			}
		}
		printf("%d\n",cnt);
		for(int i=1;i<=n;++i)
			printf("%d ",b[i]);
		puts("");
	}
	return 0;
}

E - K-th Beautiful String

题意：给出数字n，构造一串含有两个b的字符串，并按照字典顺序标号，输出要求的编号的字符串

思路：找规律，发现第一个b动的时候情况就是等差数列的和种情况，然后按照给定的数字求出相应的第一个b的位置，然后判断距离要求的还有几种情况，在确定第二个b的位置。

代码：

/*
  \\               //
   \\             //
    \\           //
##DDDDDDDDDDDDDDDDDDDDDD##
## DDDDDDDDDDDDDDDDDDDD ##
## hh   /\     ***** hh ##
## hh  //\\   **     hh ##
## hh //__\\  **     hh ##
## hh//    \\  ***** hh ##
## hh      wwww      hh ##
## hh                hh ##
## MMMMMMMMMMMMMMMMMMMM ##
##MMMMMMMMMMMMMMMMMMMMMM##
     \/            \/
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<math.h>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fora(i,a,b) for (int i = (a); i < (b); i++)
#define fors(i,a,b,s) for (int i = (a); i < (b); i=i+(s))
int main(){
	int n,m,t;
	cin>>t;
	while(t--){
		cin>>n>>m;
		char ss[n+1];
		memset(ss,'a',sizeof(ss));
		int ans=0,i;
		for(i=1;i<=n+5;i++){
			ans+=i;
			if(ans>=m)
				break;
		}
		ss[i]='b';
		int index=ans-m;
		ss[i-index-1]='b';
		for(int i=n-1;i>=0;--i)
			cout<<ss[i];
		cout<<endl;
	}
	return 0;
}

F - Carousel

题意：已知有n个点的环,点i的类型为a_i,现在需要给每个点进行染色,要求相邻不同类型的点的颜色不同且所用颜色数最小.输出颜色数及一种染色方案即可.(颜色从1开始)

思路：分情况讨论：你只要从第一个开始交替染 1 和 2，然后假如 n 为奇数把最后一个换成染 3，那么，很显然任意相邻两个颜色不同，自然也符合了条件。考虑何时答案为 1：所有 t_i相等，全染 1 即可。考虑何时答案为 2：n 为偶数，交替染 1 和 2 即可；或者，有至少两个相邻的数相等，那么从中间断开为链后交替染 1 和 2 即可。考虑何时答案为 3：n 为奇数且相邻的每一对数都不相等。此时，交替染 1 和 2 然后把最后一个改成 3 即可。

代码：

/*
  \\               //
   \\             //
    \\           //
##DDDDDDDDDDDDDDDDDDDDDD##
## DDDDDDDDDDDDDDDDDDDD ##
## hh   /\     ***** hh ##
## hh  //\\   **     hh ##
## hh //__\\  **     hh ##
## hh//    \\  ***** hh ##
## hh      wwww      hh ##
## hh                hh ##
## MMMMMMMMMMMMMMMMMMMM ##
##MMMMMMMMMMMMMMMMMMMMMM##
     \/            \/
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<math.h>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define fora(i,a,b) for (int i = (a); i < (b); i++)
#define fors(i,a,b,s) for (int i = (a); i < (b); i=i+(s))
int a[200005];
int main()
{
	int t,x,fi;
	scanf("%d",&t);
	while(t--)
	{
		int n;
		bool flag=0,flag1=1;
		scanf("%d",&n);
		for(int i=1;i<=n;++i)
			scanf("%d",a+i);
		for(int i=1;i<=n;++i){
			int p=i-1;
			if(p==0)
				p=n;
			if(a[i]==a[p])
				flag=1;
			else
				flag1=0;
		}
		if(flag1){
			printf("1\n");
			for(int i=1;i<=n;++i)
				printf("1 ");
			printf("\n");
		}
		else if(n%2==0){
			printf("2\n");
			for(int i=1;i<=n/2;++i)
				printf("%d %d ",2,1);
			printf("\n");	
		}
		else if(flag){
			printf("2\n");
			flag=0;
			for(int i=1;i<=n;++i){
				int p=i-1;
				if(p==0)
					p=n;
				if(flag)
					printf("%d ",2-(i%2));
				else if(a[i]==a[p])
					printf("%d ",2-(i%2)),flag=1;
				else 
					printf("%d ",i%2+1);
			}
			printf("\n");
		}
		else {
			printf("3\n");
			for(int i=1;i<n;++i){
				printf("%d ",i%2+1);
			}
			printf("%d\n",3);
		}
	}
	return 0;
}
上一篇：购物商城


下一篇：LuoguP1972 [SDOI2009]HH的项链