2024 YAC Round 10 题解

A 幻想乡纪年法

题意描述

一年 $12$ 个月，每个月 $30$ 天，每周 $5$ 天，分别为周一至周五。给定 $y_1$ 年 $m_1$ 月 $d_1$ 日以及这天是周几，求 $y_2$ 年 $m_2$ 月 $d_2$ 日是周几。「YAC Round 10」幻想乡纪年法

解题思路

可以直接求两天的总天数，求出两数之差就可以得出是周几（注意差为负数，$\text{C++}$ 需要加上 $5$ 再对 $5$ 取模）。当然，由题意可知一年为 $360$ 天，一个月 $30$ 天，这些都正好是 $5$ 的倍数，所以答案之和天数之差 $d_2 - d_1$ 有关。因此可以不用计算总天数，只计算天数之差即可。

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

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

string to[6] = {"", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday"};
unordered_map<string, int> mp = {
    {"Monday", 1},
    {"Tuesday", 2},
    {"Wednesday", 3},
    {"Thursday", 4},
    {"Friday", 5}
};

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        int y1, m1, d1; cin >> y1 >> m1 >> d1;
        string s; cin >> s;
        int y2, m2, d2; cin >> y2 >> m2 >> d2;

        int a = mp[s], d = d2 - d1; // d 天数之差
        int b = ((a + d - 1) % 5 + 5) % 5 + 1; // 注意负数
        cout << to[b] << "\n";
    }

    return 0;
}

B 露娜想要成为优等生

题意描述

求 $n$ 个整数的平均分，并保留 $k$ 位小数（小数点后第 $k$ 位后面全部截断）「YAC Round 10」露娜想要成为优等生

解题思路 模拟

先求出总分 $sum$，$\left \lfloor \frac{sum}{n} \right \rfloor$ 为小数点之前的整数部分。对于小数点之后 $k$ 位，模拟数学除法过程即可。

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

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

int main(){
    ios;

    int n, k, sum = 0; cin >> n >> k;
    for(int i = 1, x; i <= n; i ++ ) cin >> x, sum += x;
    cout << sum / n << "."; // 整数部分

    sum %= n;
    while(k -- ){   // 模拟除法
        sum *= 10;
        cout << sum / n;
        sum %= n;
    }

    return 0;
}

C 人偶巨大化计划

题意描述

起点为 $(0,0)$，可以朝上下左右四个方向移动，分别对应 $\text{'U', 'D', 'L', 'R'}$ 。给定一个长度为 $n$ 的基本指令序列，按照顺序重复执行 $k$ 轮整个基本序列，求整个移动过程中距离起点的最大曼哈顿距离。「YAC Round 10」人偶巨大化计划

解题思路 模拟 + 贪心 + 枚举

执行一轮基本序列后到达的位置，距离执行之前的起点会产生一个偏移量，可以假设这个偏移量为 $d$。模拟可以发现，每一轮中到达的每个点距离起点 $(0, 0)$ 的曼哈顿距离都比上一轮的每个点都多了一个偏移量 $d$，故最后第 $k$ 次到达的每个点都比前面每一轮到达的点距离起点 $(0, 0)$ 更优。

因此我们只需要先模拟第一轮得到终点位置 $(x_1, y_1)$ （$x_1 + y_1 = d$），然后乘上 $k - 1$，枚举一下最后第 $k$ 轮每个点距离起点 $(0, 0)$ 的曼哈顿距离取最大值即可。 但是，这样还不完全正确。

比如有一个序列 $\text{"UUUULLLLDDDDDRRRRR"}$，重复执行 $2$ 次，模拟后可以发现答案在第一轮执行序列中。因此，我们还需要枚举第一轮中的所有点曼哈顿距离最大值。

综上，只需要枚举第一轮和第 $k$ 轮的点取最大曼哈顿距离即可。

#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 dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
unordered_map<char, int> mp = { {'L', 0}, {'R', 1}, {'U', 2}, {'D', 3} };

