首页 > 其他分享 >C. Anji's Binary Tree

C. Anji's Binary Tree

时间:2024-03-21 21:23:21浏览次数:36  
标签:node Binary right Anji Tree dat qd jd include

网站:https://codeforces.com/problemset/problem/1900/C
这里比较容易搞混的就是各个节点的关系,不要用2*n来表示左孩子!!
以及记得添加快读快写

ios::sync_with_stdio(false);
cin.tie(nullptr);

加在int main()里即可
这里还有一个priority_queue的小技巧:结构体内部定义运算符,好像和sort的cmp有不同?

#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
typedef long long ll;
using namespace std;


struct leet
{
	int left, right;
	char tar;
	leet() { left = 0; right = 0; tar = ' '; }
};
leet node[300100];
struct dat
{
	int val, times;
	dat(){}
	dat(int va, int tim) { val = va; times = tim; }
	bool operator<(const dat& dl) const
	{
		return this->times > dl.times;//※指把小的times放前面
	}
};

int main()
{
	ios::sync_with_stdio(false);//imp
	cin.tie(nullptr);//imp
	int t; cin >> t;
	for (int ii = 0; ii < t; ii++)
	{
		//queue<dat>qd;
		priority_queue<dat, vector<dat>>qd;//用优先队列让times少的先过,类似dij?(
		int n; cin >> n; cin.get();
		string s; getline(cin, s);
		for (ll i = 1; i <= n; i++)
		{
			int xx, yy; cin >> xx >> yy;
			node[i].tar = s[i - 1];
			node[i].left = xx;
			node[i].right = yy;
		}
		qd.push(dat(1, 0));//排入第一个节点
		ll mintimes = 0, jd = 1;
		bool isend = 0;
		while (!isend)//无所谓的,写一个whiletrue也是一样
		{
			dat temp = qd.top();
			qd.pop();
			mintimes = temp.times;
			jd = temp.val;
			if (node[jd].left == 0 and node[jd].right == 0)
			{
				isend = 1;
				break;
			}
			if (node[jd].tar == 'U')//如果是u那么times一定得加一,然后分别遍历左右
			{
				if (node[jd].left != 0)qd.push(dat(node[jd].left, mintimes + 1));
				if (node[jd].right != 0)qd.push(dat(node[jd].right, mintimes + 1));
			}
			else if (node[jd].tar == 'L')//本来就是左边那么遍历左节点就不用加一,遍历右节点才需要加一
			{
				if (node[jd].left != 0)qd.push(dat(node[jd].left, mintimes));
				if (node[jd].right != 0)qd.push(dat(node[jd].right, mintimes + 1));
			}
			else//同上
			{
				if (node[jd].right != 0)qd.push(dat(node[jd].right, mintimes));
				if (node[jd].left != 0)qd.push(dat(node[jd].left, mintimes + 1));
				
			}
		}
		cout << mintimes << endl;

	}
	return 0;
}

♥对了,爱你rzbb♥

标签:node,Binary,right,Anji,Tree,dat,qd,jd,include
From: https://www.cnblogs.com/zzzsacmblog/p/18088270

相关文章

  • npm 错误,ERESOLVE unable to resolve dependency tree 解决方案
    参考:https://blog.csdn.net/qq_42055933/article/details/132098617 背景:当在使用npminstall时遇到“ERESOLVEunabletoresolvedependencytree”错误时,这通常是由于项目的依赖关系发生了冲突或不兼容问题。 方案一:在命令中增加 --legacy-peer-dep 选项或者--force......
  • CF1945E Binary Search 题解
    CF1945EBinarySearch题目大意给定一个\(1\simn\)的排列\(A\)(不保证有序),对这个排列用如下代码片段二分,查找\(m\)的位置。intl=1,r=n+1;while(r-l>1){intmid=(l+r)/2;if(A[mid]<=m) l=mid;else r=mid;}cout<<l;显然不一定能查找到正确位置,所以在......
  • vue2/3 - element组件库el-tree树形控件实现一键全选/一键反选取消/全部收起/全部折叠
    效果图在vue2、vue3|element饿了么组件库中,详细使用el-tree树状组件完成功能按钮组,支持全部选中节点、反选取消节点、对所有树节点进行折叠收起、是否上下级联动等等!提供详细示例代码教程,一键复制开箱即用~~示例代码请看下方代码及技术点介绍。<template><div......
  • Tree Compass Codeforces Round 934 (Div. 2) 1944E
    Problem-E-Codeforces题目大意:有一棵n个点的树,初始状态下所有点都是白色的,每次操作可以选择一个点u和一个距离dis,使得距离点u所有长度为dis的点变为黑色,问最少需要多少次操作能使所有点变成黑色,输出所有操作1<=n<=2000思路:要想操作数最少,就要使每次操作涂黑的点的数量尽......
  • LeetCode 2265. Count Nodes Equal to Average of Subtree
    原题链接在这里:https://leetcode.com/problems/count-nodes-equal-to-average-of-subtree/description/题目:Giventhe root ofabinarytree,return thenumberofnodeswherethevalueofthenodeisequaltothe average ofthevaluesinits subtree.Note:Th......
  • 集合系列(五) -TreeMap详解
    一、摘要在集合系列的第一章,咱们了解到,Map的实现类有HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties等等。本文主要从数据结构和算法层面,探讨TreeMap的实现。二、简介JavaTreeMap实现了SortedMap接口,也就是说会按照key的大......
  • LeetCode 1161. Maximum Level Sum of a Binary Tree
    原题链接在这里:https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/description/题目:Giventhe root ofabinarytree,thelevelofitsrootis 1,thelevelofitschildrenis 2,andsoon.Returnthe smallest level x suchthatthesumofa......
  • CF1943C - Tree Compass | 树的直径 思维
    links给定一棵\(n\)个点的树,可以执行任意次以下操作:选定一个距离\(u\),并将与\(u\)距离为\(d\)的点都染色。求使得所有节点都染上颜色的最小操作次数,并输出方案。\(n\leq2000\)看着数据范围,朝着\(O(n^2)\)的dp去想,但是没有想出来。然后又尝试大胆猜测,\(d\)只......
  • git worktree学习
    转自:https://blog.csdn.net/qq_35067322/article/details/1215514691.介绍当在一个仓储下,在A分支编译时,是不能切到B分支上工作的,只能等着A编译完成,很影响效率。所以可以使用worktree命令新建一个工作分支。步骤1:在A分支上编译中,使用以下命令新建一个目录。gitworktreeadd.......
  • 数据结构之BTree、B+Tree的含义及区别
    原文链接:https://blog.csdn.net/weixin_43407520/article/details/1142404381.引言前面学习索引时,了解到MySQL索引的数据类型有B+Tree索引和哈希索引,本文将详细介绍一下BTree和B+Tree的含义和他们的区别。2.BTree2.1概念B树是一种自平衡树数据结构,它维护有序数据并允许以对数时......