2024 YAC Round 5 题解

A. 琪露诺的相交线段

题目描述

在二维平面中，给定一条与 $x$ 轴平行的线段 $AB$ 和 一条与 $y$ 轴平行的线段 $CD$。线段可以沿着坐标轴方向平移任意单位长度，记为一次操作，问需要几次操作使得两条线段相交。「YAC Round 5」琪露诺的相交线段

解题思路 基础计算几何

由题意两条线段分别与 $x$ 轴和 $y$ 轴平行，即 $x_A < x_B$ 且 $y_A = y_B$、$x_C = x_D$ 且 $y_C < y_D$。显然，只要同时满足 $x_A \le x_C \le x_B$ 且 $y_C \le y_A \le y_D$ 这两个条件时，两条线段相交。由于每次操作可以沿着坐标轴（上下左右）任意移动任何长度，故只需要判断初始情况下的两条线段满足条件的个数，即可得到答案。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

int x[4], y[4];

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        for(int i = 0; i < 4; i ++ ) cin >> x[i] >> y[i];
        bool flag1 = (x[0] <= x[2] && x[2] <= x[1]);
        bool flag2 = (y[2] <= y[0] && y[0] <= y[3]);
        
        if(flag1 && flag2) cout << 0 << '\n';
        else if(flag1 || flag2) cout << 1 << '\n';
        else cout << 2 << '\n';
    }

    return 0;
}

B. 守矢斗牛三缺一

题目描述

给定五个不超过 $10$ 的正整数，判断是否可以凑出其中三个数字之和为 $10$ 的倍数。如果可以，输出剩下两个数字之和除以 $10$ 得到的余数 $x$（特别地，余数为 $0$，输出 $10$）；否则输出 $0$。「YAC Round 5」守矢斗牛三缺一

解法一 递归（全排列）

我们可以递归枚举全排列，每次选取排列的前三个数，看这三个数之和是否是 $10$ 的倍数，如果是，则记录剩余两个数之和除以 $10$ 得到的答案。

复杂度为 $O(n!)$，但是由于 $n=5$，且数据组数不超过 $10^5$，大概需要 $1.2$ 秒左右。特意没有卡这个做法。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

int a[6];

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        for(int i = 1; i <= 5; i ++ ) cin >> a[i];
        sort(a + 1, a + 6);
        
        int res = 0;
        do{
            int sum = a[1] + a[2] + a[3];
            if(sum % 10 == 0) res = max(res, (a[4] + a[5] - 1) % 10 + 1);
        }while(next_permutation(a + 1, a + 6));

        cout << res << '\n';
    }

    return 0;
}

解法二 枚举

我们可以反过来思考。只需要两两枚举数字，判断剩下三个数字之和是否是 $10$ 的倍数即可。故我们需要先求出五个数字之和，然后两两枚举记录答案。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

int a[6];

int main(){
    ios;
    
    int T; cin >> T;
    while(T -- ){
        int sum = 0, res = 0;
        for(int i = 1; i <= 5; i ++ ) cin >> a[i], sum += a[i];
        for(int i = 1; i <= 5; i ++ )
            for(int j = i + 1; j <= 5; j ++ )
                if((sum - (a[i] + a[j])) % 10 == 0)
                    res = max(res, (a[i] + a[j] - 1) % 10 + 1);
        cout << res << '\n';
    }

    return 0;
}

解法三 数学 + 枚举

五个麻将数字之和 $sum$ 除以 $10$ 得到余数 $x$，根据麻将斗牛的规则，我们可以发现，这五个数字最终要么就是 牛 $x$（特别的，余数为 $0$ 时对应牛 $10$），要么就是无牛。这也验证了一副麻将不会凑出其他的牛。

假设有 $sum = a_1 + a_2 + \ldots + a_5$，$x = sum$ $\text{mod}$ $10$。若有 $(a_i + a_j)$ $\text{mod}$ $10 = x$，那么剩余的数字之和 $\text{mod}$ $10$ 显然等于 $0$ 。（取余运算的加法性质）

所以，我们只需要先求出五个数字之和除以 $10$ 的余数 $x$，然后两两枚举是否存在两个数字之和除以 $10$ 的余数正好是 $x$。如果存在，那么直接记录答案并退出；否则就是无牛。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

int a[6];

int work(int x){
    for(int i = 1; i <= 5; i ++ )
        for(int j = i + 1; j <= 5; j ++ )
            if((a[i] + a[j] - 1) % 10 + 1 == x)
                return x;
    return 0;
}

int main(){
    ios;
    
    int T; cin >> T;
    while(T -- ){
        int sum = 0;
        for(int i = 1; i <= 5; i ++ ) cin >> a[i], sum += a[i];
        int x = (sum - 1) % 10 + 1;
        cout << work(x) << '\n';
    }

    return 0;
}

