-
csp-j/s模拟题详细题解
csp-j/s模拟题详细题解
装水
题目详情
题目描述
一天小理买了N个容量可以认为是无限大的瓶子，开始时每个瓶子里有1升水。接着小理发现瓶子实在太多了，于是他决定保留不超过K个瓶子，每次他选择两个当前含水量相同的瓶子合并。（即把一个瓶子的水全部倒进另一个里然后把空瓶丢弃）（注：不能丢弃有水的瓶子）
显然在某些情况下小理无法达到目标，比如N = 3, K = 1。此时小理会重新购买一些新的瓶子（新瓶子容量无限，开始时有1升水）以达到目标。
现在小理想知道最少需要多少新瓶子才能达到目标呢？
输入格式
一行两个正整数N和K，含义见题。输出格式
输出文件包含一个非负整数，表示最少需要购买的瓶子数量。1.4 测试样例
1.4.1 样例输入1(water.in)
3 1
1.4.2 样例输出1(water.out)
1
1.4.3 样例输入2(water.in)
13 2
2
CSP-J 模拟题 执理OI
1.4.4 样例输出2(water.out)
3
1.4.5 样例输入3(water.in)
1000000 5
1.4.6 样例输出3(water.out)
15808
1.5 任务约束
对于50%的数据，保证1 ⩽ n ⩽ 10^7
对于100%的数据，保证1 ⩽ n ⩽ 10^9, 0 ⩽ k ⩽ 1000AC代码
这道题只需要将瓶子数转化为2进制看看里面包含多少个1即可,例如13的二进制是1101,16的二进制是10000,只有一个1,小于输入的2,所以最终答案就是16-13,所以这道题的难点就在于如何不超时传化二进制
代码1(90分)
可以用到__builtin_popcount(n)来做到快速计算二进制的1的个数
代码如下#include#include #include #include using namespace std; int main(){ //freopen("water.in","r",stdin); //freopen("water.out","w",stdout); int n,k; cin >> n >> k; int ans = 0; while(__builtin_popcount(n) > k){ ans++; n++; } cout << ans << endl; return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
如果不会的话手写也是可以的
代码2(90分)
#include#include #include #include #include using namespace std ; int count(int x){//这里的作用是一样的 int s=0; while(x){ if(x%2) s++; x/=2; } return s; } int main() { int n,k; cin >> n >> k; int ans = 0; while(count(n) > k){ ans++; n++; } cout << ans << endl; return 0; } - 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
怎么做到ac呢?
代码3(AC)
代码如下
#include#include #include #include #include using namespace std ; int count(int x){ int s=0; while(x){ if(x%2) s++; x/=2; } return s; } int lowbit(int x){ return x&-x; } int main() { int n,k; cin >> n >> k; int ans = 0; while(count(n) > k){ ans+=lowbit(n);//直接寻找二进制最后一个1的位置,这样做不会超时 n+=lowbit(n); } cout << ans << endl; return 0; } - 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
和数(sum)
题目详情
2.1 问题描述
小理对数字之美的追求不局限于质数了，他发现了一种非常靓丽的数字，
并命名为「和数」。「和数」就是能表示为一些互不相同的整数的阶乘之和的
数。如9 = 1! + 2! + 3!。
现在给定一个非负整数n，要求判断n是否为「和数」。
如果是，则输出“YES”，否则输出“NO”(引号不输出)。
2.2 输入格式
每行一个非负整数n，最后一行是一个负数，作为输入的结束。
2.3 输出格式
对于每个非负整数n，在输出文件中分别输出“YES”或“NO”，各占1行。
2.4 测试样例
2.4.1 输入文件(sum.in)
9
5
-1
2.4.2 输出文件(sum.out)
YES
NO
2.5 任务约束
对于20%的数据，保证n ⩽ 10000
对于60%的数据，保证n ⩽ 100000
对于所有的数据，保证n ⩽ 1000000AC代码
可以发现所有的数字都是由1-10中的数字组成的,所以只需要看他们是否可以被1-10中小于等于他们的数字减完等于0,如果等于就是yes,否则是no
#include#include #include #include using namespace std; int a[1006]; int n,wc=0; int ans[100006]; int main(){ //freopen("sum.in","r",stdin); //freopen("sum.out","w",stdout); a[0]=1; for(int i=1;i<=11;i++) a[i]=a[i-1]*i; while(cin>>n){ if(n<0){//注意题目要求,输入负数结束程序 break; } if(n==0){//特判下 cout<<"NO"<<endl; continue; } for(int i=10;i>=0;i--){ if(n>=a[i]) n-=a[i]; } wc++; if(n==0){ ans[wc]=1; continue; }else{ ans[wc]=0; continue; } } for(int i=1;i<=wc;i++){//我这里单独记录了答案输出,边做边输出也是可以的,不用在意(一开始不停的wa,以为是输出格式的问题......) if(i==wc){ if(ans[i]){ cout<<"YES"; }else{ cout<<"NO"; } }else if(ans[i]){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } } - 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
解方程(equationagain)
题目详情
3.1 问题描述
小理学习了计算机编程之后，他发现运用编程可以轻松结局令他头疼的一
元一次方程问题，于是他准备编一个程序用于解方程。
给出一个字符串，表达一个方程。
数据保证方程有且只有一个解，而且方程只会有一个未知数X，且X的最
高指数也只会有1。方程中所有的系数都是整数，且系数是1就会被省略。只会
出现加、减符号，不会出现乘、除。
3.2 输入格式
输入一个字符串表示方程。
3.3 输出格式
输出X的解，保留三位小数。
3.4 测试样例
3.4.1 输入文件(equationagain.in)
6x+7x+8x+1=6x+7x+9x
3.4.2 输出文件(equationagain.out)
1.000
3.5 任务约束
对于10%的数据，输入满足ax = b 的形式
对于另外的30%的数据，含未知数的参数仅一项
对于另外的10%的数据，未知数仅出现在等号左边且符号仅为加号
对于另外的10%的数据，未知数仅出现在等号左边
对于100%的数据，保证字符串的长度不会超过255AC代码
#include#include #include #include using namespace std; char a[10006]; int main(){ //freopen("equationagain.in","r",stdin); //freopen("equationagain.out","w",stdout); cin>>a; int c=strlen(a); int wc=0; for(int i=0;i<=c;i++){ if(a[i]=='('){ wc=1; c-=1; for(int j=i;j<=c;j++){ a[j]=a[j+1]; } } if(a[i]==')'){ wc=0; c-=1; for(int j=i;j<=c;j++){ a[j]=a[j+1]; } } if(wc){ if(a[i]=='+'){ a[i]='-'; }else if(a[i]=='-'){ a[i]='+'; } } } a[c]='-'; int fg=0; double wcc=0; double x=0,y=0; int p=1; for(int i=0;i<=c;i++){ if(a[i]=='x'&&(a[i-1]!='9'&&a[i-1]!='8'&&a[i-1]!='7'&&a[i-1]!='6'&&a[i-1]!='5'&&a[i-1]!='4'&&a[i-1]!='3'&&a[i-1]!='2'&&a[i-1]!='1'&&a[i-1]!='0'))//这里用isdigit(n)更方便,这个是判断字符是不是数字的 { wcc=1; } if (isdigit(a[i])) wcc=wcc*10+(a[i]-'0'); if((a[i-1]<='9'&&a[i-1]>='0')&&(a[i]=='-'||a[i]=='+'||a[i]=='=')){ wcc=wcc*p; if(!fg){ y=y-wcc; }else{ y=y+wcc; } wcc=0; }else if(a[i]=='x'){ wcc=wcc*p; if(!fg){ x+=wcc; }else{ x-=wcc; } wcc=0; } if(a[i]=='+'||a[i]=='='||a[i]=='-'){ if(a[i]=='-'){ p=-1; }else { p=1; }} if(a[i]=='='){ fg=1; } } double ww; ww=y/x; printf("%.3lf\n",ww); } - 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
溜乌龟(tortoise)
题目详情
4.1 问题描述
乌龟们在被划分成N行M列的草地上游走。
设S为乌龟在T秒内从(R1,C1)走到(R2,C2)所能选择的路径总数，每一秒
内，乌龟会水平或垂直地移动1单位距离（乌龟总是在移动，不会在某秒内停在
它上一秒所在的点）。草地上的某些地方有树，自然，乌龟不能走到树所在的
位置，也不会走出草地。
现在你拿到了一张整块草地的地形图，其中.表示平坦的草地，∗表示挡路
的树。你的任务是计算出，乌龟在T秒内从(R1,C1)移动到(R2,C2)可能经过的
路径条数。
4.2 输入格式
第1行: 3个用空格隔开的整数：N，M，T
第2…N+1行: 第i+1行为M个连续的字符，描述了草地第i行各点的情况，保
证字符是.和*中的一个
第N+2行: 4个用空格隔开的整数：R1，C1，R2，以及C2。
4.3 输出格式
输出S，表示乌龟在T秒内从(R1,C1)移动到(R2,C2)可能经过的路径条数。
4.4 测试样例
以文件形式下发
4.5 任务约束
对于10%的数据，保证地图中没有「挡路的树」
对于另外60%的数据，2 ⩽ N, M ⩽ 20
对于100%的数据，2 ⩽ N ⩽ 100; 2 ⩽ M ≤ 100; 0 < T ≤ 15AC代码
记忆化搜索完事
#include#include #include #include #include using namespace std; int tx[5]={0,1,-1,0,0}; int ty[5]={0,0,0,1,-1}; int t,x,y,x1,y11; int mapp[1000][1000]; int n,m; struct node{ int x,y,st; }; int dp[101][101][20]; void bfs(int xx,int yy){ queue<node> q; q.push((node){xx,yy,0}); dp[xx][yy][0]=1; while(!q.empty()){ node c; c=q.front(); for(int i=1;i<=4;i++){ int dx=c.x+tx[i]; int dy=c.y+ty[i]; int dt=c.st+1; if(dp[dx][dy][dt]) dp[dx][dy][dt]+=dp[c.x][c.y][c.st]; if(dx>0&&dy>0&&dx<=n&&dy<=n&&mapp[dx][dy]==0){ dp[dx][dy][dt]+=dp[c.x][c.y][c.st]; q.push((node){dx,dy,dt}); } } } } int main(){ //freopen("tortoise.in","r",stdin); //freopen("tortoise.out","w",stdout); cin>>n>>m>>t; char w; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>w; if(w=='*'){ mapp[i][j]=1; }else{ mapp[i][j]=0; } } } cin>>x>>y>>x1>>y11; bfs(x,y); cout<<dp[x1][y11][t]; } - 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
@^ _ ^@
-
相关阅读:
LeetCode刷题记录-简单模块（三）
SMART PLC飞剪控制算法
新发现，新挑战，技术出海的机遇与挑战丨PingCAP DevCon 2022 出海专场
推动智行生态融合！Flyme 迎来大动作，魅族与星纪时代布局初显
基于STM32+物联网设计的货车重量检测系统(OneNet)
关于跨域问题详解
新一代信息技术与制造业融合发展背景下网络安全挑战和思考
英文论文（sci）解读复现【NO.21】一种基于空间坐标的轻量级目标检测器无人机航空图像的自注意
Google Earth Engine（GEE）—— Landsat7和8的2000-2021年的影像土地分类的下载和视频导出
JavaSE题
- 原文地址：https://blog.csdn.net/m0_66623111/article/details/126507277
