AtCoder Beginner Contest 219

比赛链接

D Strange Lunchbox

Description

题目链接

Solution

设 $dp[i][j][k]$ 表示考虑前 $i$ 个盒子，选了 $j$ 个，takoyaki 数量为 $k$ （大于 $k$ 仍记为 $k$）时能获得 taiyaki 的最大值，状态转移如下：

• 选第 $i$ 个盒子，则 $dp[i][j][min(k,X)] \leftarrow dp[i-1][j-1][k-A_i] + B_i$，其中 $A_i \le k \le X+A_i$。
• 不选第 $i$ 个盒子，则 $dp[i][j][k] \leftarrow dp[i-1][j][k]$，其中 $0 \le k \le X$。

最后答案为 $\min \limits_{1 \le j \le N}dp[N][j][X]$。

时间复杂度：$O(N^2X)$。

Code

Strange Lunchbox

#include <bits/stdc++.h>

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

using namespace std;
typedef long long LL;

const int MAXN = 3E2 + 5;
const int MOD = 1E9 + 7;
int n, x, y;
int dp[2][MAXN][MAXN], a[MAXN], b[MAXN];

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> x >> y;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    memset(dp, -1, sizeof(dp));
    dp[0][0][0] = 0;
    for (int i = 1; i <= n; i++) {
        memset(dp[i & 1], -1, sizeof(dp[i & 1]));
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k <= x + a[i]; k++) {
                if (j && k - a[i] >= 0 &&
                    dp[(i & 1) ^ 1][j - 1][k - a[i]] != -1)
                    dp[i & 1][j][min(k, x)] =
                        max(dp[i & 1][j][min(k, x)],
                            dp[(i & 1) ^ 1][j - 1][k - a[i]] + b[i]);

                if (dp[(i & 1) ^ 1][j][min(k, x)] != -1)
                    dp[i & 1][j][min(k, x)] = max(
                        dp[i & 1][j][min(k, x)], dp[(i & 1) ^ 1][j][min(k, x)]);
            }
        }
    }
    for (int j = 0; j <= n; j++)
        if (dp[n & 1][j][x] >= y) {
            cout << j;
            return 0;
        }
    cout << -1;
    return 0;
}

E Moat

Description

题目链接

Solution

由于矩阵大小为 $4*4$，我们可以枚举哪些格子没有被护城河包围，哪些格子被护城河包围。在一个合法方案中，所有城市应该被护城河包围，且被包围的格子和没有被包围的格子恰好形成两个联通块（规定边界的没有被包围的格子和外部一个超级源点相连），因此二进制枚举包围状态，然后用并查集求联通块个数即可。

Code

Moat

#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, ans;
int a[4][4], num[4][4], fa[17];

int find(int x) {
    if (fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

void unionn(int a, int b) {
    int r1 = find(a), r2 = find(b);
    if (r1 != r2) fa[r2] = r1;
}

signed main() {
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++) cin >> a[i][j], num[i][j] = i * 4 + j;
    for (int s = 0; s < (1 << 16); s++) {
        for (int i = 0; i <= 16; i++) fa[i] = i;
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++) {
                if (i) {
                    if (!((s >> num[i][j]) & 1) && !((s >> num[i - 1][j]) & 1))
                        unionn(num[i - 1][j], num[i][j]);
                    if (((s >> num[i][j]) & 1) && ((s >> num[i - 1][j]) & 1))
                        unionn(num[i][j], num[i - 1][j]);
                }
                if (j) {
                    if (((s >> num[i][j]) & 1) && ((s >> num[i][j - 1]) & 1))
                        unionn(num[i][j], num[i][j - 1]);
                    if (!((s >> num[i][j]) & 1) && !((s >> num[i][j - 1]) & 1))
                        unionn(num[i][j - 1], num[i][j]);
                }
            }

        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                if ((!i || !j || i == 3 || j == 3) && !((s >> num[i][j]) & 1))
                    unionn(16, num[i][j]);
        int cnt = 0;
        for (int i = 0; i <= 16; i++)
            if (fa[i] == i) cnt++;
        if (cnt != 2) continue;
        bool ok = 1;
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                if (a[i][j] && !((s >> num[i][j]) & 1)) ok = 0;
        ans += ok;
    }
    cout << ans;
    return 0;
}

F Cleaning Robot

Description

题目链接

Solution

设第 $1$ 次执行指令访问到的点集为

$V_1=\{(X_1,Y_1),(X_2,Y_2),\dots,(X_n,Y_n)\}$

记终止位置为 $(a,b)$。类似定义第 $2k$ 次执行指令访问到的点集：

$V_2=\{(X_1+a,Y_1+b),(X_2+a,Y_2+b),\dots,(X_n+a,Y_n+b)\}$
$\vdots$
$V_k=\{(X_1+(k-1)a,Y_1+(k-1)b),(X_2+(k-1)a,Y_2+(k-1)b),\dots,(X_n+(k-1)a,Y_n+(k-1)b)\}$

