AtCoder Beginner Contest 223

比赛链接

D Restricted Permutation

Description

题目链接

Solution

给出 $A_i,B_i$，由 $A_i$ 向 $B_i$ 连边，表示 $A_i$ 比 $B_i$ 更早出现，从而得到一个有向图。若该有向图中存在环则无解；否则进行拓扑排序，优先选取编号最小的入度为 $0$ 的点，我们用优先队列存储这些点即可。

Code

Restricted Permutation

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, m, T;
array<int, MAXN> in;
vector<int> G[MAXN], ans;

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        in[v]++;
    }
    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 1; i <= n; i++)
        if (in[i] == 0) q.push(i);
    while (!q.empty()) {
        int now = q.top();
        ans.push_back(now);
        q.pop();
        for (auto& to : G[now]) {
            in[to]--;
            if (in[to] == 0) q.push(to);
        }
    }
    for (int i = 1; i <= n; i++)
        if (in[i]) return cout << -1, 0;
    for (auto& i : ans) cout << i << " ";
    return 0;
}

E Placing Rectangles

Description

题目链接

Solution

任何一种合法的方案都可以转化成下面四种方案之一：

枚举这四种方案判断是否可行即可。

Code

Placing Rectangles

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

#define int long long

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int x, y, a, b, c;

bool solve2(int x, int y, int a, int b) {
    if (y <= 0) return false;
    int k1 = (a % y == 0 ? a / y : a / y + 1);
    int k2 = (b % y == 0 ? b / y : b / y + 1);
    if (k1 + k2 > x) return false;
    return true;
}

bool solve3(int x, int y) {
    int k1 = (a % x == 0 ? a / x : a / x + 1);
    int k2 = (b % x == 0 ? b / x : b / x + 1);
    int k3 = (c % x == 0 ? c / x : c / x + 1);
    if (k3 + k2 + k1 <= y) return true;
    if (solve2(x, y - k1, b, c)) return true;
    if (solve2(x, y - k3, a, b)) return true;
    if (solve2(x, y - k2, a, c)) return true;
    return false;
}

