2025陕西ICPC邀请赛题解（部分）

2025陕西ICPC邀请赛题解（部分）

A Color 染色

题意

输入：

• $n$ ：颜色数量
• $c_i$ ：第 $i$ 节彩带的颜色
• $w_i$ ：第 $i$ 种颜色需要花费的钱

你可以做任意次操作，指定一段彩带，把彩带变成颜色 $\text{i}$ ，花费 $(\text{距离}+w_i)$ 钱.
问：对于每种颜色 $\text{i}$ ，若要把整段彩带都涂上颜色 $\text{i}$，至少要花费多少钱？

题解

tag：贪心

首先，对于某一种颜色 $\text{i}$ 而言，对于第一段 非 $\text{i}$ 的颜色，是一定要涂的。
假设有第二段非 $\text{i}$，这一段也是一定要涂的。
那么现在问题就来到了：中间要不要一起涂了呢？
那么我们可以直接贪心：因为如果涂中间，那么我们的花费变化就是 $(-w_i+\text{中间段的距离})$ ，只要这个数小于 $0$ ，那么就加上这个数（取尽可能小的值嘛）

然后，我们会出现第二个问题：如果分别每一种颜色扫一遍的话，那么复杂度就来到了 $O(n^2)$ ，来到了了 $1e10$ ，会超时，那么就不能这样暴力去做了。
我们仔细思考一下，如果某一段颜色全是 $\text{i}$ ，也就是这一段就是上面提到的“中间段”，这个“中间段”的长度是只用扫一遍全部都能计算出来的！同时我们还可以得到每种颜色的数量，那么非颜色 $\text{i}$的数量就是 $(n-\text{颜色i})$，再加上 $(\text{段数}\times w_i)$ 就是贪心之后的最终结果了！

代码

#include <bits/stdc++.h>using vi = std::vector<int>;signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n;std::cin >> n;vi c(n),w(n);for(int i = 0 ; i < n ; i ++) std::cin >> c[i],c[i] --;for(int i = 0 ; i < n ; i ++) std::cin >> w[i];vi cnt(n,0),howmany(n,0),add(n,0);int last = -1;bool f = false;int cntt = 0;for(auto i : c) {if(i != last) {if(last >= 0) {if(f && cntt < w[last]) {add[last] += cntt;} else cnt[last] ++;f = true;}cntt = 0;}cntt ++;howmany[i] ++;last = i;}cnt[last] ++;for(int i = 0 ; i < n ; i ++) {cnt[i] ++;howmany[i] = n - howmany[i];}cnt[c[0]] --;cnt[c[n-1]] --;for(int i = 0 ; i < n ; i ++) {std::cout << (howmany[i] ? w[i] * cnt[i] + howmany[i] + add[i] : 0) << " ";}return 0;
}

C gcd 最大公因数

题意

变量：$\text{a.b.x}$ 范围： $1\le a,b,x,10^{18}$
给定 $\text{a,b}$，求一个 $\text{x}$ （可能不存在，不存在直接输出 $-1$ ）
使得 $gcd(a,x)=1$ 和 $gcd(b,x)>1$ 均成立

题解

tag：简单数论（？）

我们先假设这个 $x$ 就是 $b$ 本身，这样可以确保对这个 $x$ 做任何操作，结果都是 $b$ 的因数
那么我们就要对 $x$ 处理，使得 $gcd(a,x)=1$。
最简单的做法！一直执行 $x÷gcd(a,x)$ ，直到 $gcd(a,x)=1$
然后再检查 $gcd(b,x)>1$ 是否成立即可

代码

#include <bits/stdc++.h>
#define int long longinline int gcd(int a,int b) {return b ? gcd(b , a%b) : a;
}inline void solve() {int a,b;std::cin >> a >> b;int x = b;int g;while((g = gcd(x,a)) != 1) {x /= g;}std::cout << (gcd(x,b) > 1 ? x : -1) << "\n";
}signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t = 1;std::cin >> t;while(t--) {solve();}return 0;
}