对 $(X_i,Y_i)∈V_1$，记 $d_i$ 为最小的满足 $(X_i+d_ia,Y_i+d_ib)∈V_1$ 的正整数（没有则为 $\infty$)。由反证法可知 $(X_i,Y_i),\dots,(X_i+(d_i-1)a,Y_i+(d_i-1)b)$ 不会与从 $(X_j,Y_j),j \neq i$ 开始执行过程中访问到的点重复，否则会存在一个更小的 $d$，同时容易知道答案为 $\sum\limits_{i=1}^{n}min(d_i,k)$。

接下来考虑如何求解 $d$。

设 $q_i=\lfloor \frac{X_i}{a} \rfloor,S_i=X_i-aq_i,T_i=Y_i-bq_i$，那么 $(X_j,Y_j)=(X_i+da,Y_i+db)⇔(S_i,Y_i) = (S_j,T_j)⇔(X_j,Y_j)=(X_i+(q_j-q_i)a,Y_i+(q_j-q_i)b)$。我们先根据 $(S,T)$ 对 $q$ 分组，再进行组内排序，相邻两项的差就是 $d$。

时间复杂度：$O(|S|log|S|)$。

Code

Cleaning Robot

#include <bits/stdc++.h>

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

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;

int cnt = 0;
LL k;
string s;
set<pair<int, int>> p;
map<pair<int, int>, int> mp;
vector<int> q[MAXN];

signed main() {
    ios::sync_with_stdio(false);
    cin >> s >> k;
    int a = 0, b = 0;
    p.insert({a, b});
    for (auto& c : s) {
        if (c == 'U') b--;
        if (c == 'D') b++;
        if (c == 'L') a--;
        if (c == 'R') a++;
        p.insert({a, b});
    }
    if (!a && !b) return cout << p.size(), 0;
    for (auto& [x, y] : p) {
        int m1 = a ? (x % a + a) % a : (y % b + b) % b;
        int k = a ? (x - m1) / a : (y - m1) / b;
        int m2 = a ? y - k * b : x - k * a;
        int id = mp[{m1, m2}];
        if (!id) {
            mp[{m1, m2}] = ++cnt;
            q[cnt].push_back(k);
        } else
            q[id].push_back(k);
    }
    LL ans = 0;
    for (int i = 1; i <= cnt; i++) {
        sort(q[i].begin(), q[i].end());
        for (int j = 0; j < q[i].size() - 1; j++)
            ans += min(k, (LL)q[i][j + 1] - q[i][j]);
        ans += k;
    }
    cout << ans;
    return 0;
}

G Propagation

Description

题目链接

Solution

将每次询问分为下面两步操作：

1. 根据相邻点的修改状态更新当前点的值。
2. 根据当前点的度修改周围节点的值/打上延迟修改标记。

对于操作 $2$，若当前点的度小于 $B$，则直接将所有相邻点的值修改为当前点的值，并记录这些点的最后一次被修改的时刻（$qid$）为当前询问编号；若当前点的度大于等于 $B$，则不立刻更新相邻点的值，而是对这个点记录当前询问编号为 $sign$，同时用 $tag$ 记录该点的值。

对于操作 $1$，由于对度大于等于 $B$ 的点采用延迟更新，因此我们要遍历这些点，并根据这些点的状态更新当前点的值。具体的，如果某一度大于等于 $B$ 的点的 $sign$ 大于等于当前点 $qid$，说明需要更新，将 $tag$ 赋给当前点，同时将当前点的 $qid$ 更新为 $sign$。

由于度大于等于 $B$ 的点不超过 $\frac{2M}{B}$ 个，因此总的复杂度为 $O(Q(B+\frac{2M}{B})$。由均值不等式可知，$B$ 取 $\sqrt{M}$ 比较合适。

类似题目：CF1580C Train Maintenance(参考代码)、CF342E Xenia and Tree(参考代码)

Code

Propagation

#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, q, B;
vector<int> G[MAXN];
array<int, MAXN> v, sign, qid, deg, tag;

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> q;
    B = max((int)sqrt(m), 1);
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
        deg[v]++, deg[u]++;
    }
    auto cmp = [&](int& a, int& b) -> bool { return deg[a] > deg[b]; };
    for (int i = 1; i <= n; i++) v[i] = i, sort(G[i].begin(), G[i].end(), cmp);
    for (int i = 1, x; i <= q; i++) {
        cin >> x;
        for (auto& to : G[x]) {
            if (deg[to] < B) break;
            if (sign[to] > qid[x]) {
                qid[x] = sign[to];
                v[x] = tag[to];
            }
        }
        if (deg[x] < B)
            for (auto& to : G[x]) v[to] = v[x], qid[to] = i;
        else
            sign[x] = i, tag[x] = v[x];
    }
    for (int i = 1; i <= n; i++) {
        for (auto& to : G[i]) {
            if (deg[to] < B) break;
            if (sign[to] > qid[i]) {
                qid[i] = sign[to];
                v[i] = tag[to];
            }
        }
        cout << v[i] << " ";
    }
    return 0;
}