My Brain

文章标签

首页

归档

标签

关于

友人帐

载入天数...

载入时分秒...

阅

2022-08-31

13 min read

算法刷题小记

[NOIP1998 普及组] 幂次方

P1010 NOIP1998 普及组] 幂次方 - 洛谷

题目描述

任何一个正整数都可以用 $2$ 的幂次方表示。例如 $137=2⁷⁺²3+2^0 $。

同时约定方次用括号来表示，即 $a^b$ 可表示为 $a(b)$ 。

由此可知， $137$ 可表示为 $2(7)+2(3)+2(0)$

进一步：

$7= 2^2+2+2^0$ ( $2^1$ 用 $2$ 表示)，并且 $3=2+2^0$ 。

所以最后 $137$ 可表示为 $2(2(2)+2+2(0))+2(2+2(0))+2(0)$ 。

又如 $1315=2^{10} +2^8 +2^5 +2+1$

所以 $1315$ 最后可表示为 $2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)$ 。

输入格式

一行一个正整数 $n$ 。

输出格式

符合约定的 $n$ 的 $0, 2$ 表示（在表示中不能有空格）。

样例 #1

样例输入 #1

样例输出 #1

2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

提示

【数据范围】

对于 $100\%$ 的数据， $1 \le n \le 2 \times {10}^4$ 。

解题过程

看完题之后第一个想到的方法就是递归，先将输入的数字表示为相应的二进制，然后递归调用函数即可，具体思路如下方代码所示：

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

//递归函数，打印数字n对应的幂次方表示 
void PrintPower(int n){
	//递归的中止条件，遇到0则直接输出 
	if(n==0){
		cout<<"0";
		return;
	}
	vector<int> Binary;//存储n的二进制表示中为1的位 
	int bit=0;
	while(n!=0){
		if(n%2) Binary.push_back(bit);
		n=n/2;
		bit++;
	}
    //递归输出
	for(int i=Binary.size()-1;i>=0;i--){
		if(Binary[i]==1){
			cout<<"2";
		}
		else{
			cout<<"2(";
			PrintPower(Binary[i]);
			cout<<")";
		}
		if(i!=0) cout<<"+";
	}
	return;
}
int main(){
	int n;
	cin>>n;
	PrintPower(n);
	return 0;
}

[USACO1.5] [IOI1994]数字三角形 Number Triangles

[P1216 USACO1.5][IOI1994]数字三角形 Number Triangles - 洛谷

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

        7 
      3   8 
    8   1   0 
  2   7   4   4 
4   5   2   6   5

在上面的样例中,从 $7 \to 3 \to 8 \to 7 \to 5$ 的路径产生了最大

输入格式

第一个行一个正整数 $r$ ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】
对于 $100\%$ 的数据， $1\le r \le 1000$ ，所有输入在 $[0,100]$ 范围内。

解题过程

我第一个想到的方法是记忆化递归，自顶向下即可实现求解最大值。

#include<iostream>
#include<algorithm> 
#include<cmath>
using namespace std;

int r;//数字三角形行数
int triangle[1001][1001]={0};//存储数字三角形 
int MAX[1001][1001]={0};//存储计算结果，记忆化递归，避免重复计算
int MAX_route(int i,int j){//MAX_route(i,j)计算从第i行第j列到底边的最大路径
	if(i==r) return triangle[i][j];
	int x,y;
	//记忆化递归 
	if(MAX[i+1][j]!=0){
		x=MAX[i+1][j];
	}
	else{
		MAX[i+1][j]=MAX_route(i+1,j);
		x=MAX[i+1][j];
	}
	if(MAX[i+1][j+1]!=0){
		y=MAX[i+1][j+1];
	}
	else{
		MAX[i+1][j+1]=MAX_route(i+1,j+1);
		y=MAX[i+1][j+1];
	}
	return max(x,y)+triangle[i][j];
} 
int main(){
	cin>>r;
	for(int i=1;i<=r;++i){//读取数字三角形 
		for(int j=1;j<=i;++j){
			cin>>triangle[i][j];
		}
	}
	cout<<MAX_route(1,1);
	return 0;
}

但是发现竟然卡了一个测试集，看来还得将递归转成动态规划：

递归转动态规划只需要将递归函数替换为循环即可，同时要自底向上得去寻找路径：

#include<iostream>
#include<algorithm> 
#include<cmath>
using namespace std;

int r;//数字三角形行数
int triangle[1001][1001]={0};//存储数字三角形 

int main(){
	cin>>r;
	for(int i=1;i<=r;++i){//读取数字三角形 
		for(int j=1;j<=i;++j){
			cin>>triangle[i][j];
		}
	}
	//动态规划,我们可以直接在原数组上进行操作
	for(int i=r-1;i>=1;--i){
		for(int j=1;j<=i;++j){
			triangle[i][j]+=max(triangle[i+1][j],triangle[i+1][j+1]);
		}
	} 
	cout<<triangle[1][1];
	return 0;
}