D Stock 买股票

题意

有一股票初始值 $v$ 元 ，后面连续 $n$ 天都涨了
每天都有一个 $\text{op}0$ 和 $x$

• 当 $\text{op}0$ 为 + 时 ，代表今天股票比昨天多了 $x$ 元
• 当 $\text{op}0$ 为 * 时 ，代表今天股票是昨天的 $x$ 倍

要求你对 $n$ 天的操作排序，使得这 $n$ 天的收盘价均价最高，直接输出最高的均价即可

题解

tag：数学？搜索？贪心？

他现在说要你排序，那么我们怎么排序呢？
我们需要关注的是均价，也就是一次涨幅对后面的贡献

假设现在有两个操作（ $\text{op}$ 相同），我们怎么对他们排序更优呢？
比如一个是 $+1$ ，一个是 $+2$，我们可以发现，不管谁先谁后，最后都是 $+3的结果$
那么前面那天的操作的涨幅岂不是越大越好？对于乘法也是如此
虽然这样说法比较粗略，但是大体思路就是这样的，详细证明参见官方题解

因此，我们就先单独把不同的 $\text{op}$ 取出来排序
然后对他们从前到后进行 $\text{dfs}$，得到最大的均值，然后直接输出即可

代码

这题同步流并没有造成很大的常数差异

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()signed main() {// std::ios::sync_with_stdio(false);// std::cin.tie(nullptr);// std::cout.tie(nullptr);int n;double v;std::cin >> n >> v;std::vector<std::pair<char,double> > a(n);for(auto & i : a) {std::cin >> i.first >> i.second;}std::vector<std::vector<double> >  op(2);for(auto i : a) {if(i.first == '+') op[0].push_back(i.second);else op[1].push_back(i.second);}std::sort(all(op[0]),std::greater<>());std::sort(all(op[1]),std::greater<>());int n1 = op[0].size(),n2 = op[1].size();double ans = 0;auto dfs = [&](auto && dfs, int l, int r, double now, double sum) -> void {if(l == n1 - 1 && r == n2 - 1) {ans = std::max(ans,sum / n);return;}if(l + 1 < n1) {dfs(dfs,l+1,r,now + op[0][l+1],sum + op[0][l+1] * (n - (l + r + 2)));}if(r + 1 < n2) {double add = op[1][r+1] - 1;add *= now;dfs(dfs,l,r+1,now + add, sum + add * (n - (l + r + 2)));}};dfs(dfs,-1,-1,v,v*n);printf("%.10f",ans);return 0;
}

E Printer 打字

题意

tag：dp；状压dp

小明要打一个长度为 $n$ 的字符串 $s$
他一开始把手放在键盘 $\text{a}$ 处
他每次可以执行三种操作：

1. 移动手指，从 $\text{字母\_x}$ 移动到 $\text{字母\_y}$ ,消耗的代价为 $cos{t}_{x,y}$
2. 移动光标（往左或往右），代价为 $t$
3. 打当前手指所在的键盘位置的字母，并且光标同时往右移动一位，代价为 $t$
   问：他打完长度为 $n$ 的字符串 $s$ 消耗的代价最小为多少？

题解

已知 $n\le 20$，很明显这是一个状压 $\text{DP}$ （真的明显吗？）
我们用 $0$ 和 $1$ 代表某个字符是否已经被打出，因此 $\text{dp}$ 数组的第一维范围就到了 $2^n$
然后第二维就用来维护当前光标的位置，里面的元素就代表到当前位置的最小代价

然后从0开始往外面转移，还是直接看我的代码吧
（因为我没有正经学过 $\text{dp}$ ，所以代码可能不太容易看懂）

代码

