AtCoder Beginner Contest 218

发表于2021-09-21更新于2023-09-15字数统计2.5k阅读时长26分

比赛链接

C Shapes

Description

题目链接
有两个 N * N 的 grid S 和 T（仅包含 * 和 #），问能否通过若干次 90° 旋转和平移操作使得两个 grid 相同。

Solution

90° 旋转 4 次，每次旋转后用最小矩形 Rs 框出 S 中的所有 #，用 Rt 框出 T 中所有 #。判断 Rs、Rt 是否相同。

Code

Shapes
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << endl
#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 202, MOD = 1e9 + 7;

int n;
char s[MAXN][MAXN], t[MAXN][MAXN];

bool equal() {
    int ups(1e9), downs(-1);
    int ls(1e9), rs(-1);
    int upt(1e9), downt(-1);
    int lt(1e9), rt(-1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (s[i][j] == '#') {
                ups = min(ups, i);
                ls = min(ls, j);
                rs = max(rs, j);
                downs = max(downs, i);
            }
            if (t[i][j] == '#') {
                upt = min(upt, i);
                lt = min(lt, j);
                rt = max(rt, j);
                downt = max(downt, i);
            }
        }

    if (downt - upt != downs - ups) return false;
    if (rs - ls != rt - lt) return false;

    for (int i = 0; i <= downt - upt; i++) {
        for (int j = 0; j <= rt - lt; j++)
            if (s[ups + i][ls + j] != t[upt + i][lt + j]) return false;
    }

    return true;
}

void rotate() {
    int tmp[MAXN][MAXN];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            tmp[i][j] = s[j][n - i + 1];
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            s[i][j] = tmp[i][j];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin.ignore(1, '\n');
        for (int j = 1; j <= n; j++)
            cin >> s[i][j];
    }
        
    for (int i = 1; i <= n; i++) {
        cin.ignore(1, '\n');
        for (int j = 1; j <= n; j++)
            cin >> t[i][j];
    }
  
    for (int i = 1; i <= 4; i++) {
        rotate();
        if (equal()) {
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
    return 0;
}

D Rectangles

Description

题目链接
给出 1≤N≤20001 \le N \le 2000 个互异点，求出这些点构成的边界与 xx 或 yy 轴平行的矩形个数。

Solution

如果一个矩形的左下角和右上角都确定了，那么该矩形也就确定了。因此只需要枚举两个顶点，然后通过 map 查找另外两个顶点是否存在即可。

Code

下给出 pair<int, int> 的哈希方法。

Rectangles
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
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << endl
#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

template <typename T>
inline void hash_combine(std::size_t &seed, const T &val) {
    seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// auxiliary generic functions to create a hash value using a seed
template <typename T> inline void hash_val(std::size_t &seed, const T &val) {
    hash_combine(seed, val);
}
template <typename T, typename... Types>
inline void hash_val(std::size_t &seed, const T &val, const Types &... args) {
    hash_combine(seed, val);
    hash_val(seed, args...);
}

template <typename... Types>
inline std::size_t hash_val(const Types &... args) {
    std::size_t seed = 0;
    hash_val(seed, args...);
    return seed;
}

struct pair_hash {
    template <class T1, class T2>
    std::size_t operator()(const std::pair<T1, T2> &p) const {
        return hash_val(p.first, p.second);
    }
};

unordered_map<pair<int, int>, bool, pair_hash> um;

int main() {
    boost;
    int n;
    cin >> n;
    vector<pair<int, int>> p(n);
    for (int i = 0; i < n; i++) cin >> p[i].first >> p[i].second, um[p[i]] = true;
    sort(p.begin(), p.end());
    int ans(0);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            if (p[i].first < p[j].first && p[i].second < p[j].second) {
                if (um.count({p[i].first, p[j].second}) &&
                    um.count({p[j].first, p[i].second}))
                    ans++;
            }
        }
    cout << ans << "\n";
    return 0;
}

E Destruction

Description

题目链接

Solution

问题等价于求出原图的最小生成树，用 ∑Ci>0\sum C_i>0 减去最小生成树中大于 0 的边权和。

Code

Destruction
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
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;

int n, m, fa[MAXN];

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

vector<tuple<int, int, int>> v;

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    v.resize(m);
    for (int i = 1; i <= n; i++) fa[i] = i;
    LL tot = 0;
    for (auto& [c, a, b] : v) {
        cin >> a >> b >> c;
        if (c > 0) tot += c;
    }
    sort(v.begin(), v.end());
    LL res = 0;
    for (auto& [c, a, b] : v) {
        int r1 = find(a), r2 = find(b);
        if (r1 != r2) {
            fa[r2] = r1;
            if (c > 0) res += c;
        }
    }
    cout << tot - res;
    return 0;
}

