[NBOJ0023][Easy Problem]

小灰灰 2022-01-14 11:03 197阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

**\[题目要求\]**

[http://acm.bupt.edu.cn/onlinejudge/newoj/showProblem/show\_problem.php?problem\_id=23][http_acm.bupt.edu.cn_onlinejudge_newoj_showProblem_show_problem.php_problem_id_23]

**\[题目涉及的相关理论与算法\]**  
位操作与位运算

**\[题目中需要注意的地方\]**  
就是对于大数据查找等处理，虽然要求很简单，但是常规的思路解决不了问题。。。因为会超出时间。

**\[思路过程\]**  
一开始以为真是大水题了。。题目要求真的很简单，就是对一组数据找出配不成对的一个数，我一开始的思路就是建立一个list容器，然后每次查找，只要是新数据就加到尾部，是出现过的数据就删除掉原来的数据。这样，在循环结束后只剩下题目要求的那个数。代码写出来如下：

#include<iostream>
    #include<list>
    #include<algorithm>
    using namespace std;
    void casesolve(int n)
    {
    	list<long long> table;
    	int numLoop = 2*n-1;
    	long long num;
    
    	while((numLoop--) != 0)
    	{
    		cin>>num;
    		list<long long>::iterator key;
    		key = find(table.begin(),table.end(),num);//find方法。
    		if( key != table.end())  //这里就是核心部分，如果老数据，则返回的迭代器就不是末尾。
    		{
    			table.erase(key);
    		}
    		else table.push_back(num);//新数据则加入到列表尾部。
    	}
    	cout<<table.front()<<endl;//最后只剩下要求的数据。
    }
    
    int main()
    {
    	//freopen("in.txt", "r", stdin);
    	//freopen("out.txt", "w", stdout);
    	int n;
    	cin>>n;
    	while(n != 0)
    	{
    		casesolve(n);
    		cin>>n;
    	}
    	//fclose(stdin);
    	//fclose(stdout);
            return 0;
    }

然后上面的代码提交之后，就是LTE。。我设想可能是find方法效率低？就打算用数组写一个，自己写查找函数，但是还是觉得基本上效率也不会差太多，也可能是erase的操作问题，但是按照我的算法，如果不使用erase不行。  
最后觉得在我接触的东西中，基本上没有好办法处理了。。这时去网上查了一下，然后发现原来，是可以用位的异或运算解决的！ 好强大的想法，我之前是无论如何不能想到的，异或运算有如下的重要性质：

1.  a ^ a = 0
2.  a ^ 0 = a
3.  a ^ b ^ c = a ^ ( b ^ c )

这三条性质正好可以解决此题，设想输入数据后，所有成对的数据都会和自己异或掉，变成零，然后剩下的数据与0异或还是自己。所以将每次的结果异或后，最后剩下的就是没有成对的数！  
代码如下：

**\[代码\]**

#include<iostream>
    using namespace std;
    void casesolve(int n)
    {
    	long long result=0,temp=0;
    	int numLoop = 2*n-1;
    	while((numLoop--)!=0)
    	{
    		cin>>temp;
    		result = result ^ temp; //这就是核心的部分，真是非常的巧妙！
    	}
    	cout<<result<<endl;
    }
    int main()
    {
    	int n;
    	cin>>n;
    	while(n != 0)
    	{
    		casesolve(n);
    		cin>>n;
    	}
    	return 0;
    }

**\[尾声\]**  
选对了方法之后，就会觉得一下子变得很简单了，今天虽然这道题很简单，但是对我的思路有了很大的启发。考虑问题的处理上，很多时候可以尝试跳出惯性的框框，会一下子豁然开朗！

转载于:https://my.oschina.net/o0Kira0o/blog/82873

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/5c201e5963114e21b84a8b031dcc7015.png
[http_acm.bupt.edu.cn_onlinejudge_newoj_showProblem_show_problem.php_problem_id_23]: http://acm.bupt.edu.cn/onlinejudge/newoj/showProblem/show_problem.php?problem_id=23