程序设计思维与实践 CSP-M2 补题 (3/4/数据班)

A - HRZ 的序列

题意

相较于咕咕东，瑞神是个起早贪黑的好孩子，今天早上瑞神起得很早，刷B站时看到了一个序列，他对

这个序列产生了浓厚的兴趣，他好奇是否存在一个数，使得一些数加上，一些数减去，一些数不

变，使得整个序列中所有的数相等，其中对于序列中的每个位置上的数字，至多只能执行一次加运算或

减运算或是对该位置不进行任何操作。由于瑞神只会刷B站，所以他把这个问题交给了你！

输入格式

输入第一行是一个正整数表示数据组数。 接下来对于每组数据，输入的第一个正整数表示序列的长

度，随后一行有个整数，表示序列。

输出格式

输出共包含行，每组数据输出一行。对于每组数据，如果存在这样的K，输出"YES"，否则输出“NO”。

（输出不包含引号）

思路

统计输入的数据中不同数字的个数就可以，如果大于3个不同数字，则肯定不可以，1、2个是可以的，3个不同数字要判断最大数最小数和中间数字的查是否相等。

总结

很简单的一个题，但是由于自己的zz操作痛失90分，我在不同数字大于三个时直接加了一句break，由于是多组数据，所以后面所有的输出格式全部错乱，但是当时自己测试的数据正好出巧了，没有发现这个问题，归根结底还是自己没有考虑全面。

代码

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{
	
	int t,n;
	scanf("%d",&t);
	while(t--)
	{
		vector<long long> v;
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		{
			long long tmp;
			scanf("%lld",&tmp);
			if(v.size()==0)
				v.push_back(tmp);
			else
			{
				for(int k=0;k<v.size();k++)
				{
					if(v[k]==tmp)
						break;
					if(k==v.size()-1 && v[k]!=tmp)
						v.push_back(tmp);
				}
			}
		
		}
		if(v.size()>3)
			printf("NO\n");
		else if(v.size()==3)
		{
			sort(v.begin(),v.end());
			if((v[1]-v[0]) == (v[2]-v[1]))
				printf("YES\n");
			else
				printf("NO\n");
		}
		else if(v.size()==1)
			printf("YES\n");
		else if(v.size()==2)
			printf("YES\n");
	}
	
	return 0;
	
}
           

B - HRZ 学英语

题意

瑞神今年大三了，他在寒假学会了英文的26个字母，所以他很兴奋！于是他让他的朋友TT考考他，TT想

到了一个考瑞神的好问题：给定一个字符串，从里面寻找连续的26个大写字母并输出！但是转念一想，

这样太便宜瑞神了，所以他加大了难度：现在给定一个字符串，字符串中包括26个大写字母和特殊字

符’?’，特殊字符’？'可以代表任何一个大写字母。现在TT问你是否存在一个位置连续的且由26个大写字

母组成的子串，在这个子串中每个字母出现且仅出现一次，如果存在，请输出从左侧算起的第一个出现

的符合要求的子串，并且要求，如果有多组解同时符合位置最靠左，则输出字典序最小的那个解！如果

不存在，输出-1！ 这下HRZ蒙圈了，他刚学会26个字母，这对他来说太难了，所以他来求助你，请你帮

他解决这个问题，报酬是可以帮你打守望先锋。

说明：字典序 先按照第一个字母，以 A、B、C……Z 的顺序排列；如果第一个字母一样，那么比较第二

个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，SIGH 和 SIGHT），那么把短者排

在前。例如

上面两种填法，都可以构成26个字母，但是我们要求字典序最小，只能取前者。

注意，题目要求的是 第一个出现的，字典序最小的！

输入格式

输入只有一行，一个符合题目描述的字符串。

输出格式

输出只有一行，如果存在这样的子串，请输出，否则输出-1

思路

滑动窗口问题，用一个bool数组记录当前窗口中已经存在的26个字母，并用num统计已经存在的字母个数，用一个cnt统计？出现的次数，如果num+cnt==26则找到了合适的，根据 l 、r的值输出即可，当遇到？时用bool数组的记录由前向后找第一个为false的输出。

总结

当时第一眼就知道这是个滑动窗口，没多想就开始写，但是由于一开始没有规划如何处理‘？’的问题（当时一开始想的是边移动窗口边替换），导致自己越写越麻烦，发现自己错了就去前面改，前面改了后面改，耗费了大量时间，所以做题的时候不能一上手就写，要先仔细考虑、规划一下会遇到一些什么样的问题，如何去用代码实现自己的思路，要不然很可能将简单问题复杂化。

代码

#include<iostream>
#include<string>
#include<string.h>
using namespace std;

int con(char c)
{
	return c-'A';
}

