淘汰赛

没有复杂的pair版

#include<bits/stdc++.h>
using namespace std;
int n,a[200],xx[200],z=1;//用xx[i]记录谁赢了第i队
int arcaea(int l,int r,int c)
{
	if(c==0)//初始化树的最底层 c==0时l-r区间内只有一队
	{
		xx[l]=l;
		return a[l];
	}
	int mid=(l+r)/2;
	int lans=arcaea(l,mid,c-1);
	int rans=arcaea(mid+1,r,c-1);
	if(c==n)
		if(lans<rans)
			return xx[l];
		else
			return xx[r];
	if(lans<rans)
	{
		xx[l]=xx[r];
		return rans;
	}
	else
	{
		xx[r]=xx[l];
		return lans;
	}
}
int main()
{
	cin>>n;
	int aa=n;
	while(aa--)
		z*=2;//z 总共队数
	for(int i=1;i<=z;i++)
		cin>>a[i];
	cout<<arcaea(1,z,n);
	return 0;
}

淘汰赛

#include<bits/stdc++.h>
using namespace std;
const int MAXN = (1<<7);
int n,len;//len==2^n
int a[MAXN+5];
//返回 l 开始的，2^level 个人比赛的前两名的编号 
pair<int,int> f(int l,int level)
{
	//如果当前比赛只有一个人，返回这个人的编号 
	if(level==0)
		return make_pair(l,0);//第一名是 l，第二名没有 
	//先把左右两个分赛进行完 
	int nxtLen = (1<<(level-1));//分赛人数 
	pair<int,int> left = f(l,level-1); // 左边分赛结果 
	pair<int,int> right = f(l+nxtLen,level-1); //右边分赛的结果
	//用两边分赛的第一名，进行比赛 
	pair<int,int> now = make_pair(left.first,right.first);
	if(a[now.second]>a[now.first])
		swap(now.first,now.second);
	//返回比赛结果 
	return now;
}
int main()
{
	cin>>n;
	len=(1<<n);
	for(int i=1;i<=len;i++)
		cin>>a[i];
	pair<int,int> final = f(1,n);
	cout<<final.second;
	return 0;
}

对称二叉树

#include <bits/stdc++.h>
using namespace std;
int n;
int v[1000001];
int l[1000001];
int r[1000001];
int cnt[1000001];
// 计算x这棵树的所有子树的大小，并返回这棵树的大小
int dfs(int x)
{
    // 边界
    if (l[x] == -1 && r[x] == -1)
    {
        cnt[x] = 1;
        return cnt[x];
    }
    // 递归
    cnt[x] = 1;
    if (l[x] != -1)
    {
        cnt[x] += dfs(l[x]);
    }
    if (r[x] != -1)
    {
        cnt[x] += dfs(r[x]);
    }
    return cnt[x];
}

bool check(int p, int q)
{
    if (p == -1 && q == -1)
        return true;
    if (p != -1 && q != -1 && v[p] == v[q])
    {
        bool b1 = check(l[p], r[q]);
        bool b2 = check(r[p], l[q]);
        return b1 && b2;
    }
    return false;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> l[i] >> r[i];
    }
    // 计算每个子树的大小
    dfs(1);
    int ans = 0;
    // 检验每一个子树
    for (int i = 1; i <= n; i++)
        // 如果是一个对称二叉树
        if (check(l[i], r[i]) == true)
            //  如果比最大的更大
            if (cnt[i] > ans)
                // 最大的设置为这个
                ans = cnt[i];
    // 输出 最大的大小
    cout << ans << endl;
    return 0;
}

图的遍历

60分

#include<bits/stdc++.h>
using namespace std; 
//邻接矩阵-有向无权图 
int n,m; 
bool g[1005][1005]; 
int vis[1005]; 
int dfs(int x,int u){
	int maxX=x;
	//枚举所有点 
	for(int i=1;i<=n;i++){
		//如果能走到并且没走过 
		if(g[x][i]&&vis[i]!=u){
			//走一下 
			vis[i]=u;
			maxX=max(maxX,dfs(i,u));  
		}
	}
	return maxX;	 
}
int main(){
	cin>>n>>m;
	memset(g,false,sizeof(g)); 
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		g[u][v]=true;
	} 
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		cout<<dfs(i,i)<<" ";
	}
	return 0;
}

满分

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> e[100005];
int A[100005];
void dfs(int u, int d)
{
    if (A[u] != -1)
        return;
    A[u] = max(d, A[u]);
    //枚举u能连接到的点
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        dfs(v, d);
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        e[i].clear();
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[v].push_back(u);
    }
    memset(A, -1, sizeof(A));
    for (int i = n; i >= 1; i--)
        dfs(i, i);
    for (int i = 1; i <= n; i++)
        cout << A[i] << " ";
    return 0;
}