期中复习

模拟考试的题：

0706:输出Fibonacci数列

总时间限制:: 1000ms
内存限制:: 65536kB

描述

Fibonacci数列指的是数列第一项和第二项为1，之后每一项是之前两项的和所构成的数列。现有多组数据，每组数据给出一个数字n，请你输出Fibonacci数列的前n-1项。

#include <iostream>
#include <iterator>
using namespace std;

template<class T1, class T2>
void Copy(T1 s, T1 e, T2 x) {
    for(; s != e; ++s, ++x)
        *x = *s;
}

// 在此处补充你的代码

int main() {
	while(true) {
		int n;
		cin >> n;
		if(n == 0)
			break;
		
	    Fib f1(1), f2(n);
	    ostream_iterator<int> it(cout, " ");
	    Copy(f1, f2, it);
	    cout << endl;
	}
	return 0;
}

输入

每组数据一行，整数n
输入以0结尾

输出

对每组数据输出前 n-1项

样例输入

3
0

样例输出

1 1

 1 #include <iostream>
 2 #include <iterator>
 3 using namespace std;
 4 
 5 template<class T1, class T2>
 6 void Copy(T1 s, T1 e, T2 x) {
 7     for(; s != e; ++s, ++x)
 8         *x = *s;
 9 }
10 // 在此处补充你的代码
11 class Fib{
12     int number;
13 public: 
14     Fib(int n_):number(n_){}
15     bool operator!=(Fib b){
16         return number!=b.number;
17     }
18     void operator++(){
19         number++;
20     }
21     int operator*(){
22         int f[10000], i;
23         for(i = 0; i <= number; i++) f[i] = 0;
24         f[1] = 1; f[2]=1;
25         for(i = 3; i <= number; i++)
26             f[i] = f[i-2]+f[i-1];
27         return f[number];
28     }
29 }; 
30 int main() {
31     while(true) {
32         int n;
33         cin >> n;
34         if(n == 0)
35             break;
36         
37         Fib f1(1), f2(n);
38         ostream_iterator<int> it(cout, " ");
39         Copy(f1, f2, it);
40         cout << endl;
41     }
42     return 0;
43 }

备注：这道题的关键就是思路要开阔，当时没想明白怎么能做到让f（1）输出第n个数，答案就在于重载++和*号！最妙的是用*的重载来实现计算！

0707:二进制数位复制并取反

总时间限制:: 1000ms
内存限制:: 65536kB

描述

输入整数a b i j，把b从第i到j位(包括i,j)的二进制位全部取反，并填入a的i到j位中，a的其他位不变。输出a。最右边一位是第0位。

输入

整数a b i j(范围不超过int)

输出

改变以后的a

样例输入

6123 3344 2 9

样例输出

#include <iostream>
#include <iterator>
using namespace std;
//1111111  1000111
int main() {
    int a, b, i, j;
    cin>>a>>b>>i>>j;
    int block = (1<<(j+1))-(1<<i); //制造了一个001111100000的块
    a &= ~block; //把a的第i到j为置为0
    b&=block; 
    a |= b^block;
    //或者写
    //a|=(~b)&block;
    cout<<a; 
    return 0;
}

备注：位运算好巧妙好难orz 这道题的关键是用了减法制造了一个从i到j为1，其它位为0的“块”，十分巧妙。

0709:求平均数的类真叫mean

总时间限制:: 1000ms
内存限制:: 65536kB

描述

输入一系列正整数, 计算它们的平均值，结果去尾取整数

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
class CMean {

// 在此处补充你的代码

};

int main(int argc, char* argv[]) {
	int  v;
	int t;
	cin >> t;
	while ( t -- ) {
		cin >> v;
		vector<int> vec;
		while (v) {
			vec.push_back(v);
			cin >> v;
		}
		int myAver = 0;
		for_each(vec.begin(), vec.end(), CMean(myAver));
		cout << myAver << endl;
	}
	return 0;
}

输入

第一行是测试数据组数T
接下T行，每行一组数据。每行是若干个正整数，以0表示输入结束(0不算)。

输出

对每组数据，输出所有数的平均值，结果去尾取整数

样例输入

1
17 4 8 18 0

