abc271 A-F 题解

AtCoder-Beginner-Contest-271 A-F

A - 484558

输出一个十进制数的十六进制表示（两位数），记得补0

#include <bits/stdc++.h>

using namespace std;
char c[] = {'A', 'B', 'C', 'D', 'E', 'F'};

int main () {
    int n;
    cin >> n;
    int a = n / 16, b = n % 16;
    if (a < 10)     cout << a;
    else    cout << c[a-10];
    if (b < 10)     cout << b;
    else    cout << c[b-10];
}

// exactly two-digit hexadecimal numeral,

B - Maintain Multiple Sequences

输出第n行第m列的数

#include <bits/stdc++.h>

using namespace std;

int main () {
    int n, m;
    cin >> n >> m;
    vector <int> v[n];
    for (int i = 0; i < n; i++) {
        int len;
        cin >> len;
        while (len--) {
            int x;
            cin >> x;
            v[i].push_back (x);
        }
    }
    while (m --) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        cout << v[a][b] << endl;
    }
}

C - Manga

题意

按顺序 1,2,3,…n 读取序列，如果读到断开的地方，可以从序列中移走两个数，然后补上这个空位，问最多能读取多少书

分析

先把序列中小于等于n的存下来（因为是有可能被读取到的），读到中断的地方就把当前位置以及序列末尾的挪走（一种贪心的最优策略）。

#include <bits/stdc++.h>

using namespace std;
const int N = 3e5 + 5;
bool a[N];

int main () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x <= n) a[x] = true;
    }
    for (int i = 1; i <= n; i++) {
        if (!a[i])  n --;
    }
    cout << n;
}

D - Flip and Adjust

题意

n 张卡片，正反两面都是有数字，现在任意翻转摆放这 n 张卡片，问存不存在一种方案，使得正面和为 s

分析

dp[i][j]: 选到第 i 张卡，总和为 j 的情况是否存在

依次转移，方案输出就是倒着推回去

#include <bits/stdc++.h>

using namespace std;
const int N = 105, M = 10005;
int a[N], b[N], n, m;
int f[N][M]; 

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)    cin >> a[i] >> b[i];
    memset (f, -1, sizeof f);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (f[i-1][j] == 1) {
                f[i][j+a[i]] = 1;
                f[i][j+b[i]] = 1;
            }
        }
    }
    if (f[n][m] == 1) {
        puts ("Yes");
        string s;
        if (f[n-1][m-a[n]] == 1)    m -= a[n], s += 'H';
        else    m -= b[n], s += 'T';
        for (int i = n - 1, j = m; i >= 1; i--) {
            if (f[i][j] == 1 &&  f[i - 1][j - a[i]] == 1)     s += 'H', j -= a[i]; 
            else if (f[i][j] == 1 &&  f[i - 1][j - b[i]] == 1)   s += 'T', j -= b[i];
        }
        reverse (s.begin (), s.end ());
        cout << s;
    }
    else    puts ("No");
}

E - Subsequence Path

题意

现在有 n 个点, m 条带权有向边，现在我们给定一个序列 E 。现在要找一条 1-n 的，满足是 E 子集的最短路径。

分析

松弛只会变小，全松弛一遍就是最优

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
long long f[N], a[N], b[N], w[N];

int main () {
    int n, m, k;
    cin >> n >> m >> k;
    memset (f, 0x3f, sizeof f);
    f[1] = 0;
    for (int i = 1; i <= m; i++)    cin >> a[i] >> b[i] >> w[i];
    for (int i = 1; i <= k; i++) {
        int x;
        cin >> x;
        f[b[x]] = min (f[b[x]], f[a[x]] + w[x]);
    }
    if (f[n] == f[0])     f[n] = -1;
    cout << f[n];
}
//松弛只会变小
//全松弛一遍就是最优

F - XOR on Grid Path

题意

有一个n *n 的地图，从 (1, 1) 走到 (n, n)，每次只能向下或者向右走，问异或和为0的路径有多少条。

分析

n <= 20, 考虑爆搜，稍微优化：双向搜索（从两头开始搜， meet int the middle）

关于和的顺序问题：整个dfs过程看作一个栈，相当于是把两头合并在一起，所以sum错开来取即可，就是只加一次

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 25;
int a[N][N], n, ans;
map <int, int> f[N];

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

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

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, 0), dfs2 (n, n, 0);
    cout << ans;
}