#include <bits/stdc++.h>
#define INF 1e18using vi = std::vector<int>;
using vii = std::vector<vi>;signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n,m,t;std::cin >> n >> m >> t;std::string s;std::cin >> s;vii cost(m,vi(m));for(auto & i : cost) {for(auto & j : i) {std::cin >> j;}}int N = 1LL << (n);vii dp(N + 10,vi(n+1,INF));dp[0][0] = 0;vi howmany(N);howmany[0] = 0;std::queue<int> q;q.push(0);vi isq(N,0);isq[0] = 1;while(!q.empty()) {int i = q.front();q.pop();vi mem(howmany[i] + 1,' ');int cntt = 0;for(int idx = 0 ; idx < n ; idx ++) {if(i & (1LL << idx)) {mem[cntt] = s[idx];cntt ++;continue;}}int cnt = 0;for(int idx = 0 ; idx < n ; idx ++) {if(i & (1LL << idx)) {cnt ++;continue;}int next = i | (1LL << idx);howmany[next] = howmany[i] + 1;int res = INF;for(int pi = (i == 0 ? 0 : 1) ; pi <= howmany[i] ; pi ++) {int res1 = std::abs(cnt - pi) * t;if(pi-1 >= 0) res1 += cost[mem[pi-1] - 'a'][s[idx] - 'a'];else res1 += cost[0][s[idx] - 'a'];res = std::min(res,res1 + dp[i][pi] + t);}dp[next][cnt + 1] = std::min(dp[next][cnt + 1], res);if(!isq[next]) {q.push(next);isq[next] = 1;}}}int ans = INF;for(auto i : dp[N-1]) {ans = std::min(ans,i);}std::cout << ans << "\n";return 0;
}

AI 根据我的代码给我的转移方程是：

$$\text{dp}[next][cnt+1]=\min \left(\text{dp}[next][cnt+1],\underset{pi\in [1,\text{howmany}[i]]}{\min }\left(\text{dp}[i][pi]+|\text{cnt}-pi|\times t+{\text{cost}}_{prev\_char\to s[idx]}+t\right)\right)$$

其中：

$$\begin{gathered} next=mask\mid (1\ll idx) \\ \text{cnt}是mask中已打出字符的数量 \\ \text{prev\_char}是上一个打出的字符（或初始字{符}^{\prime }{a}^{\prime }） \\ {\text{cost}}_{prev\_char\to s[idx]}是从prev\_char移动到s[idx]的代价 \end{gathered}$$

G student 学生

题意

有 $n$ 个学生排成一行，第 $i$ 个学生的成绩为 $a_i$
老师每次可以把一个符合以下条件中的一个的学生移除：

• 该学生左侧存在成绩大于等于他的学生，且右侧存在成绩小于等于他的学生
• 该学生左侧存在成绩小于等于他的学生，且右侧存在成绩大于等于他的学生
  问：最后最少剩余多少学生？

题解

我的做法其实就是模拟，从左到右，看这个学生能不能删，能删就删掉，不能删就不删，得到的结果是正确的。
官方题解提供的做法是：可以证明：
由于 $a_0$ 和 $a_{n-1}$ 都删不掉，假如 $\max$ 和 $\min$ 在中间，那么这四个数之间的数字都可以删掉
因此最终结果答案就是
KaTeX parse error: Can't use function '$' in math mode at position 20: …xt{ans} = 2 + [$̲\min$ 在中间] + [$…
不过记得特判 $n=1$ 的情况

代码1

#include <bits/stdc++.h>
using pii = std::pair<int,int>;
using vi = std::vector<int>;signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n;std::cin >> n;vi a(n);for(auto & i : a) {std::cin >> i;}if(n <= 2) {std::cout << n << "\n";return 0;}std::priority_queue<pii,std::vector<pii>,std::greater<> > q1;std::priority_queue<pii> q2;for(int i = 0 ; i < n ; i ++) {q1.push({a[i],i});q2.push({a[i],i});}int ans = 2;int min = a[0],max = a[0];for(int i = 1 ; i < n - 1 ; i ++) {while(q1.top().second <= i) q1.pop();while(q2.top().second <= i) q2.pop();if(!(a[i] >= min && a[i] <= q2.top().first) && !(a[i] <= max && a[i] >= q1.top().first)) {ans ++;max = std::max(max,a[i]);min = std::min(min,a[i]);}}std::cout << ans << "\n";return 0;
}

