首页 程序设计 AtCoder

# A

水题

C++
1
2
3
4
5
6
7
void solve () {
    cin >> n >> s >> t;
    for (int i = 0; i < s.size(); i++)
        if (s[i] != t[i])
            cnt++;
    cout << cnt;
}

# B

水题，就是个排名问题

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
int n, p[N];
PII peo[N];

bool cmp1(PII x, PII y) {
    return p[x.first] > p[y.first];
}

bool cmp2(PII x, PII y) {
    return x.first < y.first;
}

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i], peo[i].first = i;

    sort(peo + 1, peo + n + 1, cmp1);

    int rank = 0, cnt = 1, last = 0;

    while (cnt <= n) {
        if (p[peo[cnt].first] == last)
            peo[cnt++].second = rank;
        else
            last = p[peo[cnt].first], peo[cnt].second = cnt, rank = cnt++;
    }

    sort(peo + 1, peo + n + 1, cmp2);

    for (int i = 1; i <= n; i++)
        cout << peo[i].second << endl;
}

# C

# 题目大意

给你一个无向图，问要删除多少条边才能使得图中不存在环？

# 题解

考察并查集的题目，对于新进的一条边

  • 如果两个端点在一个集合中，则这条边需被删去
  • 如果不在，则是有效边
    计算被删去的边的数量即可
    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
    int n, f[N], m, a, b;

    int find(int x) {
        if (x != f[x])
            f[x] = find(f[x]);
        return f[x];
    }

    void solve () {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
            f[i] = i;

        int cnt = 0;

        while (m--) {
            cin >> a >> b;
            int fa = find(a), fb = find(b);
            
            if (fa == fb)
                cnt++;
            else
                f[fa] = fb;
        }

        cout << cnt << endl;
    }

# D

# 题目大意

毁了，理解题目大意用了半年
给定一个 nn，和序列 A=(a1,...a2N)A=(a_1,...a_{2N})，其中每个 1,...,n1,...,n 都出现两次
问，能找到多少对情侣对 (a,b)(a,b)

情侣对是什么？
  • 在原序列中，a,ba,b 的两个出现位置不邻接
  • 可以通过交换这四个数的位置，使得 a,ba,b 分别的两个数邻接

# 题解

# 错解

只考虑了不连在一起的情况，但对于 1 2 1 2 3 4 3 4 这样的， 1 2 1 2 就会被算 1 2 ， 2 1 ， 1 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
int n, peo[N];

void solve () {
    cin >> n;
    vector<vector<int>> g(n + 10);
    
    for (int i = 1; i <= 2 * n; i++) {
        cin >> peo[i];
        g[peo[i]].push_back(i);
    }

    int cnt = 0;

    for (int i = 1; i <= 2 * n - 1; i++) {
        int a = peo[i], b = peo[i + 1];
        
        if (a == b)
            continue;

        int l1 = g[a][0], l2 = g[a][1], r1 = g[b][0], r2 = g[b][1];
        
        if (l1 + 1 == l2 || r1 + 1 == r2)
            continue;

        if (abs(l1 - r1) == 1 && abs(l2 - r2) == 1)
            cnt++;
    }

    cout << cnt / 2 << endl;
    return;
}

# 正解

为了避免上面的情况，可以利用

C++
1
2
3
vector<int> kk = {l1, l2, r1, r2};
sort(kk.begin(), kk.end());
res.insert({min(a, b), max(a, b)}); // res 是 set

统计不同数对，时间复杂度也是在可接受的范围之内
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
int n, peo[N];

void solve () {
    cin >> n;
    
    vector<vector<int>> g(n + 10);
    set<PII> res;

    for (int i = 1; i <= 2 * n; i++) {
        cin >> peo[i];
        g[peo[i]].push_back(i);
    }

    int cnt = 0;

    for (int i = 1; i <= 2 * n - 1; i++) {
        int a = peo[i], b = peo[i + 1];
        int l1 = g[a][0], l2 = g[a][1], r1 = g[b][0], r2 = g[b][1];
        
        if (a == b || l1 + 1 == l2 || r1 + 1 == r2)
            continue;

        vector<int> kk = {l1, l2, r1, r2};
        sort(kk.begin(), kk.end());
        
        if (kk[0] + 1 == kk[1] && kk[2] + 1 == kk[3])
            res.insert({min(a, b), max(a, b)});
    }

    cout << res.size() << endl;
    return;
}

还需要多注意的是，题目数据范围到了 1e51e5，一开始用的 vector<int> g[N] 结果直接爆了，能开 vector<vector<int>> g(n + 1) 还是尽可能用后者吧

# E

更新于 阅读次数 次

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

duoxichangan 微信支付

微信支付

duoxichangan 支付宝

支付宝