Atcoder ABC395游记

写在游记之前

啊哈！福建真好玩！今天拔灯拔得真开心，欸我的手臂怎么弯不下来了

从墩板到广惠宫全程没松手，直接彻底疯狂！！！

耳鸣手残buff叠加！！！

Atcoder ABC395游记（A~F）

A.Strictly Increasing?

题目描述

给你个序列，判断是不是单调递增。

思路

水

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++) {
        if (a[i] <= a[i - 1]) {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    return 0;
}

B.Make Target

题目描述

创建一个 $N*N$ 图案，如下所示。

###########
#…#
#.#######.#
#.#…#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#…#.#
#.#######.#
#…#
###########

**概述**：创建一个 $N times N$ 模式，如下所示。

###########
#.........#
#.#######.#
#.#.....#.#
#.#.###.#.#
#.#.#.#.#.#
#.#.###.#.#
#.#.....#.#
#.#######.#
#.........#
###########

您将获得一个正整数 $N$。

考虑一个 $N*N$ 网格。设 $(i,j)$ 表示从顶部开始的第 $i$ 行和从左开始的第 $j$ 列的单元格。最初，没有单元格着色。

然后，对于 $i = 1,2, \dots, N$ 依次执行以下作：

• 设 $j = N + 1 - i$。
• 如果$i \leq j$，如果 $i$ 为奇数，则用黑色填充左上角单元格为 $（i，i）$ 且右下角单元格为 $（j，j）$ 的矩形区域，如果 $i$ 为偶数，则用白色填充。如果某些单元格已着色，则覆盖其颜色。
• 如果$i > j$，则不执行任何作。

经过所有这些作，可以证明没有未着色的单元格。确定每个单元格的最终颜色。

您将获得一个正整数 $N$。

考虑一个 $N*N$ 网格。设 $(i,j)$ 表示从顶部开始的第 $i$ 行和从左开始的第 $j$-列的单元格。最初，没有单元格着色。

然后，对于 $i = 1,2, \dots, N$ 依次执行以下作：

• 设 $j = N + 1 - i$。
• 如果$i \leq j$，如果 $i$ 为奇数，则用黑色填充左上角单元格为 $(i,i)$ 且右下角单元格为 $(j,j)$ 的矩形区域，如果 $i$ 为偶数，则用白色填充。如果某些单元格已着色，则覆盖其颜色。
• 如果$i > j$，则不执行任何作。

经过所有这些操作，可以证明没有未着色的单元格。确定每个单元格的最终颜色。

思路

模拟即可。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<vector<char>> grid(n, vector<char>(n, ' '));
    for (int i = 1; i <= n; i++) {
        int j = n + 1 - i;
        if (i <= j) {
            char color = (i % 2 == 1) ? '#' : '.';
            for (int x = i - 1; x < j; x++) {
                for (int y = i - 1; y < j; y++) {
                    grid[x][y] = color;
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << grid[i][j];
        }
        cout << '\n';
    }
    return 0;
}

C.Shortest Duplicate Subarray

题目描述

给你个正整数$N$，和一个长度为$N$的整数序列$A=(A_1,A_2,...,A_N)$

确定是否存在$A$的非空连续子数组，该子数组具有重复的值，并且在$A$中出现多次，如果存在，请输出最小符合条件子数组的长度。

思路

map存一下就好了

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    unordered_map<int, int> ls;
    int ans = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (ls.find(a[i]) != ls.end()) {
            ans = min(ans, i - ls[a[i]] + 1);
        }
        ls[a[i]] = i;
    }
    cout << (ans == INT_MAX ? -1 : ans);
    return 0;
}

D.Pigeon Swap

题目描述

有编号为$1,2,...,N$的鸽子和标记为$1,2,...,N$的巢。

最初，鸽子$i(1 \leq i \leq N)$在巢$i$。

你将对这些鸽子进行$Q$个操作。

操作有三种类型：

• 类型1：你将会得到整数$a$和$b(1 \leq a \leq N,1 \leq b \leq N)$，把鸽子$a$移动到巢$b$。

• 类型2：你将会得到整数$a$和$b(1 \leq a \leq N,1 \leq b \leq N)$，把巢$a$和巢$b$中的鸽子互换。

• 类型3：你将会得到整数$a(1 \leq a \leq N)$，告诉我鸽子$a$所在的位置。

思路

我们搞两个数组映射，一个鸽子到位置，一个位置到鸽子，然后就简单了，具体看代码。

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, q;
    cin >> n >> q;
    vector<int> ltp(n + 1), ptl(n + 1);
    for (int i = 1; i <= n; i++)
    {
        ltp[i] = i;
        ptl[i] = i;
    }
    vector<int> pig(n + 1);
    for (int i = 1; i <= n; i++)
    {
        pig[i] = i;
    }
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int a, b;
            cin >> a >> b;
            pig[a] = ltp[b];
        }
        else if (type == 2)
        {
            int a, b;
            cin >> a >> b;
            swap(ltp[a], ltp[b]);
            ptl[ltp[a]] = a;
            ptl[ltp[b]] = b;
        }
        else if (type == 3)
        {
            int a;
            cin >> a;
            cout << ptl[pig[a]] << '\n';
        }
    }
    return 0;
}

E.Flip Edge

