目录

题目49.修理牛棚 

题目51.部落人乘法

题目52.序列

题目55.人见人爱A-B     set,vector的应用

---

题目49.修理牛棚 

个人总结

1.把“求木板最小总长度问题”转化为“求最大总空隙和的问题 ” 
用 M 块木板最多可以切断 M-1 个空隙，节省的长度就是这些空隙的和。

2.求空隙(易错点） 
    vector<int>gaps;    //空隙数组 
    for(int i=1;i<c;i++){
        int d = cows[i] - cows[i-1] - 1; // 两个牛之间的空位数
        if (d > 0) {//易错点--注意判断空隙值d>0 
            gaps.push_back(d);
        }

3.对空隙从大到小排序
     sort(gaps.begin(),gaps.end(),greater<int>());

 4.//求空隙数--m个木板最多可以分割出m-1个 ，与总空隙数，进行比较找最小值 
     int num=min((int)gaps.size(),m-1);

5.易漏：//如果只有一头牛，直接输出 1 并结束
    if(c==1){
        cout<<1;
    }

修理牛棚

作者: xxx

时间限制: 1s

章节: 一维数组

问题描述

在一个暴风雨的夜晚，农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假，所以牛棚（牛棚的总数S:1<= S<=200）没有住满。 剩下的牛一个紧挨着另一个被排成一行安置在有屋顶的牛棚来过夜。 所以有些牛棚里有牛，有些没有。

所有的牛棚有相同的宽度，且宽度设为1。 因为有些门遗失，农民约翰需要架起新的木板作为门。 他的新木材供应者将会供应他任何他想要的长度,但是供应者只能提供有限数目的木板。 农民约翰想将他购买的木板总长度减到最少。

计算拦住所有有牛的牛棚所需木板的最小总长度。

输出所需木板的最小总长度作为的答案。

说明：拦住一个牛棚需要的木板长度为1，拦住相邻的三个牛棚则需要木板长度为3。

比如有牛的牛棚编号为：

3 5 8 10 11

并且只能使用两块木板，

则第一块木板从3到5，长度为3，

第二块木板从8到11，长度为4，

因此，需要木板的总长度为7。

输入说明

第 1 行: M 和 C(用空格分开)

第 2 到 C+1行: 每行包含一个整数，表示牛所占的牛棚的编号。

其中：

可能买到的木板最大的数目：M(1<= M<=50);

需要安置的牛的数目C(1<= C <=S)

安置后牛所在的牛棚的编号stall_number(1<= stall_number <= S)。

输出说明

单独的一行包含一个整数表示所需木板的最小总长度

完整答案

#include<bits/stdc++.h>
using namespace std;
int main(){
	int m,c;//m:木板最大的数目	c:牛的数目
	cin>>m>>c;
	vector<int>cows(c);		//牛棚数组 
	int x;

	for(int i=0;i<c;i++){
		cin>>cows[i];
	} 
//for(int x : cows) {    // 错误！cows 为空，循环一次都不会执行
//    cin >> x;          // 这里 x 是 cows 元素的拷贝，无法修改原数组
//    cows.push_back(x); // 即使循环能执行，也会改变容器结构，导致迭代器失效
//}

	//0.如果只有一头牛，直接输出 1 并结束
	if(c==1){
		cout<<1;
	}
	//1.对牛棚编号从小到大排序 
	sort(cows.begin(),cows.end());
	
	//2.求空隙(易错点） 
	vector<int>gaps;	//空隙数组 
	for(int i=1;i<c;i++){
		int d = cows[i] - cows[i-1] - 1; // 两个牛之间的空位数
        if (d > 0) {//易错点--注意判断空隙值d>0 
            gaps.push_back(d);
		}
	}
	//3.对空隙从大到小排序
	 sort(gaps.begin(),gaps.end(),greater<int>());
	 
	 //4.求空隙数--m个木板最多可以分割出m-1个 ，与总空隙数进行比较找最小值 
	 int num=min((int)gaps.size(),m-1);
	 int sum=0;//空隙和 
	 for(int i=0;i<num;i++){
	 	sum+=gaps[i]; 
	 }
	 //5.求所需木板的最小总长度
	 int len= cows.back()-cows.front()+1;//一根覆盖所有牛棚的木板长度
	 int res=len-sum;
	 cout<<res;	 

}

题目51.部落人乘法

作者: 朱星垠

时间限制: 10s

章节: 一维数组

问题描述

其规则是：

左边不断除2，写下商，舍去余数；

右边不断加倍，直到左边变成1为止。

取结果的方法是：

如果某行左边是偶数，就划去整个这一行；

如果某行左边是奇数，右边剩下的数相加即可。

例如求13与15的乘积的过程是：

计算过程：

13--------15 ：13除以2等于6，舍去余数1，15乘以2等于30；

6---------30 ：6除以2等于3，30乘以2等于60；

3---------60 ：3除以2等于1，舍去余数1，60乘以2等于120；

1---------120 ：左边数字为1，停止计算。

取结果过程：

13--------15 ：左边是奇数，取15；

6---------30 ：左边是偶数，划去；

3---------60 ：取60；

1---------120 ：取120；

其结果就是： 13*15=15+60+120=195。

问题可以归结为：给你两个整数，使用上面描述的乘法过程，输出最后的相加的式子。

输入说明

你的程序需要从标准输入设备（通常为键盘）中读入多组测试数据。每组测试数据占一行，其中包含两个整数a和b（1 <= a, b <= 100）。

输出说明

对每组测试数据，你的程序需要向标准输出设备（通常为启动该程序的终端）依次输出一组对应的答案。格式参见样例。

输入范例

13 15
2 4

输出范例

13*15=15+60+120=195
2*4=8=8
 

#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b;
	while(cin>>a>>b){
		cout<<a<<"*"<<b<<"="; 
		int sum=0;
		while(a!=1){
			if(a%2==1){//如果左边是奇数，右边相加 
				cout<<b<<"+";
				sum+=b;
			}
			a/=2;
			b*=2;
		}
		sum+=b;//左边等于1时，右边累加		
		cout<<b<<"="<<sum<<endl; 
	}
}

题目52.序列

作者: ZhuKai

时间限制: 2s

章节: 一维数组

问题描述

明明的爸爸经常用做游戏的方法启发明明对数学的兴趣。有一次，明明爸爸准备了许多盒子和球，他要和明明做一个放球的游戏。

游戏如下：要将k个小球依次装入到若干个盒子中去（可以使用的盒子数不限）。

小球装入盒子的规则如下： 

1）第一个盒子不能为空。 

2）依次装入各个盒子的球数必须严格递增。例如：当k=8时，装入方法有1，2，5或1，3，4。 

3）装入的盒子数尽可能多。 

4）所有相邻盒子的球数之差的绝对值之和最小。

如上例中：装入法1，2，5，则差的绝对值之和为(2-1)+(5-2)=4。装入法1，3，4，则差的绝对值之和为(3-1)+(4-3)=3。因此应该采用后一种装法。 

明明明白了规则以后，就兴致盎然地玩起了游戏。起先明明玩得很有劲，每次都能顺利的找出最佳的装小球的方法。但是随着小球数量的增多，装小球的方法也就变得越来越多，明明就需要花更多的时间才能找到最佳的装球方法，这使得明明有些犯难了。于是明明想到了你，他想请你帮他写一个程序，他把小球的数量告诉你，而你的程序用来计算装小球的方法。 

 明明的问题可以归结为：告诉你小球的数量k，然后通过程序计算出盒子装小球的最佳方法。

输入说明

你写的程序要求从标准输入设备中读入测试数据作为你所写程序的输入数据。标准输入设备中有多组测试数据，每组测试数据仅占一行，每行有一个整数k（1 ≤k ≤10000），即小球的个数。每组测试数据与其后一组测试数据之间没有任何空行，第一组测试数据前面以及最后一组测试数据后面也都没有任何空行。

输出说明

对于每一组测试数据，你写的程序要求计算出一组相应的运算结果，并将每组运算结果作为你所写程序的输出数据依次写入到标准输出设备中。每组运算结果为一串整数，即表示依次放入各个盒子里的小球的个数，每两个数字之间用一个‘,’分隔。每组运算结果单独占一行，其行首和行尾都没有任何空格或其他任何字符，每组运算结果与其后一组运算结果之间没有任何空行或其他任何字符，第一组运算结果前面以及最后一组运算结果后面也都没有任何空行或其他任何字符。 注：通常，显示屏为标准输出设备。

输入范例

1
8
10

输出范例

1
1,3,4
1,2,3,4
 

个人总结

这个问题可以这样理解：我们要把k个小球放进尽可能多的盒子里，且每个盒子的小球数严格递增。在盒子数最多的情况下，还要让相邻盒子球数之差的和最小（即序列尽可能平缓）。

一个直观的算法如下：

1. 找出最多的盒子数 m
   因为要盒子数最多，每个盒子至少要放1、2、3……这样递增，所以最小的可能总和是 1+2+…+m。我们找到最大的 m 使得这个和不超过 k。
   例如：k=8时，1+2+3=6≤8，1+2+3+4=10>8，所以m=3。

2. 先构造一个初始序列
   让每个盒子先放 1, 2, 3, …, m，此时总和为 S = m(m+1)/2。
   剩余的小球数为 d = k - S。

3. 把剩余的小球均匀地加在后面的盒子上
   为了保持递增且使序列尽可能平缓，我们从最后一个盒子开始，依次给每个盒子加1个球，共加d次。这样最后d个盒子各增加1，前面的不变。
   例如k=8时，S=6，d=2，初始序列[1,2,3]，给最后两个加1得[1,3,4]。
   如果d=0，则保持原样；如果d=m，则所有盒子都加1，变成[2,3,…,m+1]。

4. 输出结果
   按顺序输出每个盒子的小球数，用逗号分隔。

这个算法简单易懂，因为它在保证盒子数最多的前提下，让序列尽可能接近连续自然数，从而相邻差之和最小（因为相邻差之和等于最后一个减第一个，这种构造使首尾差距最小）。

以下是实现代码：

#include<bits/stdc++.h>
using namespace std;

int main() {
    int k;
    while (cin >> k) {
        // 1. 求最大盒子数 m
        int m = 0, sum = 0;
        while (sum + m + 1 <= k) {
            m++;
            sum += m;   // sum = 1+2+...+m
        }
        // 2. 剩余小球数
        int d = k - sum;
        // 3. 构造初始序列 1,2,...,m
        vector<int> ans(m);
        for (int i = 0; i < m; i++) {
            ans[i] = i + 1;
        }
        // 4. 从后往前给 d 个盒子加 1
        for (int i = m - 1; i >= m - d; i--) {
            ans[i]++;
        }
        // 5. 输出
        for (int i = 0; i < m; i++) {
            if (i > 0) cout << ',';
            cout << ans[i];
        }
        cout << endl;
    }
    return 0;
}

题目55.人见人爱A-B     set,vector的应用

人见人爱A-B

作者: xxx

时间限制: 1s

章节: 一维数组

问题描述

A和B是两个集合，A-B求的是两个集合的差，就是做集合的减法运算。（当然，大家都知道集合的定义，就是同一个集合中不会有两个相同的元素，这里还是提醒大家一下）呵呵，很简单吧？

输入说明

输入数据包含T个测试实例。

首先输入数字T，然后输入T组测试数据，每组输入数据占1行,每行数据的开始是2个整数n(0<=n<=100)和m(0<=m<=100),分别表示集合A和集合B的元素个数，然后紧跟着n+m个元素，前面n个元素属于集合A，其余的属于集合B. 每个元素为不超出int范围的整数,元素之间由一个空格隔开. 

输出说明

针对每组数据输出一行数据,表示A-B的结果,如果结果为空集合，则输出“NULL”,否则从小到大输出结果,为了简化问题，每个元素后面跟一个空格.

输入范例

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

输出范例

2 3 
NULL

个人总结

1.A-B定义：A 和 B 的差集（也称为相对补集）指的是：属于集合 A 但不属于集合 B 的所有元素组成的集合。

2.经典代码：A-B

set<int>A,B;

vector<int>v;        
        for(int a:A){        //A-B属于A,但不属于B----即在B中未找到的A 
            if(B.find(a)==B.end()){      //find()未找到则返回end（） 
                v.push_back(a);          //符合A-B则加入数组v中 
            
            }

//A 和 B 的差集（也称为相对补集）指的是：
//属于集合 A 但不属于集合 B 的所有元素组成的集合?。
#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;//共t组数据 
	cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		set<int>A,B;
		int x;
		for(int i=0;i<n;i++){
			cin>>x;			//输入A 
			A.insert(x);	//插入A中 
			
		}
		for(int i=0;i<m;i++){
			cin>>x;			//输入B 
			B.insert(x);	//插入B中 
			
		}
		vector<int>v;		
		for(int a:A){//A-B属于A,但不属于B----即在B中未找到的A 
			if(B.find(a)==B.end()){//find()未找到则返回end（） 
				v.push_back(a);//符合A-B则加入数组v中 
			
			}
		}
		if(v.empty()) {
			cout<<"NULL"<<endl;
		}
		else{
			for(int x:v){
				cout<<x<<' ';
			}
			cout<<endl;
		}
	}
	
}

