一堆模拟题是真的好烦啊！！！！！

不过还是复习了一点点东西的，比如真正把map实操了，还有初步接触了下stringstream，第一次自己搓单链表……更重要的是在找回以前搞OI时的感觉吧（果然写题是永远是王道）

吐槽归吐槽，但这还是一篇正经的题解报告QAQ

另外说个开心的事，出人意料的数模校赛一等奖耶！（尽管没有第一轮就进答辩名单）

本周作业让我感觉比较有收获的题（从高到低）：

10.内存管理（单链表写法） 8。买房与选房（思维）

1.众数

题目

【问题描述】

一组数据中出现最多的数，称为众数。比如

1 2 3 3

众数为3。一组数据中也可能有多个众数，以最先出现的作为众数。比如

2 2 3 3

众数为2。

问题是一组按升序排好的数据，指出它的众数。

【输入形式】

有多组测试数据（不超过100组测试数据）。

每组测试数据占两行，第一行是正整数N：表示这组测试数据中数据项数。

第二行是N个用空格隔开的正整数，表示这组测试数据的数据元素。每个数据元素都不大于10000。

N=0，表示输入结束，并且不需要处理。

40%的测试数据N 1 ≤N≤ 10；

30%的测试数据N 10 < N≤ 100；

20%的测试数据N 100 < N≤ 1000；

10%的测试数据N 1000 < N≤ 10000；

【输出形式】

对于每组测试数据，输出一行包含一个正整数：对应的众数。

【样例输入】

4
1 2 3 3
4
2 2 3 3
0
【样例输出】

3
2

题解

很明显这题水分极高，排序都帮忙排好了。如果你想显得不是那么水的话，可以考虑直接一遍迭代

那如果想稳一点的话就随便用个桶排序原理再找最大即可。基于本题的数据量来讲map倒是不怎么需要用，开个10000大小的数组就行

桶排序原理：把数字看作桶的编号，然后遇到某个数字就往对应的桶kv[i]++即可。

代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[10001]= {0};
int main(){
	int n;
	while(scanf("%d",&n)){
		if(n==0)break;
		memset(a,0,sizeof(a));
		while(n--){
			int b;
			scanf("%d",&b);
			a[b]++;
		}
		int best = 0;
		for(int i=1;i<=10000;i++)
			if(a[i]>a[best])best = i;
		cout<<best<<endl;	
	}
	return 0;
}

2.错误的里程表

题目

【问题描述】

三月八日，小明买了台新车。但很快小明发现汽车的里程表有问题：里程表上每一位都不显示数字3和数字8，也就是说直接从数字2跳到数字4，直接从数字7跳到数字9。小明纳闷：这车到底行驶里程是多少。

现在，小明向你求助：根据里程表显示的数字，给出真实的行驶里程。

【输入形式】

输入有多组测试数据。

输入第一行正整数T，表示有多少组测试数据。

后面有T行，每行一个非负整数，表示里程表显示数字，里面不含有数字3和8。该数字不超过10位。

40%的测试数据组数T 10≤T≤ 102；

30%的测试数据组数T 102≤T≤ 103；

20%的测试数据组数T 103≤T≤ 104；

10%的测试数据组数T 104≤T≤ 105；

【输出形式】

对于每组测试数据，输出一个整数占一行：真实的行程里程。

【样例输入】

6
0
1
12
159
111224459
124567976
【样例输出】

0
1
10
103
19212007
21913077

题解

这题稍微转了个弯，其实就是0-10里面少了3和9，即变成了8个数字就进1

唉，这不就八进制嘛，简单！

那接下来就好办了，把这个看起来像十进制的八进制数变成正常的八进制数不就好了。也就是4-7都减去1，9则减去2。然后进行一次八进制求十进制操作就是答案啦！

代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[10001]= {0};
int main(){
	int n;
	cin>>n;
	while(n--){
		string num;
		cin>>num;
		int ans=0;
		int l = num.length();
		for(int i=0;i<l;i++){
			if(num[i]>'8')ans=ans*8+int(num[i]-'0')-2;
			else if(num[i]>'3')ans=ans*8+int(num[i]-'0')-1;
			else ans=ans*8+int(num[i]-'0');
	}
	cout<<ans<<endl;
	}
	return 0;
}

3.拳王阿里

题目

【问题描述】

   阿里是上个世纪美国最著名的拳击手，阿里在20年的时间里多次获得重量级拳王称号。不过不幸的是，他在之后患上了帕金森氏病。他参加了许多比赛，多到连自己都数不清了。有这么一段时间，他总是参加各种不同的比赛，以至于他自己也不知道从第一场比赛开始到最后一场比赛结束到底用了多长时间。他只记得比赛的第一天是星期几（S)，最后一场比赛的最后一天是星期几(E)。他还记得比赛的总天数（包括第一和最后一天）不少于L天，也不多于R天。给定S和E，能否唯一确定参加比赛总天数(包含该段时间内比赛间的间隔天数)？

【输入形式】

   输入的第一行包含一个整数T，代表测试数据的组数。接下来是 T 组数据。每组数据仅有一行，首先包含两个字符串S和E，然后包含两个整数L和R。• 1 ≤ T ≤ 10,000        1 ≤ L ≤ R ≤ 100• S, E ∈ {“monday”,“tuesday”,“wednesday”,“thursday”,“friday”,“saturday”, “sunday”}

【输出形式】

对于每组数据：

如果不存在满足条件的天数，输出一行“impossible”；

如果存在多个满足条件的天数，输出一行“many”；

否则，输出一行，包含一个整数，代表唯一满足条件的天数。

【样例输入】

3
saturday sunday 2 4
monday wednesday 1 20
saturday sunday 3 5
【样例输出】

2
many
impossible

题解

这题也是一道暴力的题，确定一下合适的天数就行啦。

首先确定下这两个星期几总共包含了几天，然后对这个得到的天数不断自增7，看看有几次是在L-R里边

这边星期就可以用map<string, int>来减少代码量啦，可以直接星期对应数字，节约一点敲代码时间

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
string s,e;
int l,r;


int main(){
	int n;
	map<string, int> a;
	a["monday"]=1,a["tuesday"]=2,a["wednesday"]=3,a["thursday"]=4,a["friday"]=5,a["saturday"]=6,a["sunday"]=0;
	scanf("%d",&n);
	while(n--){
		cin>>s>>e>>l>>r;
		int dweek=a[e]-a[s]+1;
		if(dweek<=0)dweek+=7;
		int ans=0;
		while(1){
			if(dweek<l){dweek+=7;continue;}
			if(dweek>r)break;
			ans+=1,dweek+=7;
		}
		if(ans==0)printf("impossible\n");
		else if(ans==1)printf("%d\n",dweek-7);
		else printf("many\n");
	}
	return 0;
}

4.欧洲冠军联赛

题目

【问题描述】

   欧洲冠军联赛常被誉为全世界最具影响力的俱乐部级赛事。在比赛的小组赛阶段，欧洲的各个足球俱乐部被分为八个小组，每个小组中四支球队。每个小组中的球队按照如下规则排序：

球队会根据比赛结果获得积分。一场比赛的双方被称为主队和客队。如果其中一方进球数多于另一方，那么进球较多的一方获得3 分，另一方获得0 分。如果双方打成平手，则各得1分。

