HRBUST - 1688 数论中的异或 -------HPU组队选拔赛（三）

深藏阁楼爱情的钟 2022-05-26 11:25 147阅读 0赞

## [HRBUST - 1688 数论中的异或][HRBUST - 1688] ##

<table> 
 <tbody> 
  <tr> 
   <td>数论中的异或</td> 
  </tr> 
  <tr> 
   <td> 
    <table> 
     <tbody> 
      <tr> 
       <td>Time Limit: 1000 MS</td> 
       <td>Memory Limit: 32768 K</td> 
      </tr> 
     </tbody> 
    </table> 
    <table> 
     <tbody> 
      <tr> 
       <td>Total Submit: 80<span>(42 users)</span></td> 
       <td>Total Accepted: 39<span>(31 users)</span></td> 
       <td>Rating: <img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-solid.png" alt=""><img src="http://acm.hrbust.edu.cn/Public/images/star-half2.png" alt=""></td> 
       <td>Special Judge: <span>No</span></td> 
      </tr> 
     </tbody> 
    </table></td> 
  </tr> 
  <tr> 
   <td>Description</td> 
  </tr> 
  <tr> 
   <td><span style="white-space:nowrap;">给出两集合A和B, 找出最小的非负整数x使得A⊕x=B.</span><br><span style="white-space:nowrap;">假设A={a1,a2,…,an}, A⊕x={a1⊕x,a2⊕x,…,an⊕x}.⊕代表异或操作</span></td> 
  </tr> 
  <tr> 
   <td>Input</td> 
  </tr> 
  <tr> 
   <td><span style="white-space:nowrap;">输入的第一行是一个整数T，表示一共有T组测试数据；<br>对于每组测试数据，第一行是一个整数n代表集合A和B的大小<br>第二行包含n个整数a1,a2,a3,....an，代表集合A的元素。<br>第三行包含n个整数b1,b2,b3,....bn，代表集合B的元素。<br>(1&lt;=n&lt;=100000，n是奇数，0&lt;=ai&lt;2^30)<br></span><span style="white-space:nowrap;"></span></td> 
  </tr> 
  <tr> 
   <td>Output</td> 
  </tr> 
  <tr> 
   <td><span style="white-space:nowrap;">如果存在x就输出最小的x，如果不存在就输出-1。</span></td> 
  </tr> 
  <tr> 
   <td>Sample Input</td> 
  </tr> 
  <tr> 
   <td><span style="white-space:nowrap;">1</span><br><span style="white-space:nowrap;">3</span><br><span style="white-space:nowrap;">0 1 3</span><br><span style="white-space:nowrap;">1 2 3</span></td> 
  </tr> 
  <tr> 
   <td>Sample Output</td> 
  </tr> 
  <tr> 
   <td><span style="white-space:nowrap;">2</span></td> 
  </tr> 
  <tr> 
   <td>Author</td> 
  </tr> 
  <tr> 
   <td>陈禹@HRBUST</td> 
  </tr> 
 </tbody> 
</table>

这道题是队友做出来的，我还不知道他用的啥方法。。

赛后看了下解析，只要理解这个知识点，也不是很难哎

[异或——百度百科][Link 1]

**思路：**

**如果有：a\[i\]^b\[j\]=ans (0<i<n,0<j<n)**

**那么：a\[0\]^a\[1\]^a\[2\]^.....^a\[n-1\]^b\[0\]^b\[1\]^b\[2\]^......^b\[n-1\]=ans;**

**将数组a和数组b的所有元素全都异或一下之后**

**再另 a\[i\]=a\[i\]^ans;**

**排序a\[i\]和b\[i\] 看着两个集合是不是完全相同，完全相同的话，ans就是结果，否则输出-**1

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    
    const int maxn=1e5+3;
    
    int a[maxn];
    int b[maxn];
    
    int main()
    {
    	int t,n;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		int ans=0;
    		for(int i=0;i<n;i++)	
    		{
    			scanf("%d",&a[i]);
    			ans^=a[i];
    		}
    		for(int i=0;i<n;i++)	
    		{
    			scanf("%d",&b[i]);
    			ans^=b[i];
    		}
    		
    		for(int i=0;i<n;i++)	a[i]^=ans;
    		
    	
    		sort(a,a+n);
    		sort(b,b+n);
    		for(int i=0;i<n;i++)
    			if(a[i]==b[i])	continue;
    			else{ans=-1;break;}
    	
    	
    		printf("%d\n",ans);		
    	}
    	return 0;
    }

总之有时候不会的话，还是得蒙。

[HRBUST - 1688]: http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1688
[Link 1]: https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fr=aladdin#1