F Blocked Roads

Description

题目链接
给出 2≤N≤4002\le N \le 400 个点，1≤M≤N(N−1)1\le M \le N(N-1) 条边的有向图，问删除边 i 后从 1 到 N 的最短路。

Solution

从 1 到 N 的最短路所经过的边数是 O(N)O(N) 的。对于不在最短路上的边，答案是最短路长度；否则重新跑最短路，遇到该边则跳过。

注意图一开始就不连通的情况。

Code

Blocked Roads
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
66
67
68
69
70
71
72
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << endl
#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 404, MOD = 1e9 + 7;

int n, m;
vector<pair<int, int>> g[MAXN];
pair<int, int> e[MAXN * MAXN];
int dis[MAXN];
bool inq[MAXN];

void spfa() {
    memset(dis, 0x3f, sizeof(dis));
    memset(inq, false, sizeof(inq));
    queue<int> q;
    q.push(1), dis[1] = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        inq[cur] = false;
        for (auto& [to, id] : g[cur]) {
            if (dis[to] > dis[cur] + 1) {
                dis[to] = dis[cur] + 1;
                if (!inq[to]) q.push(to), inq[to] = true;
            }
        }
    }
}

bool vis[MAXN];
int dis2[MAXN];
int bfs(int del) {
    memset(vis, false, sizeof(vis));
    queue<int> q;
    q.push(1), vis[1] = true, dis2[1] = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto& [to, id] : g[cur]) {
            if (id == del) continue;
            if (vis[to]) continue;
            dis2[to] = dis2[cur] + 1;
            q.push(to), vis[to] = true;
        }
    }
    if (!vis[n]) return -1;
    else return dis2[n];
}

int main() {
    boost;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> e[i].first >> e[i].second;
        g[e[i].first].emplace_back(e[i].second, i);
    }
    spfa();
    for (int i = 1; i <= m; i++) {
        int u = e[i].first, v = e[i].second;
        if (dis[v] == dis[u] + 1) {
            cout << bfs(i) << "\n";
        } else {
            if (dis[n] == 0x3f3f3f3f) cout << -1 << "\n";
            else cout << dis[n] << "\n";
        }
    }
    return 0;
}

G Game on Tree 2

Description

题目链接
给定一颗 N 个节点的树，每个点有一个奇数值 AiA_i。根节点 1 处有一个棋子，两个人轮流移动棋子到未被访问过的节点。将棋子所到的节点的值保存到 multisetmultiset，先手希望 mulitsetmulitset 的中位数尽可能大，后手希望中位数尽可能小。假设两人都按最有决策行动，问最后的中位数是多少。

Solution

可以发现棋子最终会从根节点一直走到叶子节点，并在叶子节点得出中位数的值。

如果能知道叶子节点中位数的值，那么根据 Min-Max 搜索，可以得到根节点移动的最有策略与最优值（即给每个节点一个估值，表示最终能得到的最优结果；先手会选择估值最大的子节点，后手会选择估值最小的子节点；叶子节点的估值为 multisetmultiset 的中位数）。