球队的净胜球数是其进球数减去失球数（不考虑该球队在比赛中作为主队还是客队）。

积分较高的球队排名更加靠前。

如果两支球队积分相同，那么净胜球数较多的球队排名靠前。

  小组的各队伍进行循环赛，即每两支球队之间进行两场比赛，双方交替作为主队。给定一个小组内12 场比赛的结果，请求出小组的出线队伍：即排名第一和第二的两支球队。

保证答案唯一。

【输入形式】

  输入的第一行包含一个整数T，代表测试数据的组数。接下来是 T 组数据。  每组数据共有12 行，每行描述一场比赛，格式为：“主队队名主队进球数vs. 客队进球数客队队名”，其中“主队队名”和“客队队名”为字符串，“主队进球数”和“客队进球数”为两球队在本场比赛中各自的进球数量。

1 ≤ T ≤ 50

球队队名仅包含小写英文字母

球队队名长度不超过10 个字符

0 ≤ 进球数 ≤ 100

【输出形式】

   对于每组数据，输出一行，包含两个字符串，代表排名第一和第二的球队的队名。

【样例输入】

2
manutd 8 vs. 2 arsenal
lyon 1 vs. 2 manutd
fcbarca 0 vs. 0 lyon
fcbarca 5 vs. 1 arsenal
manutd 3 vs. 1 fcbarca
arsenal 6 vs. 0 lyon
arsenal 0 vs. 0 manutd
manutd 4 vs. 2 lyon
arsenal 2 vs. 2 fcbarca
lyon 0 vs. 3 fcbarca
lyon 1 vs. 0 arsenal
fcbarca 0 vs. 1 manutd
a 3 vs. 0 b
a 0 vs. 0 c
a 0 vs. 0 d
b 0 vs. 0 a
b 4 vs. 0 c
b 0 vs. 0 d
c 0 vs. 0 a
c 0 vs. 0 b
c 1 vs. 0 d
d 3 vs. 0 a
d 0 vs. 0 b
d 0 vs. 0 c
【样例输出】

manutd fcbarca
d b
【样例说明】

第一组数据：每支球队的积分与净胜球数分别为：

manutd：16 分，净胜球数12。

manutd：8 分，净胜球数 4。

manutd：5 分，净胜球数 −5。

manutd：4 分，净胜球数 −11。

第二组数据：每支球队的积分与净胜球数分别为：

d：7 分，净胜球数 2。

b：7 分，净胜球数 1。

a：7 分，净胜球数 0。

c：7 分，净胜球数 −3。

所有球队的积分相同，但是净胜球数较多的队伍排名更加靠前。

题解

从这题开始就有挺多要根据名字来查找信息的题目了。这边到下面都会用到一个技巧，用结构体数组来存取名字，然后用map来存储名字对应的下标，这样将名字和数组下标就构成了一个双向的对应表。

而除了这个就以下几个要点要搞定：

排序规则不能写错，确定一个队名是不是存过了之类的，至于净胜球这些细节样例说明已经很明显了，不懂就看代码吧。

代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
struct t{
	string name;
	int score=0,ball=0;
};

bool cmp(t a, t b){
	if(a.score == b.score)return a.ball>b.ball;
	return a.score>b.score;
}

int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		string team1,team2,pa;
		int score1,score2,index=0;
		map<string,int> teamindex;
		t team[4];
		for(int i=0;i<12;i++){
			cin>>team1>>score1>>pa>>score2>>team2;
			if(index<4 && teamindex.find(team1) == teamindex.end()){
				team[index].name = team1;
				teamindex[team1] = index;
				index++;
			}
			if(index<4 && teamindex.find(team2) == teamindex.end()){
				team[index].name = team2;
				teamindex[team2] = index;
				index++;
			}
			int i1 = teamindex[team1], i2 = teamindex[team2];
			if(score1 > score2){
				team[i1].score+=3;
				team[i1].ball+=score1-score2;
				team[i2].ball-=score1-score2;
			}
			else if(score1 == score2){
				team[i1].score+=1;
				team[i2].score+=1;
			}
			else{
				team[i2].score+=3;
				team[i1].ball+=score1-score2;
				team[i2].ball-=score1-score2;
			}
		}
		sort(team, team+4, cmp);
		cout<<team[0].name<<" "<<team[1].name<<endl;
		
	}
	return 0;
}

5.合法的括号串

题目

【问题描述】

一个合法的括号串，是指只包含括号的串，如果满足如下条件：

（1）<> () [] {} 这四对括号是合法的；

（2）如果r是合法括号串，则(r) [r] {r}也是；

（3）如果r，s是合法括号串，则rs也是；

