NOIP2016普及组初赛部分题解

川长思鸟来 2021-11-11 10:04 408阅读 0赞

问题求解1：

从一个 4×4 的棋盘（不可旋转）中选取不在同一行也不在同一列上的两个方格，共有\_\_\_\_72\_\_\_\_\_种方法。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70][]

> 假设选择第一行，共有4个格子可以选择，然后从剩余的3行中进行选择，有4X3种可能。假设选择第2行，有3个格子可以选，有4X3X3种可能，第一个格子可能是4行中的任意一行，公共有4X3X3X4=144种可能，要排除重复（a,b),(b,a)这种情况，总共要除以2,所以最后有72种选择。

问题求解2

约定二叉树的根节点高度为1，一颗节点数为2016的二叉树最少有 \_\_\_\_1\_\_\_\_\_个叶子节点；一颗节点数为2016的二叉树最小的高度值为\_\_\_\_11\_\_\_\_\_。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1][]

三、阅读程序写结果

#include<iostream>
    using namespace std;
    int main()
    {
    	int max,min,sum,count = 0;
    	int tmp;
    	cin >> tmp;
    	if(tmp == 0) return 0;
    	max = min = sum = tmp;
    	count ++;
    	while(tmp!=0)
    	{
    		cin >> tmp;
    		if(tmp != 0)
    		{
    			sum+=tmp;
    			count++;
    			if(tmp > max)
    				max = tmp;
    			if(tmp < min)
    				min = tmp;
    			//printf("%d %d %d %d\n",sum,count,max,min); 
    		}
    	 } 
    	 cout << max <<"," << min <<","<< sum/count <<endl;
    	return 0;
    }

输入：1 2 3 4 5 6 0 7

答案： 6 1 3

> 这里其实输入到0后while就不执行了，就直接输出答案了，7不会再进行运算，不会输入进去。sum=1+2+3+4+5+6=21,
> 
> count=2+1+1+1+1=6

#include<iostream>
    using namespace std;
    int main()
    {
    	int i = 100, x=0, y=0;
    	while(i > 0)
    	{
    		i--;
    		x = i%8;
    		if(x==1)
    			y++;
    	}
    	cout << y << endl; 
    	return 0;
     }

答案：13

> 相当于求解的100以内某个数除以8的余数为1的个数。
> 
> 1
> 
> 8\*1+1 8\*2+1 8\*3+1 …… 8\*12+1
> 
> 共有13个数

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 2][]

#include<iostream>
    using namespace std;
    int main()
    {
    	int a[6]={1,2,3,4,5,6};
    	int pi = 0;
    	int pj = 5;
    	int t,i;
    	while(pi < pj)
    	{
    		t = a[pi];
    		a[pi] = a[pj];
    		a[pj] = t;
    		pi++;
    		pj--;
    	}
    	for(int i = 0; i < 6;i++)
    		cout << a[i] <<",";
    		cout << endl;
    		return 0;
     }

答案：6，5，4，3，2，1，

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 3][]

> 这个代码实现的就是将数据倒序输出。
> 
> 这里需要注意最后一个数也要有“，”号。还有缩进的问题，在for循环或者是while循环中，当只有一个语句的时候可以不打\{\}，也就是说循环不打括号的时候，只有第一个语句在循环语句中。
> 
> \#include<iostream>  
> using namespace std;  
> int main()  
> \{  
> for(int i = 0; i < 4; ++i)  
> cout << i << ",";  
> cout << "hello";  
> return 0;  
> \}
> 
> 与
> 
> \#include<iostream>  
> using namespace std;  
> int main()  
> \{  
> for(int i = 0; i < 4; ++i)  
> \{  
> cout << i << ",";  
> \}  
> cout << "hello";  
> return 0;  
> \}
> 
> 等价。

