这个题目是我无聊的时候想出来的，话说这样的题目还是比较适合做比赛的签到题。 1118 在 1117 的基础上加强了数据（除了用异或写，其他的应该都是 TLE）。 题目的意思很简单，也就是找到一个单独的数。 在 1117 里面，数字的范围是 `[1,10000]`，这样的话，我们就可以用数组来解决这个问题。 开一个 10000 大小的数组，然后暴力跑一遍 `1~10000`，看看哪个数组是落单的。 代码： ```cpp #include <cstdio> #include <cstdlib> int num[10001],tmp; int main() { int n; //freopen("data.in","r",stdin); scanf("%d",&n); while(n--) {scanf("%d",&tmp);num[tmp]++;} for(int i = 1;i <= 10000;i++){ if(num[i]%2) {printf("%d",i);exit(0);} } } ``` 除了这种写法呢，还有一种特别好的写法就是异或运算。 这个运算一般的符号是 "⊕"，在 C/C++ 里面是 `^`（这个可不是次方，这个是异或运算）。 异或运算是一个二进制二元运算，那么异或运算算的是什么呢？ 这里先放上一张真值表： | A | B | ⊕ | |---|---|---| | F | F | F | | F | T | T | | T | F | T | | T | T | F | 也就是说，对于 0、1 两个数来说，不同得 1，相同得 0。 放到 int 的范围来说，对于： ```cpp int a,b; ``` `a^b` 的值即将 a、b 都转换成二进制的数字，他们对应位置计算出的结果即是最后的结果。 例如 `9^5 = 1001 ^ 0101 = 1100 = 12`。 而正是因为这样，对于这个题目异或有一个很好的性质，那就是： ``` 0^a=a; a^a=0; ``` 这里的 `a` 表示任何整数。 因此这样我们就有 `ans = a1 ^ a2 ^ ... ^ an`。 代码： ```cpp #include <cstdio> int main() { //freopen("data.in","r",stdin); int n,ans=0,tmp; scanf("%d",&n); while(n--) {scanf("%d",&tmp);ans=ans^tmp;} printf("%d",ans); } ``` 链接： - [hhuoj1117][1] - [hhuoj1118][2] - [Wikipedia 对异或的解释][3] [1]: http://acm.hhu.edu.cn/problem.php?id=1117 [2]: http://acm.hhu.edu.cn/problem.php?id=1118 [3]: https://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96 Loading... 这个题目是我无聊的时候想出来的，话说这样的题目还是比较适合做比赛的签到题。 1118 在 1117 的基础上加强了数据（除了用异或写，其他的应该都是 TLE）。 题目的意思很简单，也就是找到一个单独的数。 在 1117 里面，数字的范围是 `[1,10000]`，这样的话，我们就可以用数组来解决这个问题。 开一个 10000 大小的数组，然后暴力跑一遍 `1~10000`，看看哪个数组是落单的。 代码： ```cpp #include <cstdio> #include <cstdlib> int num[10001],tmp; int main() { int n; //freopen("data.in","r",stdin); scanf("%d",&n); while(n--) {scanf("%d",&tmp);num[tmp]++;} for(int i = 1;i <= 10000;i++){ if(num[i]%2) {printf("%d",i);exit(0);} } } ``` 除了这种写法呢，还有一种特别好的写法就是异或运算。 这个运算一般的符号是 "⊕"，在 C/C++ 里面是 `^`（这个可不是次方，这个是异或运算）。 异或运算是一个二进制二元运算，那么异或运算算的是什么呢？ 这里先放上一张真值表： | A | B | ⊕ | |---|---|---| | F | F | F | | F | T | T | | T | F | T | | T | T | F | 也就是说，对于 0、1 两个数来说，不同得 1，相同得 0。 放到 int 的范围来说，对于： ```cpp int a,b; ``` `a^b` 的值即将 a、b 都转换成二进制的数字，他们对应位置计算出的结果即是最后的结果。 例如 `9^5 = 1001 ^ 0101 = 1100 = 12`。 而正是因为这样，对于这个题目异或有一个很好的性质，那就是： ``` 0^a=a; a^a=0; ``` 这里的 `a` 表示任何整数。 因此这样我们就有 `ans = a1 ^ a2 ^ ... ^ an`。 代码： ```cpp #include <cstdio> int main() { //freopen("data.in","r",stdin); int n,ans=0,tmp; scanf("%d",&n); while(n--) {scanf("%d",&tmp);ans=ans^tmp;} printf("%d",ans); } ``` 链接： - [hhuoj1117][1] - [hhuoj1118][2] - [Wikipedia 对异或的解释][3] [1]: http://acm.hhu.edu.cn/problem.php?id=1117 [2]: http://acm.hhu.edu.cn/problem.php?id=1118 [3]: https://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96 Last modification：January 18, 2019 © Allow specification reprint Support Appreciate the author Like 如果觉得我的文章对你有用，请随意赞赏