模拟题t1，t2，t4"/>
week8——csp模拟题t1，t2，t4
Problem1——HRZ的序列
问题描述
问题分析
如果这个数列是满足情况的，只会有三种情况，1全是一样的数字，每个数字不变即可达到目标。2总共有两个数字，其中一种数字加上k可以变成另一种数字。3有三种数字，分别对应的操作是，加k，不变，减k。
于是我先是对每一个输入进来的数据先进行去重，是一样的数字，或者不一样但是不一样数字的个数小于等于三。一旦超过三，就判断为NO。然后对于判重后的数字进行一下排序。如果是三个数字，那么最小的数字加上最大的数字一定等于中间那个数字的两倍。如果是一个或者两个数字，则不需要判断，直接是对的。
这个的算法比较简单，复杂度只有n。
代码
#include<iostream>
using namespace std;
#include<algorithm>
long long a;//[10001];
int t,n;
long long ans[3];
bool pan=true;
bool cmp(long long a,long long b)
{return a<b;}
int main()
{scanf("%d",&t);for(int k=0;k<t;k++){scanf("%d",&n);ans[0]=0;//初始化 ans[1]=0;ans[2]=0;pan=true;for(int i=0;i<n;i++){scanf("%lld",&a);//cout<<a<<endl;for(int j=0;j<3;j++){if(ans[j]==0){ans[j]=a;//cout<<" kong="<<a<<endl;break;}else if(ans[j]==a){//cout<<" youle"<<a<<endl;break;}else if(j==2&&ans[j]!=a){//cout<<" duole"<<a<<endl;pan=false;break;}}}sort(ans,ans+3,cmp);//for(int i=0;i<3;i++)//cout<<ans[i]<<endl;//cout<<" yayaya"<<ans[0]+ans[2]<<" wwww"<<ans[1]*2<<endl;if(pan&&ans[0]+ans[2]==ans[1]*2){printf("YES");}else if(ans[0]==0||ans[1]==0||ans[2]==0){printf("YES");}else{printf("NO");}if(k!=t-1)printf("\n");}return 0;
}
遇到的问题
情况没考虑全面，想到什么写什么，导致只有一种大小数字的情况没有想到，以后一定先分析一下情况再开始描写。
Problem2——HRZ 学英语
问题描述
问题分析
采用了尺取法，选取区间，判断该区间是否符合要求，不符合要求左区间往右移，直到满足条件（不是得到答案的那种满足条件，只是每个字母出现的个数和总共区间的长度），因为描述了里面只有26个大写字母和？，所以就用了数组vis[]确定每个大写字母在我所选择的区间的个数，一旦超过1，则这个选择的区间就是不合格的。不合格就让左端点往右移动，并对应出区间的字符做出相应的改变操作。
代码
#include<iostream>
using namespace std;
char zi[1000001];
int vis[27];
char English[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
int num=0;
int main()
{cin>>zi;int left=0,right=0;int shu;for(int i=0;i<27;i++)vis[i]=0;while(zi[right]!='\0'&&left<=right){//cout<<"left="<<left<<" right="<<right<<endl;if(zi[right]=='?'){num++;right++;}else {shu=zi[right]-'A';//cout<<" shu="<<shu<<" zi="<<zi[right]<<endl;if(vis[shu]==0)//满足条件{vis[shu]=1;num++;right++;} else if(vis[shu]==1)//不满足条件{if(zi[left]=='?')num--;else{vis[zi[left]-'A']=0;num--;}left++;} }//cout<<num<<endl;if(num==26){break;} }/*for(int i=left;i<left+26;i++){cout<<zi[i]<<" ";}cout<<endl;for(int i=0;i<26;i++){cout<<vis[i]<<" ";}*/if(num==26){for(int i=left;i<left+26;i++){if(zi[i]=='?'){for(int j=0;j<26;j++){if(vis[j]==0){cout<<English[j];vis[j]=1;break;}}}elsecout<<zi[i];}//cout<<endl;}else{cout<<-1;}return 0;
}
Problem3——咕咕东的奇妙序列
问题描述
问题分析
这道题主要是一个数学归纳问题，利用归纳方法我们会发现，在1 ~ 9数字一个占一位字符，10 ~ 99数字一个占两位以此类推。所以先算出是第几个这样的数（1 ~n），然后再算出是这个n中的第几个，然后得到该数是多少，再得到我们找的是这个数的第几位数，将这个数直接转化成string型，输出你要找的位数上的字符即可。
具体一些的操作就是，先用二分法去找到这个位数在于哪一个数上面，复杂度为log（n）*lg（n），首先先找到我们要求的数的位数，并顺便把它前面的数也算一遍，利用几位数的个数乘以其位数，即可。然后在找到位数后，进行计算其前面的数字个数，从而得到他的个数。
代码
#include<iostream>
using namespace std;
#include<cstdio>
#include<string>
#include<cmath>
int q;
long long k;
long long sum;
long long a,c,n,po;//之前的位数和 当前每个数字占的长度 当前位数的数字之和 位数
long long mid,ll,rr,ans,number;
string shu;
int tot;
void wei(long long num)
{sum=0;a=0;c=0;n=0;po=1;while(true){po=po*10;c=c+1;//每个数字的长度n=po-po/10;//当前位数 if(num>=po)//完全大于这个位数的数字{sum=sum+(a+c)*n+(n-1)*n/2*c;a=a+c*n;}else{n=num-po/10+1;sum=sum+(a+c)*n+(n-1)*n/2*c;a=a+c*n;break;}}}
/*char shuzi(long long x,long long y)
{sum=0;a=0;c=0;n=0;pow=1;while(pow<=y){pow=pow*10;c=c+1;//每个数字的长度n=pow-pow/10;a=a+c*n;if(a>=x)//完全大于这个位数的数字{a=a-c*n;n=x-a;sum=n/c;pow=pow/10;break;}}y=pow+n/c;shu=char(y*pow*10+y+1);cout<<shu;return shu[n%c+c-1]; }*/
int main()
{scanf("%d",&q);for(int i=0;i<q;i++){scanf("%lld",&k);ll=0;rr=1000000000;//cout<<"111"<<endl;while(ll<=rr){mid=(ll+rr)>>1;//cout<<" mid="<<mid<<" rr="<<rr<<" ll="<<ll<<endl;wei(mid);//cout<<"ans="<<sum<<endl;if(sum>=k){ans=mid;rr=mid-1;}else if(sum<k){ll=mid+1;}}wei(ans-1);k=k-sum;//cout<<ans<<" "<<k<<endl;ll=0;rr=ans+1;while(ll<=rr){mid=(ll+rr)>>1;wei(mid);if(a>=k){ans=mid;rr=mid-1;}else if(a<k){ll=mid+1;}}wei(ans-1);k=k-a;//cout<<ans<<" "<<k<<endl;//第ans个数的第k位//number=shuzi(k,ans);shu=to_string(ans);//cout<<shu<<endl;printf("%c\n", shu[k - 1]);//}return 0;
}
遇到的问题
这个有些多，
1.没有搞清楚题意，骗分都没骗到，错误理解为输出的是整个数字而不是这个数字的某一位数
2.对于二分法没有掌握的十分确切，耗费了很多时间再调改二分法上面。
更多推荐
week8——csp模拟题t1,t2,t4
发布评论