首页 程序设计 AtCoder

# B

# 题目大意

给你一个由 . # 组成的字符串，现在要求你找出一个字符串 TT，要求你把给定字符串的 . 变为 o ，要求，对于任意两个 o ，之间至少有一个 # ，整个字符串中只有一个 o 也是合法的，找出 o 最多的 TT

# 数据范围

  • 1≤∣S∣≤1001 \le |S| \le 100

# 题解

需要特别注意 ....... ， #####...... ， #######......### 这几种情况

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
void solve () {
    cin >> s, n = s.size(), s = " " + s, pre = vector<int>(s.size() + 10);
    for (int i = 1; i <= n; i++)
        cnt += (s[i] == '#');

    int r = n;

    if (cnt == 0) {
        s[1] = 'o';
        cout << s.substr(1) << '\n';
        return;
    }

    for (int i = 2; i <= n; i++)
        if (s[i] == '#' && s[i - 1] == '.')
            s[i - 1] = 'o';

    while (r - 1 >= 1 && s[r - 1] != '#' && s[r] == '.')
        r--;

    if (s[r] == '.' && s[r - 1] == '#')
        s[r] = 'o';

    for (int i = 1; i <= n; i++)
        cout << s[i];
    cout << '\n';
}

# C

比 BB 简单

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs(int u, string t) {
    if (u == k + 1) {
        res.push_back(t);
        return;
    }

    for (int i = 1; i <= n; i++)
        dfs(u + 1, t + s[i]);
}

void solve () {
    cin >> n >> k >> x, s = vector<string>(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> s[i];

    dfs(1, "");

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

    cout << res[x - 1] << '\n';
}

# D

# 题目大意

有长度为 nn 的序列 a1,...,ana_1,...,a_n 和 b1,...,bnb_1,...,b_n，还有一个正整数 mm，你可以随意排列 aa 中的元素，请你求出 min(∑i=1n((ai+bi)%m))min (\sum\limits_{i=1}^{n}((a_i+b_i) \% m))

# 数据范围

  • 1≤T≤1051 \le T \le 10^5
  • 1≤n≤3×1051 \le n \le 3 \times 10^5
  • 1≤m≤1091 \le m \le 10^9
  • 0≤ai,bi<m0 \le a_i,b_i < m

# 题解

题目中有个很重要的信息不能忽略：0≤ai,bi<m0 \le a_i, b_i < m，这也就是说，ai+bi<2ma_i+b_i < 2m 一定成立

ai+bi={ai+bi(ai+bi<m)ai+bi(m≤ai+bi<2m)a_i+b_i=\begin{cases}a_i+b_i & (a_i+b_i < m) \\ a_i+b_i & (m \le a_i+b_i <2m)\end{cases}

那么式子可以化为

∑i=1n((ai+bi)%m)=(∑i=1n(ai+bi))−t∗m\sum\limits_{i=1}^{n}((a_i+b_i) \% m)=(\sum\limits_{i=1}^{n}(a_i+b_i))-t*m

我们是要求最小，也就是说，我们可以让 tt 最大即可
那我们只需要把 aa 降序排列，bb 升序排列，从 a1a_1 开始匹配，尽可能让 aia_i 拿到更小的 bjb_j 从而使得 ai+bj>ma_i+b_j > m，算出 tt 的值即可

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
void solve () {
    cin >> n >> m, a = vector<int>(n + 1), b = vector<int>(n + 1), res = 0;

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

    sort(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end(), [](int x, int y)
         { return x > y; });

    int i = 1, j = 1, t = 0;

    while (i <= n) {
        while (j <= n && a[i] + a[j] < m)
            j++;
        
        if (j > n)
            break;

        i++, j++, t++;
    }

    cout << res - t * m << '\n';
}

# E

# 题目大意

有 nn 个城市，mm 条道路（双向道路），kk 个机场
第 ii 条路连接 AiA_i 和 BiB_i，通行时间为 CiC_i
机场位于 D1,...,DkD_1,...,D_k，有机场的两个城市可以在 TT 时间内互相抵达

现有 QQ 个查询

  • 1 x y t ：在 xx 和 yy 之间新建一条双向道路，通行时间为 tt
  • 2 x ：在 xx 新建一个机场
  • 3 ：记 f(x,y)f(x,y) 为从 xx 到 yy 通过道路和机场可以到达的最短时间，不可到达时为 00。请计算 ∑x=1n∑y=1nf(x,y)\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{n}f(x,y)

# 题解

  • 1≤n≤5001 \le n \le 500
  • 1≤m≤1051 \le m \le 10^5
  • 1≤Ai<Bi≤n1 \le A_i < B_i \le n
  • 1≤Ci≤1091 \le C_i \le 10^9
  • 0≤K≤n0 \le K \le n
  • 1≤T≤1091 \le T \le 10^9
  • 1≤D1<...<DK≤n1 \le D_1 < ... < D_K \le n
  • 1≤Q≤10001 \le Q \le 1000

# 题解

# 错解 - TLE

QQ 次查询，一次 FloydFloyd 是 n3n^3 级别的，O(Q⋅n3)O(Q·n^3) 直接爆炸了

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
53
54
55
56
int floyd() {
    vector<vector<int>> gg(n + 1, vector<int>(n + 1, INF));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            gg[i][j] = (i == j ? 0 : g[i][j]);
    
    for (int mid = 1; mid <= n; mid++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (gg[i][mid] != INF && gg[mid][j] != INF)
                    gg[i][j] = min(gg[i][j], gg[i][mid] + gg[mid][j]);

    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            res += (gg[i][j] == INF ? 0 : gg[i][j]);

    return res;
}

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

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

    cin >> k >> T;

    for (int i = 0, dd; i < k; i++) {
        cin >> dd;
        for (int j = 0; j < (int)d.size(); j++)
            g[d[j]][dd] = g[dd][d[j]] = min(g[d[j]][dd], T);
        d.push_back(dd);
    }

    cin >> q;
    while (q--) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> t;
            g[x][y] = g[y][x] = min(g[x][y], t);
        }
        else if (op == 2) {
            cin >> x;
            for (int i = 0; i < d.size(); i++)
                g[x][d[i]] = g[d[i]][x] = min(g[x][d[i]], T);
            d.push_back(x);
        }
        else {
            cout << floyd() << '\n';
        }
    }
}