所以<<>> , [<>{}(())],[({<>})]是合法的括号串，而)(,[( ])就不是。

【输入形式】

输入第一行正整数t (10 ≤ n ≤ 100)，表示有多少组测试数据。

后面有t行，每行一个只包含8种括号符号的括号串。

40%的括号串的长度L 2 ≤ L≤ 20；

30%的括号串的长度L 2 ≤ L≤ 200；

20%的括号串的长度L 2 ≤ L≤ 2000；

10%的括号串的长度L 2 ≤ L≤ 20000；

【输出形式】

对于每组测试数据，如果括号串是合法的，输出“Yes”（输出没有引号）占一行，否则，输出“No”（输出没有引号）占一行。

【样例输入】

6
<<>>
)(
[<>{}(())]
[({<>})]
[(])
<([{
【样例输出】

Yes
No
Yes
Yes
No
No

题解

学过栈(stack)的都知道，这是栈运用最最经典的题型了。

简单的说，就是遇到左括号就进栈，遇到右括号就判断一下栈顶元素，如果栈为空或者不是对应左括号就非法，否则出栈。

最后记得字符串都走完了要注意一下栈是否为空，最后是空的栈才能说明括号完全匹配，该括号串合法

代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		stack<char> s;
		string str;
		bool flag=true;
		cin>>str;
		int l = str.length();
		for(int i=0;i<l;i++){
			if(str[i] == '(' || str[i] == '[' || str[i] == '{' || str[i] == '<')s.push(str[i]);
			else{
				if(s.empty() || (str[i]==')' && s.top()!='(') || (str[i]==']' && s.top()!='[') || (str[i]=='}' && s.top()!='{') || (str[i]=='>' && s.top()!='<')){
					flag = false;
					break;
				}
				else s.pop();
			}
		} 
		if(s.empty() && flag)printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

6.世界杯来了

题目

【问题描述】

   2018年俄罗斯世界杯结束了，法国获得冠军，全世界球迷度过了一个非常愉快的夏天。作为中国球迷，不能总是看别人踢球，这不福利来了，根据FIFA（国际足联）及全体成员协会的一致决定，2118年世界杯将在中国举办，作为东道主，中国队将无需参加预选赛而直接参加决赛阶段的比赛。

比赛规则如下：

总共n（n为偶数）个球队参加比赛

按照分组赛积分排名，前n/2的球队进入淘汰赛

积分排名的规则如下：球队获胜得3分，平局得1分，失利得0分，按照积分递减、净胜球递减以及进球数递减方式排名

编写一个程序，根据给出的参赛队伍名单和所有比赛的结果，找出成功进入淘汰赛阶段的球队名单。

【输入形式】

   第一行输入包含唯一整数n(1<=n<=50)，参加世界杯决赛的球队数量。接下来的n行是各球队的名字，为长度不超过30个字符的英文字符。接下来的n*(n-1)/2行，每行格式name1-name2 num1:num2（0<=num1, num2<=100），表示对阵球队及比分.

【输出形式】

   输入n/2行，表示进入淘汰赛阶段的球队，按照字典序进行排列，每个球队名字占一行。

【样例输入】

4
A
B
C
D
A-B 1:1
A-C 2:2
A-D 1:0
B-C 1:0
B-D 0:3
C-D 0:3

【样例输出】

A
D

题解

这题的字符串切割我写复杂了，其实直接find一下就行。

其实这题和第四题大体上是一样的，不过这里需要注意的是排序。先按常规排序之后再对前n/2个队伍以名字为依据排序（不会吧不会吧，不会还有人不知道字符串可以直接比大小的吗）

代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
struct t{
	string name;
	int score=0,ball=0,v=0;
};

bool cmp1(t a, t b){
	if(a.score == b.score)
		if(a.ball==b.ball)return a.v>b.v;
		else return a.ball>b.ball;
	return a.score>b.score;
}

bool cmp2(t a, t b){
	return a.name<b.name;
}

int split(string s, char r){
	int l=s.length();
	for(int i=0;i<l;i++){
		if(s[i]==r)return i;
	}
}

string p(string s, int begin, int end){
	string res="";
	for(int i=begin;i<end;i++){
		res+=s[i];
	}
	return res;
}

int change(string num){
	int res=0,l=num.length();
	for(int i=0;i<l;i++)res=res*10+int(num[i]-'0');
	return res;
}

int main(){
	int n;
	scanf("%d", &n);
	string sname;
	t team[50];
	map<string,int> teamindex;
	for(int i=0;i<n;i++){
		cin>>sname;
		teamindex[sname] = i;
		team[i].name = sname;
	}
	int all = n*(n-1)/2;
	for(int i=0;i<all;i++){
		string s1,s2;
		cin>>s1>>s2;
		int pos = split(s1, '-');
		string team1 = p(s1, 0, pos);
		string team2 = p(s1, pos+1, s1.length());
		pos = split(s2, ':');
		int score1 = change(p(s2, 0, pos));
		int score2 = change(p(s2, pos+1, s2.length()));
		
		int i1 = teamindex[team1], i2 = teamindex[team2];
		team[i1].v+=score1;
		team[i2].v+=score2;
		if(score1 > score2){
			team[i1].score+=3;
			team[i1].ball+=score1-score2;
			team[i2].ball-=score1-score2;
		}
		else if(score1 == score2){
			team[i1].score+=1;
			team[i2].score+=1;
		}
		else{
			team[i2].score+=3;
			team[i1].ball+=score1-score2;
			team[i2].ball-=score1-score2;
		}
	}
	sort(team, team+n, cmp1);
	sort(team, team+n/2, cmp2);
	for(int i=0;i<n/2;i++)
		cout<<team[i].name<<endl;
	return 0;
}

7.F1方程式冠军

题目

【问题描述】

一级方程式F1锦标赛由一系列称为大奖赛的分站赛组成。每一场比赛的车手都根据他们的最后位置获得积分。只有前10名车手按以下顺序获得分数：25、18、15、12、10、8、6、4、2、1。在锦标赛结束时，得分最多的车手是冠军。如果有平分，则冠军是赢的最多的人（即排位第一）。如果还是平分，则选择得到排位第二最多的人，依此类推，直到没有更多的排位进行比较。

后来又提出了另一个得分制度，其中冠军是赢的最多的。如果有平手，冠军是得分最多的。如果仍然存在平手，则按原来的得分制度进行，即比较第二、第三、第四、…排位的次数。

在本赛季，你会得到所有比赛的结果，你将根据两个得分系统来分别确定冠军。数据保证两套系统都能得到唯一的冠军。

【输入形式】

第一行一个整数t（1<=t<=20），t是分站赛的场次数。之后是每个分站赛的最终排位情况，每个的第一行一个整数n(1<=n<=100)表示排位车手人数，之后n行按排位列出车手的名字，排位从第一到最后，车手的名字为长度不超过50的英文字符，大小写区分。
【输出形式】、

输出为两行，第一行为按照原始规则确定的冠军，第二行是按照可选规则确定的冠军。

【样例输入】

3
3
apple
banana
pear
2
pear
banana
2
apple
banana

【样例输出】

banana
apple

题解

跟第四，第六题一样，录名字，算分数，排序。不过这里有个小坑需要注意一下，这里的排名不止计算到第十名，也就是说排序比较同一排名次数时是得一直往下比直到比出结果的（这个坑了我一个点）

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#include <map>
using namespace std;

struct players{
	string name;
	int rank[100]={0};
	int score=0;
}player[100];

int rankscore[10] = {25, 18, 15, 12, 10, 8, 6, 4, 2, 1};

bool cmp1(players a, players b){
	if(a.score==b.score)
		for(int i=0;i<100;i++){
			if(a.rank[i]!=b.rank[i])
				return a.rank[i]>b.rank[i];
			}
	else
		return a.score>b.score;
}

bool cmp2(players a, players b){
	if(a.rank[0]==b.rank[0])
		if(a.score!=b.score)
			return a.score>b.score;
		else 
			for(int i=1;i<100;i++){
				if(a.rank[i]!=b.rank[i])
					return a.rank[i]>b.rank[i];
				}
	else
		return a.rank[0]>b.rank[0];
}

int main(){
	int t,index=0;
	scanf("%d",&t);
	map<string, int> playerindex;
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			string name;
			cin>>name;
			if(playerindex.find(name)==playerindex.end()){
				player[index].name = name;
				memset(player[index].rank, 0, sizeof(player[index].rank));
				playerindex[name] = index++;
			}
			int id = playerindex[name];
			player[id].rank[i]++;
			player[id].score+=rankscore[i];
		}
	}
	
	sort(player, player+index, cmp1);
	cout<<player[0].name<<endl;
	sort(player, player+index, cmp2);
	cout<<player[0].name<<endl;
	
	return 0;
}

8.买房与选房

题目

【问题描述】

   在 X 国许多一线城市住房非常紧张，政府部门制定了相关的政策，重点满足住房刚性需求（住房面积为0，社保缴纳必须超过2年），然后才能照顾改善性需求（住房面积大于0）。   具体的原则为：

对于刚性需求，缴纳社保月数多者优先

对于改善性需求，现有自有住房面积小者优先

   由于房源有限，为公平起见，开发商在不违背上述原则下特意指定同等条件下申报时间同时作为排队的条件，时间越早优先级越高。   最近有一批新楼盘准备开盘，总共有 m （≤1000）套房，所有的网上申报工作都已经完成并保存到二进制文件house.bin中，申请者提交了自己的基本材料，格式为：身份证号（18位，加1位空字符'\0'，共19位）、社保缴纳月数、自有住房面积、申报时间(格式为：MM-DD-YYYY，10位字符串，加1位空字符'\0'，共11位)，社保缴纳月数、自有住房面积均为整数，文件最后为总报名人数 n（≤105）。   申请者可以通过身份证号查询最终的结果。

【输入形式】

   输入的第一行为两个正整数 m（≤1000）和 T （ T ≤ n ），分别表示本次开盘的楼盘可供申请的套数以及查询的组数   接下来的 T 行，每行为一个18位的字符串，表示需要查询的身份证号

【输出形式】

   输出为 T 行，对应每个查询的输出结果：   1. 申请者不符合购房条件或排位超出了所推出的房源数量不能中签，则输出"Sorry";   2. 申请者符合购房条件，且该名次人数为1人，则直接输出一个整数，表示选房顺序号;   3. 申请者符合购房条件，且该名次人数有多人，同时人数不大于所剩房源数量，则直接输出用空格分隔的两个整数，表示选房顺序号区间;   4. 申请者符合购房条件，且该名次人数有多人，同时人数大于所剩房源数量，则输出用/分隔两个整数，如 A/B，表示 B 人中选 A 人，选房顺序为排名倒数 A 名范围。

【样例输入】

9 6
350102200609166049
350102200609163286
250342323545313434
130502201805070787
110101196003074525
430102201102181455
【样例输出】

2
3 4
Sorry
6
2/3
Sorry
【代码框架】

建议复制以下代码框架， 在此基础上完成本题需求。此建议不是必须，你可以忽略。

#include

using namespace std;

struct people

{

char id[19];                  /* 身份证号码 */int social;                     /* 社保缴纳月数 */int area;                       /* 现有住房面积 */char date[11];              /* 申报日期 */

};

people* getMess(int &n);

int main()

{

people *person;          /* 指向所有报名人的基本资料首地址，通过调用函数getMess获取 */     int n;                            /* n为报名人数，通过调用函数getMess获取 */person=getMess(n);// ...return 0;

}

people* getMess(int &n) /* 将文件数据读入内存 */

{

FILE *fp;fp=fopen("house.bin","rb");fseek(fp,-1*(long)sizeof(int), 2);fread(&n, sizeof(int),1, fp);rewind(fp);people *tmp=new people[n];fread(tmp, sizeof(people), n, fp);fclose(fp);return tmp;

}

【测试用例说明】

10%的用例无同等条件的数据，30%的用例只有刚性需求，20%的用例只有改善性需求。

题解

这题算是栽了，被前面的题目直接名字下标两两对应给套了进去QAQ，然后想着记录下标完再排完排名赋值后再根据下标重排。。。然后改了结构体，然后数据读入出错，然后两小时白给~

这题其实是应该先排序再做两两对应处理，然后开始查询需要查询的id对应排名，找这个排名的上下界。如果上界在m后或者这人没地社保没交够还想白嫖直接sorry；其它情况下如果上下界相等就是唯一解；如果下界在m前就是稳了，输出上下界；如果排名刚好卡在那就很难受，概率是（m-l+1)/(r-l+1)，按题目说的就不用约分啦。

另外这题还让我知道了，原来lower_bound和upper_bound也可以加cmp参数QAQ

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;

struct people{
    char id[19];                  /* 身份证号码 */
    int social;                     /* 社保缴纳月数 */
    int area;                       /* 现有住房面积 */
    char date[11];              /* 申报日期 */
};

people* getMess(int &n){            /* 将文件数据读入内存 */
    FILE *fp;
    fp=fopen("house.bin","rb");
    fseek(fp,-1*(long)sizeof(int), 2);
    fread(&n, sizeof(int),1, fp);
    rewind(fp);
    people *tmp=new people[n];
    fread(tmp, sizeof(people), n, fp);
    fclose(fp);
    return tmp;
}

bool cmp(people a, people b){
	if(a.area==0 && a.social<=24)return 0;
	if(b.area==0 && b.social<=24)return 1;
	if(a.area==0 && b.area==0)
		if(a.social!=b.social)
			return a.social>b.social;
	if(a.area!=b.area)
		return a.area<b.area;
	for(int i=6;i<10;++i)
    	if(a.date[i]!=b.date[i])return a.date[i]<b.date[i];
    for(int i=0;i<2;++i)
       	if(a.date[i]!=b.date[i])return a.date[i]<b.date[i];
  	for(int i=3;i<5;++i)
        if(a.date[i]!=b.date[i])return a.date[i]<b.date[i];
    return 0;
}

int main(){
    people *person;          /* 指向所有报名人的基本资料首地址，通过调用函数getMess获取 */     
    int n;                            /* n为报名人数，通过调用函数getMess获取 */
    person=getMess(n);
    
	sort(person, person+n, cmp);
	//for(int i=0;i<n;i++) cout<<person[i].id<<" "<<person[i].area<<" "<<person[i].social<<" "<<person[i].date<<endl;
	map<string, int> id2pos;
	for(int i=0;i<n;i++){
		string s = person[i].id;
		id2pos[s] = i;
	}
	int m,t;
	scanf("%d %d", &m,&t); 
	while(t--){
		string s;
		cin>>s;
		int pos = id2pos[s];
		int l=lower_bound(person, person+n, person[pos], cmp)-person+1;
		int r=upper_bound(person, person+n, person[pos], cmp)-person;
		if((person[pos].area==0 && person[pos].social<=24) || l>m)printf("Sorry\n");
		else if(l == r)printf("%d\n", l);
		else if(r <= m)printf("%d %d\n", l, r);
		else printf("%d/%d\n", m-l+1, r-l+1);
	}
    return 0;

}

9.二叉树遍历，从前序、中序到后序

题目

【问题描述】

二叉树是一种非常重要的数据结构，非常多其他数据结构都是基于二叉树的基础演变而来的。对于二叉树，深度遍历有前序、中序以及后序三种遍历方法。

三种基本的遍历思想为：

前序遍历：根结点 —> 左子树 —> 右子树

中序遍历：左子树—> 根结点 —> 右子树

后序遍历：左子树 —> 右子树 —> 根结点

比如，求以下二叉树的各种遍历

hhh.png

前序遍历：1 2 4 5 7 8 3 6

中序遍历：4 2 7 5 8 1 3 6

后序遍历：4 7 8 5 2 6 3 1

需要你编写程序解决的问题是：已知一个二叉树的前序遍历和中序遍历的结果，给出该二叉树的后序遍历的结果。

【输入形式】

有多组测试数据，每组测试数据三行，每组测试数据第一行只有一个正整数n，表示二叉树节点的数目，n=0意味着输入结束并且不需要处理。

每组测试数据第二行是二叉树的前序遍历的结果，是一个长度为n的字符串，每个节点由一个字符表示，字符是大小写英文字母及10个数字,不同的节点用不同的字符表示，也即无论前序遍历和中序遍历的字符串中没有重复的字符。

每组测试数据第二行是二叉树的中序遍历的结果，也是一个长度为n的字符串。

40%的测试数据1 ≤ n≤ 10；

30%的测试数据1 ≤ n≤ 20；

20%的测试数据1 ≤ n≤ 40；

10%的测试数据1 ≤ n≤ 62；

【输出形式】

对于每组测试数据，输出一行，是一个长度为n的字符串，表示二叉树后序遍历的结果。

【样例输入】

8
12457836
42758136
4
abcd
abcd
4
abcd
dcba
0
【样例输出】

47852631
dcba
dcba

题解

这题啊，二叉树的经典题。要解决也就只需要知道什么是前中后序遍历， 然后知道原理找找数据规律就有了

前中后序遍历使用递归做的，那求它当然是递归啦！

代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
void f(string s1,string s2,int now,int start,int end){
	if(start>=end)return;
	int i;
	for(i=start;i<end;i++)
		if(s2[i]==s1[now])break;
	f(s1,s2,now+1,start,i);
	f(s1,s2,now+1+(i-start),i+1,end);
	cout<<s1[now];
}
int main(){
	int n;
	while(scanf("%d",&n) && n){
		string s1,s2;
		cin>>s1>>s2;
		f(s1,s2,0,0,n);
		cout<<endl;
	}
	return 0;
}

10.内存管理

题目

【问题描述】

   离第一个操作系统HNU-OS发布已经没有多少时间了，但它的一些组件还没有完成，内存管理器就是其中之一。根据开发人员的计划，在第一个版本中，内存管理器将非常简单和直观。它将支持三个操作：

alloc n —— 分配n个字节内存，返回已分配块的正整数标识符x(x初始值为0，每次分配增长1)

erase x —— 删除标识符x所在的块

defragment —— 整理空余内存碎片，将所有块尽量靠近内存的开始位置，并保持各自的顺序

   在此情况下，内存模型非常简单，它是一个m字节的序列，为了方便起见，从第一个字节到第m字节进行编号。   第一个操作alloc n有一个参数n，表示被分配的内存块大小。在处理此操作时，内存中将分配n个连续字节的空闲块。 如果这些块的数量超过一个，则优先选择最接近内存开始(即第一个字节)的块。 所有这些字节都被标记为非空闲，内存管理器返回一个32位整数数字令牌，代表该块的标识符。 如果不可能分配这样大小的空闲块，则返回NULL。   第二个操作erase x以x为参数，表示某个块的标识符。此操作释放系统内存，将此块的字节标记为空闲以供进一步使用。 如果此标识符没有指向先前分配的块(该块尚未被释放)，则返回ILLEGAL_ERASE_ARGUMENT。   最后一个操作defragment没有任何参数，只会使占用的内存部分更接近内存的开始，而不会更改它们各自的顺序。    在当前的实现中，将使用从1开始的连续整数作为标识符。每个成功的alloc操作过程都应该返回接下来的编号。不成功的alloc操作不影响计数。    编写内存管理器的实现，为每个alloc命令输出返回的值，为所有失败的erase命令输出ILLEGAL_ERASE_ARGUMENT。

【输入形式】

   输入数据的第一行包含两个正整数t和m（1<=t<=500, 1<=m<=105)，其中t表示需要内存管理器来处理的操作个数，m表示有效的内存字节大小。接下来的t行每一行代表一个操作。