题目描述

给定一个有 $N$ 个顶点和 $M$ 条边的有向图。第 $i$ 条边 $(1 \leq i \leq M)$ 是从顶点 $u _ i$ 指向顶点 $v _ i$ 的有向边。

初始时，你位于顶点 $1$。你需要重复以下操作，直到到达顶点 $N$：

• 执行以下两种操作之一：
  • 沿着当前顶点的有向边移动。这会产生 $1$ 的成本。具体来说，如果你位于顶点 $v$，选择一个顶点 $u$，使得存在一条从 $v$ 到 $u$ 的有向边，并移动到顶点 $u$。
  • 反转所有边的方向。这会产生 $X$ 的成本。具体来说，如果在此操作之前存在一条从 $v$ 到 $u$ 的有向边，那么在此操作之后将存在一条从 $u$ 到 $v$ 的有向边。

保证在给定的图中，你可以通过重复这些操作从顶点 $1$ 到达顶点 $N$。

请找到到达顶点 $N$ 所需的最小总成本。

思路

把节点扩展为两个状态：

• 为0：按照正向边移动

• 为1：按照反向边移动

所以每个节点$i$的标号转换函数就是$idx(i, state) = (i-1)*2 + state$

你看那个权重，是不是非负的？dijkstra就可以了！

所以Bellman-Ford应该会挂

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = LLONG_MAX;
int idx(int node, int state)
{
    return (node - 1) * 2 + state;
}
signed main()
{
    int n, m, X;
    cin >> n >> m >> X;
    vector<vector<int>> g(n + 1), gr(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        gr[v].push_back(u);
    }
    int total = n * 2;
    vector<int> dist(total, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int> > > pq;
    dist[idx(1, 0)] = 0;
    pq.push(make_pair(0, idx(1, 0)));
    while (!pq.empty()) {
        pair<int, int> topPair = pq.top();
        pq.pop();
        int d = topPair.first;
        int cur = topPair.second;
        if (d != dist[cur]) {
            continue;
        }
        int node = cur / 2 + 1;
        int state = cur % 2;
        if (node == n) {
            cout << d;
            return 0;
        }
        if (state == 0) {
            for (int i = 0; i < g[node].size(); i++) {
                int nxt = g[node][i];
                int nxtIdx = idx(nxt, state);
                if (d + 1 < dist[nxtIdx]) {
                    dist[nxtIdx] = d + 1;
                    pq.push(make_pair(dist[nxtIdx], nxtIdx));
                }
            }
        } else {
            for (int i = 0; i < gr[node].size(); i++) {
                int nxt = gr[node][i];
                int nxtIdx = idx(nxt, state);
                if (d + 1 < dist[nxtIdx]) {
                    dist[nxtIdx] = d + 1;
                    pq.push(make_pair(dist[nxtIdx], nxtIdx));
                }
            }
        }
        int flipIdx = idx(node, 1 - state);
        if (d + X < dist[flipIdx]) {
            dist[flipIdx] = d + X;
            pq.push(make_pair(dist[flipIdx], flipIdx));
        }
    }
    cout << "taomenyongcun!!!"; // 显然不会到达这一行
    return 0;
}

F.Smooth Occlusion

题目描述

ht有 $2N$ 颗牙齿：$N$ 颗上牙和 $N$ 颗下牙。

从左数第 $i$ 颗上牙的长度为 $U _ i$（$1 \leq i \leq N$），从左数第 $i$ 颗下牙的长度为 $D _ i$（$1 \leq i \leq N$）。

当满足以下两个条件时，ta的牙齿被称为“咬合良好”：

• 存在一个整数 $H$，使得对于所有 $1 \leq i \leq N$，满足 $U _ i + D _ i = H$。
• 对于所有 $1 \leq i < N$，满足 $\lvert U _ i - U _ {i+1} \rvert \leq X$。

ta可以进行以下操作任意次数：

• 支付 $1$ 摩拉使用磨牙机，选择一颗长度为正的牙齿，并将其长度减少 $1$。

不允许使用其他方法改变牙齿的长度。

请找到ta需要支付的最小总金额，以ta他的牙齿咬合良好。

思路

二分答案！哈哈！

有E难么

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, diff;
bool check(int mid, const vector<int>& up, const vector<int>& down) {
    int l = max(0LL, mid - down[0]);
    int r = min(up[0], mid);
    if (l > r) {
        return 0;
    }
    for (int i = 1; i < n; i++) {
        int lb = max(0LL, mid - down[i]);
        int rb = min(up[i], mid);
        l = max(lb, l - diff);
        r = min(rb, r + diff);
        if (l > r) {
            return 0;
        }
    }
    return 1;
}
signed main()
{
    cin >> n >> diff;
    vector<int> up(n), down(n);
    int sum = 0;
    int maxH = LLONG_MAX;
    for (int i = 0; i < n; i++) {
        cin >> up[i] >> down[i];
        sum += up[i] + down[i];
        maxH = min(maxH, up[i] + down[i]);
    }
    int l = 0, r = maxH, ans = 0;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid, up, down)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << sum - ans * n;
    return 0;
}

总结

今天和上周一样也是中吉，但是是真的！！！

差点忘了，祝今天参加省选的神犇们RP++！！！

拔灯真是够累的。。。