首页 程序设计 AtCoder

# C

# 题目大意

有 NN 个多米诺骨牌，第 ii 个骨牌的大小是 sis_i
把部分骨牌排成一行然后推导，当第 ii 个骨牌向右倒时，如果它右边的骨牌的大小不超过 2si2s_i，那么右边这个也会倒下，你需要选择两个或者更多骨牌，从而满足

  • 最左侧骨牌是第一个
  • 最右侧骨牌是第 NN 个
  • 推到最左侧的骨牌，最右侧的骨牌也会倒下

请问，是否存在满足上述要求的排列？如果存在，最少要几块骨牌？

# 数据范围

  • 1≤T≤1051 \le T \le 10^5
  • 2≤N≤2×1052 \le N \le 2 \times 10^5

# 题解

初始时，fir=s[1],lst=s[n]fir=s[1],lst=s[n]
最优解肯定是，每次找的时候，找 ≤fir×2\le fir \times 2 的最大的那个，用二分去找即可

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, fir, lst, res = 0;
vector<int> s;

int find(int l, int r, int x) {
    while (l < r) {
        int mid = l + r + 1 >> 1;

        if (s[mid] > x)
            r = mid - 1;
        else
            l = mid;
    }

    return (s[l] <= x ? l : -1);
}

void solve () {
    vector<int> ss;
    cin >> n >> fir, s = ss;
    for (int i = 2, x; i < n; i++)
        cin >> x, s.push_back(x);
    cin >> lst, res = 2;

    sort(s.begin(), s.end());

    int l = 0, r = s.size() - 1, maxx;

    while (fir * 2 < lst) {
        if (l > r) {
            cout << -1 << '\n';
            return;
        }

        maxx = fir * 2;

        int li = find(l, r, maxx);

        if (li == -1) {
            cout << -1 << '\n';
            return;
        }

        res++, fir = s[li], l = li + 1;
    }

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

# D

# 题目大意

有一个 NN 个点，MM 条边的无向图，你可以任意执行一下两种操作

  • 加一条边
  • 删一条边

问，将 GG 变为所有点度数都为 22 的无向图（无重边、自环）的最小操作次数

# 数据范围

  • 3≤N≤83 \le N \le 8
  • 0 \le M \le \frac{N(N-1)}

# 题解

暴搜

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
49
50
51
52
int n, m, u, v, res = 1e18;
vector<vector<int>> init_g, g;
vector<int> ds;

void dfs(int u) {
    if (u == n + 1) {
        int x = 0, y = 0;
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                if (g[i][j]) {
                    if (init_g[i][j] == 1)
                        x++;
                    else
                        y++;
                }

        res = min(res, m + y - x);
        return;
    }

    if (ds[u] == 2)
        dfs(u + 1);
    else if (ds[u] == 1) {
        for (int to = u + 1; to <= n; to++)
            if (ds[to] != 2) {
                ds[to]++, ds[u]++, g[u][to] = g[to][u] = 1;
                dfs(u + 1);
                g[u][to] = g[to][u] = 0, ds[to]--, ds[u]--;
            }
    }
    else {
        for (int to1 = u + 1; to1 <= n; to1++)
            for (int to2 = to1 + 1; to2 <= n; to2++)
                if (ds[to1] != 2 && ds[to2] != 2) {
                    ds[u] += 2, ds[to1]++, ds[to2]++, g[u][to1] = g[to1][u] = g[u][to2] = g[to2][u] = 1;
                    dfs(u + 1);
                    ds[u] -= 2, ds[to1]--, ds[to2]--, g[u][to1] = g[to1][u] = g[u][to2] = g[to2][u] = 0;
                }
    }
}

void solve () {
    cin >> n >> m;
    init_g = vector<vector<int>>(n + 1, vector<int>(n + 1));
    g = vector<vector<int>>(n + 1, vector<int>(n + 1)), ds = vector<int>(n + 1);
    for (int i = 1; i <= m; i++)
        cin >> u >> v, init_g[u][v] = init_g[v][u] = 1;

    dfs(1);

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

这题提供了一个在图中暴搜的新思路
如果正面考虑问题较难，我们不妨暴搜的方向改为：直接构造出一个新图
通过对比新图和原有图，得出相关结论

更新于 阅读次数 次

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

duoxichangan 微信支付

微信支付

duoxichangan 支付宝

支付宝