中位数可在 dfs 过程中通过两个 multisetmultiset 动态维护。当访问一个节点树，将其加入两个 multisetmultiset 中的一个；当删除一个节点时，将其从两个 multisetmultiset 中的一个删除；当访问叶子节点时，求出当前两个 multisetmultiset 的中位数即可。

需要保证两个 multisetmultiset 的大小差值不超过 1，即每次插入或删除操作后需要调整两个 multisetmultiset 的大小。

Code

Game on Tree 2
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << endl
#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 2e5 + 5, MOD = 1e9 + 7;

int n;
int dp[MAXN], a[MAXN];
vector<int> g[MAXN];

multiset<int> s1, s2;
void adjust() {
    if (s1.size() + 1 < s2.size()) {
        auto it = s2.begin();
        s2.erase(it);
        s1.insert(*it);
    } else if (s2.size() + 1 < s1.size()) {
        auto it = s1.end();
        --it;
        s1.erase(it);
        s2.insert(*it);
    }
}

void insert(int x) {
    if (!s2.size()) s2.insert(x);
    else {
        if (x > *s2.begin()) s2.insert(x);
        else s1.insert(x);
    }
    adjust();
}

void remove(int x) {
    if (s1.count(x)) s1.erase(s1.find(x));
    else if (s2.count(x)) s2.erase(s2.find(x));
    adjust();
}

int median() {
    adjust();
    auto it1 = s1.end();
    auto it2 = s2.begin();
    if (s1.size() == s2.size()) return ((*--it1) + (*it2)) >> 1;
    else if (s1.size() > s2.size()) return *--it1;
    else return *it2;
}

void DP(int cur, int f, bool isMax) {
    int mn = 2e9, mx = 0;

    insert(a[cur]);

    for (auto& to : g[cur]) {
        if (to == f) continue;
        DP(to, cur, isMax ^ 1);
        mn = min(mn, dp[to]), mx = max(mx, dp[to]);
    }
    if (mx == 0) dp[cur] = median();
    else if (isMax) dp[cur] = mx;
    else dp[cur] = mn;

    remove(a[cur]);
}

int main() {
    boost;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    DP(1, 0, true);
    cout << dp[1] << "\n";
    return 0;
}

官方动态中位数求法：

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
#include <bits/stdc++.h>
using namespace std;

multiset<int> S,T; // Always S.size()==T.size() or S.size()==T.size()+1
void eval(){
    if(S.size()){
        auto itr = S.end(); itr--;
        T.insert(*itr); S.erase(itr);
    }
    while(S.size() < T.size()){
        S.insert(*T.begin()); T.erase(T.begin());
    }
}
int val(){
    auto itr = S.end(); itr--;
    if(S.size()==T.size()+1)return *itr;
    return (*itr+*T.begin())/2;
}
void erase(int x){
    auto itr = S.end(); itr--;
    if(*itr < x) T.erase(T.lower_bound(x));
    else S.erase(S.lower_bound(x));
}

int main(){
    int n; cin >> n;
    vector<int> A(n); for(int i = 0; i < n; i++) cin >> A[i];
    vector<int> dp(n);
    vector<vector<int>> g(n);
    for(int i = 0; i < n-1; i++){
        int a, b; cin >> a >> b; a--; b--;
        g[a].push_back(b); g[b].push_back(a);
    }
    function<void(int,int,int)> dfs=[&](int i,int p,int d){
        S.insert(A[i]); eval();
        int mi = 1000000005, ma = 0;
        for(int x : g[i]) if(x != p) {
            dfs(x, i, d+1);
            mi = min(mi,dp[x]); ma = max(ma,dp[x]);
        }
        if(ma == 0) dp[i] = val();
        else if(d&1) dp[i] = mi;
        else dp[i] = ma;
        erase(A[i]); eval();
    }; dfs(0,-1,0);
    cout << dp[0] << endl;
}