样例输出

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <iterator>
 5 using namespace std;
 6 /* 
 7 Function for_each(InputIterator beg, InputIterator end, Function f) {
 8   while(beg != end) 
 9     f(*beg++);
10 }
11 */ 
12 class CMean {
13 // 在此处补充你的代码
14 public:
15     int totaln = 0;
16     int total = 0;
17     int *ans;
18     CMean(int & num){
19         ans = &num;
20     } 
21     void operator()(int a){
22         totaln++;
23         total += a;
24         *ans = total/totaln;
25     } 
26 };
27 
28 int main(int argc, char* argv[]) {
29     int  v;
30     int t;
31     cin >> t;
32     while ( t -- ) {
33         cin >> v;
34         vector<int> vec;
35         while (v) {
36             vec.push_back(v);
37             cin >> v;
38         }
39         int myAver = 0;
40         for_each(vec.begin(), vec.end(), CMean(myAver)); //CMean(myAver)整体相当于一个函数指针 
41         cout << myAver << endl;
42     }
43     return 0;
44 }

备注：不知道怎么说，首先要明白for_each的第三个参数是一个函数指针，所以CMean（myAver）是一个函数对象。反正就，类里面设了个指针从而可以直接修改myAver，要不然也没法改是吧。

0708:宠物小精灵

总时间限制:: 1500ms
内存限制:: 65536kB

描述

宠物小精灵的世界中，每位训练师都在收集自己的小精灵。但是，训练师的背包里只能同时携带6只小精灵。如果一位训练师抓到了更多的精灵，那么最早抓到的精灵将被自动传送到电脑中，保证持有的小精灵数量依然是6只。训练师也可以随时从电脑中取出精灵，取出的精灵将从电脑中传送到训练师的背包里。取出的精灵同样被认为是最新的，导致背包中最早取出或抓到的精灵被替换到电脑中，训练师持有的精灵数量依然是6只。初始状态下，所有训练师的背包中都没有小精灵，电脑中也没有任何训练师的精灵。

输入

输入数据包含多组测试。第一行一个整数T(1<=T<=20)，表示测试数据数目。
每组数据第一行有一个正整数N(1<=N<=20000)表示发生事件的数目。
接下来有N行分别表示发生的事件。
一共有两种事件：
C X, Y 表示训练师X抓到了精灵Y
T X, Y 表示训练师X试图从电脑中取出精灵Y。

X和Y都是长度在20以下的由字母或数字构成的字符串。

小精灵的世界中同样存在着作恶多端的火箭队。他们试图利用电脑的漏洞，从电脑中取出本不属于自己的小精灵。因此，电脑需要识别并拒绝取出这种请求。注意，如果一只小精灵仅存在于训练师的背包中而未被传送至电脑，该训练师也不能取出这只精灵。相同训练师不会多次抓到相同名字的精灵。

输出

对于每次从电脑中取出小精灵的请求，输出一行。成功则输出Success，失败则输出Failed。

样例输入

1 10
C satoshi pikachu1
C satoshi pikachu2
C satoshi pikachu3
C satoshi pikachu4
C satoshi pikachu5
C satoshi pikachu6
C satoshi pikachu7
T satoshi pikachu2
T satoshi pikachu1
T pikachu pikachu2

样例输出

Failed
Success
Failed

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <iterator>
 5 #include <string>
 6 #include <set>
 7 #include <map>
 8 using namespace std;
 9 class trainer {
10     vector<string>bag;
11     set<string>computer;
12 public:
13     void C(string Y){
14         bag.push_back(Y);
15         if(bag.size()>6)
16             computer.insert(bag[bag.size()-7]); //不需要从书包里删除 
17     }
18     void T(string Y){
19         if(computer.find(Y)==computer.end()){
20             cout<<"Failed"<<endl; return;
21         }
22         computer.erase(Y); //vector的erase只能通过迭代器 
23         bag.push_back(Y);
24         if(bag.size()>6)
25             computer.insert(bag[bag.size()-7]);
26         cout<<"Success"<<endl;
27     }
28 };
29 map<string, trainer>M;
30 int main() {
31     int t;
32     cin >> t;
33     while ( t -- ) {
34         M.clear();
35         int n;
36         cin>>n;
37         for(int i = 0; i < n; i++){
38             string a, b, c;
39             cin>>a>>b>>c;
40             if(a=="C")
41                 M[b].C(c);
42             else M[b].T(c);
43         }
44     }
45     return 0;
46 }

备注：博客后台编辑器的这个缩进太奇怪了。bag可以是一个deque，这样就可以pop_front了。但其实bag没必要删除元素。