前言
21世纪的长城真让人无可奈何。
前两个题很水，第三题略微有点麻烦。
题目 A - Non-zero
链接： Non-zero
题意：
给定n个数字，每次可以将其中任意一个数字的值加1，要求最后所有数的总和与乘积均不为零，最少需要操作多少次。
输入格式
每个测试包含多个测试用例。
第一行包含测试用例的数量 t ( 1 ≤ t ≤ 103 ) 测试用例的说明如下。
每个测试用例的第一行包含一个整数n ( 1 ≤ n ≤ 100 ） — 数组的大小。
每个测试用例的第二行包含n个整数a1、a2、…、an ( −100 ≤ ai ≤ 100 ） — 数组的元素。
输出格式
对于每个测试用例，输出使数组中所有元素的总和和乘积与零不同所需的最小步骤数。
数据范围
1 ≤ t ≤ 103
1 ≤ n ≤ 100
−100 ≤ ai ≤ 100
输入样例：
4
3
2 -1 -1
4
-1 0 0 1
2
-1 2
3
0 -2 1输出样例：
1
2
0
2思路：
- 思维 。共有两个条件，总和不能为零且乘积不能为零。
- 乘积不为零最容易实现，只要读入0就让它的值加1即可。定义
sum为所有元素的总和，最后单独判断一下sum是否为零，如果为零，就让操作次数加1。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef long long ll;
int a[N];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,cnt=0,sum=0;
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>a[i];
if(a[i]==0)
{
cnt++;
a[i]=1;
}
sum+=a[i];
}
if(sum==0)cnt++;
cout<<cnt<<endl;
}
system("pause");
return 0;
}题目 B - Assigning to Classes
题目：Assigning to Classes
题意：
给定一个奇数n，然后输入2n个数，每个数代表一个学生的技能水平。将2n个学生分到两个组中，两组学生人数可以不同，每组的技能水平用该组的技能水平中位数来表示。求两组学生技能水平的最小可能绝对差。
输入格式：
每个测试包含多个测试用例。第一行包含测试用例的数量t (1 ≤ t ≤ 104)。测试用例的说明如下。
每个测试用例的第一行包含一个整数n (1 ≤ n ≤ 105） — 学生人数减半。
每个测试包含多个测试用例。第一行包含测试用例的数量t (1 ≤ t≤104).测试用例的说明如下。
每个测试用例的第一行包含一个整数n (1 ≤ n ≤ 105 ） — 学生人数减半。
每个测试用例的第二行包含2n个整数a1、a2、…、a2n (1 <= ai <= 109） — 学生的技能水平。
保证n在所有测试用例中不超过105 。
输出格式
对于每个测试用例，输出一个整数，即两组奇数大小的技能水平之间的最小可能绝对差。
数据范围
1 ≤ t ≤ 104
1 ≤ n ≤ 105
1 <= ai <= 109
输入样例：
3
1
1 1
3
6 5 4 1 2 3
5
13 4 20 13 2 5 8 3 17 16输出样例：
0
1
5思路：
- 思维 。先将2n个学生的技能水平按升序排序。假设所分两组学生的中位数，在有序数列中的位置分别为x1和x2，且x1在x2前面。那么如果x2后面有t位学生，x2前面就至少有t+1个学生。此时x1可以是[1, t+1]中任意一个学生，因为这是个升序数列，所以越靠近x2，两组学生的技能水平差值越小，x1取t+1。此时x1和x2的取值分别是n/2，n/2+1。
- 如果x2不取n/2+1，是否能找到其它合理的位置？。我们依旧假设x2后面有t位学生，前面可以有t+3名学生，t位学生与x2一组，两位与x1一组。此时我们会发现差值最小的情况就是x1这一组紧贴着x2时。而此时x2也可以与x1组中水平最高的学生交换位置，使得两组的水平之差更小。
- 综上，x1和x2的取值一定是n/2，n/2+1。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef long long ll;
int a[N];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
n*=2;
for(int i=1;i<=n;++i)cin>>a[i];
sort(a+1,a+n+1);
cout<<a[n/2+1]-a[n/2]<<endl;
}
system("pause");
return 0;
}题目 C - Anu Has a Function
题目：Anu Has a Function
题意：
定义 f(x,y)=(x|y) - y ，n个数的序列为： f(f(…f(f(a1,a2),a3),…an−1),an) 。给我们n个数，如何排列可以使得最后的结果最大。
输入格式
第一行包含单个整数 n ( 1 ≤ n ≤ 105 )。
第二行包含n个整数a1， a2，…， an (0 ≤ ai ≤ 109 ) 数组的元素不保证不同。
输出格式
输出n个整数，以最大值对数组进行重新排序。如果有多个答案，请打印任何答案。
数据范围
1 ≤ n ≤ 105
0 ≤ ai ≤ 109
输入样例：
4
4 0 11 6输出样例：
11 0 4 6思路：
- f(11,4)=11|4 - 4。观察这个式子我们会发现
f(x,y)的本质是：从x中减去x和y相同的位。那么我们只需要确定第一个数字，剩下的数字可以任意排列。为什么？因为我们无论怎么排后面的数，本质上仍然是将[ a2, an ]依次与a1进行f(x,y)的运算。 - 如何确定第一个数字？首先我们要排除一个误区，第一个数字未必是数列中最大的数字，例如
8 8 4 1，将两个8放在前面，最后的结果是0。而如果是4 1 8 8，那么结果是5。由于所有的数字均满足小于109，最多只有32位，所以我们可以遍历每个数字的所有位数，记录每一位上有多少数字该位为1，我们只要找到 所有位数中只有1个数字为1的最高位 所代表的那个数字即可。 - ps：
bitset<int>b[40]前32位就是ai的前32位。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int a[N];
int w[40],t[40];//w[i]表示第i位有多少数字 t[i]表示第i为1的任意一个数字在原数列中的下标
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
//记录每一位有多少数字
for(int i=1;i<=n;++i)
{
bitset<32>b=a[i];
for(int j=0;j<32;++j)
{
if(b[j])
{
w[j]++;
t[j]=i;
}
}
}
//找到只有一个数字为1的最高位
for(int i=31;i>=0;--i)
{
if(w[i]==1)
{
swap(a[1],a[t[i]]);
break;
}
}
for(int i=1;i<=n;++i)cout<<a[i]<<" ";
system("pause");
return 0;
}
