HRZ的序列

题目描述

思路分析

那道题目首先看一下测试数据的范围，选择合适数据类型，这道题目选择long long类型。typedef long long ll。
序列中每个数字经过加或者减去k或者不做处理之后每个数字都相等，这个数字k是一旦确定，对于序列中每个数字的加减来说，加数/减数都是这个k，所以不妨使用sort将序列升序排序，根绝最小的数字和最大的数字确定出这个k可以是哪些值，然后对这些确定了的k值代入序列中一一判断，只要满足以下三种情况，就可以继续判断下一个数字，如都不满足就代表不存在这样的k。
（1）num[i] = =num[i+1];
（2）num[ i]+k= =num[i+1]-k;
（3）num[i]+k==num[i+1]。
如何根据最小值和最大值确定出k呢？无外乎两种情况：（1）最小值+k=最大值-k，则k=(min+max)/2；（2）最小值+k=最大值，则k=(max-min)

代码实现

#include<bits/stdc++.h>
using namespace std;long long num[100010];
int main(){int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=0;i<n;i++) scanf("%lld",&num[i]);sort(num,num+n);//升序long long minv=num[0];long long maxv=num[n-1];if(minv==maxv){printf("YES\n");continue;}long long k2,k=0;//两个可能的k值 if((maxv-minv)%2==0)//这里就相当于判断求k的时候的第一种情况k=(maxv-minv)/2;k2=maxv-minv;//printf("k,k2(%d,%d)\n",k,k2);//以下对两个k分别进行判断bool stop1=false;if(k==0) stop1=true;for(int i=0;i<n-1&&k!=0&&!stop1;i++){if(num[i]==num[i+1]) continue;else if((num[i]+k)==(num[i+1]-k)) continue;else if(num[i]+k==num[i+1]) continue;else stop1=true;}bool stop2=false;for(int i=0;i<n-1&&!stop2;i++){if(num[i]==num[i+1]) continue;else if((num[i]+k2)==(num[i+1]-k2)) continue;else if(num[i]+k2==num[i+1]) continue;else  stop2=true;}if(stop1&&stop2)printf("NO\n");else printf("YES\n");}return 0;
}

HRZ学英语

题目描述

思路分析

这道题目我审题很不仔细，导致多次超时，题目中要求第一次出现并且使字典序最小的序列。我的代码是求出所有这样的序列中最小的序列，导致又是WA又是TL。
for(int i=0;i<s.size();i++)每次取从i开始的26个字符的子串存储到tmp中，接下来对这个tmp字符串进行判断，首先要获得tmp中各个字符的个数，定义一个cnt数组记录A~Z每个字符的个数，只要某一个字符的个数cnt[char-‘A’]大于1，那么就说明tmp一定不满足题意，就要继续从i+1开始取出26个字符的子串，如果所有的都不大于1，说明有问号存在或者无问号存在，直接就是连续的26个字母。从j=0开始找cnt[j]等于0的，然后找到问号所在位置pos，将这个(char)(j+‘A’)覆盖到pos,这样就可以保证字典序最小

代码实现

#include<bits/stdc++.h>//这个头问件 
using namespace std;int cnt[26]={0};
bool cannot=false;//子串是否是连续的英文字母组成 int main(){string s;string tmp;getline(cin,s);for(int i=0;i<s.size()-25;i++){memset(cnt,0,sizeof(cnt));cannot=false;tmp=s.substr(i,26);//复制子串for(int j=0;j<26;j++){//统计前缀和 if(tmp[j]-'A'>=0&&tmp[j]-'A'<26){cnt[tmp[j]-'A']++; if(cnt[tmp[j]-'A']>1) cannot=true;}}if(cannot) continue;//有重复字符，找下一个 for(int j=0;j<26;j++){//找第一个出现的并且是字典序最小的！ if(cnt[j]!=0) continue;//以下情况就是每个字母只有一次，那么缺少多少个字母就有多少个问号，所以pos一定为-1 int pos=tmp.find('?');tmp[pos]=(char)(j+'A');}cout<<tmp;return 0; }cout<<"-1"; return 0;
}

总结反思

做题一定要看测试数据范围，不在数据类型上吃亏，在简单的测试点上拿到分。做题也要审清楚题，有的题目很长很复杂，但一定要学会边读边圈点，转化成简洁的描述，更不要曲解题意。

HRZ学英语

题目描述

思路分析

