概要

	A	B	C	D	E	F	G	H	I	J	K
总体	✔	✔	?	?	✔	?	✔	✔	✔	?	✔
wzgy					✔				✔	?	✔
csz	✔	✔	?				✔
wh				?		?		✔

比赛地址

2020牛客暑期多校训练营（第二场）

题目

A

B

C

D

E. Exclusive OR

题目大意
给定 ? 个数，从中选择恰好 ? 个数，要求其异或和最大。
对于 ?\in[1…?] 分别输出答案。
解题思路
注意到 A[i]<2^{18}。由线性基的知识可知，这一组数的线性基大小为18，因此最多选取18个数后可以得到最大异或和。因此当 i\ge 20 时，ans[i]=ans[i-2]：显然 ans[i]\ge ans[i-2]，若 ans[i]>ans[i-2]，说明至少选取 i-1 个数才到达最大值。因此我们只需求出前19个答案。
对 A 数组含有的数作为下标，进行异或卷积，得到的新数组如果某下标的值不为0，则说明可以异或出这个数。我们进行18次异或卷积即可得到答案。
AC代码

#include <bits/stdc++.h>
using namespace std;
const int P = 998244353;

int extend(int n) {
    int N = 1;
    for (; N < n; N <<= 1);
    return N;
}
void FWTxor(vector<int> &a, bool rev) {
    int n = (int)a.size(), inv2 = (P + 1) >> 1;
    for (int l = 2, m = 1; l <= n; l <<= 1, m <<= 1) {
        for (int j = 0; j < n; j += l) for (int i = 0; i < m; i++) {
            int x = a[i + j], y = a[i + j + m];
            if (!rev) {
                a[i + j] = (x + y) % P;
                a[i + j + m] = (x - y + P) % P;
            }
            else {
                a[i + j] = 1LL * (x + y) * inv2 % P;
                a[i + j + m] = 1LL * (x - y + P) * inv2 % P;
            }
        }
    }
}
vector<int> Xor(vector<int> a1, vector<int> a2) {
    int n = (int)max(a1.size(), a2.size()), N = extend(n);
    a1.resize(N); FWTxor(a1, false);
    a2.resize(N); FWTxor(a2, false);
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) A[i] = 1LL * a1[i] * a2[i] % P;
    FWTxor(A, true);
    return A;
}

int qmax(vector<int> &a) {
    for (int i = (1 << 18) - 1; i; i--) {
        if (a[i]) {
            return i;
        }
    }
    return -1;
}

const int N = 1e6 + 50;
int f[N], ans[N];

int main(int argc, const char * argv[]) {
    int n; scanf("%d", &n);
    vector<int> a(1 << 18), b;
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        f[x] = 1;
    }
    for (int i = 0; i < (1 << 18); i++) {
        a[i] = f[i];
    }
    b = a;

    ans[1] = qmax(b);
    for (int i = 2; i < 20; i++) {
        b = Xor(b, a);
        ans[i] = qmax(b);
    }
    for (int i = 20; i <= n; i++) {
        ans[i] = ans[i - 2];
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", ans[i], i == n ? '\n' : ' ');
    }

    return 0;
}

F

G

H

I. Interval

题目大意
给一个初始区间 [1,?] ,当 l<r 时，每次可以将当前区间 [?,?] 变成 [?+1,r] ，[?−1,?] ，[?,?+1] ，[?,?−1] 四种，并且有若干种禁止操作，第 ? 个操作表示你可以花 ?? 的代价永久禁止掉区间为 [??,??] 时的前两个操作或者后两个操作，问任意时刻区间都不能为 ?=? 的最小代价。

解题思路
将 [?,?] 区间抽象成平面上的一个点 (?,?)，问题可以转化到一个网格图上，从 (1,n)开始，每次可以上下左右走，不能走到对角线上；对于题目中给出的可以禁止的边，其权值为禁止的代价，其余边权值为 INF。我们要求的就是这个图的最小割，如果最小割大于 INF，即不存在最小割，则输出 -1。
利用最小割等于最大流的定理，我们可以跑Dinic得到答案，这里要注意，即便是ban掉一条单向边，我们也要建立权值均为禁止代价的双向边（原理暂时没想明白）。但是这样做会TLE。
赛后学习了平面图上的网络流。平面图的最大流问题，可以转化为其对偶图上的最短路问题。此题转化出来如下：

