atcoder abc 244

D - swap hats

给定两个 R,G,B 的排列

进行刚好 \(10^{18}\) 次操作，每一次选择两个交换

问最后能否相同

刚好 \(10^{18}\) 次

算出交换最少次数，判断是否为偶数。

E - King Bombee

\(n\) 点 \(m\) 边的简单无向图，给定 \(K,S,T\) 和 \(X\)

求满足以下条件的路径数 \(\;mod\;998244353\)

路径 \(A\) 以长度为 \(K\) ，以 \(S\) 开使，\(T\) 结束，点 \(X\) 经过偶数次

简单的计数，设 \(f_{i,j,0/1}\) 为第 \(i\) 步到 \(j\) 经过 \(X\) 次数 \(\mod 2\) 为 \(0/1\) 的方案

\(n\le 2000\)

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

typedef long double LD;

typedef long long LL;

typedef double db;

const int N = 2005;

const LL P = 998244353;

int n, m, K, St, Ed, X, lst[N], Ecnt;

struct Edge { int to, nxt; } e[N << 1];

LL f[N][N][2];

inline void Ae(int fr, int go) {

    e[++Ecnt] = (Edge){ go, lst[fr] }, lst[fr] = Ecnt;

}

int main() {

    scanf("%d%d%d%d%d%d", &n, &m, &K, &St, &Ed, &X);

    for (int i = 1, u, v; i <= m; i++) {

        scanf("%d%d", &u, &v);

        Ae(u, v), Ae(v, u);

    }

    f[0][St][0] = 1;

    for (int i = 1; i <= K; i++)

        for (int j = 1; j <= n; j++) {

            for (int k = lst[j], v, t; k; k = e[k].nxt) {

                v = e[k].to;

                t = j == X;

                (f[i][j][0] += f[i - 1][v][0 ^ t]) %= P;

                (f[i][j][1] += f[i - 1][v][1 ^ t]) %= P;

            }

        }

    printf("%lld", f[K][Ed][0]);

}

F - Shortest Good Path

\(n\) 点 \(m\) 边的简单无向图，

长度为 \(n\) 的序列 \(s_i\) 且 \(s_{i}\in\set{0,1}\) 能表示一条路径 \(A\) 当点 \(i\) 出现次数 \(\mod 2=s_i\)

对所有 \(2^n\) 个序列，所表示的最短路径的长度和

\(n\le 17\)

简单的 bfs ，设 \(f_{s,i}\) 为序列 \(s\) 最后 \(i\) 的最短路

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

typedef long double LD;

typedef long long LL;

typedef double db;

const int N = 20;

int n, m, mx, a[N][N], l[N];

int f[1 << 18][N], res;

LL ans;

queue< pair<int, int> > Q;

int main() {

    scanf("%d%d", &n, &m);

    for (int i = 1, u, v; i <= m; i++) {

        scanf("%d%d", &u, &v);

        u--, v--;

        a[u][++l[u]] = v;

        a[v][++l[v]] = u;

    }

    mx = (1 << n) - 1;

    for (int i = 0; i <= mx; i++)

        for (int j = 0; j < n; j++) f[i][j] = 1e9;

    for (int i = 0; i < n; i++) f[1 << i][i] = 1, Q.push(make_pair(i, 1 << i));

    while (!Q.empty()) {

        int u = Q.front().first, s = Q.front().second;

        Q.pop();

        for (int i = 1, v, ts; i <= l[u]; i++) {

            v = a[u][i], ts = s ^ (1 << v);

            if (f[s][u] + 1 >= f[ts][v]) continue;

            f[ts][v] = f[s][u] + 1, Q.push(make_pair(v, ts));

        }

    }

    for (int i = 1; i <= mx; i++) {

        res = 1e9;

        for (int j = 0; j < n; j++) res = min(res, f[i][j]);

        if (res < 1e9) ans += res;

    }

    printf("%lld", ans);

}

G - Construct Good Path

\(n\) 点 \(m\) 边的简单无向图，和一个序列 \(s\) ，\(s_i\in\set{0,1}\)

构造一条路径，使得点 \(i\) 的出现次数 \(\mod 2\) 为 \(s_i\)

输出任意一个长度小于等于 \(4n\) 的路径，可以证明存在

\(n,m\le 2\times 10^5\)

构造题

无向图可以转换为树，结果不变

定义序列，\(A\) 如下：

\(A_u=(u)+\sum_{(u,v)\in E} A_v+(u)+B_v\)
\(+\) 表示序列的连接。
当 \(v\) 出现次数 \(mod\;2\ne s_i\) 时 \(B_v=(v,u)\) ，否则 \(B_v=()\)

\(A\) 满足：

\(A_u\) 从 \(u\) 开始，以 \(u\) 结束
对于 \(u\) 的所有儿子 \(v\) ，\(v\) 出现次数满足条件
长度最多为 \(4n-3\) （菊花图）

从任意 \(root\) 开始，最后判断 \(root\) 出现次数

若不满足条件，答案为 \(A_{root}+(v,root,v)\) ，\(v\) 为任意儿子。否则为 \(A_{root}\)

复杂度 \(O(n)\)

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

typedef long double LD;

typedef long long LL;

typedef double db;

const int N = 2e5 + 5;

int n, m, lst[N], Ecnt, vis[N], a[N];

int ans[N << 2], len;

char str[N];