# 正解 - 优化

我们先考虑飞机场如何优化，显然，如果按照上面的暴力写法的话，每次都要给新建机场的点，和已经有机场的所有点直接，都连一条边，我们不妨这样想，既然有机场之间的城市是 TT 时间到达，我们是不是能建立一个虚点，让每个机场到虚点的距离都是 T2\frac{T}{2} 呢

此处提出 虚点 的想法：即为，如果存在有多个相互能等代价到达（TT）的点，那么不妨建立一个新点，让其到每个点的距离为 T2\frac{T}{2}，这样我们每次只需要给新加入的点和 虚点 直接连接起来即可，大大减小了时间复杂度

引入上面的虚点概念后，我们的操作 11 和操作 22 就均为添加一条边了

加边之后，最短路有变化的就是经过这条边的路径，所以我们只需要枚举起点和终点，然后用经过这条边的路径更新值即可，重要关注 updateupdate 部分

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
53
54
55
56
57
58
59
60
61
62
63
64
65
void floyd() {
    for (int mid = 1; mid <= n + 1; mid++)
        for (int i = 1; i <= n + 1; i++)
            for (int j = 1; j <= n + 1; j++)
                    g[i][j] = min(g[i][j], g[i][mid] + g[mid][j]);
}

void update(int x, int y, int val) {
    for (int i = 1; i <= n + 1; i++)
        for (int j = 1; j <= n + 1; j++)
            g[i][j] = min(g[i][j], min(g[i][x] + g[y][j], g[i][y] + g[x][j]) + val);
}

void solve() {
    cin >> n >> m;
    g = vector<vector<int>>(n + 2, vector<int>(n + 2, INF)), st = vector<bool>(n + 2);

    for (int i = 1; i <= n + 1; i++)
        g[i][i] = 0;

    for (int i = 1, a, b, c; i <= m; i++) {
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c * 2);
    }

    cin >> k >> T;

    for (int i = 0, d; i < k; i++) {
        cin >> d, st[d] = 1;
        g[d][n + 1] = g[n + 1][d] = T;
    }

    floyd();

    cin >> q;
    while (q--) {
        cin >> op;
        if (op == 1) {
            cin >> x >> y >> t, t *= 2;
            g[x][y] = g[y][x] = min(g[x][y], t);
            
            update(x, y, t);
        }
        else if (op == 2) {
            cin >> x;

            if (st[x])
                continue;

            st[x] = 1, g[x][n + 1] = g[n + 1][x] = T;

            update(x, n + 1, T);
        }
        else {
            int res = 0;

            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (g[i][j] < INF)
                        res += g[i][j];
            
            cout << res / 2 << '\n';
        }
    }
}

更新于 阅读次数 次

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

duoxichangan 微信支付

微信支付

duoxichangan 支付宝

支付宝