翻译

 翻译：

RFID和电子标签或RFID标签一起应用在任意物品被监视或追踪时。这个标签可能应用在任何物品上，例如商品，工具，智能手机，电脑，动物或者人。这个目的是用无线电波或传感信号确认和追踪物品。一些标签可以通过无线阅读器从几十米或者几百米外被读。大多数RFID标签包含至少两个主要部分。一个是集成电路，为了存储和处理信号的，调制和解调射频（RF）信号和其他功能。另一部分是天线，为了接收和发送无线电信号。

现在的传感器网络大多是无线的，被称为无线传感器网络（WSNs）。典型的WSN由空间分布的自主传感器组成，为了协作监视物理或环境条件，例如温度，声音，震动，压力，运动或污染物。无线传感器网络发展的动机是军事应用，例如战场监视。WSN技术现在被用于很多工业和民用应用领域，包括过程监视和控制，机器健康监视，环境和栖息地监视，医疗保健家庭自动化和智能交通控制。

GPS是由美国空军于1973年开发的。同样的发展也发生在欧盟，俄罗斯和中国。从1994年以来，退化的GPS在提供可靠的位置，导航和计时服务上已可用于民用。对于任何有GPS接收器的人，在世界任何地方，无论什么天气，无论白天黑夜，系统将会提供准确的位置和时间信息给无限数量的用户。

单词