struct Ed { int to, nxt; } e[N << 1];

inline void Ae(int fr, int go) {

    e[++Ecnt] = (Ed){ go, lst[fr] }, lst[fr] = Ecnt;

}

void dfs(int u) {

    vis[u] = 1, ans[++len] = u, a[u] ^= 1;

    for (int i = lst[u], v; i; i = e[i].nxt)

        if (!vis[v = e[i].to]) {

            dfs(v), ans[++len] = u, a[u] ^= 1;

            if (a[v]) {

                ans[++len] = v, a[v] ^= 1;

                ans[++len] = u, a[u] ^= 1;

            }

        }

}

int main() {

    scanf("%d%d", &n, &m);

    for (int i = 1, u, v; i <= m; i++) {

        scanf("%d%d", &u, &v);

        Ae(u, v), Ae(v, u);

    }

    scanf("%s", str + 1);

    for (int i = 1; i <= n; i++) a[i] = str[i] - 48;

    dfs(1);

    if (a[1]) {

        ans[++len] = e[lst[1]].to;

        ans[++len] = a[1];

        ans[++len] = e[lst[1]].to;

    }

    printf("%d\n", len);

    for (int i = 1; i <= len; i++) printf("%d ", ans[i]);

}

Ex Linear Maximization

\(Q\) 次操作，每次给 \(x,y,a,b\) ，要求将 \((x,y)\) 插入集合 \(S\) ，再查询 \(\max_{(x,y)\in S} ax+by\)

\(Q\le 2\times 10^5\)

[SDOI2014]向量集弱化版。

其实是求点积最大，\(ans=ax+by\) ，变形得 \(y=-\dfrac{a}{b}x+\dfrac{ans}{b}\)

根据 \(b\) 的正负，求最大或最小截距，答案在上凸或下凸壳上

线段树维护凸包，每次查询对应凸包三分。

#include <bits/stdc++.h>

#define PB push_back

using namespace std;

typedef unsigned long long uLL;

typedef long double LD;

typedef long long LL;

typedef double db;

const int N = 500005;

int Ti, cnt;

LL ans;

struct vec {

    LL x, y;

    vec(LL _x = 0, LL _y = 0) : x(_x), y(_y) { }

    bool operator < (vec a) const { return x ^ a.x ? x < a.x : y < a.y; }

    vec operator - (vec a) { return vec(x - a.x, y - a.y); }

    LL operator * (vec a) { return x * a.y - y * a.x; }

    LL operator ^ (vec a) { return x * a.x + y * a.y; }

} a[N], b[N], c[N], s[N], now;

vector<vec> t[N << 2][2];

#define ls (rt << 1)

#define rs (rt << 1 | 1)

inline void bui(int rt) {

    int n, m, top, len;

    for (int o = 0; o <= 1; o++) {

        n = m = len = top = 0;

        for (vec x : t[ls][o]) a[++n] = x;

        for (vec x : t[rs][o]) b[++m] = x;

        for (int i = 1, j = 1; i <= n || j <= m; ) {

            if (j > m || (i <= n && a[i] < b[j])) c[++len] = a[i++];

            else c[++len] = b[j++];

        }

        for (int i = 1; i <= len; s[++top] = c[i++])

            while (top >= 2 && ((c[i] - s[top]) * (s[top] - s[top - 1]) <= 0) ^ o) top--;

        for (int i = 1; i <= top; i++) t[rt][o].PB(s[i]);

    }

}

void ins(int x, int l, int r, int rt) {

    if (l == r) return t[rt][0].PB(now), t[rt][1].PB(now);

    register int mid = l + r >> 1;

    if (x <= mid) ins(x, l, mid, ls);

    else ins(x, mid + 1, r, rs);

    if (x == r) bui(rt);

}

inline LL calc(int rt, vec a) {

    int o = a.y <= 0;

    int l = 1, r = t[rt][o].size();

    LL res = -(1ll << 62), m1, m2;

    while (r - l + 1 >= 4) {

        m1 = (l + l + r) / 3, m2 = (l + r + r) / 3;

        (t[rt][o][m1 - 1] ^ now) > (t[rt][o][m2 - 1] ^ now) ? r = m2 : l = m1;

    }

    for (int i = l; i <= r; i++) res = max(res, t[rt][o][i - 1] ^ a);

    return res;

}

void ask(int ql, int qr, int l, int r, int rt) {

    if (ql > r || l > qr) return;

    if (ql <= l && r <= qr) { ans = max(ans, calc(rt, now)); return; }

    register int mid = l + r >> 1;

    ask(ql, qr, l, mid, ls), ask(ql, qr, mid + 1, r, rs);

}

#undef ls

#undef rs

int main() {

    scanf("%d", &Ti);

    int n = Ti;

    for (LL i = 1, x, y, l, r; i <= Ti; i++) {

        scanf("%lld%lld", &x, &y);

        now.x = x, now.y = y;

        ins(++cnt, 1, n, 1);

        scanf("%lld%lld", &x, &y);

        now.x = x, now.y = y;

        ans = -(1ll << 62);

        ask(1, i, 1, n, 1);

        printf("%lld\n", ans);

    }

}

巴特西

atcoder abc 244

atcoder abc 244

D - swap hats

E - King Bombee

F - Shortest Good Path

G - Construct Good Path

Ex Linear Maximization

最新文章

热门文章