[NBOJ 0023][Easy Problem]

[件名要求]
http://acm.bupt.edu.cn/onlinejudge/newoj/showProblem/show_problem.php?problem_id=23
[題目の関連している理論と計算方]ビット操作とビット演算
「問題の中で注意すべき点」とは、大きなデータの検索などの処理についてです.簡単に要求されますが、従来の考え方では問題が解決できません.時間を超えるからです.
【思考過程】最初は本当に大水の問題だと思いました.題目は本当に簡単であることが要求されます.つまり、組のデータに対してペアに合わない一つの数を探し出すことです.最初の構想はリスト容器を作ることです.そして毎回検索して、新しいデータであれば末尾に加えて、現れたデータは元のデータを削除します.このように、サイクル終了後は題名の要求するその数だけを残します.コードは次のように書きます.

#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を使わないといけません.最後に私が接触したものの中では、基本的にうまく処理できないと思います.この時ネットで調べてみたら、元の位置の違いや演算で解決できます.強い考えです.私は前にはどうしても思いつかなかったです.異種演算は次のような重要な性質があります.

a^a=0

a^0=a

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;
}

【終わりに】正しい方法を選ぶと、急に簡単になりました.今日はこの問題は簡単ですが、私の考えに大きな啓発があります.問題の処理を考えると、慣性の枠から飛び出してみることができます.急に明るくなります.