国三啦！

赛后感想

今年整体来讲题目确实是比去年要难一点，L1做到后面就开始有点思维了，看到L2-3和L3-1以后就果断放弃拿国二的想法，好在运气好最后拿了个国三。总之，不打铁就算成功！

  • L1-1输出一句话，L1-2整数除法，这种5分水题就没啥好说了。
  • L1-3条件分支，一开始把输入的两个年龄比大小换了一下，拿了7分，后来发现要按输入的顺序输出，最后写完L1-8才重新改回来。难度倒是不大，就是有点麻烦，得静下心来。
  • L1-4是啥忘记了，就记得当时一遍就莽过去了。
  • L1-5好像是丢骰子的题，直接记录出现过的点数写个循环。
  • L1-6字符串，给了伪代码，读懂题意后就直接莽过去。
  • L1-7看了眼数据有十万，开二维数组显然不现实，就给每一行每一列设计一个标记（做过八皇后的话对这种套路应该不陌生），最后记录被boss放过技能的行数和列数，然后输出$nm-cnt1m-cnt2n+cnt1cnt2$。总数减去行格数减去列格数再加上重复部分。
  • L1-8一开始还以为是排序题，后来发现只要是天梯赛175及以上且PAT分数达标的第一次就会被推过去，所以就先记下这部分人数，然后对175分及以上但PAT分数不够的用map记下来，然后k次迭代遍历map计数，就得出了答案。
  • L2-1松针，和去年的包装机差不多，一个队列推松针，一个栈临时存松针，就一个比较繁琐的模拟，要注意各种边界条件。
  • L2-2排序题，最后加上00:00:00和23:59:59，再处理一下输出就行。
  • L2-4大众情人，要求找异性缘最大的男性和女性，其实就是找在异性眼中最大距离最小的男性和女性。用Floyd就可以求出两两之间的距离，不过要注意这是有向图。最后就找答案输出。
  • L3-1据说正解是拓扑排序，那时候在想怎么存两个字符串的大小关系，搞了半天没调出来直接开摆，就写了n=1的情况，拿了一分。
  • L2-3最后十五分钟想出来暴搜且返回根结点，最后再减去最深的那段路径，但是来不及了。

拿个奖退役，还行。

注意的东西

  1. 如果选择对输入一个个读入，循环体不能随便break，因为可能会导致该询问的输出 输出到下个询问。

  2. 比较麻烦的字符串处理题，可以先考虑简化版怎么处理，再加上特殊判断。

  3. 结构体重载运算符作比较时，可以再写一个比较函数cmp进行基本比较，然后再在重载运算符里写总的比较规则，遇到重复的基本比较时就可以调用cmp，简化了代码。

  4. 优先队列默认大根堆，小根堆要修改。小根堆要重载大于号，大根堆要重载小于号。

    1
    2
    3
    4
    5
    priority_queue<int,vector<int>,greater<int> >q;
    //可以记成 <类型,<存储方式>,<比较函数> >
    struct node;
    priority_queue<node,vector<node>,greater<node> > coll;
    //一样的道理，但是这个node只能是结构体，不能是define的定义

  5. 看清楚题目有没有说第一个是根，有没有说按顺序输入。没有的话，要注意。

  6. pair的声明

    1
    2
    3
    #define pis pair<int,int>
    pis a={1,2};
    cout<<a.first<<" "<<a.second<<endl;

  7. 完全二叉树用数组存储，只要知道任意四种遍历方式的一种，就可以给数组填上值构造出完全二叉树。

  8. std::string 的方法 find，返回值类型是std::string::size_type， 对应的是查找对象在字符串中的位置（从0开始），如果未查找到，该返回值是一个很大的数据（4294967295），判断时与 std::string::npos 进行对比。

  9. 无穷大的定义const int inf=0x3f3f3f3f;

  10. L2 的题先想明白思路，规划好怎么写，再开始写。

  11. 看清楚题目给出的每个量的数据范围，是不是正数，是不是整数，这些很重要。

  12. 是小于还是大于还是小于等于还是大于等于还是等于还是不等于，想清楚。

  13. printf("%.2lf\n",ans)保留两位小数，四舍六入五成双。若五后有大于0的有效数字，五入，否则看五前面是奇数还是偶数，凑偶。所以说保留整数时，用强制类型转换，因为强转是截断式的。要四舍五入时，就加0.5再强转。

  14. 求是否有公共祖先时，可以把祖先放到set里，如果放进去set大小不变说明有重复，就说明有公共祖先。

  15. 五代以内没有公共祖先的意思是各自的四代都没有对方的祖先，对方的祖先可以不在四代以内。

  16. cin cout 加速

    1
    2
    3
    //cin cout 的加速
    ios::sync_with_stdio(false);
    cin.tie(0);

