Atto Round 1 (Codeforces Round 1041, Div. 1 + Div. 2)

2025-08-09

Atto Round 1 (Codeforces Round 1041, Div. 1 + Div. 2)

A

给一个长度为 $n$ 的数组，是否可以通过把其中的 $-1$ 更换成任意数字，使得对于 $1 \le i \le n - 2$ :

$mex(a_i, a_{i + 1}, a_{i + 2}) = max(a_i, a_{i + 1}, a_{i + 2}) - min(a_i, a_{i + 1}, a_{i + 2})$

solution

三个数字的 MEX 值只可能等于 ${0, 1, 2, 3}$。

当 $mex > 0$ 时，$min(a_i, a_{i + 1}, a_{i + 2}) = 0$，于是 $max(a_i, a_{i + 1}, a_{i + 2}) = mex$，那么显然对于 $mex = x$ 的数组，其中肯定不能出现值等于 $x$ 的元素。

所以当且仅当 $mex(a_i, a_{i + 1}, a_{i + 2}) = 0$ 时可以满足条件，所以 $a$ 中所有元素必须全部相等且不等于 $0$ 才可以是一个好数组。

code

// Date: 2025-08-07
// Time: 22:37:15
void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    if(count(a.begin() + 1, a.end(), 0)){
        cout << "NO\n";
        return;
    }
    int mx = *max_element(a.begin() + 1, a.end());
    for(int i = 1; i <= n; i++){
        if(a[i] != -1 && a[i] != mx){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

B

有一个长度为 $n$ 的通道，有 $n$ 个格子，最左边的是第 $1$ 个，刚开始时 Hamid 在第 $x$ 个格子。有一些格子是空的，有一些格子是墙。

在每一天开始的时候 Mani 会选择一个空格子，并在这个格子上建一堵墙。

然后 Hamid 会选择一个方向，如果这个方向上没有格子了，那么他可以离开，否则他会摧毁这个方向上离他最近的墙，这一天结束时他会呆在这个地方。

Hamid 想早点离开，Mani 不想让 Hamid 早点离开。如果两人都足够聪明，Hamid 需要多少天才能离开？

solution

如果当前一堵墙都没有，那么 Mani 只能在一个方向建墙，所以 Hamid 一天就可以离开。

让答案为 $ans$，那么显然 $ans \le min(x, n - x + 1)$，因为如果啥都不管只往一个方向走，肯定至少能达到这个数字。

但如果只考虑了这个，我喜提了 Wa on test 2。

因为 Hamid 其实是可以瞬移到离他最近的墙，我们可以找到离他左边和右边最近的墙，分别记它们的位置为 $L, R$。Hamid 一定可以用一天到达 $L$，或 $R$。那么 $ans \le max(L + 1, n - R + 2)$。

因为假如 $L + 1$ 更小，那么 Mani 肯定会在 $x - 1$ 建墙，使得你无法瞬移到 $L$，反之他会在 $x + 1$ 建墙，所以只能取 max。

code

// Date: 2025-08-07
// Time: 22:48:46
void ChatGptDeepSeek()
{
    int n, x;
    cin >> n >> x;
    string s; cin >> s;
    int ans = min(x, n - x + 1);
    s = " " + s;
    int L = 0, R = n + 1;
    for(int i = x - 1; i >= 1; i--){
        if(s[i] == '#'){
            L = i;
            break;
        }
    }
    for(int i = x + 1; i <= n; i++){
        if(s[i] == '#'){
            R = i;
            break;
        }
    }
    ans = min(ans, max(L + 1, n - R + 1 + 1));
    cout << ans << '\n';
}

C

有两个长度为 $n$ 的数组 $a, b$。

Ali 和 Bahamin 在玩一个游戏，持续 $k$ 回合。在每回合中：

• 首先，Ali 选择两个下标 $i$ 和 $j$ ($1 \le i < j \le n$)；

• 然后 Bahamin 可以重新排列 $a_i, a_j, b_i, b_j$，交换几个数字的值，也可以让这几个数字保持不变。

在 $k$ 轮游戏之后，游戏的得分为 $v = \sum\limits_{i=1}^n |a_i - b_i|$. Ali 希望 $v$ 尽量小，Bahamin 希望 $v$ 尽量大，并且两个人都足够聪明，最终的 $v$ 是多少。

solution

• hint 1

  $k$ 轮游戏后，$v$ 不可能减小，因为如果减小，Bahamin 肯定不操作，那值起码不会变。

• hint 2

  Ali 只会选择一对不同的 $(i, j)$，Bahamin 也最多只有第一次需要进行操作。Bahamin 一定可以使得操作后，可以达到最大的 $v$。

所以我们只需要去找一对 $(i, j)$ 使得进行操作后，$v$ 的增加值尽量小。

想一下，假如我们有四个数字，$v1 \le v2 \le v3 \le v4$，我们想要假设它们是我们选的 $a_i,a_j,b_i,b_j$ 那四个数字，操作之后 $|a_i - b_i| + |a_j - b_j|$ 的值可能是什么呢？

其实就是排列组合嘛，其中最大的一定是 $v3 + v4 - v1 - v2$。也就是我们交换后，不要让最大的两个数字的下标相同，就可以使得答案变得最大。

由于可以自由交换，我们可以交换 $a_i,b_i$，使得 $a_i >= b_i$，然后我们按 $a$ 的值递增排序。

那么对于 $i < j$，一定有 $a_i \le a_j,b_j \le a_j, b_i \le b_j$。所以 $a_j$ 一定是这几个数字中最大的。

它们四个的关系只能是

v2 v4
v1 v3

或者

v3 v4 or v3 v4
v1 v2    v2 v1

对于下面的两种，这四个数字的贡献已经是 $v4 + v3 - v2 - v1$，所以不会让答案变大。假设存在满足这种关系的 $(i, j)$ 那么答案不会变。

对于第一种，其对答案的贡献为 $v4 + v2 - v3 - v1$。Bahamin 交换之后，答案的变化为 $(v4 + v3 - v2 - v1) - (v4 + v2 - v3 - v1) = 2(v3 - v2)$。

所以若无使得答案不变的 $(i,j)$，交换并排序之后，$b$ 也一定是一个有序数组。

若不存在 $1$ 的情况，$v$ 会增加 $2\min\limits_{1 \le i < j \le n} (b_j - a_i)$ 。

code

// Date: 2025-08-07
// Time: 23:25:18
void ChatGptDeepSeek()
{
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i].first;
    for(int i = 1; i <= n; i++) cin >> a[i].second;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        if(a[i].first < a[i].second)
            swap(a[i].first, a[i].second);
        ans += a[i].first - a[i].second;
    }
    int add = INF;
    sort(a.begin() + 1, a.end(), [](pair<int,int> x, pair<int, int> y){
        return x.first < y.first;
    });
    for(int i = 2; i <= n; i++){
        auto [x, y] = a[i];
        if(a[i - 1].first >= y){
            cout << ans << "\n";
            return;
        }
        add = min(add, y - a[i - 1].first);
    }
    cout << ans + 2 * add << '\n';
}

