题意:
给你一个数组,从这个数组可以得到一个三元组组成的新数组,
新数组可以任意交换三元组里元素的位置(例如(1,4,2)变成(4,1,2,)),也可以任意交换三元组在数组中的位置。
求原数组。(原数组是1~n的排列)
思路:
例如:1,4,2,3,5就产生(1,4,2),(4,2,3),(2,3,5)
思路:
比赛的时候发现第一个数和最后一个数肯定只出现过一次,第二个数字和倒数第二个数字只出现过两次,其他数字均出现过三次。
但是不会模啊啊啊啊啊啊。
乱七八糟摸了一百多行害WA叻。
又发现好玩的东西:
find()
begin(),end()find(start,end,value)
start搜寻的起点,end搜寻的终点,要寻找的value值,查找元素需要是基本元素类型,失败返回end。容器表示:find(a.begin(),a.end(),value)返回迭代器 (set,map,multiset,multimap,vector等)
数组表示:find(a,a+length,val)返回指针
C++11引入了 begin 和 end 的函数,这两个函数与容器中的两个同名成员功能类似,不过这两个函数不是成员函数,而是含有参数的函数。 用法说明: begin 返回首元素的地址,end 返回尾元素的下一个地址。 例如:begin( v )
AC代码:
int main() { fast; int n;cin>>n; vector<vi> ady(n, vi()); vi cnt(n, 0); forn(i,0,n-2) { int a,b,c;cin>>a>>b>>c; a--;b--;c--; cnt[a]++; cnt[b]++; cnt[c]++; ady[a].push_back(b); ady[a].push_back(c); ady[b].push_back(c); ady[b].push_back(a); ady[c].push_back(a); ady[c].push_back(b); } int x,y,z; x = find(all(cnt), 1) - begin(cnt); y = cnt[ady[x][0]] == 2 ? ady[x][0] : ady[x][1]; vi ans(n); vector<bool> used(n); used[x] = true; ans.push_back(x+1); used[y] = true; ans.push_back(y+1); forn(i,0,n-2) { for(int k : ady[x]) if(!used[k]) z = k; used[z] = true; ans.push_back(z+1); x = y; y = z; } cout<<ans; return 0; }