C. 秘神摩多罗

题目描述

给定一个完全图，每个点有一个点权 $a_i$，两个点之间的边权为 $a_i - 2 \times a_j + c$，其中 $c$ 为常数。每次询问一个点集，求包含点集的最短简单路径长度。（保证 $a_i - 2 \times a_j + c$ 非负）「YAC Round 5」秘神摩多罗

解题思路 贪心

这题和图论没有什么关系。

对于一个点集 $S$，其大小为 $k$，我们将点集中的点映射到 $1 ~ k$。我们可以先看一下，简单路径为 $1 \rightarrow 2 \rightarrow \dots \rightarrow k$ 得到的路径长度：

$$(a_1 - 2 \times a_2 + c) + (a_2 - 2 \times a_3 + c) + \dots (a_{k-1} - 2 \times a_k + c)$$

显然，我们可以合并并消去一些项：

$$a_1 - a_2 - \dots - a_{k-1} - 2 \times a_k + (k-1) \times c$$

化简可得：

$$2 \times a_1 - a_k + \sum_{i=1}^k (-a_i) + (k-1) \times c$$

故我们可以发现，简单路径的长度 只和起点和终点有关。

而我们需要让长度尽可能小，显然，我们只需要最小化 $a_1$，并最大化 $a_k$ 即可。故对于每次询问的点集，我们只需要记录点集中的最大值和最小值。对于 $\sum_{i=1}^k (-a_i)$ ，只需要在记录最大和最小值的同时累加一下即可。（注意开 long long）

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;

int main(){
    ios;

    int n, c, q; cin >> n >> c >> q;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++ ) cin >> a[i];

    while(q -- ){
        int k, mn = 1e9, mx = 0; cin >> k;
        ll sum = 0;
        for(int i = 1, x; i <= k; i ++ ){
            cin >> x;
            mn = min(mn, a[x]), mx = max(mx, a[x]);
            sum -= a[x];
        }
        cout << (2ll * mn - mx + sum + (ll)(k - 1) * c) << '\n';
    }

    return 0;
}

D. 异或操作真是太棒啦

题目描述

两种操作，第一种为修改第 $k$ 个数为 $x$；第二种为询问一个区间 $[l, r]$，求出区间内 所有子区间异或和的异或和。https://www.luogu.com.cn/problem/T426567

解题思路 树状数组 + 位运算

对于区间 $[l, r]$，根据按位异或的交换律以及两个相等的数异或抵消为 0 的性质，我们可以发现：

$a_l \oplus a_{l+1} \oplus \dots \oplus a_r$ 抵消 $(a_l \oplus a_{l+1} \oplus \dots \oplus a_r)$

$(a_l \oplus a_{l+1}) \oplus (a_{l+1} \oplus a_{l+2}) \oplus \dots \oplus (a_{r-1} \oplus a_{r})$ 抵消 $(a_l \oplus a_{l+1} \oplus a_{l+2} \oplus \dots \oplus a_{r-1}) \oplus (a_{l+1} \oplus a_{l+2} \oplus \dots \oplus a_{r-1} \oplus a_{r})$

$\dots$ 以此类推

因此，当区间长度 $r - l + 1$ 为偶数时，所有项全部抵消为 $0$；

而当区间长度 $r - l + 1$ 为奇数时，记 $len = r - l + 1$，则最后剩下的是：

$$(a_l \oplus a_{l+1} \oplus \dots \oplus a_{\frac{len + 1}{2}}) \oplus (a_{l+1} \oplus a_{l+2} \oplus \dots \oplus a_{\frac{len + 1}{2}} \oplus a_{\frac{len + 1}{2} + 1}) \oplus \dots \oplus (a_{\frac{len + 1}{2}} \oplus a_{\frac{len + 1}{2} + 1} \oplus \dots \oplus a_{r})$$

可以发现，区间内 第奇数个元素，经过抵消后最后还剩下一个，而 第偶数个元素，全部抵消。

故对于每次询问的区间，我们只需要输出区间 $[l, r]$ 内所有第奇数个元素的异或和即可。

由于涉及到单点修改，我们可以用开两个树状数组，为 $tr_0$ 和 $tr_1$，分别维护数组中偶数位的异或和 与 奇数位的异或和。

对于区间 $[l,r]$，如果区间长度为偶数，那么就直接输出 $0$；

如果区间长度为奇数，若 $r$ 为奇数，那么只需要取出 $tr_1$ 中对应的区间异或和即可；若 $r$ 为偶数，那么取出 $tr_0$ 中对应的区间异或和即可。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define lowbit(x) (x) & (-x)
const int N = 2e5 + 10;
int a[N], n, q;
int tr[2][N]; // 两个树状数组维护奇数位和偶数位异或和