代码2

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()using pii = std::pair<int,int>;
using vi = std::vector<int>;signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n;std::cin >> n;vi a(n);for(auto & i : a) {std::cin >> i;}if(n <= 2) {std::cout << n << "\n";return 0;}int min = *std::min_element(all(a)),max = *std::max_element(all(a));std::cout << 2 + (max != a[0] && max != a[n-1]) + (min != a[0] && min != a[n-1]) << "\n";return 0;
}

J win 赢

题意

给你一个长度为 $n$ 的字符串 $s$
你可以执行 $k$ 次操作，往字符串里面插入任意一个字符
问：最后字符串里最多出现多少个 “lose” ？

题解

简单观察一下可以发现：“lose”这个字符串，没有一个字符是重复出现的，这就大大降低了这道题目的难度，可以直接贪心暴力
我们可以扫一遍字符串 $s$ ，看里面有多少个子串是lose的子序列，然后就可以往里面补字符
又因为“lose”这个字符串很短，我们可以直接把他的所有子序列打出来然后一一去匹配
然后按照要补充的字符个数从少到多排列，按顺序补充
注意！如果余下的补充数还有多的，还可以直接消耗 $4$ 次凭空添加一个“lose”！

代码

#include <bits/stdc++.h>signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int k;std::cin >> k;std::string s;std::cin >> s;std::map<std::string,int> mp;mp["lose"] = 4;mp["los"] = 3;mp["loe"] = 3;mp["lse"] = 3;mp["ose"] = 3;mp["lo"] = 2;mp["ls"] = 2;mp["le"] = 2;mp["os"] = 2;mp["oe"] = 2;mp["se"] = 2;mp["l"] = 1;mp["o"] = 1;mp["s"] = 1;mp["e"] = 1;std::string t;std::priority_queue<int> q;for(auto i : s) {std::string tmp = t + i;if(mp.count(tmp)) {t = tmp;} else {if(mp.count(t)) {q.push(mp[t]);}t = "";t += i;}}if(mp.count(t)) q.push(mp[t]);int ans = 0;while(!q.empty()) {if(k >= (4 - q.top())) {k -= (4 - q.top());ans ++;q.pop();} else {break;}}ans += (k / 4);std::cout << ans << "\n";return 0;
}

K Welfare 福利

题意

有 $n$ 只无私的奶牛， $m$ 只自私的奶牛，他们可以做出选项 $\text{A,B}$ 中的一个，来获取牧草
选择选项 $\text{A}$ 的所有奶牛平分 $x$ 个单位的牧草（不取整）；
选择选项 $\text{B}$ 的奶牛均可获得 $y$ 个单位的牧草；

首先由无私的奶牛选择，无私的奶牛会推出一个领袖，帮助每一头无私的奶牛做出选择。
他们知道自私的奶牛最终的选择，领袖会做出使所有奶牛获得的牧草之和最大的选择

然后由自私的奶牛选择，自私的奶牛知道无私的奶牛的所有选择。
每一头自私的奶牛都会假设其他自私的奶牛都选了选项 $\text{B}$，在此基础上再做出自己的选择，使自己获得的牧草最大化。

问：最终所有奶牛获得的牧草之和是多少？

题解

乍一看：

无私的奶牛知道自私的奶牛如何决定做什么选择
自私的奶牛知道无私的奶牛的选择

我当时有点疑惑：是不是死锁了？难道是博弈？

但是仔细想一下：不对！
无私的奶牛知道自私的奶牛如何选择，也就是说：
他们可以操纵自私的奶牛的选择，他们一做出选择，最终的结果就已经决定了
所以我们只需要看无私的奶牛如何选择即可