【输出形式】

   输出有多行，每行或者是alloc操作的结果，或者是失败的erase操作的结果ILLEGAL_ERASE_ARGUMENT。其顺序与输入的操作次序一致。

【样例输入】

6 10
alloc 5
alloc 3
erase 1
alloc 6
defragment
alloc 6

【样例输出】

1
2
NULL
3

题解

HNU-OS可还行……这题实际上用一个长度为m的数组模拟就能过（可能是数据太小了，我写这题的时候构建了一个很极端的数据应该能让这种做法妥妥超时）

然后我感觉应该用单链表写这题（理论上来讲这题的最优解应该也是单链表），从来没写过单链表的我（只记得原理）硬生生搓了个单链表出来A了这题

所以这里我不讲暴力模拟的做法，来讲讲单链表的解法（这21道题对我来说意义最大的也是这题）

开始时我们可以把整个长度看作是一个长度为m，未被占用的块，其id（标识符）不记。对于每个块，无论它是否被使用，都记为单链表的一个节点；

然后康康它给的三个操作：

  • alloc n —— 分配n个字节内存，返回已分配块的正整数标识符x(x初始值为0，每次分配增长1)

这个操作可以将以前已经清除掉且长度合适的空块重新分配。因为不一定是最后的那段。好在我们把未分配也看作成一个空块，与被释放内存的块无本质上的差别。
所以这个操作转化成，从头到尾查询第一个可以被插入的空块

  • 1，假设这个合适的空块长度为l
    于是乎这个空块不再是空块了，它就被占用了，长度变为了n，有了自己的id——标识符；那如果不是那么刚刚好分配，剩下了l-n呢？我们在这个块的后边插入一个长度为l-n的空块
  • 2，如果没有合适的空块呢？
    那当然是返回NULL啊~
  • erase x —— 删除标识符x所在的块