字符串处理

1
2
3
4
5
6
7
8
9
10
11
12
//str的pos位置前插入str1,注意若pos是循环的下表，pos要加上插入字符串的长度
str.insert(pos,str1);
//返回从str的pos开始长度为len的子串，记得前面要加个str=，不然相当于啥也没干
str=str.substr(pos,len);
//创建一个输入流ss，内容是str
#include<sstream>
stringstream ss(str);
while(ss>>str)
//把字母变成小写
tolower(char x)
//返回从pos开始找str1的第一个位置    
str.find(pos,str1)

哈夫曼树和哈夫曼编码

  1. 哈夫曼树的带权路径长度 = 非叶子结点的权值之和。可以用小根堆计算。
  2. 判断哈夫曼编码的合法性：
    • 带权路径和对不对。小根堆。
    • 有无前缀。str.find()

迪杰特斯拉求单源最短路

问题：n个点，m条带权边，求从起点s到终点d的最短路径长度。

二维数组存图

  • 创建一个二维数组，初始化置为无穷大。const int inf=0x3f3f3f3f;
    • fill(e[0],e[0]+n*n,inf);
  • dist[i] 表示从源点s到图中各点的最短路径长度，dist[i]是在动态变化的，每迭代一次都会产生一个不会再变化的dist数据。n次迭代后得到最终的dist。dist初始化也置为正无穷，表示无穷远。
  • dist[s]=0; 设置起点的最短路径就是0。
  • bool vis[i]表示i点是否已经得到最短路径。因为每次迭代我们都会得到一个最短路径，所以我们每次都把得到最短路径的结点标记一下，表示加入已找到最短路径的集合S。
  • 查找下一个点。遍历dist，找到离S最近的那个点，将其加入S。
  • 关于新加入的结点u维护dist数组，对于不在S中的结点，若两点间有路径（即e[u][v]!=inf）,if dist[v]>dist[u]+e[u][v] dist[v]=dist[u]+e[u][v]。
  • 最后我们就得到了一个dist数组，表示最短路径。
  • pre[i]表示结点的最短路径的前驱结点，用于打印最短路径，写个递归就可以了。

紧急救援

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,s,d;
int w[505],e[505][505],cnt1[505],cnt2[505],dist[505],pre[505];
bool vis[505];
void print(int x){
	if(x==s){
		cout<<s;
		return;
	}
	print(pre[x]);
	cout<<" "<<x;
}
int main(){
	cin>>n>>m>>s>>d;
	fill(dist,dist+505,inf);
	fill(e[0],e[0]+505*505,inf);
	for(int i=0;i<n;i++) cin>>w[i];
	int u,v,val;
	for(int i=0;i<m;i++){
		cin>>u>>v>>val;
		e[u][v]=val;
		e[v][u]=val;
	}
	dist[s]=0;
	cnt1[s]=1;
	cnt2[s]=w[s];
	for(int i=0;i<n;i++){
		u=-1;
		int minn=inf;
		for(int j=0;j<n;j++){
			if(vis[j]==false&&dist[j]<minn){
				minn=dist[j];
				u=j;
			}
		}
		if(u==-1) break;
		vis[u]=true;
		for(int v=0;v<n;v++){
			if(vis[v]==false&&e[u][v]!=inf){
				if(dist[v]>dist[u]+e[u][v]){
					dist[v]=dist[u]+e[u][v];
					cnt1[v]=cnt1[u];
					cnt2[v]=cnt2[u]+w[v];
					pre[v]=u;
				}else if(dist[v]==dist[u]+e[u][v]){
					cnt1[v]=cnt1[v]+cnt1[u];
					if(cnt2[v]<cnt2[u]+w[v]){
						cnt2[v]=cnt2[u]+w[v];
						pre[v]=u;
					}
				}
			}
		}
	}
	cout<<cnt1[d]<<" "<<cnt2[d]<<endl;
	print(d);
	cout<<endl;
	return 0;
}