int main(){
    ios;

    int T; cin >> T;
    while(T -- ){
        ll n, K; cin >> n >> K;
        string a; cin >> a;

        ll x = 0, y = 0, res = 0;
        for(int i = 0; i < n; i ++ ){ // 第一轮也需要枚举，并求出第一轮终点位置
            int k = mp[a[i]];
            x = x + dx[k], y = y + dy[k];
            res = max(res, llabs(x) + llabs(y));
        }

        x *= (K - 1), y *= (K - 1);
        for(int i = 0; i < n; i ++ ){ // 第 k 轮枚举每个点
            int k = mp[a[i]];
            x = x + dx[k], y = y + dy[k];
            res = max(res, llabs(x) + llabs(y));
        }

        cout << res << "\n";
    }

    return 0;
}

D Touhou 兽王原

题意描述

有 $n$ 个关卡，每个关卡消耗 $h_i$ 点生命值和 $s_i$ 点耐力值，价值 $w_i$ 个金币。现在有 $H$ 点生命值 和 $S$ 点耐力值，求选择一些关卡可以获得的金币最大数量。 「YAC Round 10」Touhou 兽王原

解题思路 二维费用背包

显然是二维费用背包问题，但是由于空间限制，只能使用空间优化的二维费用背包模板（AcWing 8. 二维费用的背包问题【二维费用01背包问题】）。

几乎和模板没有差别，只需要增加一个透支耐力值是否可以用生命值来代替的状态转移即可：

$$\begin{cases} dp[j][k] = \max(dp[j][k], dp[j - h][k - s] + w), & j > h, k >= s \\\\ dp[j][k] = \max(dp[j][k], dp[j - h - (s - k)][0] + w), & j - h - (s - k) > 0, k < s \end{cases}$$

#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 = 1010, M = 310;

ll dp[M][M];
int n, H, S;

int main(){
    ios;

    cin >> n >> H >> S;
    for(int i = 1, h, s, w; i <= n; i ++ ){
        cin >> h >> s >> w;
        for(int j = H; j > h; j -- ) // 不能减少到0
            for(int k = S; k >= 0; k -- ){
                if(k >= s) dp[j][k] = max(dp[j][k], dp[j - h][k - s] + w);
                else if(j - h - (s - k) > 0) 
                    dp[j][k] = max(dp[j][k], dp[j - h - (s - k)][0] + w);
            }
    }
    cout << dp[H][S] << "\n";

    return 0;
}

E 甜蜜的点心时间

题意描述

有 $n$ 个字符串，求有多少对字符串拼接后可以分成完全相同的两个串。「YAC Round 10」甜蜜的点心时间

解题思路 字符串哈希

首先，若一个串 $A$ 和 一个串 $B$ 拼接后得到的 $AB$ 是可以完全分成相同两份的，显然 $BA$ 也是可以的。因此在统计过程中只需要正着做一次即可。

可以发现一个串 $A$ 和 一个串 $B$ 拼接后得到的 $AB$ 是可以完全分成相同的两个串有如下几种情况：

• $A$ 和 $B$ 完全相同；

• $A$ 和 $B$ 的中间部分完全相同。

• $A$ 的中间部分和 $B$ 完全相同；

PS：这里的串的中间部分前提是中间部分的两侧的串是一样的。

我们可以枚举每个串，累计这个串出现的次数，并且枚举这个串的中间部分也进行统计。对于枚举的每个串，其答案的贡献就是先前 与其完全相同的串的个数 + 与其完全相同的中间部分的个数 + 与其中间部分完全相同的串的个数 。

我们可以用字符串哈希来实现，维护每个串以及中间部分的出现次数。本题对于卡了一些比较常用的 $\text{base}$，建议使用双哈希或者使用比较稀奇古怪的 $\text{base}$ 。

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

#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define MP make_pair
#define fi first
#define se second
typedef long long ll;
typedef pair<ll, ll> pll;
const int N = 4e5 + 10;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;

ll hs1[N], bs1[N], hs2[N], bs2[N];
ll base1, base2;
string s;
int n;

void work(){ // 双哈希
    base1 = 131, base2 = 233;
    hs1[0] = hs2[0] = 0;
    bs1[0] = bs2[0] = 1;

    for(int i = 1; i <= n; i ++ ){
        bs1[i] = (bs1[i - 1] * base1) % mod1;
        bs2[i] = (bs2[i - 1] * base2) % mod2;
        hs1[i] = (hs1[i - 1] * base1 + s[i - 1] - 'a' + 1) % mod1;
        hs2[i] = (hs2[i - 1] * base2 + s[i - 1] - 'a' + 1) % mod2;        
    }
}

