1040——Codeforces Round #507 (Div. 2, based on Olympiad of Metropolises)

codeforces

https://codeforces.com/contest/1040

2018.9.6凌晨实时参加
2018.9.6整理

比赛经过

记一下比赛经过。0:35开始，10点半左右搬到机房被子，然后写了一下“互不侵犯”，然后得了80分，11点半了，有点困，于是躺下休息一会，想休息一个小时或者40分钟左右，然后一觉睡到了1点半，起来还有一个小时。还有点困。先写了A，一遍过了，然后B调了好几个错误，过了，然后见C之后几个人过，D又是交互题，还有没写过，于是看E（E比C过的人还多），还有17分钟，没读懂题已经结束了。

A

模拟
维护两个指针，不同了直接输出-1，如果一个可以买，那么让他跟另一个样，如果两个都可以买，买便宜的。特判一下n为奇数，枚举到中间的情况。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int w[1000];
int main () {
    int n = read(), a = read(), b = read();
    for (int i=1; i<=n; ++i) w[i] = read();
    LL Ans = 0;
    for (int l=1,r=n; l<=r; r--,l++) {
        if (l == r) {
            if (w[l] == 2) Ans += min(a, b);
        }
        else if (w[l] == w[r]) {
            if (w[l] == 2 && l!=r) Ans += min(a, b) * 2;
        } else {
            if (w[l] == 2 && w[r] == 1) Ans += b;
            else if (w[l] == 2 && w[r] == 0) Ans += a;
            else if (w[r] == 2 && w[l] == 1) Ans += b;
            else if (w[r] == 2 && w[l] == 0) Ans += a;
            else { puts("-1"); return 0; }
        }
    }
    cout << Ans;    
    return 0;
}

B

模拟。
每次优先选最长，即k+k+1，假设选t个，剩下的如果大于等于k+1，那么就再选一个k+1，否则，t--，然后选两个在k+1大于k+1的。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline int read() { 
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
int main () {
    int n = read(), k = read();
    if (k >= n) {
        puts("1");
        puts("1"); return 0;
    }
    if (k + k + 1 >= n) {
        puts("1");
        cout << n / 2 + 1;
        return 0;
    }
    int f = 0, e = 0;
    int c = n / (k + k + 1), t = (n % (k + k + 1));
    if (t >= k + 1) f = t;
    else if (t == 0) t = 0;
    else t += (k + k + 1), c --, f = k + 1, e = t - f;
    //cout << c << " " << f << " " << e; return 0;
    int cnt = c + (f?1:0) + (e?1:0);
    cout << cnt << "\n";
    int now = -(k);
    if (f) now = f - (k), cout << now << " ";
    for (int i=1; i<=c; ++i) {
        now += k;
        now += (k + 1);
        printf("%d ", now);
    }
    if (e) {
        now +=k; 
        now += (k + 1);
        cout << now;
    }
    return 0;
}

E

题意：
一张图，n个点，m条边，然后每个点有个权值x，x<=1e18。如果一条边是安全的，那么这条边的两个端点的权值不能一样，给定的图所有的边都是安全的。现在有一个病毒，病毒有一个权值（不知道这个权值），病毒可以入侵任意的点，入侵后的权值为(x^原来的权值)。
(S,x)表示病毒的权值为x，它只入侵了点集S中的点，然后整张图的边都是安全的。
求出所有的(S,x)。

题意二：

一张图，n个点，m条边，然后每个点有个权值x，x<=1e18。如果一条边的两个端点不一样，那么这条边是安全的，开始时所有边都是安全的。现在有一个病毒y，病毒可以入侵任意的点，入侵一个点后的权值为(y^x)。
(S,y)表示病毒的权值为y，它只入侵了点集S中的点，然后整张图的边都是安全的。求出所有的(S,x)。

设一条的边的两个端点为u,v，病毒为x。
如果u,v同时异或了x，那么他们还是安全的。
不安全的情况当且仅当，u^x=v。如果存在这样的x，那么一定知道v^x=u（由异或的性质a^x=b,b^x=a,a^b=x），那么这两个点要么同时异或x，要么都不异或x。所以可以把这两个点缩成一个。
所以原图中设每条边的权值为u^v（最多边数个x），然后对于每个x，枚举边权等于x的边，将两个端点合并，按一个点来考虑。缩点后的图假设有siz个点，那么对于x，有$2^{siz}$个点集是合法的。对于每个x都这样求一遍，提前将边权相同的边放在同一个vector里，最后的复杂度就是O(m)。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
inline LL read() {
    LL x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
#define pa pair<int,int>
#define mp(a,b) make_pair(a,b)
const int N = 500100;
const int mod = 1e9 + 7;
vector< pa > e[N];
map<LL, int> mp;
int fa[N], mi[N];
LL c[N];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main() {
    int n = read(), m = read(), k = read(), Index = 0;
    mi[0] = 1;
    for (int i=1; i<=n; ++i) mi[i] = 1ll * mi[i - 1] * 2 % mod;
    LL sum = (1ll << k);
    for (int i=1; i<=n; ++i) c[i] = read();
    for (int i=1; i<=m; ++i) {
        int u = read(), v = read();
        LL x = c[u] ^ c[v];
        if (!mp[x]) mp[x] = ++Index;
        e[mp[x]].push_back(mp(u, v));
    }
    LL ans = 0;
    for (int i=1; i<=n; ++i) fa[i] = i;
    for (int i=1; i<=Index; ++i) {
        int siz = n;
        for (pa j : e[i]) {
            int u = j.first, v = j.second;
            if (find(u) != find(v)) {
                fa[fa[u]] = fa[v];
                siz --;
            }
        }
        ans = (ans + mi[siz]) % mod;
        for (pa j : e[i]) {
            int u = j.first, v = j.second;
            fa[u] = u, fa[v] = v;
        }
    }
    ans = (ans + 1ll * (sum - Index) % mod * mi[n] % mod) % mod;
    // sum：病毒所有的取值，减去Index个取值，剩下的取值对应的点集是随便取的，即2^n
    cout << ans;
    return 0;
}