#include<iostream>
    using namespace std;
    int main()
    {
    	int i,length1,length2;
    	string s1,s2;
    	s1 ="I have a dream. ";
    	s2 ="I Have a Dream. ";
    	length1 = s1.size();
    	length2 = s2.size();
    	for(int i = 0; i < length1; i++)
    	{
    		if(s1[i]>='a' && s1[i] <= 'z')
    			s1[i]-='a'-'A'; 
    	}
    	for(int i = 0; i < length1; i++)
    	{
    		if(s2[i]>='a' && s2[i] <= 'z')
    			s2[i]-='a'-'A'; 
    	}
    	if(s1 == s2) 
    		cout << "=" << endl;
    	else if(s1 > s2)
    		cout << ">" << endl;
    	else
    		cout << "<" << endl;
    	return 0;
     }

答案：=

> 该代码实现的就是将字符串中的小写字母转换成大写字母，因此最终两个字符串都是“I HAVE A DRAEAM. "

四、完善程序

1.（读入整数）请完善下面的程序，使得程序能够读入两个int范围内的整数，并将这两个整数分别输出，每行一个。

输入的整数之间和前后只会出现空格或者回车。输入数据保证合法。

例如：

输入：

123

\-789

输出：

123

\-789

#include<iostream>
    using namespace std;
    int readint(){
    	int num = 0;//存储读取到的整数
    	int negative = 0;//负数标识
    	char c;//存储当前读取到的字符
    	c = cin.get();
    	while((c < '0' || c>'9') && c!='-')
    		c = ____1____;
    	if(c =='-')
    		negative = 1;
    	else
    		______2____;
    	c = cin.get();
    	while(_____3____)
    	{
    		______4____;
    		c = cin.get();
    	}
    	if(negative == 1)
    		_____5_____;
    	return num;
    }
    int main()
    {
    	int a,b;
    	a = readint();
    	b = readint();
    	cout << a << endl << b << endl;
    	return 0;
    }

答案：

（1）cin.get()或者c=getchar()

(2) num = c-'0'或者num=c-48

(3)c >='0'&&c<='9'或者c>=48&&c<=57或isdigit(c)

（4）num = num\*10+c-'0'或num=num\*10+c-48

(5)num=-num或return -num

#include<iostream>
    using namespace std;
    int readint(){
    	int num = 0;
    	int negative = 0;
    	char c;
    	c = cin.get();
    	while((c < '0' || c>'9') && c!='-')//如果是非法读入，就不管它，继续读入 
    		c = cin.get();
    	if(c =='-')//如果读入的是负号，则标记负号，最后按照负数的格式输出 
    		negative = 1;
    	else//如果读入的不是负号，则将字符转成数字格式 
    		num = c-'0';
    	c = cin.get();
    	while(c >= '0' && c <= '9')//如果读入的字符是0~9之间的数 
    	{
    		num = num*10 + c-'0';//将字符转成数字 
    		c = cin.get();
    	}
    	if(negative == 1)//按照负数的格式输出 
    		num = - num;
    	return num;
    }
    int main()
    {
    	int a,b;
    	a = readint();
    	b = readint();
    	cout << a << endl << b << endl;
    	return 0;
    }