这个操作看起来像简单的修改单链表的一个节点的数据，这听起来很容易，然而：
如果这个块的前后是空块呢？如果我们不进行合并，那么加alloc操作时遇到了一堆连续的空块，把他们加起来可插入但又无法插入其中的第一个时（插入到后面的会导致顺序出错）就很难受了

  • 所以在把这个块变成空块之后，要进行前后是否是空块的检验与合并
    记得变成空块不是只改个占用状态，还要清掉id哦！当然找不到标识符x所在的块时记得返回ILLEGAL_ERASE_ARGUMENT
  • defragment —— 整理空余内存碎片，将所有块尽量靠近内存的开始位置，并保持各自的顺序

这个操作很明显转换成了，删除单链表中所有的空块，记录长度和l，然后在单链表最后插入一个长度为l的空块

这题里面单链表的时间复杂度和空间复杂度无疑是非常优秀的，在痛心疾首我为什么不先试试暴力的同时窃喜第一次用到了单链表。单链表考一堆细节逻辑操作，我能用单链表把它写出来就很高兴了。

代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

struct node{
	int id;
	bool used = false;
	int l=0;
	node *next;
}*head, *p, *r;

int main(){
	int t,m;
	scanf("%d %d", &t, &m);
	head = new node;
	p = new node;
	head->next = p;
	p->l = m;
	p->next = NULL;
	int x=0,nownum=1;
	while(t--){
		string s;
		cin>>s;
		if(s=="alloc"){
			int n;
			scanf("%d", &n);
			r = head;
			while(r->next != NULL){
				p = r->next;
				if(!p->used && p->l>=n){
					if(p->l - n != 0){
						node *newnode;
						newnode = new node;
						newnode->next = p->next;
						newnode->l = p->l - n;
						p->next = newnode; 
					}
					p->id = ++x;
					p->l = n;
					p->used = true;
					break;
				}
				r = p;
			}
			if(r->next == NULL)
				printf("NULL\n");
			else
				printf("%d\n", x);
		}
		else if(s=="erase"){
			int n;
			scanf("%d", &n);
			r = head;
			while(r->next != NULL){
				p = r->next;
				if(p->id == n)break;
				r = p;
			}
			if(r->next == NULL or !p->used)
				printf("ILLEGAL_ERASE_ARGUMENT\n");
			else{
				p->used = false;
				if(p->next != NULL){
					node *q;
					q = p->next;
					if(!q->used){
						p->next = q->next;
						p->l += q->l;
					}
				}
				if(r != head){
					if(!r->used){
						r->next = p->next;
						r->l += p->l;
					}
				}
			}
		}
		else{
			int k=0;
			r = head;
			while(r->next != NULL){
				p = r->next;
				if(!p->used){
					r->next = p->next;
					k += p->l;
				}
				if(r->next == NULL)break;
				r = p;
			}
			if(k!=0){
				node *newnode;
				newnode = new node;
				r->next = newnode;
				newnode->next = NULL;
				newnode->l = k;
			}
		}
	} 
	return 0;
}