D

有 $n$ 个房子 $m$ 座桥，这 $n$ 个房子可以通过这些桥联通。

问有多少种排列房子的方式，使得有桥连接的房子都在河的两边，且所有桥之间不会交叉。

solution

• hint 1 桥的数量一定只能是 $n - 1$，否则就会存在环，有环的话就百分百不行。

• hint 2 一个节点的子节点中，不是叶子的节点最多只能有两个。

我赛时没写出这题，之后也是又想了挺久才想明白。我当时是直接先确定树的根节点，然后每个点的子节点中的叶子节点可以自由排列。然后我想的非常混乱了，我找一个有两个不是叶子的子节点的点作为根节点，然后 dfs，乘每个点的非叶子子节点数量的排列。。。但显然这是错的，而且我到最后也越写越不知道怎么确定根节点，也不能确定什么时候需要乘2。

我想的是，根节点有时候会有2个不是叶子节点的子节点，有时候是1个，这让我很不好算答案啊。

但是看了题解才发现一个有用的事情，如果去掉所有的叶子节点，剩下的部分一定是一条链。

这条链一定是相邻的节点在河的不同边，所以最左边的节点其实是可以确定的，每个点的叶子节点的数量都可以自由排列，所以直接算就好了。画个图就会非常的清晰了。

如果这条链上至少有两个节点，那么则可以左右对称一下，答案可以乘2。

#include<bits/stdc++.h>
using namespace std;
using LL = long long;

constexpr int mod = int(1e9) + 7;
constexpr int N = int(2e5);
int fact[N + 1];
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    vector<int> d(n + 1);
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        d[u]++, d[v]++;
    }
    if(m != n - 1){
        cout << "0\n";
        return;
    }
    int ans = 2, cnt = 0;
    for(int u = 1; u <= n; u++){
        int leaf = 0, not_leaf = 0;
        for(int v : g[u]){
            if(d[v] == 1) leaf++;
            else not_leaf++;
        }
        if(d[u] > 1) cnt++;
        if(not_leaf > 2){
           ans = 0; break;
        }
        ans = 1LL * ans * fact[leaf] % mod;
    }
    if(cnt > 1) ans = 2 * ans % mod;
    cout << ans << '\n';
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    fact[0] = 1;
    for(int i = 1; i <= N; i++)
        fact[i] = 1LL * fact[i - 1] * i % mod;
    int T; cin >> T; while(T--)
    {solve();} return 0;
}