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;
}//懶就不打注釋了