11.平均方差

题目

【问题描述】

一个数列的平均方差是指数列中的每个元素与数列的平均值的差的平方和的平均值，比如下面数列：

1 2 3 4 5 6 7

其平均值为4，每个元素与平均值的差的平方为

9 4 1 0 1 4 9

其平方和为28，所以该数列的平均方差为4。

对给定的数列，求出其平均方差。

【输入形式】

有多组测试数据。

每组测试数据第一行是一个正整数N，表示数列中元素个数，接下来一行N个用空格分隔开的正整数，表示数列的N个元素，每个元素的值都是不大于500的正整数。

N=0表示输入结束，并且不需要处理。

40%的数列元素个数N 1 ≤ N≤ 10；

30%的数列元素个数N 1 ≤ N≤ 100；

20%的数列元素个数N 1 ≤ N≤ 1000；

10%的数列元素个数N 1 ≤ N≤ 10000；

【输出形式】

对于每组测试数据，输出一个整数：平均方差。平均方差不是整数的，输出其向下取整的整数。比如平均方差是4.5，输出4。

【样例输入】

7
1 2 3 4 5 6 7
4
1 2 3 4
0
【样例输出】

4
1

题解

emmm，水题，没什么好讲的，过吧。

代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int main(){
	int n;
	double a[10000];
	while(scanf("%d",&n) && n){
		memset(a,0,sizeof(a));
		double s=0;
		for(int i=0;i<n;i++){
			cin>>a[i];
			s+=a[i];
		}
		double ava = s/(double)n;
		s=0;
		for(int i=0;i<n;i++){
			s+=(a[i]-ava)*(a[i]-ava);
		}
		int ans=s/n;
		printf("%d\n",ans);
	}
	return 0;
}

12.IP地址

题目

【问题描述】

一个IP地址由32位二进制的数组成，比如：

111111111111111111111111000000002

为了便于记忆，我们将8个二进制位用一个十进制数表示，一个IP地址由四个十进制数表示，上述的IP地址表示为：

255.255.255.0

现在给你一个上述形式的IP地址，请回答IP地址的32个二进制位中，有多少位是1。

如IP地址为255.255.255.0，其中24位是1。

【输入形式】

有多组测试数据。

测试数据第一行是一个正整数T，表示测试数据组数。

每组测试数据是一个IP地址，形式为：

IP1.IP2.IP3.IP4

其中0 ≤IP1,IP2,IP3,IP4≤ 255,用十进制表示。每个IP地址不保证是实用IP地址。

40%的测试数据组数T 10≤T≤ 102；

30%的测试数据组数T 102≤T≤ 103；

20%的测试数据组数T 103≤T≤ 104；

10%的测试数据组数T 104≤T≤ 105；

【输出形式】

对于每个IP地址，输出一行包含一个非负整数：该IP地址的32个二进制位中，1的位数。

【样例输入】

5
255.255.255.0
127.0.0.1
0.0.0.1
1.2.3.4
0.0.0.0
【样例输出】

24
8
1
5
0
提示：样例中32位的IP地址为：

111111111111111111111111000000002

011111110000000000000000000000012

000000000000000000000000000000012

000000010000001000000011000001002

000000000000000000000000000000002

题解

这题就考察二进制转十进制罢了，不过为了偷懒就直接用了个函数__builtin_popcount，能把十进制数对应二进制的1的数量求出来

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        unsigned int a=0,b=0,c=0,d=0;
        scanf("%d.%d.%d.%d", &a,&b,&c,&d);
        int ans = __builtin_popcount(a)+__builtin_popcount(b)+__builtin_popcount(c)+__builtin_popcount(d);
        cout<<ans<<endl;
    }
    return 0;
}

13.开关与灯

题目

【问题描述】

    给定n个开关和m个灯，第i个开关只能打开部分灯。矩阵a包含n行m列，当aij=1时表示开关i可以打开灯j，否则aij=0。

开始时所有的m个灯都是关着的。

开关只能从状态”关”到”开”。这意味着，对于每个可以打开某个灯的开关，无论你按多少次，这个灯都是开的。

确保当你按下所有开关时，所有的灯都能打开，考虑是否可以忽略其中某个开关也能打开所有的灯。

你的任务是确定是否存在这样的开关可以忽略，而使用其余的n-1个开关来打开所有m个灯。

【输入形式】

     输入第1行包含两个整数n和m(1<=n, m<=2000)，表示开关的数量和灯的数量。

接下来的n行，每行包含m个字符，字符aij=1时表示开关i可以打开灯j，否则aij=0。

【输出形式】

     如果存在这样的可以忽略的开关，而使用其他n-1个开关打开所有的m个灯，输出"YES"，否则输出"NO"。

【样例输入】

4 5
10101
01000
00111
10000

【样例输出】

YES

题解

这题其实一开始的时候想的是二进制取或，但后来想想那个数据量。。。算了

讲讲思路吧：首先我们要对每一列求和，那么我们得到m个和；然后开始枚举哪个开关扔了，我们用这堆和分别减去它对应的1，如果有一个值为0就说明不行，我们遍历下一个。

如果一次遍历每个值都不为0，那么就说明这n-1个开关可以开m个灯，也就是YES啦。

当然你要骗分的话，输出一次YES提交康康对几个点，对的少就换NO提交一次，就一堆分到手啦！

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[2000][2000];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    string s;
	int b[2000];
    memset(b,0,sizeof(b));
    for(int i=0;i<n;i++){
        cin>>s;
        for(int j=0;j<m;j++)
            a[i][j]=int(s[j]-'0'),b[j]=b[j]+a[i][j];
    }
	for(int i=0;i<n;i++){
		int j;
		for(j=0;j<m;j++)
			if(b[j]-a[i][j]<=0)
				break;
		if(j==m)return printf("YES\n"),0;
	} 
	return printf("NO\n"),0;
}

14.可删除的点

题目

【问题描述】

平面上有n个不同的点，没有在Y轴的点，检查是否存在这样一个点，将其删除后其余所有的点均位于Y轴的同一边。
【输入形式】

输入第一行包含一个正整数n(2<=n<=105)。

接下来的n行，包含所有点的坐标，第i行包含两个整数xi和yi(|xi|、|yi|<=109，xi<>0)。
【输出形式】

如果存在这样的点，则输入”Yes”，否则输出”No”。
【样例输入】

3
1 1
-1 -1
2 -1

【样例输出】

Yes

题解

这题显然y没有什么用处，记录一下x的正负个数，如果有哪一边小于等于1就有可删除的点啦

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[2000][2000];
int main(){
    int n;
    scanf("%d",&n);
    int l=0,r=0;
    while(n--){
    	int x,y;
    	scanf("%d %d",&x,&y);
    	if(x<0)l++;
    	else r++;
	}
	if(l<=1 || r<=1)return printf("Yes\n"),0;
	return printf("No\n"),0;
}

15.字符串反转3

题目

【问题描述】

   给出一个字符串，请将其每个单词反转后输出。

【输入形式】

  输入第一行为一个正整数N，表示测试用例数，接下来的N行，每行一个字符串。

