AtCoder Beginner Contest 211题解

传送门：AtCoder Beginner Contest 211

A. Blood Pressure

题意：给了AA和BB，算CC。C=A−B3+BC = \frac{A - B}{3} + B。

思路：暴力，注意浮点数。

1
2
3
4
5
6
7
8
#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b; scanf("%d%d", &a, &b);
    printf("%.10f\n", (a - b) / 3.0 + (double)b);
    return 0;
}

B. Cycle Hit

题意：给了四个字符串，判断它们是否为H,2B,3B,HRH, 2B, 3B, HR四个字符串。

思路：暴力。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int main() {
    set<string> st;
    st.insert("H");
    st.insert("2B");
    st.insert("3B");
    st.insert("HR");
    set<string> st2;
    for (int i = 0; i < 4; i++) {
        string s; cin >> s;
        st2.insert(s);
    }
    puts(st == st2 ? "Yes" : "No");
    return 0;
}

C. chokudai

题意：在一个字符串中按照chokudai的顺序选择8个字母有多少种选法。

思路：dp[i][j]={1(j=0)0(i=0,1≤j≤8)dp[i−1][j](1≤i≤N,1≤j≤8,S[i]≠T[j])dp[i−1][j]+dp[i−1][j−1](1≤i≤N,1≤j≤8,S[i]=T[j])\displaystyle dp[i][j] = \begin{cases} 1 & ( j = 0) \newline 0 & ( i=0 , 1 \leq j \leq 8) \newline dp[i-1][j]& ( 1 \leq i \leq N , 1\leq j \leq 8, S[i] \neq T[j] ) \newline dp[i-1][j] + dp[i-1][j-1] & (1 \leq i \leq N , 1\leq j \leq 8, S[i] = T[j])\end{cases}。

最后的答案位dp[N][8]dp[N][8]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll MOD = 1e9+7;
const int MAX = 1e5+50;
char s[MAX], t[10] = "chokudai";
int n;

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    map<char, ll> mp;
    for (int i = 1; i <= n; i++) {
        int pos = find(t, t + 8, s[i]) - t;
        if (pos == 8) continue;
        if (s[i] == 'c') ++mp['c'];
        else mp[s[i]] = (mp[s[i]] + mp[t[pos - 1]]) % MOD;
    }
    printf("%lld\n", mp['i'] % MOD);
    return 0;
}

D. Number of Shortest paths

题意：从11到nn的最短路有多少条。

思路：经典最短路变形，只需要在求最短路的同时更新cntcnt数组即可，初始化cnt[1]=1cnt[1] = 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll MOD = 1e9+7;
const int MAX = 2e5+50;
struct Edge {
    int v, next;
}es[MAX<<1];
int head[MAX], k, n, m;
int dis[MAX];
ll cnt[MAX];
bool vis[MAX];

void add(int u, int v) {
    es[++k].next = head[u]; es[k].v = v; head[u] = k;
    es[++k].next = head[v]; es[k].v = u; head[v] = k;
}

void dij() {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    q.push(make_pair(0, 1));
    dis[1] = 0;
    cnt[1] = 1;
    while (q.size()) {
        int u = q.top().second; q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = head[u]; i; i = es[i].next) {
            int v = es[i].v;
            if (!vis[v] && dis[v] > dis[u] + 1) {
                dis[v] = dis[u] + 1;
                cnt[v] = cnt[u];
                q.push(make_pair(dis[v], v));
            } else if (dis[v] == dis[u] + 1) {
                cnt[v] = (cnt[v] + cnt[u]) % MOD;
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d%d", &u, &v);
        add(u, v);
    }
    dij();
    printf("%lld\n", cnt[n]);
    return 0;
}

E. Red Polyomino

题意：有一个n×nn×n的地图，连续染kk个方块，有多少种方式。

思路：因为nn最多只有88，所以方法很多，如果直接进行dfsdfs不带剪枝会超时，有一种比较好理解的做法是将每次dfsdfs的图利用setset存起来，如果下次遇到直接返回。再优化一下可以将setset里放一个unsigned long longunsigned \ long \ long型的数字，代表整张地图，因为最多就6464位刚好存放的下。最快的做法是将该点的所有状态找完后将该点设置为#\#，再在新图上dfsdfs。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

set<vector<string>> st;
vector<string> s;
int f[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
int n, k, res;

void dfs(int now) {
    if (st.find(s) != st.end()) return;
    st.insert(s);
    if (now == k) return (void)(++res);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] != '.') continue;
            bool flag = false;
            for (int k = 0; k < 4 && !flag; k++) {
                int nx = i + f[k][0];
                int ny = j + f[k][1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && s[nx][ny] == '@') flag = true; 
            }
            if (!flag) continue;
            s[i][j] = '@';
            dfs(now + 1);
            s[i][j] = '.';
        }
    }
}

int main() {
    cin >> n >> k;
    s = vector<string>(n);
    for (auto& v: s) cin >> v;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == '.') {
                s[i][j] = '@';
                dfs(1);
                s[i][j] = '.';
            }
        }
    }
    cout << res << "\n";
    return 0;
}