裝水

題目詳情

題目描述
一天小理買了N個容量可以認為是無限大的瓶子，開始時每個瓶子里有1升水。接著小理發(fā)現(xiàn)瓶子實在太多了，于是他決定保留不超過K個瓶子，每次他選擇兩個當(dāng)前含水量相同的瓶子合并。（即把一個瓶子的水全部倒進另一個里然后把空瓶丟棄）

（注：不能丟棄有水的瓶子）

顯然在某些情況下小理無法達到目標，比如N = 3, K = 1。此時小理會重新購買一些新的瓶子（新瓶子容量無限，開始時有1升水）以達到目標。

現(xiàn)在小理想知道最少需要多少新瓶子才能達到目標呢？

輸入格式
一行兩個正整數(shù)N和K，含義見題。

輸出格式
輸出文件包含一個非負整數(shù)，表示最少需要購買的瓶子數(shù)量。

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 模擬題 執(zhí)理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 任務(wù)約束
對于50%的數(shù)據(jù)，保證1 ? n ? 10^7
對于100%的數(shù)據(jù)，保證1 ? n ? 10^9, 0 ? k ? 1000

AC代碼

這道題只需要將瓶子數(shù)轉(zhuǎn)化為2進制看看里面包含多少個1即可,例如13的二進制是1101,16的二進制是10000,只有一個1,小于輸入的2,所以最終答案就是16-13,所以這道題的難點就在于如何不超時傳化二進制

代碼1(90分)

可以用到__builtin_popcount(n)來做到快速計算二進制的1的個數(shù)
代碼如下

#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;
}

如果不會的話手寫也是可以的

代碼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;
}

怎么做到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;
}

和數(shù)(sum)

題目詳情

2.1 問題描述
小理對數(shù)字之美的追求不局限于質(zhì)數(shù)了，他發(fā)現(xiàn)了一種非常靚麗的數(shù)字，
并命名為「和數(shù)」?！负蛿?shù)」就是能表示為一些互不相同的整數(shù)的階乘之和的
數(shù)。如9 = 1! + 2! + 3!。
現(xiàn)在給定一個非負整數(shù)n，要求判斷n是否為「和數(shù)」。
如果是，則輸出“YES”，否則輸出“NO”(引號不輸出)。
2.2 輸入格式
每行一個非負整數(shù)n，最后一行是一個負數(shù)，作為輸入的結(jié)束。
2.3 輸出格式
對于每個非負整數(shù)n，在輸出文件中分別輸出“YES”或“NO”，各占1行。
2.4 測試樣例
2.4.1 輸入文件(sum.in)
9
5
-1
2.4.2 輸出文件(sum.out)
YES
NO
2.5 任務(wù)約束
對于20%的數(shù)據(jù)，保證n ? 10000
對于60%的數(shù)據(jù)，保證n ? 100000
對于所有的數(shù)據(jù)，保證n ? 1000000

AC代碼

可以發(fā)現(xiàn)所有的數(shù)字都是由1-10中的數(shù)字組成的,所以只需要看他們是否可以被1-10中小于等于他們的數(shù)字減完等于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){//注意題目要求,輸入負數(shù)結(jié)束程序
			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;
			}
	}
} 

解方程(equationagain)

題目詳情

3.1 問題描述
小理學(xué)習(xí)了計算機編程之后，他發(fā)現(xiàn)運用編程可以輕松結(jié)局令他頭疼的一
元一次方程問題，于是他準備編一個程序用于解方程。
給出一個字符串，表達一個方程。
數(shù)據(jù)保證方程有且只有一個解，而且方程只會有一個未知數(shù)X，且X的最
高指數(shù)也只會有1。方程中所有的系數(shù)都是整數(shù)，且系數(shù)是1就會被省略。只會
出現(xiàn)加、減符號，不會出現(xiàn)乘、除。
3.2 輸入格式
輸入一個字符串表示方程。
3.3 輸出格式
輸出X的解，保留三位小數(shù)。
3.4 測試樣例
3.4.1 輸入文件(equationagain.in)
6x+7x+8x+1=6x+7x+9x
3.4.2 輸出文件(equationagain.out)
1.000
3.5 任務(wù)約束
對于10%的數(shù)據(jù)，輸入滿足ax = b 的形式
對于另外的30%的數(shù)據(jù)，含未知數(shù)的參數(shù)僅一項
對于另外的10%的數(shù)據(jù)，未知數(shù)僅出現(xiàn)在等號左邊且符號僅為加號
對于另外的10%的數(shù)據(jù)，未知數(shù)僅出現(xiàn)在等號左邊
對于100%的數(shù)據(jù)，保證字符串的長度不會超過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)更方便,這個是判斷字符是不是數(shù)字的
		{
			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);
} 

溜烏龜(tortoise)

題目詳情

4.1 問題描述
烏龜們在被劃分成N行M列的草地上游走。
設(shè)S為烏龜在T秒內(nèi)從(R1,C1)走到(R2,C2)所能選擇的路徑總數(shù)，每一秒
內(nèi)，烏龜會水平或垂直地移動1單位距離（烏龜總是在移動，不會在某秒內(nèi)停在
它上一秒所在的點）。草地上的某些地方有樹，自然，烏龜不能走到樹所在的
位置，也不會走出草地。
現(xiàn)在你拿到了一張整塊草地的地形圖，其中.表示平坦的草地，?表示擋路
的樹。你的任務(wù)是計算出，烏龜在T秒內(nèi)從(R1,C1)移動到(R2,C2)可能經(jīng)過的
路徑條數(shù)。
4.2 輸入格式
第1行: 3個用空格隔開的整數(shù)：N，M，T
第2…N+1行: 第i+1行為M個連續(xù)的字符，描述了草地第i行各點的情況，保
證字符是.和*中的一個
第N+2行: 4個用空格隔開的整數(shù)：R1，C1，R2，以及C2。
4.3 輸出格式
輸出S，表示烏龜在T秒內(nèi)從(R1,C1)移動到(R2,C2)可能經(jīng)過的路徑條數(shù)。
4.4 測試樣例
以文件形式下發(fā)
4.5 任務(wù)約束
對于10%的數(shù)據(jù)，保證地圖中沒有「擋路的樹」
對于另外60%的數(shù)據(jù)，2 ? N, M ? 20
對于100%的數(shù)據(jù)，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];
}

@^ _ ^@文章來源地址http://www.zghlxwxcb.cn/news/detail-686855.html

到了這里，關(guān)于csp-j/s模擬題詳細題解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！