signed main() {
    cin >> x >> y >> a >> b >> c;
    if (solve3(x, y))
        cout << "Yes";
    else if (solve3(y, x))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

F Parenthesis Checking

Description

题目链接

Solution

记 ( 为 $1$，) 为 $-1$，则合法的括号序列满足任意前缀和大于等于 $0$，且总和为 $0$，用线段树维护区间和与区间前缀和最小值即可。

Code

Parenthesis Checking

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int n, q;
char s[MAXN];

#define lid id << 1
#define rid id << 1 | 1

struct node {
    int l, r;
    int sum, mipre;
} tr[MAXN << 2];

void update(int id) {
    tr[id].sum = tr[lid].sum + tr[rid].sum;
    tr[id].mipre = min(tr[lid].mipre, tr[lid].sum + tr[rid].mipre);
}

void build(int id, int l, int r) {
    tr[id].l = l, tr[id].r = r;
    if (l == r) {
        tr[id].sum = tr[id].mipre = (s[l] == '(' ? 1 : -1);
        return;
    }
    int mid = l + r >> 1;
    build(lid, l, mid);
    build(rid, mid + 1, r);
    update(id);
}

void modify(int id, int x, char v) {
    if (tr[id].l == x && tr[id].r == x) {
        tr[id].sum = tr[id].mipre = (v == '(' ? 1 : -1);
        return;
    }
    int mid = tr[id].l + tr[id].r >> 1;
    if (x <= mid)
        modify(lid, x, v);
    else
        modify(rid, x, v);
    update(id);
}

int qsum(int id, int l, int r) {
    if (tr[id].l == l && tr[id].r == r) return tr[id].sum;
    int mid = tr[id].l + tr[id].r >> 1;
    if (r <= mid)
        return qsum(lid, l, r);
    else if (l > mid)
        return qsum(rid, l, r);
    else
        return qsum(lid, l, mid) + qsum(rid, mid + 1, r);
}

int qmin(int id, int l, int r) {
    if (tr[id].l == l && tr[id].r == r) return tr[id].mipre;
    int mid = tr[id].l + tr[id].r >> 1;
    if (r <= mid)
        return qmin(lid, l, r);
    else if (l > mid)
        return qmin(rid, l, r);
    else
        return min(qmin(lid, l, mid),
                   qsum(lid, l, mid) + qmin(rid, mid + 1, r));
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> s[i];
    build(1, 1, n);
    for (int i = 1, t, l, r; i <= q; i++) {
        cin >> t >> l >> r;
        if (t == 1) {
            modify(1, l, s[r]), modify(1, r, s[l]);
            swap(s[l], s[r]);
        } else {
            if (qmin(1, l, r) >= 0 && qsum(1, l, r) == 0)
                cout << "Yes\n";
            else
                cout << "No\n";
        }
    }
    return 0;
}

G Vertex Deletion

Description

题目链接

Solution

首先考虑如何得到一棵树的最大匹配：

设根节点为 1，每个节点初始为白色。然后从叶子节点向根节点染色，如果一个节点存在一个子节点颜色为白色，则将其染成黑色，并将其与该子节点匹配。

可以证明最大匹配为上述操作后黑色节点的个数。删除节点 1 并且最大匹配不变，当且仅当节点 1 不为黑色。

对于一个节点，判断将其删除后最大匹配是否不变，可通过简单树形 DP 解决。设 $dp_i$ 表示对 $i$ 子树染色后 $i$ 的颜色 （0 为 白色，1 为 黑色）。则$dp_i |= !dp_{son_i}$，同时用 $cnt_{i, 0/1}$ 表示节点 $i$ 的颜色为白色或黑色的子节点数目。

然后考虑换根 DP，用 $f_i$ 表示以 $i$ 为根，染色操作后 $i$ 最后为什么颜色，$f_1 = dp_1$。

对于 $i != 1$，首先让 $fa_i$ 的 $dp_i$ 颜色数目减 1（即 $cnt_{fa_i,dp_i}-1$），得出以 $i$ 为根时 $fa_i$ 的颜色，从而修改 $cnt_{i, color_{fa_i}}$，进一步可判断出 $f_i$。最后将让 $fa_i$ 的 $dp_i$ 颜色数目加 1。

DFS 对每个节点进行上述操作即可得到以每个节点为根，染色后的最终颜色。

最后统计 $f_i = 0$ 的节点个数即可。

时间复杂度 $O(n)$。

Code

Vertex Deletion

#include <bits/stdc++.h>

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 2e5 + 5, MOD = 1e9 + 7;

int n;
bool dp[MAXN], f[MAXN];
int cnt[MAXN][2]; // 0 white && 1 black
vector<int> g[MAXN];

void DP(int cur, int fa) {
    for (auto& to : g[cur]) {
        if (to == fa) continue;
        DP(to, cur);
        dp[cur] |= (!dp[to]);
        cnt[cur][dp[to]]++;
    }
}

void dfs(int cur, int fa) {
    for (auto& to : g[cur]) {
        if (to == fa) continue;
        cnt[cur][dp[to]]--;

        bool colorCur;
        if (cnt[cur][0]) colorCur = true;
        else colorCur = false;

        f[to] = (dp[to] | (!colorCur));
        cnt[to][colorCur]++;

        dfs(to, cur);

        cnt[cur][dp[to]]++;
    }
}

signed main() {
    boost;
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    DP(1, 0);
    f[1] = dp[1], dfs(1, 0);
    int ans(0);
    for (int i = 1; i <= n; i++) ans += (!f[i]);
    cout << ans << "\n";
    return 0;
}

H Xor Query

Description

题目链接

Solution

前缀线性基模板题。建出前缀线性基，剩下的就是线性基的基本操作了。

类似题目：Ivan and Burgers

Code

Xor Query

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl
#define int long long

using namespace std;
typedef long long LL;

const int MAXN = 4E5 + 5;
const int MOD = 1E9 + 7;
const int BIT = 60;
int n, q;

struct PrefixLinearBasis {
    int p[BIT], pos[BIT];  // 60 位记得 define int long long

    void init() {
        memset(p, 0, sizeof(p));
        memset(pos, 0, sizeof(pos));
    }

    bool insert(PrefixLinearBasis& pre, int w, int x) {
        *this = pre;
        for (register int i = BIT; ~i; i--)
            if ((x >> i) & 1)
                if (!p[i]) {
                    pos[i] = w;
                    p[i] = x;
                    return true;
                } else {
                    if (pos[i] < w) swap(pos[i], w), swap(p[i], x);
                    x ^= p[i];
                }
        return false;
    }

    bool query(int l, int x) {
        for (int i = BIT; i >= 0; i--)
            if (p[i] && pos[i] >= l && ((x >> i) & 1)) x ^= p[i];
        return x == 0;
    }
} plb[MAXN];

signed main() {
    read(n, q);
    plb[0].init();
    for (int i = 1, x; i <= n; i++) read(x), plb[i].insert(plb[i - 1], i, x);
    for (int i = 1, l, r, x; i <= q; i++) {
        read(l, r, x);
        if (plb[r].query(l, x))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}