[NOIP2005 普及组] 采药

[P1048 NOIP2005 普及组] 采药 - 洛谷

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

第一行有 $2$ 个整数 $T$ （ $1 \le T \le 1000$ ）和 $M$ （ $1 \le M \le 100$ ），用一个空格隔开， $T$ 代表总共能够用来采药的时间， $M$ 代表山洞里的草药的数目。

接下来的 $M$ 行每行包括两个在 $1$ 到 $100$ 之间（包括 $1$ 和 $100$ ）的整数，分别表示采摘某株草药的时间和这株草药的价值。

输出格式

输出在规定的时间内可以采到的草药的最大总价值。

样例 #1

样例输入 #1

样例输出 #1

提示

【数据范围】

对于 $30\%$ 的数据， $M \le 10$ ；
对于全部的数据， $M \le 100$ 。

【题目来源】

NOIP 2005 普及组第三题

解题过程

可以说这又是一道非常标准的模板题，即0-1背包，其实现思想如下：（过于基础，就不细说了）

#include<iostream>
#include<algorithm> 
#include<cmath>
#include<vector>
using namespace std;

int main(){
	int T,M;//采药总时间和草药数 
	cin>>T>>M;
	vector<pair<int,int> > Herb;//存储草药数据
	pair<int,int> p0(0,0);
	Herb.push_back(p0);//为了下标从1开始计起 
	for(int i=1;i<=M;++i){
		pair<int,int> p;
		cin>>p.first>>p.second;
		Herb.push_back(p); 
	}
	int dp[101][1001]={0};
	//dp[i][j]表示在前i个草药中采摘且用时不超过j时获得的最大价值
	for(int i=1;i<=M;++i){
		for(int j=1;j<=T;++j){
			int time,value;
			time=Herb[i].first;//时间 
			value=Herb[i].second;//价值 
			if(i==1){//首先初始化采第一株草药时的最大价值 
				if(j>=time)
					dp[i][j]=value; 
				else dp[i][j]=0;
				continue;
			}
			dp[i][j]=max(dp[i-1][j],(j>=time?dp[i-1][j-time]+value:0));
			//这里作是否采摘第i株草药的抉择：不采摘dp[i-1][j], 采摘dp[i-1][j-time]+value 
		}
	}
	cout<<dp[M][T];
	return 0;
}

[NOIP2006 普及组] 开心的金明

P1060 NOIP2006 普及组] 开心的金明 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 $N$ 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 $N$ 元。于是，他把每件物品规定了一个重要度，分为 $5$ 等：用整数 $1-5$ 表示，第 $5$ 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 $N$ 元（可以等于 $N$ 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第 $j$ 件物品的价格为 $v[j]$ ，重要度为 $w[j]$ ，共选中了 $k$ 件物品，编号依次为 $j_1,j_2,…,j_k$ ，则所求的总和为：

$v[j_1] \times w[j_1]+v[j_2] \times w[j_2]+ …+v[j_k] \times w[j_k]$ 。

请你帮助金明设计一个满足要求的购物单。

输入格式

第一行，为 $2$ 个正整数，用一个空格隔开： $n,m$ （其中 $N(<30000)$ 表示总钱数， $m(<25)$ 为希望购买物品的个数。）

从第 $2$ 行到第 $m+1$ 行，第 $j$ 行给出了编号为 $j-1$ 的物品的基本数据，每行有 $2$ 个非负整数$ v p $（其中$ v $表示该物品的价格$ (v \le 10000) $，$ p$表示该物品的重要度( $1-5$ )

输出格式

$1$ 个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值 $(<100000000)$ 。

样例 #1

样例输入 #1

样例输出 #1

提示

NOIP 2006 普及组第二题

解题过程

我们不妨换个思想理解该题，用N元钱可以买来最多的重要度，那么这就是一道典型的贪心的题目，但是显然重要度是一个整体，是不可分的，那么这就变成了一道动态规划的问题，解法如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int mult[25][300000]={0};//mult[i][j]表示前i个商品花费价格不超过j时的最高收益 
int main(){
	int n,m;//金额数n、物品数m
	cin>>n>>m;
	vector<pair<int,int> > object;//存储物品信息
	for(int i=0;i<m;++i){
		int v,p;//物品i的价格和重要度 
		cin>>v>>p;
		pair<int,int> p0(v,p);
		object.push_back(p0);
	} 
	for(int i=0;i<m;++i){
		int v=object[i].first;
		int p=object[i].second;
		for(int j=1;j<=n;++j){
			if(i==0){
				mult[i][j]=v<=j?v*p:0;
			}
			else if(j-v>0){
				mult[i][j]=max(mult[i-1][j],mult[i-1][j-v]+v*p);
			}
			else{
				mult[i][j]=max(mult[i-1][j],0);
			}
		}
	}
	cout<<mult[m-1][n]; 
	return 0;
}

可以发现此题解法与上一道题基本相同，我们需要辨别题目所对应的算法类型。