Atcoder ABC399游记（A~D）

今天d题什么情况啊 有点意思哈 极限通过

。。。今天掉了7分 这个d题在还剩20秒时居然过了 我对拍瞅了半天test代码发现没问题 结果最后上了个厕所就突发奇想看了bf程序，结果：

1
2
3
4
if (abs(pos[i].first - pos[j].first) == 1 && abs(pos[i].second - pos[j].second) == 1 && pos[i].second - pos[i].first > 1 && pos[j].second - pos[j].first > 1) {
            cout << i << ' ' << j << '\n';
            ans++;
}
1
2
3
4
if (abs(pos[i].first - pos[j].first) == 1 && abs(pos[i].second - pos[j].second) == 1 && pos[i].second - pos[i].first > 1 && pos[j].second - pos[j].second > 1) {
                cout << i << ' ' << j << '\n';
                ans++;
            }

小朋友们来玩找不同吧 看看第一个代码和第二个代码有什么不同

。。。

看出来了吗 就是第一行pos[j].second应该是pos[j].first才对，结果当时一个屏幕没显示完，愣是到了最后两分钟时才发现

然后我就赶紧拍了一下，在剩一分钟的时候发现这个测试点：

1
2
3
1
5
3 3 2 5 1 4 5 1 4 2

bf代码输出2 test代码输出1，少数了1 5这一对

然后我就一看，发现test有这个代码：

1
2
3
if (a[i] >= a[i + 1]) {
    continue;
}

啊哈 被误导了 悲 于是我没有多想赶紧删了 这个时候只剩20秒

然后我交了 居然过了（

qp默哀

1

…对拍万岁 遇事不决就对拍 起床对拍 吃饭对拍 睡觉对拍 头疼了也可以对拍 万物皆可对拍

A.Hamming Distance

题目描述

给你两个字符串，回答它们有几个位置对应的字符不同。

思路

水

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    string s, t;
    cin >> n >> s >> t;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans += (s[i] != t[i]);
    }
    cout << ans;
    return 0;
}

B.Ranking with Ties

题目描述

有NN个人，编号分别为1,2,...,N1,2,...,N。

给你一个长度为NN的数组P=(P1,P2,...PN)P=(P_1,P_2,...P_N)，其中编号为ii的人的分数为PiP_i。

这NN个人的排名按照下面的方法得到：

  1. 定义一个整数r=1r=1，最初所有NN个人的排名都是不确定的。

  2. 重复执行这个操作直到所有人的排名都确定了：

  • 让xx为所有未确定的人中分数的最大值，然后所有分数为xx的kk个人的排名都被确定为rr，然后把rr加上kk。

分别输出这NN个人的排名。

思路

水

代码

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
#include<bits/stdc++.h>
using namespace std;
int ans[111];
int main()
{
    memset(ans, -1, sizeof(ans));
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int cnt = 0;
    int r = 1;
    while (cnt < n) {
        int maxx = -1, k = 0;
        vector<int> tp;
        for (int i = 0; i < n; i++) {
            if (ans[i] != -1) {
                continue;
            }
            if (a[i] > maxx) {
                k = 1;
                tp.clear();
                tp.push_back(i);
                maxx = a[i];
            } else if (a[i] == maxx) {
                k++;
                tp.push_back(i);
            }
        }
        cnt += tp.size();
        for (int i = 0; i < tp.size(); i++) {
            ans[tp[i]] = r;
        }
        r += k;
    }
    for (int i = 0; i < n; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

C.Make it Forest

题目描述

给你一个无向简单图，请问最少删除几条边可以使得这个图变成森林？

思路

并查集搞定啦

代码

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
#include<bits/stdc++.h>
using namespace std;
int fa[222222];
int n, m;
void init()
{
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}
int find(int x)
{
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
    x = find(x);
    y = find(y);
    fa[x] = y;
}
bool same(int x, int y)
{
    x = find(x);
    y = find(y);
    return x == y;
}
int main()
{
    cin >> n >> m;
    init();
    int ans = 0;
    while (m--) {
        int u, v;
        cin >> u >> v;
        if (same(u, v)) {
            ans++;
        } else {
            merge(u, v);
        }
    }
    cout << ans;
    return 0;
}

D.Switch Seats

题目描述

NN对来自不同平行世界的穹&悠坐在一排上。
计算有多少成对的穹&悠满足这两对内部都不相邻但是可以通过在这四人中调换位置来满足两对穹&悠内部都相邻。

给你一个长度为2N2N的序列，内部元素都介于11到NN之间，并且对于每个1≤i≤N1 \leq i \leq N，满足在序列中正好出现了22次。

找到整数对(a,b)(a,b)满足1≤a,b≤N1 \leq a,b \leq N和以下条件的数量：

  • 在序列中的两个aa不相邻

  • 在序列中的两个bb不相邻

  • 可以在原序列中更改两个元素的位置来满足两个aa相邻，两个bb相邻。

思路

atcoderrnmtq

这题很惊险，具体怎么惊险看写在文章前的东西吧。

这里就说思路了

首先我们可以观察到序列的长度最大到200000200000，所以要动动脑子。

不难想到，满足条件的整数对(a,b)(a,b)一定在序列中存在两对(a,b)(a,b)或(b,a)(b,a)。

所以我们通过map来存储对于每个会在数组里出现的ii的两个位置，然后每次检查相邻的两个元素，满足这两个元素不同，并且这两个元素所对应的另一个元素相邻，就可以增加ans了

。。。

死去元知万事空（不喜勿喷

历经苦痛和对拍写出的代码

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
#include<bits/stdc++.h>
using namespace std;
map<int, pair<int, int>> mp;
int nex(int x, int pos)
{
    if (mp[x].first == pos) {
        return mp[x].second;
    } else {
        return mp[x].first;
    }
}
bool check(int x, int y)
{
    if (x > y) {
        swap(x, y);
    }
    return x + 1 == y;
}
void solve()
{
    int n;
    cin >> n;
    n *= 2;
    vector<int> a(n);
    for (int i = 1; i <= n; i++) {
        mp[i] = {-1, -1};
    }
    map<pair<int, int>, bool> ch;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (mp[a[i]].first == -1) {
            mp[a[i]].first = i;
        } else {
            mp[a[i]].second = i;
        }
    }
    int ans = 0;
    for (int i = 0; i < n - 1; i++) {
        if (abs(i - nex(a[i], i)) == 1 || abs(i + 1 - nex(a[i + 1], i + 1)) == 1) {
            continue;
        }
        if (check(nex(a[i], i), nex(a[i + 1], i + 1))) {
            if (ch[{a[i], a[i + 1]}] != 1) {
                ch[{a[i], a[i + 1]}] = 1;
                ch[{a[i + 1], a[i]}] = 1;
                ans++;
            }
        }
    }
    cout << ans << '\n';
}
int main()
{
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

总结

对拍真是个好东西啊 我爱对拍好吧

6 f题能暴力 没想到 乐