【输出形式】

  输出N行，每行对应一个反转后的字符串。

【样例输入】

3
olleh !dlrow
m’I morf .unh
I ekil .tae
【样例输出】

hello world!
I’m from hnu.
I like eat.

题解

这题如果用getline的话记得关掉cin/cout的缓存（反正就是加速器，不然会有一个点超时），或者用gets（这个我真忘了）

另外提一句，stringstream真香 && reverse真香

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <sstream>
using namespace std;
int a[2000][2000];
int main(){
	ios::sync_with_stdio(false);
	cout.tie(NULL);
	//关cin和cout缓存
    int n;
    cin>>n;
    cin.ignore();//忽略换行符
    
    while(n--){
    	string s;
    	getline(cin, s);
    	stringstream ss;
    	ss<<s;
    	while(ss>>s){
    		reverse(s.begin(), s.end());
    		cout<<s<<" ";
		}
		cout<<endl;
	}
	return 0;
}

16.n， 还是n

题目

【问题描述】

输出 包含n 或者是n的倍数的所有数

【输入形式】

正整数 m,n（0<m，n<1000000）

【输出形式】

从小到大排列的不大于 m 的特殊正整数（包含n，或者是n的倍数）。

【样例输入1】

20 7
【样例输出1】

7 14 17
【样例输入2】

200 11
【样例输出2】

11 22 33 44 55 66 77 88 99 110 111 112 113 114 115 116 117 118 119 121 132 143 154 165 176 187 198
【样例说明】

包含n的数可以考虑使用字符串查找解决

题解

这个提示给的是真的是。。。我看到立马去查了下string.find

这题之后也还有好几题涉及字符串和数字转换，知道string.find和它的用法这题就不剩什么难点了。

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <sstream>
using namespace std;
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	int temp=m;
	string ms="";
	while(temp!=0){
		ms+=char(temp%10+'0');
		temp/=10;
	}
	reverse(ms.begin(), ms.end());
	for(int i=1;i<=n;i++){
		if(i%m==0)printf("%d ",i);
		else{
			temp = i;
			string is="";
			while(temp!=0){
				is+=char(temp%10+'0');
				temp/=10;
			}
			reverse(is.begin(), is.end());
			if(is.find(ms)!=is.npos)printf("%d ",i);
		}
	}
	return 0;
}

17.字符串排序

题目

【问题描述】

   定义一个字符串的无序度为所有位置后面的字母比该位置的字母小的总数之和。比如"DAABEC''这个字符串的无序度是5，因为D后面有4个位置比它小（AABC），E后面有1个比它小（C），其它位置后面没有比自己小的。" AACEDGG "的无序度为1（E后面有一个D比它小）。" ZWQM "的无序度为6，每个位置后面所有的字母都比它小。   现在你的任务是给定一些字符串（只由大写字母组成），把他们按照无序度从小到大排序，如果无序度一样，那么就按照输入的相对顺序排序。

【输入形式】

 单组测试数据。 第一行有两个整数n(0 < n <= 50)和m (0 < m <= 100)，分别表示输入的字符串的长度和字符串的个数。 接下来m行，每一行包含一个长度为n的字符串，只由大写字母组成。

【输出形式】

输出m行，表示排序之后的字符串。

【样例输入】

10 6
AACATGAAGG
TTTTGGCCAA
TTTGGCCAAA
GATCAGATTT
CCCGGGGGGA
ATCGATGCAT
【样例输出】

CCCGGGGGGA
AACATGAAGG
GATCAGATTT
ATCGATGCAT
TTTTGGCCAA
TTTGGCCAAA

题解

无序度这个东西应该叫逆序对吧（都是学过线代的人了）

求逆序对其实比较好的方法应该是归并排序，但这题计算量撑死50 * 100 * 99 / 2，多大点事啊，暴力算了。。。

然后排序，没有然后了。。。

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <sstream>
using namespace std;
struct ss{
	string name;
	int dot=0;
	int pos;
}qaq[100];

bool cmp(ss a, ss b){
	if(a.dot == b.dot)return a.pos<b.pos;
	return a.dot<b.dot;
}

int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		string s;
		cin>>s;
		qaq[i].name = s;
		for(int j=0;j<n-1;j++)
			for(int k=j+1;k<n;k++)
				if(s[j]>s[k])
					qaq[i].dot++;
		qaq[i].pos=i;
	}
	sort(qaq, qaq+m, cmp);
	for(int i=0;i<m;i++)
		cout<<qaq[i].name<<endl;
	return 0;
}

18.三角形的面积

题目

【问题描述】

已知三角形的三个顶点的坐标，求该三角形的面积。

【输入形式】

有多组测试数据。

每组测试数据占一行，6个用空格分隔开的浮点数：x1,y1,x2,y2,x3,y3。表示三角形三个顶点的坐标。

一行6个0（形如0 0 0 0 0 0），表示输入结束，并且不需要处理。

40%的顶点坐标 -10 ≤ xi,yi≤ 10；i=1,2,3

30%的顶点坐标 -100 ≤ xi,yi≤ 100；i=1,2,3

20%的顶点坐标 -1000 ≤ xi,yi≤ 1000；i=1,2,3

10%的顶点坐标 -10000 ≤ xi,yi≤ 10000；i=1,2,3

【输出形式】

对于每组测试数据，输出对应三角形面积，保留小数点后6位。

【样例输入】

1 2 3 4 -2 8
0 0 0 1 1 0
0 0 0 0 0 0
【样例输出】

9.000000
0.500000
Tips：如果使用浮点数，请注意精度问题，推荐使用double

题解

向量叉乘求面积算计算几何的常识了，不过我就纳闷了没化简前错一半，化简后全对？

这题用海伦公式这种进度贼差的公式都能全对， 这不就很奇怪了嘛。。。

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <sstream>
#include<iomanip>
using namespace std;
int main(){
	double a1,b1,a2,b2,a3,b3;
	while(cin>>a1>>b1>>a2>>b2>>a3>>b3){
		if(a1==0&&a2==0&&a3==0&&b1==0&&b2==0&&b3==0)break;
		double ans = (a1*b2-a1*b3+a2*b3-a2*b1+a3*b1-a3*b2)/2.0;
		if(ans<0)ans=-ans;
		cout<<fixed<<setprecision(6)<<ans<<endl;
	}
	return 0;
}

19.循环数

题目

【问题描述】

  循环数是n位长度的整数，当乘以从1到n的任何整数时，产生原始数字的“循环”。也就是说，如果考虑最后一个数字之后的数字“绕”回到第一个数字，两个数字中的数字序列将是相同的，尽管它们可能从不同的位置开始。例如，数字142857是循环的，如下表所示：     142857 *1 = 142857    142857 *2 = 285714    142857 *3 = 428571    142857 *4 = 571428    142857 *5 = 714285    142857 *6 = 857142    编写一个程序来确定数字是否是循环数。

【输入形式】

   输入一个数，长度在2到60位之间(请注意，前面的零不应该被删除，它们被认为是确定n的大小和计数的一部分，因此，“01”是一个两位数的数字，与“1”是一个一位数的数字不同。) 。

【输出形式】

   对于每个输入，输出一行(Yes或No)标识它是否是循环数。

【样例输入】

142857
【样例输出】

Yes

题解