对于流量为 INF 的边，在最短路问题中等于不需要连边；把边界的边分别连向源点和汇点，再连接题目中可以禁止的边所对应的新边，跑Dijkstra即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e6 + 50;
const int MAXM = 2e7 + 50;

int head[MAXN], tot;
struct Edge {
    int nex, to, w;
}e[MAXM];
void addedge(int a, int b, int c) {
    e[++tot] = (Edge) {head[a], b, c};
    head[a] = tot;
}
void add(int a, int b, int c) {
    addedge(a, b, c);
    addedge(b, a, c);
}

typedef pair<ll, int> pii;
#define mp make_pair
long long dis[MAXN];
int vis[MAXN];
priority_queue<pii, vector<pii>, greater<pii> > pq;
void Dijkstra(int rt)
{
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    while(!pq.empty()) pq.pop();
    dis[rt] = 0;
    pq.push({0, rt});
    while(!pq.empty())
    {
        pii t = pq.top(); pq.pop();
        if(vis[t.second]) continue;
        vis[t.second] = 1;
        for(int i = head[t.second]; i; i = e[i].nex)
        {
            int to = e[i].to;
            if(dis[to] > t.first + e[i].w)
            {
                dis[to] = t.first + e[i].w;
                pq.push(mp(dis[to], to));
            }
        }
    }
}

int n, m, S, T;

int id(int x, int y) {
    return x * (n + 1) + y + 1;
}

int main(int argc, const char * argv[]) {
    scanf("%d%d", &n, &m);
    S = id(n, n); T = id(0, 0);
    for (int i = 1; i <= m; i++) {
        int a, b, c; char d;
        scanf("%d %d %c %d", &a, &b, &d, &c);
        if (d == 'L') {
            add(id(a, b - 1), id(a, b), c);
        }
        else {
            add(id(a - 1, b - 1), id(a, b - 1), c);
        }
    }
    for (int i = 1; i < n; i++) {
        add(id(i, n), S, 0);
        add(id(0, i), T, 0);
    }
    Dijkstra(S);
    if (dis[T] > 1e15) puts("-1");
    else printf("%lld\n", dis[T]);
    return 0;
}

J

K. Keyboard Free

题目大意
给三个以原点为圆心的同心圆，半径分别是 ?1 , ?2 , ?3 , 有三个点 ? , ? , ? 分别在三个圆上滑动，问三角形 ??? 的面积
解题思路

AC代码

#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-3;
const double PI = acos(-1);

typedef double db;
typedef db func(db);

double r1, r2, r3;

db dis(db x_1, db y_1, db x_2, db y_2)
{
    db _x = x_1 - x_2, _y = y_1 - y_2;
    return sqrt(_x * _x + _y * _y);
}

db f(db a) {
    if (a == 0) {
        return 0;
    }
    db x2 = r2 * cos(a), y2 = r2 * sin(a);
    db lab = dis(r1, 0, x2, y2);
    db d = r1 * y2 / lab;
    db alpha = asin(d / r3);
    db exp_dis = 2 * r3 * (cos(alpha) + alpha * sin(alpha)) / PI;
    return 0.5 * lab * exp_dis;
}

db simpson(db l, db r, func f) {
    db mid = (l + r) / 2;
    return (f(l) + 4 * f(mid) + f(r)) * (r - l) / 6;
}
db asr(db l, db r, db eps, db A, func f) {
    db mid = (l + r) / 2;
    db L = simpson(l, mid, f), R = simpson(mid, r, f);
    if (fabs(L + R - A) <= 15 * eps) return L + R + (L + R - A) / 15;
    return asr(l, mid, eps / 2, L, f) + asr(mid, r, eps / 2, R, f);
}
db asr(db l, db r, db eps, func f) {
    return asr(l, r, eps, simpson(l, r, f), f);
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        int a, b, c;

        scanf("%d%d%d", &a, &b, &c);
        r1 = a, r2 = b, r3 = c;
        if (r1 > r2) {
            swap(r1, r2);
        }
        if (r2 > r3) {
            swap(r2, r3);
        }
        if (r1 > r3) {
            swap(r1, r3);
        }
        printf("%.1f\n", asr(0, 2 * PI, 1e-6, f) / (2 * PI));
    }

    return 0;
}