🧩 AtCoder Beginner Contest 271

TayLockOctober 1, 2022About 4 min

🧩 AtCoder Beginner Contest 271

# Info & Summary

Date: 2022-10-01
Completion Status: A ✅ / B ✅ / C ✅ / D ✅ / E ❌ / F ❌ / G ❌
Problem Type:
- D: DP
- E: DP
- F: Meet-in-the-middle

D. Flip and Adjust (DP)

题目:

$n$ 张卡片, 正面数字 $a_i$ , 背面数字 $b_i$

你来决定每张卡片正面朝上还是反面朝上

但是最后卡片上显示的数字总和必须为 $s$

思路:

定义 $dp[i][j]$ : 是否能从 $1, 2, ..., i$ 张卡片中得到总和 $j$

转移:

$dp[i + 1][j] = 0$
if $dp[i][j] == 1$
2.1: if $j + a_i < s$ , 则 $dp[i + 1][j + a_i] = 1$
2.2: if $j + b_i < s$ , 则 $dp[i + 1][j + b_i] = 1$

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, s;
    cin >> n >> s;

    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i] >> b[i];
    }

    vector<vector<bool>> dp(n + 1, vector<bool>(s + 1, false));
    dp[0][0] = true;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= s; j++)
        {
            if (dp[i][j])
            {
                if (j + a[i] <= s)
                {
                    dp[i + 1][j + a[i]] = true;
                }
                if (j + b[i] <= s)
                {
                    dp[i + 1][j + b[i]] = true;
                }
            }
        }
    }

    if (dp[n][s])
    {
        cout << "Yes" << endl;
        string ans(n, 'H');
        for (int i = n - 1; i >= 0; i--)
        {
            if (s >= a[i] && dp[i][s - a[i]])
            {
                ans[i] = 'H';
                s -= a[i];
            } else {
                ans[i] = 'T';
                s -= b[i];
            }
        }

        cout << ans << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

E. Subsequence Path (DP)

题目:

现在有 $n$ 个点, $m$ 条带权有向边, 现在我们给定一个序列 $E$ , 我们称从 $1$ 到 $n$ 的一条路径为好的, 当且仅当他经过的边的编号, 是 $E$ 的子序列, 现在请找出最短的好的路径, 如果没有则输出 $-1$

思路:

因为给定了固定的序列, 那么我们对于一个路径其实就是选与不选两种选择, 我们可以 dp 递推一下, 用这条路径更新 dist[v]即可

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(m), b(m), c(m);
    for (int i = 0; i < m; i++)
    {
        cin >> a[i] >> b[i] >> c[i];
        a[i] -= 1;
        b[i] -= 1;
    }

    vector<long long> dist(n, 1e18);
    dist[0] = 0;
    while (k--)
    {
        int e;
        cin >> e;
        e--;

        if (dist[b[e]] > dist[a[e]] + c[e])
        {
            dist[b[e]] = dist[a[e]] + c[e];
        }
    }

    if (dist[n - 1] == 1e18)
    {
        cout << -1 << endl;
    } else {
        cout << dist[n - 1] << endl;
    }

    return 0;
}

F. XOR on Grid Path (meet-in-the-middle)

题目:

给定一个 $n * n$ 的矩阵, 每个点上都有一个权值, 问从左上角出发到右下角, 并且路径权值异或和为 0 的方案数

思路:

正常 DP: 时间复杂度 $O(2^{2n})$
meet-in-the-middle(双向广搜): 从 $(1, 1)$ 向对角线搜, $(n, n)$ 也向对角线搜, 最后合并结果

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<vector<int>> a(n, vector<int>(n, 0));
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> a[i][j];
        }
    }

    vector<vector<vector<int>>> src(n, vector<vector<int>>(n, vector<int>()));
    src[0][0].push_back(a[0][0]);

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (i + j >= n)
            {
                continue;
            }
            if (i > 0)
            {
                for (const int x : src[i - 1][j])
                {
                    src[i][j].push_back(x ^ a[i][j]);
                }
            }
            if (j > 0)
            {
                for (const int x : src[i][j - 1])
                {
                    src[i][j].push_back(x ^ a[i][j]);
                }
            }
        }
    }

    vector<vector<vector<int>>> dst(n, vector<vector<int>>(n, vector<int>()));
    dst[n - 1][n - 1].push_back(a[n - 1][n - 1]);

    for (int i = n - 1; i >= 0; --i)
    {
        for (int j = n - 1; j >= 0; --j)
        {
            if (i + j < n - 1)
            {
                continue;
            }
            if (i + 1 < n)
            {
                for (const int x : dst[i + 1][j])
                {
                    dst[i][j].push_back(x ^ a[i][j]);
                }
            }
            if (j + 1 < n)
            {
                for (const int x : dst[i][j + 1])
                {
                    dst[i][j].push_back(x ^ a[i][j]);
                }
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i)
    {
        const int j = n - i - 1;
        sort(begin(dst[i][j]), end(dst[i][j]));

        for (const int x : src[i][j])
        {
            const int val = a[i][j] ^ x;
            ans += upper_bound(begin(dst[i][j]), end(dst[i][j]), val) - lower_bound(begin(dst[i][j]), end(dst[i][j]), val);
        }
    }

    cout << ans << '\n';

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

unordered_map<int, int> f[N][N];
int a[N][N], ans, n, m;

void dfs1(int x, int y, int v) {
    if(x + y == n) {
        f[x][y][v] ++ ;
        return ;
    }
    else {
        if(x + y < n) dfs1(x + 1, y, v ^ a[x + 1][y]);
        if(x + y < n) dfs1(x, y + 1, v ^ a[x][y + 1]);
    }
}

void dfs2(int x, int y, int v) {
    if(x + y == n) {
        ans += f[x][y][v ^ a[x][y]];
        return ;
    }
    else {
        if(x + y > n) dfs2(x - 1, y, v ^ a[x - 1][y]);
        if(x + y > n) dfs2(x, y - 1, v ^ a[x][y - 1]);
    }
}

signed main() {
    cin >> n;
    for(int i = 1; i <= n ; i ++ )
        for(int j = 1; j <= n ; j ++ )
            cin >> a[i][j];

    dfs1(1, 1, a[1][1]);
    dfs2(n, n, a[n][n]);

    cout << ans << endl;
}