我们再看一下：

每一头自私的奶牛都会假设其他自私的奶牛都选了选项 $\text{B}$

也就是说，所有的自私的奶牛的选择都是一样的

无私的奶牛会推出一个领袖，帮助每一头无私的奶牛做出选择。

也就是说，无私的奶牛的选择可以不一样

那我们可以从这个角度去切入：
假如无私的奶牛让所有的自私的奶牛都选 $\text{A}$ ，他们再最大化自己的选择，那么最终的结果是多少？
假如无私的奶牛让所有的自私的奶牛都选 $\text{B}$ ，他们再最大化自己的选择，那么最终的结果是多少？

然后再输出结果的最大值即可

如何实现呢？

首先，所有的无私奶牛都不选 $\text{A}$ ，就能尽可能最大化在自私奶牛眼中自己选 $\text{A}$ 能获得的牧草了，在这个基础上再看自私的奶牛会做出什么选择，就能得到最大化的牧草了；

然后，我们可以计算出：我们要把自私的奶牛眼中自己选 $\text{A}$ 能获得的牧草的数在选 $\text{B}$ 能获得的牧草数之下，又消耗最少的无私奶牛的数量。

• 如果这个数量超过 $n$，那就是不能阻止自私奶牛选选 $\text{A}$ 了；
• 否则，假设这个数量为 $\text{maxn}$ ，那么我们让 $\text{maxn}$ 只无私的奶牛选 $\text{A}$ ，其他奶牛选 $\text{B}$ ，就能最大化获得的牧草总和了。

但是还有！ 假如没有自私的奶牛的话（虽然但是不管有没有都跑一下吧），还要再加一个选项，就是无私的奶牛留下一只选 $\text{A}$ ，把 $x$ 拿了，其余的全部选 $\text{B}$。

三者取最大值才是最终的答案！

代码

#include <bits/stdc++.h>
#define int long longinline void solve() {int n,m,x,y;std::cin >> n >> m >> x >> y;int ans1 = 0 , ans2 = 0 , ans3 = 0 , ans = 0;// 1 : 1 oth// 2 : 0 all// 3 : int maxn = 0;bool is1 = false,is3 = false;if(n > 0) {ans1 += x + (n - 1) * y;ans2 += n * y;maxn = y == 0 ? 0 : x / y + (x % y != 0);maxn = std::max(maxn-1,0LL);if(maxn > n) ans3 = n * y;else ans3 += (n - maxn) * y + x * (maxn > 0), is3 = true;}if(m > 0) {if(n == 0) ans1 += (x > y ? x : y*m);else ans1 += ((double)x / 2 > y ? 0 : y*m);ans2 += (x > y ? x : y*m);ans3 += (is3 ? y * m : (x > y ? x : y * m));}ans = std::max(ans1,ans2);ans = std::max(ans,ans3);std::cout << ans << "\n";
}signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int t = 1;std::cin >> t;while(t--) {solve();}return 0;
}

L easy 简单题

题意

有一个 $n\times n$ 的矩阵，里面的元素从 $1$ 到 $n^2$ 依次排列
你需要每行每列恰好取出两个数，问：你取出的数的和最小是多少

题解

易证：理论最小的结果肯定是能被取出的
也就是：
每行取 $2$ 个： ${\sum }_{i=0}^{n-1}i\times n\times 2$
每列取 $2$ 个： ${\sum }_{i=1}^{n}i\times 2$

把上面两个加起来输出即可

代码

#include <bits/stdc++.h>signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n;std::cin >> n;int ans = (1 + n) * n;for(int i = 0 ; i < n*n ; i += n) {ans += i*2;}std::cout << ans << "\n";return 0;
}

转载自博客https://www.cnblogs.com/jiejiejiang2004/p/18894433
博主已同意，我就是博主