codeforces 1300 题解
A. Non-zero
你可以对数组中任何一个元素进行操作，目的让他们的加和和乘积都不为 (0) 。想想什么时候加和和乘积为 (0)。
- 若数组中有至少一个 (0) ，则数组乘积为 (0)
- 若数组中正负加和互为相反数，则数组加和为 (0) ，否则不为 (0)
则若想让数组乘积不为 (0) ，则首先需要杀灭数组中所有的 (0)，这是肯定必要且不可少的操作。完成以后检验数组加和是否为 (0)，若为 (0) 则用一个操作将数组中随便一个数进行 (+1) 操作，打破平衡即可。
时间复杂度 (O(n))
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define _for(i,a,b) for(int i = (a);i < b;i ++)
#define _rep(i,a,b) for(int i = (a);i > b;i --)
#define INF 0x3f3f3f3f
#define ZHUO 11100000007
#define MOD 1000000007
#define MIKUNUM 39
#define pb push_back
#define debug() printf("Miku Check OK!
")
#define maxn 10039
#define maxe 100039
#define X first
#define Y second
int main()
{
ios::sync_with_stdio(false);
int t, n;
cin >> t;
while(t--)
{
cin >> n;
int sum = 0, pro = 1;
int zocnt = 0;
_for(i,0,n)
{
int tmp;
cin >> tmp;
sum += tmp;
if(!tmp)
zocnt ++;
}
sum += zocnt;
if(!sum)
zocnt ++;
printf("%d
",zocnt);
}
return 0;
}
B. Assigning to Classes
我们将原问题转化一下，他要两个数组的中位数绝对值最小，但是这两个数组都是从原数组分出去的，因此转化一下问题就是在原数组中找两个数作为两个数组的中位数，让他们的绝对值最小，也就是在原数组中找两个可以成为分出去后的中位数的绝对值最小。
绝对值怎么最小?自然是排序后越靠近越小！那怎么选才算是合法的呢？（可以让选中的两数成为两数组中位数）
对于原数组 (a_1,a_2,a_3...a_{2n-1},a_{2n}) ，我们将其从小到大排序为 (b_1,b_2,b_3...b_{2n-1},b_{2n}) 。若选择一个元素下标为 (iin[1,n]) 则可证明只有选择元素下标为 (i==n+1) 的元素，这样两个元素才能成为两数组中位数。同理，若选择一个元素下标为 (iin[n+1,2n]) 则可证明只有选择元素下标为 (i==n) 的元素，这样两个元素才能成为两数组中位数。
现在再考虑选哪两个。选 (i==1) 和 (i==n+1) ？还是说别的什么？既然 (i==n) 和 (i==n+1) 必选其一，那就只剩下 ({n-1,n}) ({n,n+1}) ({n+1,n+2}) 这三种可能了，因为要绝对值最小嘛！细细一想第一种和第三种也不符合刚刚我们说的合法性规则，所以答案只可能是 ({n, n+1}) 。
时间复杂度 (O(nlogn))
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define _for(i,a,b) for(int i = (a);i < b;i ++)
#define _rep(i,a,b) for(int i = (a);i > b;i --)
#define INF 0x3f3f3f3f
#define ZHUO 11100000007
#define MOD 1000000007
#define MIKUNUM 39
#define pb push_back
#define debug() printf("Miku Check OK!
")
#define maxn 200039
#define X first
#define Y second
int a[maxn];
int main()
{
ios::sync_with_stdio(false);
int t, n;
cin >> t;
while(t--)
{
cin >> n;
n*=2;
_for(i,0,n)
cin >> a[i];
sort(a,a+n);
printf("%d
",abs(a[n/2]-a[n/2-1]));
}
return 0;
}
C. Anu Has a Function
这个函数啊
事前不知道又推不出来就比较难受了。不过知道以后就蛮好做的，原式可以写成 (a_1 & (sim a_2) & dots (sim a_n)) ，因为与操作满足交换律，所以其实就是确定第一个元素是哪个就行了。预处理出前后缀，然后枚举 (a_1) 即可。
时间复杂度 (O(n))
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define _for(i,a,b) for(int i = (a);i < b;i ++)
#define _rep(i,a,b) for(int i = (a);i > b;i --)
#define INF 0x3f3f3f3f
#define ZHUO 11100000007
#define MOD 1000000007
#define MIKUNUM 39
#define pb push_back
#define debug() printf("Miku Check OK!
")
#define maxn 200039
#define X first
#define Y second
int a[maxn];
int prefix[maxn];
int suffix[maxn];
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
_for(i,1,n+1)
cin >> a[i];
prefix[1] = ~a[1];
_for(i,2,n+1)
prefix[i] = prefix[i-1]&~a[i];
suffix[n] = ~a[n];
_rep(i,n-1,0)
suffix[i] = suffix[i+1]&~a[i];
int firele = 1;
int ans = 0;
_for(i,1,n+1)
{
int tmpans = a[i];
if(i>1)
tmpans &= prefix[i-1];
if(i<n)
tmpans &= suffix[i+1];
if(tmpans>ans)
{
firele = i;
ans = tmpans;
}
}
printf("%d ",a[firele]);
_for(i,1,n+1)
if(i!=firele)
printf("%d ",a[i]);
return 0;
}
D. Aerodynamic && E. Water Balance
计算几何，交给队友了。