Set 和 Vector

  1. 声明一个vector数组，里面放的是一堆set。
  2. 输入数据时先生成set，再把集合push_back到vector中。
  3. set的遍历，auto it=s.begin();it!=s.end();it++，这里的auto相当于set<int>::iterator，it是一个指针。
  4. S.find(x)返回一个指针，指向找到的元素的位置，如果找不到则返回s.end()。可以据此判断是否存在。
  5. vector 向量，可以比较大小，有点字典序的意思。

map 和 multimap

c++ 中 map 不仅可以用于映射，还可以用于排序。

map的底层实现是红黑树，在存储的时候是按键值从小到大排序的。

对于多值的排序可以直接对vector排序，将vector作为map的键值，利用map自动排序，就不用结构体重载运算符啦。

特别是存在重复数据且重复数据不一起参与排序的情况下，用map来排序很不错。还可以利用map的映射性质对重复数量记录。

multimap不同于map的地方在于，map不允许相同的键值存在，而multimap允许，所以multimap也就没有了 [] 的操作。

multimap也是从小到大遍历的，可以用multimap作允许重复键值的排序，对于键值重复的项，按输入顺序排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<map>
#include<vector>
using namespace std;
int n,m;
vector<int> a;
map<vector<int>,int> q;
multimap<int,vector<int>,greater<int>> ans;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	a.resize(m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++) cin>>a[j];
		q[a]++;
	}
	cout<<q.size()<<endl;
	for(auto it:q) ans.insert({it.second,it.first});
	for(auto it:ans){
		cout<<it.first;
		for(auto it2:it.second) cout<<" "<<it2;
		cout<<endl;
	}
	return 0;
}

关于大模拟

L2-028 秀恩爱分得快

10号打训练赛被这道大模拟给卡住了，这种东西没想清楚就上手真的很容易出奇怪的问题，就总结一下写大模拟的一些方法论。

首先最重要的是，读题目打草稿，不要上来就瞎打。通过打草稿理清思路，敲起代码来才能胸有成竹，调试的时候也可以有条不紊。

如何读入？如何输出？

有些大模拟题的读入和输出就会很复杂，要根据实际问题决定使用什么样的输入输出，有时候输入输出比较复杂的时候，可以考虑自己写read()和print()函数。

如何存储输入的数据

存储是很重要的，要考虑用什么样的数据结构，用什么样的存储结构来实现数据结构。不同的存储方式反映数据间关系的难易程度是不同的。对于一些复杂的实体，可以struct一个结构体，再在结构体内部定义我们需要的成员变量。在思考存储方式的时候可以适当联想之后我们要怎么实现任务，让存储方式有助于任务的实现。

完成任务需要哪些步骤？如何实现这些步骤？

在草稿纸上简单写一下解决问题的流程，可以用自然语言描述这些步骤。然后思考怎么用程序语言实现这些步骤。

这个过程相当于把一个任务放在了流水线上，将其分割成几个线性有序的步骤，然后逐个考虑每个步骤的实现。当每个步骤都实现了以后，整个任务就实现了。

对于一些比较复杂的步骤可以用函数封装起来，在写主流程的时候再调用，可以简化代码，有利于调试。

题解

参数

用read读取编号并处理性别，vis数组存储性别。

结构体 photo存放照片信息，分男女存，cnt0表示男性数量，cnt1表示女性数量，num表示总人数。

参数maxa和maxb表示a和b的最亲密异性的亲密值，sumn表示a和b的异性亲密值。

流程

  1. 存储好数据。
  2. 对每张照片，如果照片中有a或b，就计算这张照片中a和b的异性亲密值。
  3. 找到a、b和异性的最大亲密值。
  4. 若a和b是彼此最亲密的人，输出为第一种情况。
  5. 否则，寻找最亲密的人，输出为第二种情况。

上述流程一定是可以完成任务的。

