题意
给出一个无相无环图(树或者是森林),给出每个节点周围节点编号个数和它周围节点的异或和,重构这棵树
思路
首先,叶子节点的异或值肯定是他的父亲节点,这样,从叶子节点开始,从底层便能逐步推导出上层的树结构,从而得到答案
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<queue> using namespace std; const int nMax = 100000; const int mMax = 100000; class edge{ public: int u,v,nex; };edge e[mMax]; int k,head[nMax]; void addedge(int a,int b){ e[k].u=a; e[k].v=b; e[k].nex=head[a]; head[a]=k;k++; } int aaa[nMax],bbb[nMax]; int vis[nMax]; queue<int>que; int main(){ int n,i,j,a,b,c; while(cin>>n){ while(!que.empty())que.pop(); memset(vis,0,sizeof(vis)); for(i=0;i<n;i++){ scanf("%d%d",&aaa[i],&bbb[i]); if(aaa[i] == 1){ que.push(i); vis[i] = 1; } } k = 0; int ans = 0; memset(head,0,sizeof(head)); while(!que.empty()){ a = que.front(); que.pop(); if(aaa[a]!=0){ addedge(a,bbb[a]); ans ++; aaa[bbb[a]]--; bbb[bbb[a]]^=a; } if(!vis[bbb[a]]){ if(aaa[bbb[a]]==1){ vis[bbb[a]] = 1; que.push(bbb[a]); } } } // cout<<ans<<" dd "<<k<<endl; cout<<ans<<endl; for(i=0;i<k;i++){ cout<<e[i].u<<" "<<e[i].v<<endl; } } return 0; }
相关推荐
Codeforces Round #723 (Div. 2).md
根据提供的文档信息,我们可以推断出这是一份由许昊然撰写的Codeforces题目的解题报告。许昊然是国际信息学奥林匹克(IOI)2012年和2013年的金牌获得者,因此他的解题报告极具参考价值。下面我们将详细解读这份报告...
Codeforces - 1107B. Digital root & 1107C. Brutality(规律 & 贪心)Codeforces - 1107B.
codeforces round 962 (div. 3)tion-ma笔记
### Codeforces Round 961 (Div. 2):深度解析与实战技巧 #### 引言 Codeforces 是一个国际知名的在线编程竞赛平台,它汇聚了来自世界各地的编程爱好者和专业人士。每一轮比赛都旨在测试参赛者的算法思维、编程...
#### 2. C++中的基本数据类型 - **整型(int)**: 包括short、int、long等。 - **浮点型(float/double)**: 表示小数。 - **字符型(char)**: 单个字符。 - **布尔型(bool)**: true或false两个值。 #### 3. 控制结构 - ...
Codeforces - 1131C. Birthday(贪心)题目链接题目给你n和n个数,要你重新排列n个数,使得这些数的相邻差值中最大的那个值最小。stat
### 2. 洛谷 (Luogu) - **特点**:国内知名的在线编程学习平台之一,拥有庞大的题库。 - **适用对象**:初学者至高手级别的程序员。 - **优势**:社区活跃度高,用户间交流频繁,便于解决疑问。 ### 3. HDUOJ (Hdu...
- **在线平台**:定期参加Codeforces、LeetCode、AtCoder等平台上的模拟赛,以适应真实的比赛节奏。 - **真题复现**:利用历年的ACM/NOI/CSP真题进行练习,模拟真实的比赛环境,特别要注意限定时间内的表现。 #####...
codeforces round 961 (div. 2)
D1. Prefix-Suffix Palindrome (Easy version) D2. Prefix-Suffix Palindrome (Hard version) 题意: ...很显然,这是一个O(n^2)时间复杂度的算法,那么还有哪里可以优化呢?其实关于求回文串palindrom
### Codeforces Round 961 (Div. 2) A题解析 #### 题目背景 Codeforces Round 961 (Div. 2) 是一场针对中级水平程序员的编程竞赛,通常会包含几个不同难度级别的题目。A题作为入门级题目,旨在测试参赛者的基础算法...
codeforces round 962 (div. 3)
#### 2. 实践操作 - **安装开发环境**:首先需要安装Java开发工具包(JDK)以及集成开发环境(IDE),如Eclipse或IntelliJ IDEA。 - **编写第一个程序**:通过编写一个简单的“Hello World”程序来熟悉开发环境。 - ...
#### 2. 离散数学的重要性 - **理论基础**:为计算机科学提供坚实的理论支撑。 - **问题解决能力**:帮助学生培养抽象思维能力和解决问题的能力。 - **应用广泛**:在算法设计、数据结构、编译原理、人工智能等多个...
全国青少年信息学奥林匹克联赛(National Olympiad in Informatics in Primary and Secondary Schools,简称NOIP)是中国计算机学会主办的一项面向全国中学生的竞赛活动。该赛事旨在通过编程技能的比拼来培养学生的...
Educational Codeforces Round 157D. XOR Construction
【标题】"Codeforces-149-D-Coloring-Brackets.zip 视觉C++实现" 本问题来源于编程竞赛网站Codeforces上的第149场竞赛中的D题——"Coloring Brackets"(括号着色)。这个问题涉及到动态规划(Dynamic Programming, ...