【作业向】程序设计思维与实践 CSP-M2

发表于 | 分类于 ，
字数统计: 1.2k | 阅读时长 ≈ 6

【作业向】程序设计思维与实践 CSP-M2

♔A HRZ的序列

这一题可以先对所有数进行遍历，求出最大和最小值，然后再次遍历，对于每个数ai判断ai是否等于最大值或最小值，ai-最小值是否等于最大值-ai，若都不符合则不满足条件，输出NO，跳出循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
ll T,n,maxi,mini,flag;
ll ai[10005];

int main()
{
	ll i,j,k;
	scanf("%lld",&T);
	while(T--)
	{
		flag=0;
		scanf("%lld",&n);
		if(n>=1) scanf("%lld",&ai[1]);
		maxi=mini=ai[1];
		for(i=2;i<=n;i++)
		{
			scanf("%lld",&ai[i]);
			maxi=max(maxi,ai[i]);
			mini=min(mini,ai[i]);
		}
		for(i=1;i<=n;i++)
		{
			if(ai[i]==maxi || ai[i]==mini || maxi-ai[i]==ai[i]-mini) continue;
			else
			{
				flag=1;
				printf("NO\n");
				break;
			}
		}
		if(!flag) printf("YES\n");
	}
	return 0;
}

♔B HRZ学英语

这一题可以用尺取法来做，从第一个字符开始，若区间中的不同的字母的数量+？的数量等于26时进行输出，输出时若遇到？，为了保证字典序最小则从A开始向后查询第一个没有出现过的字母，标记并输出。若区间中的不同的字母的数量+？的数量小于26且下一个字符为？或没出现过时，右边的标记右移一位，并对字符数量作相应的修改；当下一个字符出现过时，则左边的标记右移，直到移出了下一个字母为止。当左右标记均大于字符串的长度时若还未输出，则输出-1

（又及：模拟考试时结束的边界条件没写好导致才得了40分😭，下次一定注意

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
char c[1000005];
int sum[27],sumz;
int flag,n;

int main()
{
	int i,j;
	int l=0,r=1;
	scanf("%s",c);
	n=strlen(c);
	if(c[0]=='?') sum[26]++;
	else sum[c[0]-'A']++,sumz++;
	while(l<n && r<n)
	{
		if(c[r]=='?')
		{
			sum[26]++;
			r++;
			if(sumz+sum[26]==26) break;
		}
		else
		{
			if(!sum[c[r]-'A'])
			{
				sum[c[r++]-'A']=1;
				sumz++;
				if(sumz+sum[26]==26) break;
			}
			else 
			{
				if(c[l]=='?') sum[26]--;
				else sum[c[l]-'A']=0,sumz--;
				l++;
			}
		}
	}
	if(sumz+sum[26]==26) 
	{
		for(i=l;i<r;i++)
		{
			if(c[i]=='?')
			{
				for(j=0;j<26;j++)
					if(!sum[j]) 
					{
						sum[j]=1;
						printf("%c",'A'+j);
						break;
					}
			}
			else printf("%c",c[i]);
		}
	}
	else printf("-1");
	return 0;
}

♔C 咕咕东的奇妙序列

这一题就比较麻烦了，首先要预处理出1到9、1到99、1到999、1到9999。。。的长度，然后处理出第9组，第99组，第999组。。。的长度。然后读入q，先判断q在pow(10,n)-1组到pow(10,n+1)-1组之间，然后通过二分找到具体的组数。然后通过循环判断在该组的第几位，然后确定出具体的数字并输出。

这一题的细节的地方还是蛮多的，坑点也有，比如用c++自带的pow函数会出问题，只好自己写了一个，这还是蛮锻炼代码能力和思维能力的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<utility>
#define ll long long
using namespace std;
ll M,q,k;
ll dl[20],dll[20];

int check(ll x)
{
	ll a=((dl[k-1]+k)+(dl[k-1]+k*x))*x/2;
	ll b=((dl[k-1]+k)+(dl[k-1]+k*(x+1)))*(x+1)/2;
	if(b<q) return 0;
	else return 1;
}

ll power(ll x,ll y)
{
	ll n=1;
	for(ll i=1;i<=y;i++) n*=x;
	return n;
}

int main()
{
	ll i,j;
	dl[1]=9;
	for(i=2;i<=15;i++)
	{
		dl[i]=dl[i-1]+i*(power(10,i)-power(10,i-1));
		//printf("%lld\n",dl[i]);
	}
	for(i=1;i<=9;i++)
	{
		dll[i]=(dl[i-1]+i+dl[i])*(power((ll)10,i)-power((ll)10,i-1))/2;
		//printf("-%lld-\n",dll[i]);
	}
	scanf("%lld",&M);
	while(M--)
	{
		scanf("%lld",&q);
		for(k=1;k<=9;k++)
		{
			if(q<=dll[k]) break;
			q-=dll[k];
		}
		//printf("%lld - %lld\n",q,k);
		ll l=0,r=power(10,k)-1,mid;
		while(l<=r)
		{
			mid=(l+r)/2;
			if(check(mid)) r=mid-1;
			else l=mid+1;
		}
		//printf("%lld %lld\n",l,r);
		q-=((dl[k-1]+k)+(dl[k-1]+k*l))*l/2;
		//printf("%lld\n",q);
		for(i=1;i<=9;i++)
		{
			if(q<=dl[i])
			{
				q-=dl[i-1];
				//printf("+%lld+\n",q);
				if(i==1) 
				{
					printf("%lld\n",q);
					break;
				}
				ll hi=(q+i-1)/i;
				ll xt=q%i;
				ll dsg=power(10,i-1)+hi-1;
				if(xt==0)
				{
					//printf("-=%lld=-\n",dsg);
					printf("%lld\n",dsg%10);
				}
				else
				{	
					xt=i-xt;
					ll xxx=power(10,xt+1);
					//printf("%lld-%lld-%lld-%lld-\n",dsg,xt,xxx,i);
					dsg=dsg%xxx;
					printf("%lld\n",(dsg/power(10,xt))); 
					
				}
				break;
			}
		}
	}
	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！