Codeforces Round #618 (Div. 2)

C. Anu Has a Function

题意：定义一种函数为：f:f(x, y) = (x|y) - y

给定一个数组[a1,a2,…,an]，将其定义为f(f(…f(f(a1,a2),a3),…an−1),an)，改变数组元素的位置顺序，使得f(f(…f(f(a1,a2),a3),…an−1),an)的值最大。

分析：

按位分析可以发现：

也就是说：(x|y) - y = x & (-y)

那么f(f(…f(f(a1,a2),a3),…an−1),an) = a1 & (-a2) & (-a3) & ...... & (-an)

从上面式子可以看出答案只与a1有关，与后面(-a2)....(-an)无关

a1的选择即将所有数的二进制从最高位开始扫描，找到一个数在这个位为1，其他数在这个位均为0，这个数就是a1的选择。

///C
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100005];
int cnt[35];
int main(){
    int n;
    scanf("%d\n", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        for(int j = 0; j <= 30; j++){
            if(a[i] & (1 << j))
                cnt[j]++;
        }
    }
    int ans = -1, sum = 0;
    for(int i = 1; i <= n; i++){
        int tans = 0;
        for(int j = 0; j <= 30; j++){
            if(a[i] & (1 << j))
                if(cnt[j] == 1)
                   tans += 1 << j;
        }
        if(tans > ans){
            ans = tans;
            sum = i;
        }
    }
    printf("%d ", a[sum]);
    for(int i = 1; i <= n; i++){
        if(i != sum)
            printf("%d ", a[i]);
    }
    return 0;
}

D. Aerodynamic

题意：将给定的图形P通过平移（平移所得的图形必须包含原点），最后能达到的轮廓即为T，如果T和P相似，则输出YES，否则输出NO。

分析：画图可以知道T必定为中心对称图形，那么问题就转化为p是否为中心对称图形。

关于判断中心对称的思想：

首先，只有偶数个结点才可能成为中心对称图形，其次：

所有节点的x之和 / 有多少对节点 = 一对对应坐标的x之和

///D
#include <cstdio>
#include <map>
using namespace std;
typedef long long ll;
map<pair<int, int>, int>mp;
const int N = 3e5 + 7;
ll x[N], y[N];
int main(){
    int n;
    scanf("%d", &n);
    ll sum1 = 0, sum2 = 0;
    if(n % 2 == 1){
        printf("NO\n");
        return 0;
    }
    for(int i = 1; i <= n; i++){
        scanf("%lld%lld", &x[i], &y[i]);
        sum1 += x[i];
        sum2 += y[i];
        mp[make_pair(x[i], y[i])] = 1;
    }
    for(int i = 1; i <= n; i++){
        if(mp[make_pair(sum1 / (n / 2) - x[i], sum2 / (n / 2) - y[i])] == 0){
            printf("NO\n");
            return 0;
        }
    }
    printf("YES\n");
    return 0;
}

E.Water Balance

题意：给你一个数组，你可以选定一个区间，使得区间内的每个元素变成该区间元素的平均值，可以多次选定区间，让最终得到的数组的字典序最小。

分析：思考一下可以知道，当后一个数比前一个数小的时候，将其合并，所得结果能使得前一个数减小。

所谓字典序小，就是要让越前面的数尽可能的越小。

///E
#include <cstdio>
const int N = 1e6 + 5;
double a[N];
double b[N], l[N];
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lf", &a[i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        b[++ans] = a[i];
        l[ans] = 1;
        while(ans > 1 && b[ans] < b[ans - 1]){
            b[ans - 1] = (b[ans - 1] * l[ans - 1] + b[ans] * l[ans]) / (l[ans] + l[ans - 1]);
            l[ans - 1] += l[ans];
            ans--;
        }
    }
    for(int i = 1; i <= ans; i++){//ans为分为多少段
        for(int j = 1; j <= l[i]; j++)
            printf("%.9lf\n", b[i]);
    }
    return 0;
}