首页 程序设计 AtCoder

# B

# 题目大意

有两个网格 S,TS, T，每个网格都是 NN 行 NN 列
每个单元格都被涂成白 / 黑色，单元格是 . 就是白色，是 # 就是黑色
你可以进行下面两种操作任意次

  • 选中 SS 中的一个格子，反转颜色
  • 将 SS 顺时针旋转 90°90°

请问至少要多少次操作，才能使 SS 和 TT 变成一样的？

# 数据范围

  • 1≤n≤1001 \le n \le 100

# 题解

考虑四种旋转后，与 TT 图的差异即可，需要注意的是，这四次旋转需要的 22 操作次数是不一样的

C++
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
int calDif() {
    int dif = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dif += (c[i][j] != b[i][j]);
    return dif;
}

void solve () {
    cin >> n;
    a = vector<vector<char>>(n + 1, vector<char>(n + 1));
    b = vector<vector<char>>(n + 1, vector<char>(n + 1));
    c = vector<vector<char>>(n + 1, vector<char>(n + 1));

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

    int t[5];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            c[i][j] = a[i][j];
    t[0] = calDif();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            c[i][j] = a[n - j + 1][i];
    t[1] = calDif();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            c[i][j] = a[n - i + 1][n - j + 1];
    t[2] = calDif();

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            c[i][j] = a[j][n - i + 1];
    t[3] = calDif();

    int res = 1e18;
    for (int i = 0; i < 4; i++)
        res = min(res, i + t[i]);
    cout << res << '\n';
}

# C

# 题目大意

给你一个 NN 个点 MM 条边的无向图，请你判断这个图是否是循环图

循环图的定义
对于一个图，若存在 (1,2,...,N)(1,2,...,N) 的一个排列 (v1,v2,...,vN)(v_1,v_2,...,v_N) 满足

  1. 对于每个i=1,2,...,N−1i = 1,2,...,N-1，viv_i 和 vi+1v_{i+1} 之间有一条边
  2. v1v_1 和 vNv_N 直接有一条边
  3. 不存在其他边

那么就称这个图为循环图

# 数据范围

  • 3≤N≤2×1053 \le N \le 2 \times 10^5
  • 0≤M≤2×1050 \le M \le 2 \times 10^5

# 题解

3. 不存在其他边 这个条件，要求此时 n == m
如果是一个环图，那么每个点一定只有两个方向能走，也就是说， g[i].size()==0 ；并且任意从一点开始深搜，如果能搜到 nn 个点（在 n == m 的前提条件下），那么一定是个环图

C++
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
int n, m, cnt = 1;
vector<int> g[N];
vector<bool> st(N);

void dfs(int u) {
    for (int t : g[u])
        if (!st[t])
            st[t] = 1, cnt++, dfs(t);
}

void solve () {
    cin >> n >> m;

    for (int i = 1, a, b; i <= m; i++) {
        cin >> a >> b;
        g[a].push_back(b), g[b].push_back(a);
    }

    if (m != n) {
        cout << "No\n";
        return;
    }
    
    for (int i = 1; i <= n; i++)
        if (g[i].size() != 2) {
            cout << "No\n";
            return;
        }

    st[1] = 1, dfs(1);

    cout << (cnt == n ? "Yes" : "No") << '\n';
}

# D

# 题目大意

有 NN 个动物园，第 ii 个动物园的门票是 CiC_i 元
你喜欢 MM 种动物，1,2,...,M1,2,...,M，第 ii 种动物在 KiK_i 个动物园中被展出，分别是 Ai,1,...,Ai,KiA_{i,1},...,A_{i,K_i}
看完你喜欢的所有动物（每种看两次），最少要花多少钱

# 数据范围

  • 1≤N≤101 \le N \le 10
  • 1≤M≤1001 \le M \le 100
  • 0≤ci≤1090 \le c_i \le 10^9

# 题解

观察数据范围，可以看到 NN 很小，考虑暴力 DFSDFS

c++
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
int n, m, cost = 1e18;
vector<int> c, cnt;
vector<int> g[N];

void dfs(int u, int spend) {
    if (u == n + 1) {
        for (int i = 1; i <= m; i++)
            if (cnt[i] < 2)
                return;
        
        cost = min(cost, spend);
        return;
    }

    // 第 i 所动物园看 1 次
    for (int t : g[u])
        cnt[t]++;
    dfs(u + 1, spend + c[u]);

    // 第 i 所动物园看 2 次
    for (int t : g[u])
        cnt[t]++;
    dfs(u + 1, spend + 2 * c[u]);

    // 第 i 所动物园不看
    for (int t : g[u])
        cnt[t] -= 2;
    dfs(u + 1, spend);
}

void solve () {
    cin >> n >> m;
    c = vector<int>(n + 1), cnt = vector<int>(m + 1);

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

        while (k--) {
            cin >> a;   // 第 i 种动物可以在 a 动物园看到
            g[a].push_back(i);
        }
    }
    dfs(1, 0);
    cout << cost << '\n';
}

# E

# 题目大意

你有 NN 个茶碗，它们排成一排，编号为 0,1,...,N−10,1,...,N-1
对于 11 号碗和其右边的碗，第 ii 个碗上写着 CiC_i，里面装了 AiA_i 个豆子，00 号碗没写数字，没装豆子
你将执行以下操作若干次

  • 选择一个写了数字的、有豆子的碗，拿走若干个豆子
  • 把拿出的豆子任意放入 i−Ci,i−Ci+1,...,i−1i-C_i,i-C_i+1,...,i-1 号碗里

请问，将所有豆子放入 00 号碗，最少需要操作多少次？

# 数据范围

  • 1≤N≤20001 \le N \le 2000

# 题解

这题考虑贪心写法

  • 尽可能把豆子往左送 →\to j - c[j] < idx - c[idx]
  • 如果 i - c[i] -> i - 1 内，有 ai≠0a_i \neq 0 的点，那么往这个有豆子的点上送

C++
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
void solve () {
    cin >> n;
    vector<int> c(n + 1), a(n + 1);

    for (int i = 1; i <= n - 1; i++)
        cin >> c[i];
    for (int i = 1; i <= n - 1; i++)
        cin >> a[i];

    int res = 0;

    for (int i = n - 1; i >= 1; i--) {
        if (a[i]) {
            res++;

            bool flag = true;
            int t = -1;

            for (int idx = i - c[i]; idx <= i - 1; idx++) {
                if (a[idx]) {
                    flag = 0;
                    break;
                }

                if (t == -1 || idx - c[idx] < t - c[t])
                    t = idx;
            }

            if (flag)
                a[t] += a[i];
        }
    }

    cout << res << '\n';
}

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

duoxichangan 微信支付

微信支付

duoxichangan 支付宝

支付宝