C. 田忌赛马

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int tian[10010],king[10010];
int n;
bool cmp(int a,int b)
{
return a>b;
}
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>tian[i];
}
for(int i=1; i<=n; i++)
{
cin>>king[i];
}
sort(tian+1,tian+1+n,cmp);
sort(king+1,king+1+n,cmp);
int ans=0;
int i=1,j=1;
int ii=n,jj=n;
//i指向田忌最大的马 ii指向最小的马
//j指向国王最大的马 jj指向最小的马
while(i<=ii)//若i>ii，说明已经比完了
{
if(tian[i]>king[j])
{
ans+=200;
i++;
j++;
}
else if(tian[i]<king[j])
{
ans-=200;
j++;
ii--;
}
else
{
if(tian[ii]>king[jj])
{
ans+=200;
ii--;
jj--;
}
else
{
if(tian[ii]<king[j])
ans-=200;
ii--;
j++;
}
}
}
cout<<ans;
return 0;
}
/*
思路：
首先需要排序，可以使用sort快排；
将田忌最大的马与国王最大的马进行比较，有三种情况：
①如果田忌最大的马大于国王最大的马，那么就胜场++；
②如果田忌最大的马小于国王最大的马，那么就一定会输，所以用田忌最小的马输给国王最大的马；
③如果田忌最大的马等于国王最大的马，那么就比较最小的马：
a.如果田忌最小的马大于国王最小的马，那么胜场++；
b.如果田忌最小的马小于等于国王最小的马，那么就用田忌最小的马对国王最大的马，比较大小判断是输还是平局；
*/

D. 找筷子（感谢田泽恩同学提供题解）

#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,ans=0,a;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a);
ans^=a;
}
printf("%d",ans);
return 0;
}
/*题解：
这道题如果一一匹配，时间复杂度会极高，不可能通过。
要解决这个问题，我们需要学习一种新的位运算——异或 ^（xor）
XOR:
异或的运算法则可以说是不带进位的二进制加法，
两数二进制表示后，若两数某位不同，（二进制下）结果该位为1，否则为0。
eg. 12^8:
1 0 1 0
1 0 0 0
^ _______
0 0 1 0

XOR有四个特点：
1、a^a=0
2、a^0=a
3、a^(b^c)=(a^b)^c
4、a^b=b^a
根据这三点，我们会发现：
如果将所有筷子长度^起来，会发现能配对的筷子都抵消了，剩下的就是答案。
算法时间复杂度为O(n)，空间复杂度压缩后只有O(1)。
*/