为了简化流程，用自己写的find和 count函数完成 照片中是否有a或b的判断 和 异性亲密值的计算。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<vector>
#include<sstream>
using namespace std;
struct photo{
	int num,cnt0,cnt1;
	vector<int> boy;
	vector<int> girl;
}p[1005];
int n,m,a,b,k;
double sumn[1005],maxa,maxb;
bool vis[1005];
int read(){
	bool flag=false;
	string str;
	cin>>str;
	if(str[0]=='-'){
		flag=true;
		str=str.substr(1,str.length()-1);
	}
	stringstream ss(str);
	int res;
	ss>>res;
	vis[res]=flag;
	return res;
}
void print(int x,int y){
	if(vis[x]) cout<<"-"<<x<<" ";
	else cout<<x<<" ";
	if(vis[y]) cout<<"-"<<y<<endl;
	else cout<<y<<endl;
}
bool find(int x,int i){
	if(vis[x]){
		for(int j=0;j<p[i].cnt1;j++){
			if(p[i].girl[j]==x) return true;
		}
	}else{
		for(int j=0;j<p[i].cnt0;j++){
			if(p[i].boy[j]==x) return true;
		}
	}
	return false;
}
void count(int x,int i){
	if(vis[x]){
		for(int j=0;j<p[i].cnt0;j++){
			sumn[p[i].boy[j]]+=1.0/p[i].num;
		}
	}else{
		for(int j=0;j<p[i].cnt1;j++){
			sumn[p[i].girl[j]]+=1.0/p[i].num;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>p[i].num;
		for(int j=0;j<p[i].num;j++){
			int x;
			x=read();
			if(vis[x]){
				p[i].girl.push_back(x);
				p[i].cnt1++;
			}else{
				p[i].boy.push_back(x);
				p[i].cnt0++;
			}
		}
	}
	a=read();b=read();
	for(int i=1;i<=m;i++){
		if(find(a,i)) count(a,i);
		if(find(b,i)) count(b,i);
	}
	maxa=-1;maxb=-1;
	for(int i=0;i<n;i++){
		if(vis[a]!=vis[i]) maxa=max(maxa,sumn[i]);
		else maxb=max(maxb,sumn[i]);
	}
	if(sumn[a]==maxb&&sumn[b]==maxa) print(a,b);
	else{
		for(int i=0;i<n;i++){
			if(vis[a]!=vis[i]&&maxa==sumn[i]) print(a,i);
		}
		for(int i=0;i<n;i++){
			if(vis[b]!=vis[i]&&maxb==sumn[i]) print(b,i);
		}
	}
	return 0;
}

二分

说实话有些查找手写二分没必要，可以用lower_bound()和upper_bound()函数。当然手写二分的思路还是要有的。

可以把bound理解为等于的边界，这两个函数都表示下界，lower_bound()是大于等于，upper_bound()是大于。

1
int pos=upper_bound(s.begin(),s.end(),x)-s.begin();

返回值是一个地址，指向待符合要求的位置，所以要减去数组首地址成为下标。

查找范围是 左闭右开。不存在则返回 end 位置。

并查集

天梯赛好像就比较喜欢讨论家庭伦理，总是会出现家庭祖先这类的题目，有时候就得用上并查集的操作。

并查集数据结构并不难理解，说白了就是维护一个祖先数组f[i]，int find(int x)压缩路径，以及Uinion(int x,int y)合并两个集合。

实际应用上并查集还会有一些附加属性，比如同时维护一个并查集的大小(集合中的元素个数)，还有一些集合元素的总体值，这些值要怎么合并也是需要考虑的。

家庭房产数

也是一道初看时没头绪的模拟题。通过做这道题也总结了一些问题的解决方法：

  1. 编号不是从0或1开始的连续值时如何处理？
  2. 并查集合并过程中如果一个部分的一些需要合并的值还未录入，怎么用原地的办法让它最后能合并?

关于第一个问题，最简单的办法就是直接开一个大数组，用题目给出的编号作为数组的下标。因为编号只有4位数其实还可以接受。

但是如果编号数特别长的话可以考虑用map进行映射，将题目中给定的编号和程序中实际存储的数组下标进行一个绑定。

这样做就可以直接通过题设编号来找到实际存储的位置。有时候这个编号要输出，所以编号要存在结构体里。

还有就是一个结点，给出和它有关系的结点编号，可能这个编号是不会在行首出现的，这时候我们就得看到一个，就构建一个映射关系，差不多就是这种操作。

1
2
3
4
map<string,int> q;
int cnt=0;
//看到编号str时
q[str]=cnt++

然后第二个问题，涉及到并查集的合并操作。

意思就是一开始 n 个点，每个点都会有一个权值，也可能权值是0，我们在合并的时候，要把所有的值也合并到祖宗结点那里。

但是会有三种情况。

  1. 先给各点权值，再给各点关系。

    这种情况下就直接给各点赋值，然后在uinion里把值送过去就行了。比较简单。

  2. 先给出结点关系再给各点权值。

    这种情况下就先建立关系，把并查集给创建好，然后把每个点的权值加到祖宗结点上。

  3. 给结点关系的过程中给各点权值。

    这种情况就比较复杂，建立关系的时候可能点的权值已经给出了，就得在union里加起来，也可能没给，所以在给出点的权值的时候要加到祖宗去。所以两种操作都得写。因为一开始我们都会初始化各点祖宗是自己，所以就把值加到祖宗上，如果祖宗已经找好了就正好放到祖宗上，没找好就放自己身上，然后就会随着并查集的创建自动就都加好了。

如果是用大数组直接把编号当下标，要设一个bool类型vis标记一下这个编号是否存在，因为初始化的时候直接所有都初始化了，就得标记一下。

然后这题的话主要就是一个维护并查集以及合并各种值的操作，别的排序和计数什么的都比较简单。

在用并查集的时候的一些思想，就假设一开始每个人都是一个家庭，然后家庭合并，就不用分人的结构体和家庭的结构体了。

不用图的搜索是因为这题个体之间的关系就是同在一个集合里，两两间的关系不考虑，没必要存图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<vector>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
//node family
struct node
{
	int cnt,minid;//家庭人口数,最小成员编号 
	double sumn;//总房产数 
	double area;//总面积数
	bool vis;//这个编号是否存在 
}a[100005];
bool operator <(node x,node y)
{
	if(x.area==y.area) return x.minid<y.minid;
	else return x.area>y.area;
}
int f[100005];//并查集
set<int> s;
int find(int x)
{
	if(x!=f[x]) return f[x]=find(f[x]);
	return f[x];
}
void Union(int x,int y)
{
	int xid=find(x);
	int yid=find(y);
	if(xid==yid) return;
	f[yid]=xid;
	a[xid].cnt+=a[yid].cnt;
	a[xid].sumn+=a[yid].sumn;
	a[xid].area+=a[yid].area;
	a[xid].minid=min(a[xid].minid,a[yid].minid);
}
void print(node x)
{
	if(x.minid<1000) cout<<0;
	if(x.minid<100) cout<<0;
	if(x.minid<10) cout<<0;
	cout<<x.minid<<" "<<x.cnt<<" ";
	printf("%.3lf %.3lf\n",x.sumn,x.area);
}
int main()
{
	for(int i=0;i<100005;i++) f[i]=i,a[i].cnt=1,a[i].minid=i;
	cin>>n;
	int id,fid,mid,k,sid,sumn;
	double area;
	for(int i=0;i<n;i++)
	{
		cin>>id;
		a[id].vis=true;
		cin>>fid>>mid;
		if(fid!=-1)
		{
			a[fid].vis=true;
			Union(id,fid);
		}
		if(mid!=-1)
		{
			a[mid].vis=true;
			Union(id,mid);
		}
		cin>>k;
		for(int j=0;j<k;j++)
		{
			cin>>sid;
			a[sid].vis=1;
			Union(id,sid);
		}
		cin>>sumn>>area;
		a[f[id]].sumn+=sumn;
		a[f[id]].area+=area;
	}
	for(int i=0;i<100005;i++) find(i);
	int cnt=0;
	for(int i=0;i<100005;i++) if(a[i].vis) s.insert(f[i]);
	cout<<s.size()<<endl;
	vector<node> ans;
	for(auto it:s)
	{
		a[it].area/=a[it].cnt;
		a[it].sumn/=a[it].cnt*1.0;
		ans.push_back(a[it]);
	}
	sort(ans.begin(),ans.end());
	for(int i=0;i<ans.size();i++) print(ans[i]);
	return 0;
}

二叉树的构建

通过前序中序或中序后序构建二叉树。

也不是说不会，就是不太熟练，所以想来敲个板子。

命名规范一下，每次想名字都想好久。p[i]表示前序，m[i]表示中序,b[i]表示后序。从1开始存，默认0的位置位空结点，比较方便。写一个int build()函数返回根节点的下标。l[i]表示位置 i 的左孩子的位置,r[i]表示位置 i 的右孩子的位置。因为后序和前序的根结点比较好找，所以放的是前后序中的位置。只要调用一次build就把二叉树创建好了。

找中序的根结点位置，创建左右子树，返回根节点坐标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int build(int ml,int mr,int bl,int br)
{
	int pos;
	for(int i=ml;i<=mr;i++)
	{
		if(m[i]==b[br])
		{
			pos=i-ml;
			break;
		}
	}
	if(pos>0) l[br]=build(ml,ml+pos-1,bl,bl+pos-1);
	if(ml+pos<mr) r[br]=build(ml+pos+1,mr,bl+pos,br-1);
	return br;
}