观察这道题目的测试点，被后4个点庞大的测试数据紧张到了，在考场上时间有限，那肯定尽力拿到前6个点的分数。
言归正传，如何解题呢？第10^18次数字，这显然不能把这些数字真正存储到字符串或者数组中，内存都要溢出了叭。不妨观察一下规律。可以把一个超级长的序列按照数字的位数划分成几个块，只有1位数字的就是第一块的数字，有9位的数字就划分成第9块（块号等于位数）。在块中按照结尾数字不同又划分成不同的段。这样划分下来，同一块中的段的数字长度（段总位数）其实是一组以块号（数字位数）为公差的等差序列。
定义两个数组a,b，分别记录当前块i中总长度，位数为i的最大值即pow(10,i+1)-1结尾的段长度。
之后就要锁定要查找的k在哪个块中，只需要在数组a中找到第一个大于或者等于k的索引bit，这个bit就是块号。然后就要在这个块中进行查找k所在的哪个位置，所以需要对k值进行处理，将k转化成在块的索引位置，即k-=a[1:bit-1]。之后就要找到现在的k是以哪个数字结尾的也就是锁定是在哪个段，采用二分查找。l=1,r=r=(long long)(9pow(10,bit-1))。锁定完毕后，接下来就要锁定k所在的是在哪个数字中，这里也同样要将k值进行转化一下，k-=((b[bit-1]+bit)+(b[bit-1]+rbit))*r/2。找到所在的数字后，后面的问题就迎刃而解了。
这道题目需要有很清晰的数学应用，我就因为计算的问题绕了很久

代码实现

//把以1~number结尾的序列全部拆开看也就是：
//1;  1,2;  1,2,3;  1,2,3,4; 
#include<bits/stdc++.h>
using namespace std;
long long a[21]={0},b[21]={0};
long long n=0;void get_bit(){long long cnt=9;//10与1的距离 long long i;a[0]=0;b[0]=0;//初始 for(i=1;i<=20;i++){//i表示位数 a[i]=((b[i-1]+i)+(b[i-1]+cnt*i))*cnt/2;//i位数的序列的总长度   总！！！ b[i]=b[i-1]+cnt*i;//以最大i位数值结尾的序列的长度 cnt*=10;//位数+1 if(a[i]>=(long long)pow(10,18)) break;}n=i;//求得满足测试的最大位数 
}void get_num(long long k){long long bit;for(bit=1;bit<=n;bit++)	//求k所在序列的最后数字的位数 if(a[bit]>=k) break;for(long long j=1;j<bit;j++) k-=a[j];//减去k所在序列的前面序列的长度，转化成最后数位数是bit的若干个序列中查找//之后，查找k所在的是哪个序列（锁定到单个序列！） long long l=1,r=(long long)(9*pow(10,bit-1)),mid;//二分查找找到k是bit位中哪个序列的 while(l<=r){mid=(l+r)/2;	if((long long)(((b[bit-1]+bit)+(b[bit-1]+mid*bit))*mid/2)>=k) r=mid-1;//mid位置以上的个数小月k的话 else l=mid+1;}//找到k是该序列中哪个位置 //这个序列分成几个段  位数相同的就是一个段 d位数的序列的数字总位数是9*pow(10,d-1)k-=((b[bit-1]+bit)+(b[bit-1]+r*bit))*r/2;//把k转化成当前序列中mid之后的索引 long long d=1;long long sum=-1;
//	ll sum=9*pow(10,d-1)*d;//在这个序列中位数为1的有多少个while(true){sum=(long long)(9*pow(10,d-1)*d);//位数为d的一共有多少个位 if(sum>=k) break;//达到k结束 k-=sum;//否则d++;}long long num=(k+d-1)/d;//k实际的位置是这个序列中的第num个数的d位数字中，注意！！这里要加上d-1考虑在d位的数中间 k-=(num-1)*d;//将k转化成在这个d位数中的位置 num=pow(10,d-1)+num-1;//要找的k位置就是在这个数字中 long long cnt=d-k+1;//在这个数字中位于这个位置 /*string st;stringstream ss;ss>>num;ss<<st;printf("%c\n",st[cnt+1]);*/for(long long i=1;i<cnt;i++) num/=10;//把cnt位置后面的数字都除去 ，保留cnt以及之前的数字 printf("%lld\n",num%10);//cnt位置的数字	 
}int main(){long long q,k;scanf("%lld",&q);get_bit();//可能达到的最多的位数 while(q--){scanf("%lld",&k);get_num(k);}return 0; 
}