pll query(int l, int r){
    ll x = ((hs1[r] - hs1[l - 1] * bs1[r - l + 1]) % mod1 + mod1) % mod1;
    ll y = ((hs2[r] - hs2[l - 1] * bs2[r - l + 1]) % mod2 + mod2) % mod2;
    return MP(x, y);
}

map<pll, ll> mp1, mp2; // mp1 维护每个串出现次数，mp2 维护所有中间部分出现次数
ll res = 0;

int main(){
    ios;

    int m; cin >> m;
    while(m -- ){
        cin >> s;
        n = s.size();

        work();

        auto cur = query(1, n);
        res += mp1[cur];  // 与其完全相同的串的个数
        mp1[cur] ++ ;     // 累计每个串出现的次数

        res += mp2[cur];  // 与其完全相同的中间部分的个数

        for(int i = 1; 2 * i < n; i ++ ){ // 枚举中间部分
            auto x = query(1, i), y = query(n - i + 1, n); // 前提两侧一样
            if(x == y){
                auto z = query(i + 1, n - i); // 中间内部部分
                res += mp1[z];  // 与其中间部分完全相同的串的个数
                mp2[z] ++ ;     // 累计中间部分  
            }
        }
    }

    cout << res << "\n";

    return 0;
}

F 《文文。新闻》

题意描述

给定一颗 $n$ 节点的树，每个边有一个两个边权 $w_1$ 和 $w_2$，分别为单程使用和无限次使用。现在需要从 $1$ 到 $2$ 一直按顺序遍历到 $n$，求整个遍历过程的最小花费为多少。「YAC Round 10」《文文。新闻》

解题思路 倍增求LCA + 树上差分

有条件可知为一棵树，节点两两之间最短路径确定。倍增求 $LCA$（或者其他方法），树上边差分并 $dfs$ 求树上前缀和求出每条边经过多少次（每个点向上到其父节点的一条边为这个节点对应的边），最后枚举一下每条边上使用单程票还是多程票更划算累加即为答案。

#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 = 2e5 + 10;

struct node{ int v, w1, w2; };
vector<node> e[N];
int n, b[N], c1[N], c2[N], d[N], f[N][22];

void bfs(int src){
    queue<int> q;
    q.push(src);
    d[src] = 1;

    while(q.size()){
        int u = q.front();
        q.pop();

        for(auto &[v, w1, w2] : e[u]){
            if(!d[v]){
                q.push(v);
                d[v] = d[u] + 1, f[v][0] = u;
                for(int k = 1; k <= 20; k ++ ) f[v][k] = f[f[v][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b){
    if(d[a] < d[b]) swap(a, b);
    for(int k = 20; ~k; k -- )
        if(d[f[a][k]] >= d[b]) a = f[a][k];
    if(a == b) return a;
    for(int k = 20; ~k; k -- )
        if(f[a][k] != f[b][k]) a = f[a][k], b = f[b][k];
    return f[a][0];
}

void dfs(int u, int fa){
    for(auto &[v, w1, w2] : e[u]){
        if(v == fa) continue;
        c1[v] = w1, c2[v] = w2; // 每个节点向上到父节点的边
        dfs(v, u);
        b[u] += b[v];
    }
}

int main(){
    ios;

    cin >> n;
    for(int i = 1, u, v, w1, w2; i < n; i ++ ){
        cin >> u >> v >> w1 >> w2;
        e[u].push_back(node{v, w1, w2});
        e[v].push_back(node{u, w1, w2});
    }

    bfs(1);

    for(int u = 1; u < n; u ++ ){
        int v = u + 1, anc = lca(u, v);
        b[u] ++ , b[v] ++ , b[anc] -= 2; // 边差分
    }

    dfs(1, 0);

    ll res = 0;
    for(int i = 2; i <= n; i ++ ) res += min((ll)b[i] * c1[i], (ll)c2[i]);
    cout << res << "\n";

    return 0;
}