题库链接

https://codeforces.ml/contest/1300

A. Non-zero

一个数组,每次操作可以给某个数加1,让这个数组的积和和不为0的最小操作数
显然如果有0的话,必须操作一次,最后如果和还是为0的话,再操作一次

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,m;

int a[maxn];

signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        int sum = 0;
        int ans = 0;
        for(int i = 1; i <= n; i++) 
        {
            cin>>a[i];
            if(a[i] == 0)
            {
                ans++;
                a[i] = 1;
            }
            sum += a[i];
        }
        if(sum == 0) ans++;
        cout<<ans<<endl;
    }
    return 0;
}

B. Assigning to Classes

有一个数组有2*n个元素,要分成两个数组,每个数组必须是奇数个元素,求两个数组的中位数之差的最小值
假设左边的中位数会小于右边的中位数,显然,左边越大越好,右边越小越好,大能大到什么程度呢?最大就是原数组的中位数
所以答案就是原数组的中间两个数的差值

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,m;
 
int a[maxn];
 
signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i = 1; i <= 2*n; i++) 
        {
            cin>>a[i];
        }
        sort(a+1,a+1+2*n);
        cout<<abs(a[n]-a[n+1])<<endl;
    }
    return 0;
}

C. Anu Has a Function

\(f(x, y) = (x | y) – y\)
要求重新排列数组,使得\(f(f(\dots f(f(a_1, a_2), a_3), \dots a_{n-1}), a_n)\)最大
我们先看f函数,x或y减去y,把它拆分成二进制,对于某一位,如果x,y都是1,f(x, y)之后x的这一位会被减去
如果x是1,y是0,或者x是0,y是1,那么x的这一位不变
所以我们只需要求出某一位只有x是1,其余数组元素都是0的最高位,让它在最前面就好了,其它元素随便排列

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,m;
 
int a[maxn];
 
int vis[33];
int b[33];
 
signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    cin>>n;
    for(int i = 1; i <= n; i++) 
    {
        cin>>a[i];
        for(int j = 30; j >= 0; j--)
        {
            if((1<<j)&a[i])
            {
                vis[j]++;
                b[j] = i;
            }
        }
    }
    int ans = 1;
    for(int i = 0; i <= 30; i++)
    {
        if(vis[i] == 1) ans = b[i];
    }
    cout<<a[ans]<<' ';
    for(int i = 1; i <= n; i++) 
    {
        if(i != ans) cout<<a[i]<<' ';
    }
    return 0;
}

D. Aerodynamic

就是问你是否中心对称

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,m;

vector<pii> v;

signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    cin>>n;
    v.push_back({0,0});
    for(int i = 1,x,y; i <= n; i++) 
    {
        cin>>x>>y;
        v.push_back({x,y});
    }
    if(n%2) {puts("NO");return 0;}
    int t = n/2;
    double midx = (v[1].first + v[t+1].first)*1.0/2;
    double midy = (v[1].second + v[t+1].second)*1.0/2;
    for(int i = 2; i <= t; i++) 
    {
        double tmpx = (v[i].first + v[t+i].first)*1.0/2;
        double tmpy = (v[i].second + v[t+i].second)*1.0/2;
        if(midx != tmpx || midy != tmpy)
        {
            puts("NO");return 0;
        }
    }
    puts("YES");
    return 0;
}

E. Water Balance

有n个水桶,每次可以选择一些区间,使得区间内的水桶的水量等于区间水量之和除以区间长度
问你可以得到的水量的字典序的最小是什么
单调栈可以做,凸包也可以做,凸包我不会,说一下单调栈的做法

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
#define gcd __gcd
const int inf = 0x3f3f3f3f;
const int maxn = 1001110;
const int M = 1e9+7;
int n,m;
 
int a[maxn];
int sa[maxn];
int la[maxn];
 
signed main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("data.in", "r", stdin);
#endif
    cin>>n;
    for(int i = 1; i <= n; i++) 
    {
        cin>>a[i];
    }
    int top = 0;
    for(int i = 1; i <= n; i++) 
    {
        int tsa = a[i],tla = 1;
        for(;top && sa[top]*tla >= tsa*la[top]; top--)
        {
            tsa += sa[top];
            tla += la[top];
        }
        ++top;
        sa[top] = tsa;
        la[top] = tla;
    }
    for(int i = 1,cur = 1; i <= top; i++,cur += la[top]) 
    {
        for(int j = cur;j < cur + la[i]; j++)
        {
            printf("%.9f\n",sa[i]*1.0/la[i]);
        }
    }
    return 0;
}