csp-j/s模拟题详细题解_csp-j模拟试题

装水

题目详情

题目描述
一天小理买了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 ⩽ 1000

AC代码

这道题只需要将瓶子数转化为2进制看看里面包含多少个1即可,例如13的二进制是1101,16的二进制是10000,只有一个1,小于输入的2,所以最终答案就是16-13,所以这道题的难点就在于如何不超时传化二进制

代码1(90分)

可以用到__builtin_popcount(n)来做到快速计算二进制的1的个数
代码如下

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
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<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
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<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
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 ⩽ 1000000

AC代码

可以发现所有的数字都是由1-10中的数字组成的,所以只需要看他们是否可以被1-10中小于等于他们的数字减完等于0,如果等于就是yes,否则是no

#include<cmath>
#include<iostream>
#include<cstring>
#include<cstdio>
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%的数据，保证字符串的长度不会超过255

AC代码

#include<cmath>
#include<iostream>
#include<cstring>
#include<cstdio>
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 ≤ 15

AC代码

记忆化搜索完事

#include<cmath>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
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

@^ _ ^@