我们把每种轮换都先打个表，然后对询问的数枚举倍数后与表中每一种轮换的值进行比对即可（这样做也不会有前导0的干扰）

（我不知道stringtream可以直接转换字符串和整型，我一直都是手写转换的）

另外这题我取巧了，当这个数的数位很大(2的64次方大概19位吧）时我直接判定为no了，毕竟数位太大unsigned long long也存不下

而数位大于9时说明这个数得乘上10以上的数，位数会+1，如果想保持本身位数不变必须有前导0。前导0越多这个数越难可能是循环数，所以我就取巧了一波。

代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int main(){
	string s;
	cin>>s;
	int l=s.length();
	if(l>18)return printf("No\n"),0;
	string qaq[18];
	qaq[0]=s;
	for(int i=1;i<l;i++){
		qaq[i]="";
		for(int j=i;j<i+l;j++)
			qaq[i]+=s[j%l];
	}
	long long num=0;
	for(int i=0;i<l;i++)
		num=num*10+s[i]-'0';
	bool flag; 
	for(int i=2;i<=l;i++){
		long long b=num*i;
		flag=false;
		if(b>=pow(10,l))break;
		for(int j=0;j<l;j++){
			long long c=0;
			for(int k=0;k<l;k++)
				c=c*10+qaq[j][k]-'0';
			if(b==c){
				flag=true;
				break;
			}
		}
		if(!flag)break;
	}
	if(flag)printf("Yes\n");
	else printf("No\n");
	return 0;
}

20.电能消耗

题目

【问题描述】

  汤姆对他最喜欢的笔记本电脑的耗电量很感兴趣。他的笔记本电脑有三种模式。在正常模式下，笔记本电脑每分钟消耗P1瓦。在汤姆最后一次移动鼠标或触摸键盘后的T1分钟，屏幕保护程序启动，每分钟的功耗变化为P2瓦。最后，从屏幕保护程序启动到T2分钟后，笔记本电脑切换到“睡眠”模式，每分钟消耗P3瓦。 当笔记本电脑处于第二或第三模式时，如果汤姆移动鼠标或触摸键盘，则切换到第一种(正常)模式。 汤姆使用笔记本电脑工作的时间可以分为n个时间间期[l1, r1]、[l2, r2]、...、[ln, rn]。在每个间期，汤姆连续移动鼠标并按下键盘。 在间期之间，汤姆什么都不做。请找出在间期[l1, rn]笔记本电脑的总耗电量。

【输入形式】

  第一行包含6个整数n、P1、P2、P3、T1、T2(1<=n<=100，0<=P1、P2、P3<=100，1<=T1、T2<=60)。接下来的n行包含了汤姆工作的期间，第i行是两个用空格分隔的整数li和ri(0<=li<=ri<=1440, 当i<n时ri<li+1）, 表示工作期间的开始时间和结束时间。

【输出形式】

  输出总的耗电量。

【样例输入】

2 8 4 2 5 10
20 30
50 100

【样例输出】

570

题解

这题按部就班地模拟一遍即可

代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int main(){
	int n,p1,p2,p3,t1,t2;
	cin>>n>>p1>>p2>>p3>>t1>>t2;
	int l,r;
	cin>>l>>r;
	long long sum=(r-l)*p1;
	while(--n){
		cin>>l;
		int t = l-r;
		if(t<=t1)sum+=t*p1;
		else if(t<=t1+t2)sum+=t1*p1+(t-t1)*p2;
		else sum+=t1*p1+t2*p2+(t-t1-t2)*p3; 
		cin>>r;
		sum+=(r-l)*p1;
	}
	cout<<sum<<endl;
}

21.计算校验码

题目

【问题描述】

传送一个B（B≤16）进制的数值N时，最后加上一个一位（B进制的）校验码，使得N加上校验位后能被B-1整除。比如十进制的数值12310，其校验码就是3，因为十进制数值123310能被9整除。16进制的数7816，其校验码为0，因为16进制的78016是15的倍数。超过十进制后，用字母a表示10，字母b表示11，字母c表示12，字母d表示13，字母e表示14，字母f表示15。

告诉你进制B，以及一个B进制的正整数N，要求你计算正整数N在B进制下的校验码。

【输入形式】

输入第一行正整数t (10 ≤ n ≤ 100)，表示有多少组测试数据。

后面有t行，每行两个正整数B，N（2≤ B≤16），中间用一个空格隔开，B是10进制整数，N用B进制形式表示。测试数据保证没有非法的B进制数N（也即N中每一位都是在0到B-1之间，没有前导0）。

40%的测试数据N的位数L 1 ≤ L≤ 10；

30%的测试数据N的位数L 1 ≤ L≤ 102；

20%的测试数据N的位数L 1 ≤ L≤ 103；

10%的测试数据N的位数L 1 ≤ L≤ 104；

【输出形式】

对于每组测试数据，输出一位占一行：正整数N在B进制下的校验码。（如果校验码可以为B-1，也可以为0，输出0）。

【样例输入】

4
10 123
16 78
16 1234321
12 ab
【样例输出】

3
0
e
1
【样例说明】

第一行的4表示有4组测试数据，下面四行，每行一组测试数据。

第一组测试数据 10进制数123 最后添加检验码3，10进制数1233是9（=10-1）的倍数

第二组测试数据 16进制数78 最后添加检验码0，16进制数780是15（=16-1）的倍数

第三组测试数据 16进制数1234321 最后添加检验码e（=14），16进制数1234321e是15（=16-1）的倍数

第四组测试数据 12进制数ab 最后添加检验码1，12进制数ab1是11（12-1）的倍数

【Tips】

B进制的数能被B-1整除，当且仅当各位数字和能被B-1整除。

第一组测试数据 10进制数123 最后添加检验码3，10进制数1233各位数字和是9，是9的倍数

第二组测试数据 16进制数78 最后添加检验码0，16进制数780各位数字和是15，是15的倍数

第三组测试数据 16进制数1234321 最后添加检验码e，16进制数1234321e各位数字和是30，是15的倍数

第四组测试数据 12进制数ab 最后添加检验码1，12进制数ab1各位数字和是22，是11的倍数

题解

刚开始看错了题目好多次。。。

先算出前面几位对应的十进制后暴力枚举最后一位，然后就那样了。。。

代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
map<char,int> a;
int main(){
	int t;
	scanf("%d",&t);
	for(char i='0';i<='9';i++)
		a[i] = i-'0';
	for(char i='a';i<='f';i++)
		a[i] = i-'a'+10;
	while(t--){
		int n;
		string s;
		cin>>n>>s;
		long long num=0;
		int l=s.length();
		for(int i=0;i<l;i++)
			num =(num*n+a[s[i]])%(n-1);
		int i=0;
		for(i=0;i<n;i++)
			if((num*n+i)%(n-1)==0)break;
		if(i<10)printf("%d\n", i);
		else printf("%c\n", i-10+'a');
	}
	return 0;
}

结

写到这儿完，已经深夜三点。第一周的复盘就此结束。本来以为下午晚上写写两三天就能写完，然而还是很拖拉。而且模拟题真的代码是又臭又长。

有什么问题可以评论留言

另外貌似有个助教也写了题解集，可以参考参考[湖南大学程序设计实训训练作业一]作业一汇总篇