void add(int flag, int x, int c){
    for(int i = x; i <= n; i += lowbit(i)) tr[flag][i] ^= c;
}

int query(int flag, int x){
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res ^= tr[flag][i];
    return res;
}

int main(){
    ios;

    cin >> n >> q;
    for(int i = 1; i <= n; i ++ ) cin >> a[i], add(i & 1, i, a[i]); 
    while(q -- ){
        int op; cin >> op;
        if(op == 1){
            int x, c; cin >> x >> c;
            add(x & 1, x, a[x] ^ c), a[x] = c; // 修改为c，注意原数组也记得修改
        }else{
            int l, r; cin >> l >> r;
            if((r - l + 1) & 1) cout << (query(r & 1, r) ^ query(r & 1, l - 1)) << '\n';
            else cout << 0 << '\n'; // 若长度为偶数 全部抵消
        }
    }

    return 0;
}

E. 河童科技世界 No.1！

题目描述

给定一个长度为 $n$ 的序列 $a$ 和 $m$ 个区间 $[l_i, r_i]$，在序列 $a$ 中选择任意个数使得在满足所有区间内都有一个数被选择的情况下，所选择的数和最小。 「YAC Round 5」河童科技世界 No.1！

解题思路 单调队列DP

假设 $dp_i$ 为考虑前 $i$ 个数，并且选择了第 $i$ 个数的最小值。

我们可以设一个虚拟数 $a_{n+1} = 0$，那么最后的答案就是 $dp_{n+1}$ 。

状态转移如下：

$$dp_i = \min_{j} dp_j + a_i$$

显然，这是一个典型的可以用单调队列优化的转移方式。但是，转移到 $i$ 状态的下标 $j$ 显然是需要满足某种要求的。对于每一个合法的 $j$，在 $(j, i)$ 范围内显然不可以存在一个完整的区间条件。假如在 $(j, i)$ 范围内存在某个条件 $[l, r]$，当从 $j$ 转移到 $i$ 时，显然就直接把 $[l, r]$ 给忽略了。因此，我们需要一个数组 $pre$，$pre_i$ 记录的是能够转移到 $i$ 的最小合法的下标 $j$。

故有如下状态转移：

$$dp_i = \min_{pre_i \le j < i} dp_j + a_i$$

对于 $pre_i$，有如下表达式：

$$pre_i = \max_{r_k < i} l_k$$

上面的表达式，即给定的 $m$ 个区间条件中，所有右端点 $r_k$ 小于下标 $i$ 的区间的左端点 $l_k$ 的最大值。显然，在 $(pre_i, i)$ 之间是不存在一个完整的区间条件的。

因此，我们需要在单调队列优化DP之前，先预处理前缀最大值 $pre_i$，具体的求解如代码所示。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 5e5 + 10;
int n, m;
int q[N], hh, tt; // 单调队列 deque容易超时

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        cin >> n;
        vector<int> a(n + 2); // 增加一个a[n+1]=0作为虚拟点
        for(int i = 1; i <= n; i ++ ) cin >> a[i];

        cin >> m;
        vector<int> pre(n + 2); // [pre[i], i) 可以转移到 i
        for(int i = 1, l, r; i <= m; i ++ ){ // 预处理前缀最大值
            cin >> l >> r;
            pre[r + 1] = max(pre[r + 1], l); 
        }
        for(int i = 2; i <= n + 1; i ++ ) pre[i] = max(pre[i], pre[i - 1]);

        vector<ll> dp(n + 2);
        hh = 1, tt = 0;
        q[ ++ tt] = 0;
        for(int i = 1; i <= n + 1; i ++ ){ 
            while(hh <= tt && q[hh] < pre[i]) hh ++ ; // 出界
            dp[i] = dp[q[hh]] + a[i];
            while(hh <= tt && dp[q[tt]] >= dp[i]) tt -- ; // 队尾不比当前更优
            q[ ++ tt] = i;
        }
        cout << dp[n + 1] << '\n';
    }

    return 0;
}

F. The World 世界

题目描述

给定一个 $N$ 个点和 $M$ 条有向边的图，最多可以进行 $K$ 次让一条边权值变为原先相反数的操作，问 $1$ 到 $N$ 的最短距离是多少。「YAC Round 5」The World 世界

解题思路 倍增Floyd（矩阵快速幂）

我们可以用动态规划来解决这个图论问题（floyd）。首先我们需要预处理得到不使用魔法以及最多使用一次魔法得到的最短路，用 $d[i][j][p]$ 表示从 $i$ 到 $j$ 最多使用 $p$ 次魔法的最短路长度，状态转移如下：

• 不使用魔法

  $$d[i][j][0] = \min(d[i][j][0], d[i][k][0] + d[k][j][0])$$

  就是最简单的 $\text{Floyd}$ 模板。

