Codeforces Round 618 (Div. 2)

https://codeforces.com/contest/1300

A. Non-zero

要求和，积都不为0，则先把全部0操作一次，然后再check 和是否为0，是的话再对任意数操作一次即可。

#include <bits/stdc++.h>

using namespace std;
const int N = 105;
int n, x, s, ans;

void solve () {
    s = ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x, s += x;
        if (x == 0)  ans++, s++;
    }
    if (s == 0)     ans++;
    cout << ans << endl;
}

int main () {
    int t;
    cin >> t;
    while (t--)     solve ();
}

//不能有0

B. Assigning to Classes

排序后 \(a_{n+1}-a_n\) 即为答案

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int n, a[N];

void solve () {
    cin >> n;
    //n *= 2;
    for (int i = 1; i <= n * 2; i++)    cin >> a[i];
    sort (a + 1, a + n * 2 + 1);
    cout << a[n+1] - a[n] << endl;
}

int main () {
    int t;
    cin >> t;
    while (t--)     solve ();
}

C. Anu Has a Function

按位考虑，将 \(x,y\) 该位上所有数字的可能组合列出来可以发现：

只有 \(x=1,y=0\) 时最终答案才为1。
而上述操作，即 \(1|0-0\) 的最终结果是1，等价于把一个 \(1\) 和一个\(0\) 合并成了一个 \(1\)，即消耗了一个0。所以形如 \(10000\) 的操作，最终结果是1。而如果有一个以上 \(1\)，如 \(1100000\)，到倒数第二步一定会剩下两个 \(1\)，再合并就会变为 \(0\)。
因此 \(n\) 个数中，该位为 \(1\) 的数只能有一个（才能使得最终结果为 \(1\)）

故从高位往低位判断，如果找到一个符合上述条件的数就把那个 \(1\) 放在第一位，而剩下的数随便排就行了。

证明为什么只用管第一个数：

如上图，假设我们找到了箭头所指位为答案，考虑下一位：

1. 第一个数的下一位为 \(0\)，那么该位答案一定为0，不论后面安排；
2. 第一个数下一位为 \(1\)，且其它数的下一位都为 \(0\)，则该位为 \(1\)，最大；
3. 第一位数的下一位为 \(1\)，且其它数的下一位也有 \(1\)，则该位为 \(0\)；
   可见后面数的安排是无法对原有答案造成影响的，所以只排第一个数即可。

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int n, a[N], b[N];

void solve () {
    int f1 = 1;
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    for (int j = 30; j >= 0; j--) {
        int cnt = 0; //当前位为1的数量
        for (int i = 1; i <= n; i++) {
            if (a[i] >> j & 1) {
                f1 = i, cnt++;
            }
            if (cnt > 1)    break;
        }
        if (cnt == 1)    break;
    }
    cout << a[f1] << ' ';
    for (int i = 1; i <= n; i++)    if (i != f1)    cout << a[i] << ' ';
    cout << endl;
}

int main () {
    solve ();
    //cout << log2 (1e9);
}

//1的个数=1且0的个数>0, 当前位才是1,否则都是0
//然后把最高位的1放在前面就行

D. Aerodynamic

观察几个样例可以发现，其实这题就是要找两边对应平行且相等的图形，即中心对称图形。即对应点的中点都在同一点上。
注意输入已经排好序了，直接将 \(i\) 与 \(\frac n2 + i\) 对应起来就行

#include <bits/stdc++.h>
#define db double
#define x first
#define y second

using namespace std;
typedef pair<db, db> pii;
const int N = 2e5 + 5;
int n;
pii p[N];

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> p[i].x >> p[i].y;
    if (n & 1)  cout << "NO\n";
    else {
        //判断中点是否相等
        n /= 2;
        db xx = (p[1].x + p[n+1].x) / 2, yy = (p[1].y + p[n+1].y) / 2;
        for (int i = 2; i <= n; i++) {
            db px = (p[i].x + p[n+i].x) / 2, py = (p[i].y + p[n+i].y) / 2;
            if (px != xx || py != yy) {
                cout << "NO\n";
                return ;
            }
        }
        cout << "YES\n";
    }
}

int main () {
    solve ();
}

//必须为偶数,且对边相等并平行
//中心对称图形

E. Water Balance

#include <bits/stdc++.h>
#define ll long long

using namespace std;
typedef pair<ll, ll> pii;
int n;
vector<pii> v; //单调栈{sum, len}

int main () {
    scanf ("%d", &n);
    while (n--) {
        ll x;
        scanf ("%lld", &x);
        pii pi = {x, 1ll};
        while (v.size () && v[v.size ()-1].first * pi.second >= v[v.size ()-1].second * pi.first) {
            pi.first += v[v.size ()-1].first, pi.second += v[v.size ()-1].second;
            v.pop_back ();
        }
        v.push_back (pi);
    }
    for (auto pi : v) {
        ll sum = pi.first, len = pi.second;
        //cout << sum << ' ' << len << endl;
        double aver = 1.0 * sum / len;
        while (len--)   printf ("%.11f\n", aver);
    }
}