2.  （ 郊 游 活 动 ） 有 n 名 同 学 参 加 学 校 组 织 的 郊 游 活 动 ， 己 知 学 校 给 这 n 名 同 学 的 郊 游 总 经 费 为 A 元 ， 与 此 同 时 第 i 位 同 学 自 己 携 带 了 Mi 元 。 为 了 方 便 郊 游 ， 活 动 地 点 提 供 B(>=n ） 辆 自 行 车 供 人 租 用 ， 租 用 第 j 辆 自 行 车 的 价 格 为 Cj元 ， 每 位 同 学 可 以 使 用 自 己 携 带 的 钱 或 者 学 校 的 郊 游 经 费 ， 为 了 方 便 账 务 管 理 ， 每 位 同 学 只 能 为 自 己 租 用 自 行 车 ， 且 不 会 借 钱 给 他 人 ， 他 们 想 知 道 最 多 有 多 少 位 同 学 能 够 租 用 到 自 行 车 。

本 题 采 用 二 分 法 。 对 于 区 间 \[l ， r\], 我 们 取 中 间 点 mid 并 判 断 租 用 到 自 行 车 的 人 数 能 否 达 到 mid, 判 断 的 过 程 是 利 用 贪 心 算 法 实 现 的 。

#include<iostream>
    using namespace std;
    #define MAXN 1000000
    int n,B,A,M[MAXN],C[MAXN],l,r,ans,mid;
    bool check(int nn){
    	int count = 0,i,j;
    	i = ____(1)_____;
    	j = 1;
    	while(i <= n){
    		if(___(2)_______)
    			count += C[j]-M[i];
    		i++;
    		j++;
    	}
    	return ____(3)____; 
    }
    
    void sort(int a[],int l, int r)
    {
    	int i=l,j = r,x = a[(l+r)/2],y;
    	while(i <= j)
    	{
    		while(a[i] < x) i++;
    		while(a[j] > x) j--;
    		if(i <= j){
    			y = a[i];a[i]=a[j];a[j]=y;
    			i++;j--;
    		} 
    	}
    	if(i < r) sort(a,i,r);
    	if(l < j) sort(a,l,j);
    }
    int main()
    {
    	int i;
    	cin >> n >> B >> A;
    	for(i = 1; i <= n; i++)
    		cin >> M[i];
    	for(i = 1; i <= B; i++)
    		cin >> C[i];
    	sort(M,1,n);
    	sort(C,1,B);
    	l = 0;
    	r = n;
    	while(l <= r){
    		mid = (l+r)/2;
    		if(___(4)___)
    		{
    			ans = mid;
    			l = mid+1;
    		}
    		else
    			r = __(5)____;
    	}
    	cout << ans << endl; 
    	return 0;
     }

答案：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 4][]

> 先将租用每辆自行车的价格和学生带的钱从小到大排序。
> 
> 贪心策略：先匹配零花钱带的多的人，判断经费是否超过预算，如果没有超过预算则会有更多的学生可以租用自行车，如果超过了就减少租用自行车的人数。

#include<iostream>
    using namespace std;
    #define MAXN 1000000
    int n,B,A,M[MAXN],C[MAXN],l,r,ans,mid;
    //n个人，B辆车，A总经费，M[i]第i位学生携带的钱，C[i]第i辆车租用的价格 
    bool check(int nn){//判断nn个人租车钱是否超过了预算 
    	int count = 0,i,j;
    	i = n-nn+1;//i是排序后钱多的人 
    	j = 1;
    	while(i <= n){
    		if(M[i] < C[j])//如果学生自己带的钱不够，就要用经费 
    			count += C[j]-M[i];//花费的经费 
    		i++;
    		j++;
    	}
    	return count<=A; //花费的经费没超过预算就说明还有人可以租自行车 
    }
    
    void sort(int a[],int l, int r)//从小到大排序 
    {
    	int i=l,j = r,x = a[(l+r)/2],y;
    	while(i <= j)
    	{
    		while(a[i] < x) i++;
    		while(a[j] > x) j--;
    		if(i <= j){
    			y = a[i];a[i]=a[j];a[j]=y;
    			i++;j--;
    		} 
    	}
    	if(i < r) sort(a,i,r);
    	if(l < j) sort(a,l,j);
    }
    int main()
    {
    	int i;
    	cin >> n >> B >> A;
    	for(i = 1; i <= n; i++)
    		cin >> M[i];
    	for(i = 1; i <= B; i++)
    		cin >> C[i];
    	sort(M,1,n);
    	sort(C,1,B);
    	l = 0;
    	r = n;
    	while(l <= r){
    		mid = (l+r)/2;
    		if(check(mid))//如果没有超过经费，能租车的人数就比mid多 
    		{
    			ans = mid;
    			l = mid+1;
    		}
    		else
    			r = mid -1;
    	}
    	cout << ans << endl; 
    	return 0;
     }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70]: /images/20211109/8631b321ac0e41acb058e9f9e15df4be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 1]: /images/20211109/7927d4fcee764d24b06cdb9ff26ba92f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 2]: /images/20211109/4049cbdd9027435882bc07be66a8accc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 3]: /images/20211109/e19bfe9cded94eef91df3c796e727931.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbnlhbndlbm1lbmc_size_16_color_FFFFFF_t_70 4]: /images/20211109/7c5995f5123341d1beaeaab127c26843.png