pta L2-002 链表去重 +散列表知识小普及+二进制取反补码运算
题目链接：https://pintia.cn/problem-sets/994805046380707840/problems/994805072641245184；
废话：今天忙着学习新知识了，没怎么顾得上做题，所以说抽出晚上两个小时做做题，白天学新知识；
不得不说的是，dijkstra+priority_queue+spfa优化真的难学，我现在还停留在思想阶段，但是已经可以理解了基本的思想；
但是，堆还没有学，真的好难理解啊
这道题还是蛮有意思的；
首先，题目是“链表去重”，但又不是完全的链表去重，（小声bb，不会真有孩子手写去重链表吧？？？好难的）
其实，这道题根据题目模拟就可以了，对，没错，又是模拟，但是
这次加入了新的模拟构成--hash,也就是哈希查找，这里简单介绍一下哈希
哈希，又称散列表，是记录的储存位置和关键字之间建立一个确定的函数关系，使得每一个关键字key都对应一个确定的值，这种对应关系称为散列函数，也叫哈希函数，
同时哈希不仅是一种储存方法，也是一种查找方法，
这种方法最适合求解查找和给定的值相等的记录
在一定程度上，个人认为哈希和数学上的映射有着相似的联系，都存在一一对应关系，遵循相同对应法则，此处请看映射定义：
设A和B是两个非空集合，如果按照某种对应关系
，对于集合A中的任何一个元素a，在集合B中都存在唯一的一个元素b与之对应，那么，这样的对应（包括集合A，B，以及集合A到集合B的对应关系f）叫做集合A到集合B的映射（Mapping），记作
。其中，b称为a在映射f下的象，记作：
; a称为b关于映射f的原象。集合A中所有元素的象的集合记作f（A）。
是吧，这样更好理解了些；
这里在普及一个知识点：for(register int i=st;~i;i=ne[i])
如何理解这个循环？
~在C语言里面是二进制取反的意思，与补码颇有相似指出，按照代码运行结果来看，这个~就是对十进制的数加“-”在减1，
也就是说~i也就可以等价于i!=-1
这种处理方式对于哈希查找是具有辅助作用的；
在来说说本题思路:
我们输入首地址，键值，下一个地址，并且存入专门的数组种，在进行哈希，如果这个数的绝对值有相等的（走过已经标记的），就放入第一个储存数组中，如果没有，就标记这个数组，再存入另一个储存数组，最后按照题目要求输出相应的数组就可以了。
Talk is cheap. Show me the code.
1 #include<bits/stdc++.h> 2 using namespace std; 3 int st,n; 4 int key[100010];//键值 5 int ne[100010];//下一个地址 6 bool vis[100010];//标记数组 7 vector<int>a,b; 8 int main() 9 { 10 scanf(%d %d,&st,&n); 11 for(register int i=0;i<n;i++) 12 { 13 int tag,keys,e; 14 scanf(%d %d %d,&tag,&keys,&e); 15 key[tag]=keys; 16 ne[tag]=e; 17 } 18 for(register int i=st;~i;i=ne[i])//等价于i!=-1 19 { 20 int flag=abs(key[i]); 21 if(vis[flag])//绝对值有相等的放在b中 22 { 23 b.push_back(i); 24 } 25 else//没有就放在a 中 26 { 27 vis[flag]=true;//标记 28 a.push_back(i); 29 } 30 } 31 for(register int i=0;i<a.size();i++) 32 { 33 printf(%05d %d ,a[i],key[a[i]]); 34 if(i==a.size()-1) 35 cout<<-1<<endl; 36 else 37 { 38 printf(%05d\n,a[i+1]); 39 } 40 41 } 42 for(register int i=0;i<b.size();i++) 43 { 44 printf(%05d %d ,b[i],key[b[i]]); 45 if(i==b.size()-1) 46 cout<<-1<<endl; 47 else 48 { 49 printf(%05d\n,b[i+1]); 50 } 51 52 } 53 return 0; 54 }