• CSP-X模拟赛二王胤皓补题报告

    日期：2023.10.3                考试时间：9:00---->11:00

    学号：S07738                    姓名：王胤皓

    一、我的题目分数 (^v^)


    T1【称心如意(satisfied)】:（Accepted）100分(^v^)(^v^)(^v^)(^v^)(^v^)

    T2【AC万岁(acok)】:（Accepted）100分(^v^)(^v^)(^v^)(^v^)(^v^)

    T3【解救达达(rescue)】:（Wrong Answer）90分(^v^)(^v^)(^v^)(^v^)(^-^)

    T4【整理文本(text)】:（Runtime Error）0分  :(

    总分（290）分，比上次进步了170分，欧耶！比孙晨佑多了20分！！！（开心死我了）

    二、比赛过程

    第一题（称心如意(satisfied)）：)

    我觉得简单（一下子就作对了）

    第二题（AC万岁(acok)）：)

    我觉得简单（一下子就作对了）

    第三题（解救达达(rescue)）：)

    我觉得有点难（得了90分，还行）

    第四题（整理文本(text)）：(

    我觉得非常难（得了0分）

    题目解析：

    第一题：称心如意(satisfied)：

    题目描述：

    根据题目，我们可以知道字符串的构造要求：

    序列的长度为 N+1

    假设序列第 i 位取值为 j ( j 的范围为 1 到 9)，那么需要满足 N%j==0，并且需要满足 i 能整除，即 i%(N/j)==0

    满足条件2的基础上，j 的取值应该尽量小

    若条件2不能满足，那么第 i 位输出一个 -。

    输入样例
    12
    输出样例
    1-643-2-346-1

    样例说明

    当 i==0 时，满足条件的 j 有1,2,3,4,6，取最小的为 1

    当 i==4 时，满足条件的 j 有3,6，取最小的为 3

    做题思路：

    输入N；

    循环N+1次，i从0~N循环

    在循环的时候，嵌套一个循环，j,j从1开始循环，到9结束

    定义一个flag并初始化为0.

    如果（N%j==0&&i%(N/j)==0）输出j，flag标记，跳出循环

    如果flag为初始值，那么输出"-".

    因为N的取值范围为10^5，所以不会时间超限。

    好，我废话不多说,上Accepted代码（因为我的思路和正确代码一样，所以就贴一个代码了）

    1. #include<iostream>
    2. #include<cstdio>
    3. using namespace std;
    4. int main(){
    5. 	int N;
    6. 	scanf("%d",&N);
    7. 	for(int i=0; i<=N; i++){//循环N+1次 
    8. 		int flag=0;//定义一个标记变量flag 
    9. 		for(int j=1;j<=9;j++){//j的取值范围为1~9 
    10. 			if(N%j==0&&i%(N/j)==0){//如果满足题目条件 
    11. 				printf("%d",j);//直接输出 
    12. 				flag=1;//标记 
    13. 				break;//提前结束 
    14. 			}
    15. 		}
    16. 		if(flag==0) printf("-");//如果没有合法的，输出'-'; 
    17. 	}
    18. 	return 0;
    19. }

    第二题：AC万岁（acok）:

    题目描述：

    给定一个字符串，请计算ac作为字符串子序列出现的次数

    注意：字符串子序列指的是从最初字符串通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。例如，acf、bde、bcd都是abcdef的子序列，而cae并不是。

    输入描述

    输入一行，包含一个字符串 s 。

    注意：s中仅包含小写字母。

    输出描述

    输出一行，表示ac的数量。

    输出样例
    aaaccc
    输入样例
    9
    数据范围

    在30% 数据下：2≤∣s∣≤100

    在60% 数据下：2≤∣s∣≤1000

    在100% 数据下：2≤∣s∣≤100000

    做题思路：

    输入字符串

    定义计数器aa,ac（求每个c前面有多少个a,ac记录几个ac）

    遍历字符串

    如果当前字符为’a',那么aa+1；

    如果当前字符为'c‘，那么ac=ac+a;

    最后输出ac;

    好，我废话不多说,上Accepted代码(我一开始的代码)

    1. #include
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6. vector<int> v;
    7. int main(){
    8. 	char a[100005];
    9. 	cin>>a;
    10. 	for(int i=0;i<strlen(a); i++){
    11. 		if(a[i]=='c') v.push_back(i); 
    12. 	}
    13. 	long long cnt=0;
    14. 	for(int i=0;i<strlen(a); i++){
    15. 		if(v.size()==0){
    16. 			break;
    17. 		}
    18. 		if(*v.begin()==i) v.erase(v.begin());
    19. 		if(a[i]=='a'){
    20. 			cnt+=1ll*v.size();
    21. 		}
    22. 	}
    23. 	printf("%lld",cnt);
    24. 	return 0;
    25. }

    好，我废话不多说,上另一个Accepted代码（将了之后）

    1. #include
    2. #include
    3. using namespace std;
    4. int main(){
    5. 	string a;
    6. 	cin>>a;
    7. 	int aa=0,ac=0;//求每个c前面有多少个a,ac记录几个ac
    8. 	for(int i=0;isize(); i++){
    9. 		if(a[i]=='a') aa++;//遇到一个a,那么aa++ 
    10. 		if(a[i]=='c') ac+=aa;//如果遇到一个c，那么ac加上之前的a的个数，也就是aa
    11. 	} 
    12. 	cout<
    13. 	return 0;
    14. }

    第三题解救达达(rescue）：

    题目描述：

    达达被怪兽 1 抓走了，小可作为达达最好的朋友，要去将达达解救回来。

    怪兽的名字叫做 1，是因为怪兽最喜欢的数字就是1，而最害怕的数字就是0。

    怪兽每天以数字为食，而吃的数字是由二进制表示的。

    现在小可知道只要有足够多的 0 混入怪兽的食物，就可以击败怪兽，救出达达。

    而食物在被怪兽吃掉之前，会被检查，如果数字的二进制中有两个及以上的 0 （前导 0不算，即从第一个非0数表示二进制），怪兽不会吃掉这个数字。

    小可给怪兽贡献了一个区间为 [a,b] 的数字，请计算一下这个区间内有多少个数字会伤害到怪兽。

    输入描述

    输入一行，包含两个数字a,b

    输出描述

    输出一个整数，表示答案。

    输入样例1
    5 10
    输出样例1

    2

    数据范围

    在 100% 数据下：1≤a≤b≤10^{18}

    做题思路

    一开始的思路

    我首先枚举了符合条件的二进制和对应的十进制

    10=2

    101=5

    110=6

    1011=11

    1101=13

    1110=14

    10111=23

    11011=27

    11101=29

    11110=30

    101111=47

    110111=55

    111011=59

    111101=61

    111110=62

    1011111=95

    1101111=111

    1110111=119

    1111011=123

    1111101=125

    1111110=126

    10111111=191

    11011111=223

    11101111=239

    11110111=247

    11111011=251

    11111101=253

    11111110=254

    我先用快速幂求出2的0到62次方，并用数组存储

    规律：

    分成62组，每一组的数量为计数器

    第一组:2

    第二组：5 6

    第三组：11 13 14

    第四组：23 27 29 30

    第五组：47 55 59 61 62

    不难看出，每一组的开头为上一组开头的2倍+1

    每一组，从第二个元素开始，等于上一个元素+（2的（第几组-当前元素是这一组的第几个元素））

    最后累加求和

    1. long long ans=0;
    2. 	for(int i=0;i<v[begin].size(); i++){
    3. 		if(v[begin][i]>=a&&v[begin][i]<=b) ans++;
    4. 	}
    5. 	for(int i=begin+1; i<end; i++){
    6. 		ans+=v[i].size();
    7. 	}
    8. 	if(end!=begin){
    9. 		for(int i=0;i<v[end].size(); i++){
    10. 			if(v[end][i]<=b&&v[end][i]>=a) ans++;
    11. 		}	
    12. 	}
    正确思路

    枚举，i从1循环到63

    每一次循环,j再从0开始，循环到i-2

    如果2^{i} -1 - 2^{j}\geq a并且2^{i} -1- 2^{j}\leq b,那么计数器+1

    最后输出计数器。

    好，我废话不多说,上我一开始的代码(Wrong Answer)：

    1. #include<iostream>
    2. #include<vector>
    3. #include<cstdio>
    4. using namespace std;
    5. vector<long long> v[105];
    6. long long poww(long long a,long long b){
    7. 	if(b<0){
    8. 		return 0;
    9. 	}
    10. 	long long sum=1;
    11. 	while(b){
    12. 		if(b%2==1) sum=sum*a;
    13. 		a=a*a;
    14. 		b>>=1;
    15. 	} 
    16. 	return sum;
    17. }
    18. long long sum[63];
    19. int main(){
    20. 	long long a,b;
    21. 	int cnt=1;
    22. 	scanf("%lld%lld",&a,&b);
    23. 	for(int i=0;i<=62; i++) sum[i]=poww(2,i);
    24. 	long long begin=-1,end=62;
    25. 	for(long long i=2; i<=2000000000000000000; i=i*2+1){
    26. 		if(i>=a&&begin==-1) begin=cnt;
    27. 		if(i>b){
    28. 			end=cnt-1;
    29. 			break;
    30. 		}
    31. 		long long t=0;
    32. 		for(int j=cnt-1,k=0; j>=0; j--,k++){
    33. 			if(k==0){
    34. 				v[cnt].push_back(i);
    35. 				t=i;
    36. 			}
    37. 			else{
    38. 				v[cnt].push_back(t+sum[j]);
    39. 				t=t+sum[j];
    40. 			}
    41. 		}
    42. 		cnt++;
    43. 	}
    44. 	long long ans=0;
    45. 	for(int i=0;i<v[begin].size(); i++){
    46. 		if(v[begin][i]>=a&&v[begin][i]<=b) ans++;
    47. 	}
    48. 	for(int i=begin+1; i<end; i++){
    49. 		ans+=v[i].size();
    50. 	}
    51. 	if(end!=begin){
    52. 		for(int i=0;i<v[end].size(); i++){
    53. 			if(v[end][i]<=b&&v[end][i]>=a) ans++;
    54. 		}	
    55. 	}
    56. 	else printf("%lld",ans);
    57. 	return 0;
    58. }

    好，我废话不多说,上Accepted代码：

    1. #include
    2. #include
    3. using namespace std;
    4. int main(){
    5. 	long long a,b,cnt=0;
    6. 	scanf("%lld%lld",&a,&b); //a和b<=10的18次方，所以使用scanf来进行输入 
    7. 	for(int i=1; i<=63; i++){//2的1次方到2的63次方，所以循环从1到63 
    8. 		for(int j=0;j<=i-2; j++){//改变1个地方的1改为0 
    9. 			long long num=((1ll<<(1ll*i))-1)-(1ll<<(1ll*j));//先将2的i次方求出来，减去1之后，那么这个十进制数的二进制就全部为1，将其中一位数改为0之后，那么这个数字就减去2的j次方，而数字是long long类型，所以不能是1，而是1ll。 
    10. 			if(num>=a&&num<=b) cnt++;//判断是否在a和b这两个数的闭区间里，如果是的话，那么计数器加1. 
    11. 		}
    12. 	}
    13. 	printf("%lld",cnt);
    14. 	return 0;
    15. }

    第四题整理文本(text)：

    题目描述：

    为了使得文本可以在一页之内就打印成功，小可必须使得文本整理在 M 行之内。

    小可数出了文本中总共有 N 个单词，并且小可记录出来了每个单词的长度 L​i​​。

    整理出来的文本必须要满足行首为当前行的第一个单词，相邻的两个单词需至少由一个空格间隔。

    当所有文本按照要求整理结束之后，得到每一行的行宽（当前行中单词的∑L​i​​ 加 空格数量），请使得其中最大的行宽最小，请输出对应的行宽值。

    注意：单词不能调换顺序，并且单词不能舍弃一部分。

    在 100% 数据下：1≤M≤N≤2×10^{5}​​,1≤L​i​​≤10^{9}

    思路：

    根据数据描述，我们不能枚举，我们需要进行二分，根据题目中”最大的行宽最小“，我们可以知道，这是一个求二分最小化答案的题目，首先，打上二分最小化答案的模板

    1. while(l<r){
    2. 		long long mid=(l+r)>>1;
    3. 		if(check(mid,a,n,m)) r=mid;
    4. 		else l=mid+1;
    5. 	}

    l一开始初始化为所有Li中最大的数字，r开始的时候为所有Li累加的和

    根据题目中，我们可以知道check里面要这样写：

    定义行数的计数器(sum)，并初始值赋值为1，还有一个记录当前这一行已经打了多少字(cnt)。

    for循环，i,循环n次

    每次如果cnt+L[i]+1小于或等于mid的时候，cnt加上L[i]和空格数(1)。

    否则行数+1，把cnt赋值为L[i]。

    最后，如果行数<=m，那么返回true,
    如果行数>m,那么返回false;

    好，话不多说，上Wrong Answer代码:

    1. #include<iostream>
    2. #include<cstdio>
    3. using namespace std;
    4. bool check(long long mid,int a[],int n,int m){
    5. 	long long cnt=0,sum=1;
    6. 	for(int i=1; i<=n; i++){
    7. 		cnt+=1ll*a[i]+1;
    8. 		if(cnt>mid){
    9. 			sum++;
    10. 			cnt=1ll*a[i]+1;
    11. 			continue;
    12. 		}
    13. 		if(cnt==mid){
    14. 			sum++;
    15. 			cnt=0;
    16. 		}
    17. 		cnt++;
    18. 	}
    19. 	return sum==1ll*m;
    20. }
    21. int main(){
    22. 	int n,m;
    23. 	scanf("%d%d",&n,&m);
    24. 	int a[100005];
    25. 	long long ans=0;
    26. 	for(int i=1; i<=n; i++){
    27. 		scanf("%d",&a[i]);
    28. 		ans+=1ll*a[i];
    29. 	}
    30. 	long long l=1,r=ans/(1ll*m-1);
    31. 	while(l<r){
    32. 		long long mid=(l+r+1)>>1;
    33. 		if(check(mid,a,n,m)) r=mid-1;
    34. 		else l=mid+1;
    35. 	}
    36. 	printf("%lld",r);
    37. 	return 0;
    38. }

    好，我废话不多说,上Accepted代码：

    1. #include<iostream>//头文件 
    2. #include<cstdio>//freopen和fclose必备头文件！！！ 
    3. using namespace std;//命名空间 
    4. bool check(long long mid,int a[],int n,int m){//二分答案check判断函数 
    5. 	long long cnt=-1,sum=1;//定义行数的计数器(sum)，并初始值赋值为1，还有一个记录当前这一行已经打了多少字(cnt)。
    6. 	for(int i=1; i<=n; i++){//for循环，i,循环n次,遍历单词长度数组 
    7. 		if(cnt+a[i]+1<=mid){//每次如果cnt+L[i]+1小于或等于mid的时候.
    8. 			cnt+=a[i]+1;//cnt加上L[i]和空格数(1)。
    9. 		}//if判断结束 
    10. 		else{//否则 
    11. 			sum++;//行数(sum)加1 
    12. 			cnt=a[i];//将有一个记录当前这一行已经打了多少字(cnt)赋值为当前这个单词的单词长度 
    13. 		}//else结束 
    14. 	}//for循环结束 
    15. 	return sum<=(1ll*m);//返回一个bool值，如果行数小于等于最多可以输出行数(m)，那么说明sum是合法的，就返回true, 如果行数大于最多可以输出行数(m)，那么说明sum是不合法的，就返回false 
    16. }//二分答案判断函数check结束 
    17. int main(){//主函数 
    18. 	int n,m;//定义n和m，n表示n个单词，m表示最多可以输出几行 
    19. 	scanf("%d%d",&n,&m);//用scanf来输入n和m. 
    20. 	int a[200005];//定义数组，用来输入每个单词的长度 
    21. 	long long ans=0,maxx=0;//定义累加器和最大值(ans-->累加器，maxx-->最大值) 
    22. 	for(int i=1; i<=n; i++){//for循环(1~n)
    23. 		scanf("%d",&a[i]);//使用scanf来进行输入 
    24. 		ans+=1ll*a[i];//ans累加求和a[i] 
    25. 		maxx=max(maxx,1ll*a[i]);//maxx利用库函数max来求自己和输入的a[i]来求最大值 
    26. 	}//for循环结束 
    27. 	long long l=maxx,r=ans;//因为要二分，所以定义左端点和右端点，(l-->左端点，r-->右端点)，将左端点设置为最大值(maxx),将右端点设置为累加器(ans) 
    28. 	while(l<r){//二分答案，因为是最小化答案，所以是l<r，不是l<=r，因为最小化答案最后l=r,用l<=r的时候，是二分答案最大化答案 
    29. 		long long mid=(l+r)>>1;//求中间之,及(l+r)/2,因为位运算比普通的快，所以写成(l+r)>>1,因为最小化答案靠近左端点，所以是(l+r),而二分最大化答案靠近右端点,所以是(l+r+1) 
    30. 		if(check(mid,a,n,m)) r=mid;//判断check函数，如果返回值为true,那么右端点设置为mid 
    31. 		else l=mid+1;//半段check函数，如果返回值为false,那么左端点设置为mid+1,为什么要+1,因为要是不加1，就可能造成死循环 
    32. 	}//二分答案结束 
    33. 	printf("%lld",r);//使用printf来输出r,因为r是long long类型，用std::cout会变成科学计数法，而printf不会变成科学计数法 
    34. 	return 0;//返回值为0 
    35. }//主函数结束

    考试总结：

    今天的题目比昨天的简单，分数也比以前的高（欧耶）（欧耶）

    当然，今天还是一如既往的，孙晨佑还是没有考过我（欧耶）（欧耶）

    当然，今天还是一如既往的，口口亚宸还是没有考过我（欧耶）（欧耶）

    最后，给某些人再说一次:头文件是#include,不是其他的，并且框架是
     

    freopen(".in","r",stdin);

    freopen(".out","w",stdout);

    ................................................................................

    ............................（你的代码）...............................

    ................................................................................

    fclose(stdin);

    fclose(stdout)

    ,不是

    freopen(".in","r",stdin);

    freopen(".out","w",stdin);

    ................................................................................

    .......................（你的代码）..................................

    ................................................................................

    fclose(stdin);

    fclose(stdin),

    并且最后提交的时候要把注释掉freopen和fclose的注释去掉，要不然判题机给你判0我可不管。

  • 相关阅读:
    Shell脚本之正则表达式详解
    ML/DL2022面试必备500知识点-《机器和深度学习纲要》免费分享
    远程连接问题1
    Baumer工业相机堡盟工业相如何使用BGAPISDK通过两种不同的方法进行图像回调函数的使用（C#）
    详解TCP/IP协议第三篇：通信数据在OSI通信模型的上下传输
    模块化打包工具-Webpack插件与其他功能
    模型生成自动化测试用例
    nginx 日志处理goaccess、shell
    Nginx 平滑升级-拒绝服务漏洞
    YII项目在Docker中运行缓慢
  • 原文地址：https://blog.csdn.net/ainiyoung/article/details/133514433