test-2020-10-27 （公交换乘 对称二叉树 photo）

时隔多月，终于准备再水一篇博客了，还有9天就CSP提高了，考完没一等奖就当中考er了，应该就不会怎么动这个博客了。

这次考三道题，两道CSP2019-J原题，重温一下那种感觉吧。

T1:公交换乘

这道题是CSP2019-J的T3，满满的怀旧，当年就挫败在了这道题之下，现在一看，就一道模拟嘛。

思路：题目给的很明确:

如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。

我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。

记录既然按时间顺序给出，而票又一定是先用符合条件且先得到的，就不需要考虑哪张优惠劵先用这些诸如此类的乱七八糟的问题了。

• 最开始一看，直接数组模拟线性过一遍就完事，结果每次扫优惠劵放到数组里都从头扫到尾，直接就扫炸了。还是我太蒻了
• 然后，细细一想，原来没有控制下边界，每次扫的时候不能扫完，用时间把数组约束到一个范围里，再从最先获得的票开始找，就直接改一下原来的代码，把数组改成数组模拟队列就完事了。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,ans,tail,head;
struct node {
	int t,p;
} tik[100010];//结构体模拟优惠券，存过期时间和券的价值
bool vis[100010];//标记这张优惠劵是否用过
int main() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		int ki,pr,ti;
		cin>>ki>>pr>>ti;//kind,price,time
		if(ki==0) {
			tik[tail].p=pr;
			tik[tail++].t=ti+45;
			ans+=pr;
			//是坐地铁的话就直接把票值加到总花费去，再把得到优惠券的时间和其价值放到结构体里去。
		} else {
			while(head<tail&&tik[head].t<ti) {
				head++;
			}//如过当前时间队首的优惠券已经过期了，就直接弹出过期了的。
			bool ok=0;//看可不可以使用优惠券。
			for(int j=head; j<tail; j++) {//现在没过期的券
				if(!vis[j]&&tik[j].p>=pr) {//如果这张券能用
					vis[j]=1;
					ok=1;
					break;//用就完事了
				}
			}
			if(!ok) {
				ans+=pr;
			}//没有券可以用，那没事了，自己付钱0
		}
	}
	cout<<ans;
	return 0;
}/*
6
0 10 2
1 10 5
1 6 47
0 20 50
1 30 94
1 10 96
*/
           

T2：对称二叉树

这道题是CSP2019-J的T4，想想都是泪，当年眼中的黑题今日只值搜索。

• 要做这道题首先要明白什么是对称二叉树。

  

  如图：

  

  红笔部分就是这颗二叉树的最大对称树。细细一推，再根据题目给出的数据：每个节点的左子节点和右子节点，不难分析出，如果任意一个节点，只要其左子节点的右子节点等于其右子节点的左子节点&其左子节点的左子节点等于其右子节点的右子节点那么这棵树就是一颗对称二叉树…好吧，确实这非常的绕，脑子正常一点的人都不会想看，那我还是用图来解释。

  

  这样，总算明白了对称二叉树是什么了。

不难想到，用n次DFS从每个节点遍历所有子节点，满足上述条件即可。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,l[1000010],r[1000010],a[1000010],ans;
bool ok=1;
int cnt(int x){
	if(x==-1){
		return 0;
	}
	return cnt(l[x])+cnt(r[x])+1;
}
void dfs(int x,int y){
	if(y==-1&&x==-1){
		return;
	}
	if(y==-1||x==-1||a[x]!=a[y]){
		ok=0;
		return;
	}
	dfs(l[x],r[y]);
	dfs(r[x],l[y]);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d %d",&r[i],&l[i]);
	}
	for(int i=1;i<=n;i++){
		ok=1;
		dfs(l[i],r[i]);
		if(ok){
			ans=max(ans,cnt(i));
		}
		
	}
	cout<<ans;
	return 0;
}//懒就不打注释了