int main()
{
	
	string str;
	cin>>str;
	bool b[128];
	memset(b,0,sizeof(b));
	int l=0,r=-1;
	int cnt=0,num=0;
	
	for(int i=0;i<str.length();i++)
	{
		if(cnt+num==26)
			break;
		if(str[i]=='?')
		{
			cnt++;
			r++;
		}
		else
		{
			int v=str[i]-'A';
		
			while(b[v]==1)
			{
				if(str[l]=='?')
					cnt--;
				else
				{
					b[str[l]-'A']=0;
					
					num--;
				}
				l++;
			}
			b[v]=1;
			num++;
			r++;
			
		}
	}
	if(num+cnt==26)
	{
		for(int i=l;i<=r;i++)
		{
			if(str[i]!='?')
				printf("%c",str[i]);
			else
			{
				for(int j=0;j<26;j++)
				{
					if(b[j]==0)
					{
						char tmp= 'A'+j;
						printf("%c",tmp);
						b[j]=1;
						break;
					}
				}
			}
		}
		printf("\n");
	}
	else
		printf("-1\n");
	
	
	
}
           

C - 咕咕东的奇妙序列

题意

咕咕东 正在上可怕的复变函数，但对于稳拿A Plus的 咕咕东 来说，她早已不再听课，此时她在睡梦中

突然想到了一个奇怪的无限序列：112123123412345 …这个序列由连续正整数组成的若干部分构成，其

中第一部分包含1至1之间的所有数字，第二部分包含1至2之间的所有数字，第三部分包含1至3之间的所

有数字，第i部分总是包含1至i之间的所有数字。所以，这个序列的前56项会是

11212312341234512345612345671234567812345678912345678910，其中第1项是1，第3项是2，第20项是

5，第38项是2，第56项是0。咕咕东 现在想知道第 k 项数字是多少！但是她睡醒之后发现老师讲的东西

已经听不懂了，因此她把这个任务交给了你。

输入格式

输入由多行组成。

第一行一个整数q表示有q组询问

接下来第i+1行表示第i个输入，表示询问第项数字。

输出格式

输出包含q行

第i行输出对询问的输出结果。

思路

这道题结构比较复杂，理清序列的结构非常重要

先将 （1）最大数1位数组成的序列、最大数2位数组成的序列… 定义为段（2） 将1 、12、123…定义为大组 （3）将大组里面1位数的序列、2位数的序列…定义为小组

首先，我们看 112123123412345… 序列可以发现第一个段里面的大组长度是公差为1的等差数列，同样的，第二个段里大组长度是公差为2的等差数列，所以我们可以用等差数列求和公式求出每个大段的长度，这样由输入的k的值我们可以找到第k位位于哪一个段里面，由此也可以知道这个段最长位数是多少

然后，在上述找k的端的过程中k一直减去k前面的段的长度，现在k是在这个段中的下标，在段中我们可以发现1位数的序列长度、2位数的序列长度等都能用公式算出来，比如一位数有9位，二位数长度90位，三位数900位，这样一来，我们可以用二分来查找第一个大于等于k的位置在哪一个小组中，然后k减去前面小组的长度就是k在当前小组中的下标

最后，知道了在哪一个小组中，也就知道了这个小组是几位数的小组，然后用下标k可以直接找到k是哪一个数，然后看k的值是这个数中的第几位， 除特定个10后%10输出即可

总结

这道题我感觉是超出我的能力范围的，最后也是请教了别人才做了出来，不过现在把它掌握了，算是开阔了自己的思考问题的思路。

代码

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

long long a[15],b[15],c[15];
 
long long binary(int len,long long k)
{
	long long l=1,r=(long long)pow(10,len-1)*9;
	while(l<=r)
	{
		long long mid=(l+r)/2;
		if( (long long)(a[len-1]+len+a[len-1]+mid*len)*mid/2 >=k )
			r=mid-1;
		else
			l=mid+1;
		
	}
	return r;
}

int main()
{
	a[1]=9;
	b[1]=45;
	c[1]=45;
	for(int i=2;i<=9;i++)
	{
		a[i]=a[i-1]+9*i*pow(10,i-1);//
		b[i]=(a[i-1]+ i +a[i])*9*(long long)pow(10,i-1)/2;	
		c[i]=b[i-1]+b[i];
	} 
	int q;
	cin>>q;
	long long k;
	while(q--)
	{
		scanf("%lld",&k);
		long long len=0;
		long long kk=k;
		for(int i=1;i<=9;i++)
		{
			if(b[i]>=kk)
			{
				len=i;
				break;
			}
			k-=b[i];
		}
		long long in=binary( len ,k);
		k-=(long long)((a[len-1]+len+a[len-1]+in*len)*in/2);//k所在的小组
	
		long long i;
		long long temp=0;
		long long last=0;
		for(i=1;i<=len;i++)
		{
			last=temp;
			temp+=(long long)(i*pow(10,i-1)*9);
			if(temp>=k)
				break;
		 } 
		 
		 k-=last;
		  	
		long long tmp=(k+i-1)/i;
		k-=(tmp-1)*i;
		//cout<<k<<" "<<tmp<<" asa"<<endl;
		long long ans=pow(10,i-1)+tmp-1; 
		//cout<<ans<<" asd"<<endl;
		for(int m=0;m<i-k;m++)
			ans/=10;
		printf("%lld\n",ans%10);
		

		
	}

}