题意
给出一个无相无环图(树或者是森林),给出每个节点周围节点编号个数和它周围节点的异或和,重构这棵树
思路
首先,叶子节点的异或值肯定是他的父亲节点,这样,从叶子节点开始,从底层便能逐步推导出上层的树结构,从而得到答案
#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 - 1107B. Digital root & 1107C. Brutality(规律 & 贪心)Codeforces - 1107B.
Codeforces - 1131C. Birthday(贪心)题目链接题目给你n和n个数,要你重新排列n个数,使得这些数的相邻差值中最大的那个值最小。stat
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
D1. Prefix-Suffix Palindrome (Easy version) D2. Prefix-Suffix Palindrome (Hard version) 题意: ...很显然,这是一个O(n^2)时间复杂度的算法,那么还有哪里可以优化呢?其实关于求回文串palindrom
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
Educational Codeforces Round 157D. XOR Construction
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
传送门 题意: 给一颗n个结点的数,然后n-1条边,我们要做的...如果不是一条链,那肯定有个结点的度大于等于3,把这个结点周围的三条边分别给值0,1,2,这样所有MEX(u,v)最大值为2,因为不可能有一条边同时经过0,1,2这三
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
Codeforces 149 D-Coloring Brackets,动态规划求解
题解:6nlogn,先sort三个数组a,b,c, 六次枚举二分查找,再每次min找最小值,例如:先固定数组a,再在数组b,c中利用lower_bound找到第一个大于等于a[i]的数, #pragma GCC optimize(2) #include #define ll long long...
a2oj-codeforces-div2c-ladder-solutions 我的A2online梯子裁判解决方案div2c codeforces
Codeforces部门2,A # And a2oj Ladder 4 some problems Ladder URL:http://a2oj.com/Ladder.jsp?ID=4难度等级:2问题提示: 1- 4A. Watermelon: http://codeforces.com/problemset/problem/4/A 2- 71A. Way Too ...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
接受串子-接受字符串相等-接受Codeforces回合#684(Div.2) 2/6 1440A-购买琴弦-接受1440B -中位数的总和-已接受1440C1-二进制表(简易版)-已接受1440C2-二进制表(硬版)-已接受 Codeforces回合#683(分区2) 1/...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
D1. Prefix-Suffix Palindrome (Easy version) D2. Prefix-Suffix Palindrome (Hard version) 题意: ...很显然,这是一个O(n^2)时间复杂度的算法,那么还有哪里可以优化呢?其实关于求回文串palindrom
C. Ehab and Path-etic MEXs 题意 给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。...