• 最多使用一次魔法

  不使用魔法有可能更优

  $$d[i][j][1] = \min(d[i][j][1], d[i][j][0])$$

  使用一次魔法会更优

  $$d[i][j][1] = \min(d[i][j][1], d[i][u][0] + d[v][j][0] - w)$$

  其中 $(u, v, w)$ 为枚举的使用魔法的边。

然后，我们就可以由这两个初始状态得到最多使用 $K$ 次魔法的最短路。状态转移如下：

$$d[i][j][p] = \min(d[i][j][p], d[i][k][p - 1] + d[k][j][1])$$

用最多使用 $p - 1$ 次魔法和最多使用一次魔法转移得到最多使用 $p$ 次魔法得到的最短路。在求解最多使用 $p$ 次时，显然最多使用 $p-1$ 次魔法是先前已经求出来的。

综上，可以得到如下代码（通过点数 14 / 20）：

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 110, M = 2510;

struct node{int u, v, w;}e[M];
ll d[N][N][M];
int n, m, K;

int main(){
    ios;

    memset(d, 0x3f, sizeof d);
    cin >> n >> m >> K;
    for(int i = 1; i <= n; i ++ ) d[i][i][0] = 0;
    for(int i = 1, u, v, w; i <= m; i ++ ) {
        cin >> u >> v >> w, e[i] = node{u, v, w};
        d[u][v][0] = w;
    }

    // 不使用魔法
    for(int k = 1; k <= n; k ++ )
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )   
                d[i][j][0] = min(d[i][j][0], d[i][k][0] + d[k][j][0]);

    // 最多使用一次魔法
    for(int k = 1; k <= m; k ++ ){
        auto [u, v, w] = e[k];
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ ){
                if(d[i][j][0] < d[i][j][1]) d[i][j][1] = d[i][j][0]; // 不使用
                d[i][j][1] = min(d[i][j][1], d[i][u][0] + d[v][j][0] - w);
            }
    }

    // 最多使用K次魔法
    for(int p = 2; p <= K; p ++ )
        for(int k = 1; k <= n; k ++ )
            for(int i = 1; i <= n; i ++ )
                for(int j = 1; j <= n; j ++ )
                    d[i][j][p] = min(d[i][j][p], d[i][k][p - 1] + d[k][j][1]); // i->k最多p-1次 k->j最多一次

    cout << d[1][n][K] << '\n';

    return 0;
}

但是 $K \le 10^6$ ，不仅空间不够，而且明显会超时。不过到了这里，部分同学可能发现了先前状态转移有点像是快速幂。在快速幂中，我们把 $p$（幂次） 进行了二进制拆分，在本题我们可以将 $d[i][j][p]$ 看作是所谓的 $a$ 的 $p$ 次方，将 $d[i][j][1]$ 就看作是原始的 $a$，故我们可以使用 矩阵快速幂 来解决这个问题。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int N = 110, M = 2510;

int n, m, K;
ll d[N][N];
struct node{int u, v, w;}e[M];
struct Matrix{
    ll mat[N][N];
    Matrix() { memset(mat, 0x3f, sizeof mat); }
    Matrix operator * (const Matrix &a){ // 运算符重载
        Matrix res;
        for(int k = 1; k <= n; k ++ )
            for(int i = 1; i <= n; i ++ )
                for(int j = 1; j <= n; j ++ )
                    res.mat[i][j] = min(res.mat[i][j], mat[i][k] + a.mat[k][j]);
        return res;
    }
}ans, base; 

// 矩阵快速幂
void mat_qmi(int k){
    while(k){
        if(k & 1) ans = ans * base;
        base = base * base;
        k >>= 1;
    }
}

void floyd(){
    // 不使用魔法最短路
    for(int k = 1; k <= n; k ++ )
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    // 最多用一次魔法得到的最短路 即base
    for(int k = 1; k <= m; k ++ ) {
        auto [u, v, w] = e[k];
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                base.mat[i][j] = min(base.mat[i][j], min(d[i][j], d[i][u] + d[v][j] - w));
    }
}

void init(){
    for(int i = 1; i <= n; i ++ )
        for(int j = 1; j <= n; j ++ )
            ans.mat[i][j] = d[i][j];
}


int main(){
    ios;

    cin >> n >> m >> K;

    memset(d, 0x3f, sizeof d);
    for(int i = 1; i <= n; i ++ ) d[i][i] = 0;
    for(int i = 1, u, v, w; i <= m; i ++ ){
        cin >> u >> v >> w, e[i] = node{u, v, w};
        d[u][v] = w;
    }

    floyd(); // 求不使用魔法得到最短路 最多使用一次魔法得到base

    if(!K) cout << d[1][n] << '\n';
    else{
        init();     // 最短路赋值给ans
        mat_qmi(K);
        cout << ans.mat[1][n] << '\n';
    }

    return 0;
}