发表更新19 分钟读完 (大约2808个字)

2026 苏州外国语学校夏令营题解

体感上 F 当然是最困难的。很意外地，现场写的时候 C 正解还是挺难想到的……除此以外 A 是很标准的签到，D E 几乎是板子。

以下是我的作答。

A. Stellar Stellar

直接把数字相乘会爆 long long。考虑到数字的相乘会导致质因数指数的相加，只需要对每个数分别处理会被 $3$ 整除多少次，最后再相加就可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int main() {
	int x;
	cin>>x;
	int ans=0;
	while(x--) {
		int v;
		cin>>v;
		while(v%3==0) {
			v/=3; ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

B. 平平无奇的数学题

暴力不难写，问题是如何优化遍历过程。

我们以 $13$ 为例子。

i 1 2 3 4 5 6 7 8 9 10 11 12 13
13/i 13 6 4 3 2 2 1 1 1 1 1 1 1

实际的取值是很少的，很多时候一个数会出现一长串。

对于一个取值 $T=\lfloor \frac n i \rfloor$，其中 $i$ 是遍历到的某个数。$T$ 不变的时候右端点可以扩展到哪里呢，也就是最大的 $t$ 使得 $\lfloor \frac n t \rfloor=T$。则 $T \le \frac n t < T+1$。

解得 $t \in (\frac n {T+1}, \frac n T]$。真巧啊，右端点就是 $\lfloor \dfrac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor$。下一次令左端点为右端点 + 1，遍历问题就解决了。

这种做法可以扩展到任何求以下式子的题目，

$$ \sum_{i=1}^n F(i) \lfloor \frac n i \rfloor $$

只要预处理 $F(i)$ 的前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
	int n;
	cin>>n;
	int ans=0;
	int l=1,r=1;
	while(l<=n) {
		r=n/(n/l);
		ans += (r-l+1)*(n/l);
		l=r+1;
	}
	cout<<ans<<endl;
	return 0;
}

记得开 long long。

C. CSP

Round 1 的解法可以获得 90 分，不再重复。

设 $cntC/S/P[i]$ 为前 $i$ 个字符中 C/S/P 的数量。$a$ 为第一段的长度，$j$ 为第一、二段的总长度。固定 $j$ 之后，前两段的代价分别为 $a - cntC[a]$ 和 $j-a-(cntS[j]-cntS[a])$。

两者和为 $(j-cntS[j])+(cntS[a]-cntC[a])$。两部分一个只和 $j$ 有关，一个只和 $a$ 有关。则枚举 $j$，同时对于每个 $j$，目标是最小化 $(cntS[a]-cntC[a]),1 \le a <j$。

接下来，我们考虑如何高效计算最小值。在枚举 $j$ 时，$a$ 的取值范围是 $1 ≤ a < j$，因此随着 $j$ 的增加，候选的 $a$ 逐渐增多。我们可以维护一个变量 $best$，它表示当前已经枚举过的所有 $a$ 中 $cntS[a]-cntC[a]$ 的最小值。初始时，$j$ 至少为 2，此时 $a$ 只能取 1，所以 $best = cntS[1]-cntC[1]$。

当 $j$ 从 2 增加到 $n-1$ 时，每次在计算新的 $j$ 之前，我们先将 $a = j-1$ 纳入考虑，即更新 $best = min(best, cntS[j-1]-cntC[j-1])$。这样，对于每个 $j$，前两段的最小代价就可以直接由 $(j-cntS[j]) + best$ 得到，再加上第三段的代价，即可快速求出当前 $j$ 下的最优修改次数。

整个枚举过程只需 $O(n)$ 时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int cntC[200005],cntS[200005],cntP[200005];
int n;
string s;
int main() {
    cin>>n>>s;
    for(int i=1;i<=n;i++) {
        cntC[i]=cntC[i-1]+(s[i-1]=='C');
        cntS[i]=cntS[i-1]+(s[i-1]=='S');
        cntP[i]=cntP[i-1]+(s[i-1]=='P');
    }
    int ans=1e9,now=1e9;
    for(int j=2;j<=n-1;j++) {
        now=min(now,cntS[j-1]-cntC[j-1]);
        int s1=j-cntS[j]+now,s2=n-j-(cntP[n]-cntP[j]);
        ans=min(ans,s1+s2);
    }
    cout<<ans<<endl;
    return 0;
}

D. Luna Say Maybe

不难发现某个解一定是 Day 1 买入，Day 2 卖出。买入的总金额不能超过 $V$，然后得到一些收益。每种兑换券可以无限买入卖出。

是的。这就是完全背包！

背包体积自然是 $V$。每个物品 $i$ 的代价（体积）是 $P_{i,1}$，收益（价值）为 $P_{i,2}$。然而你可能会剩下一些钱。这些钱当然也是你的收益。处理方法有两种：一种是定义收益为净利润 $\max(P_{i,2}-P_{i,1},0)$，然后把求得的结果加上 $V$；另一种是加入一个代价为 $1$、收益为 $1$ 的物品。（它的堆叠可以无副作用地填满余下的钱）

实现采用前者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int n,V,v[105],w[105],dp[10005];
int main() {
	cin>>n>>V;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<=n;i++) {
		cin>>v[i];
		v[i]=max(0,v[i]-w[i]);
	}
	for(int i=1;i<=n;i++) {
		for(int j=w[i];j<=V;j++){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<dp[V]+V<<endl;
	return 0;
}

E. Crescent Steps

姑且称为 「点权最短路」 问题吧。核心在于如何转化为边权模型。

令点权为 $c_i$。有三种流派：

  • 认为点权是进入点的代价。则 $u \to v$ 边权为 $c_v$。为了统计起点点权，需要加一个虚拟点指向起点，或者直接令 $dis[s] = c_s$。
  • 认为点权是离开点的代价。则 $u \to v$ 边权为 $c_u$。为了统计终点点权，需要让终点指向一个虚拟点。
  • 以上两者的结合，则 $u \to v$ 边权为 $(c_u + c_v) / 2$。需要加两个虚拟点。

虚拟点不需要真的加，只需要计算答案的时候把对应点权加回去就可以了。

我的实现是第二种，且确实加了个虚拟点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
int n,m,s,t;
int c[100005];
using pii=pair<int, int>;
vector<pii> G[100005];
int dis[100005];
const int INF = 0x3f3f3f3f;
int main() {
	cin>>n>>m>>s>>t;
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=n;i++) cin>>c[i];
	for(int i=1;i<=m;i++) {
		int x,y;
		cin>>x>>y;
		G[x].emplace_back(y,c[x]);
		G[y].emplace_back(x,c[y]);
	}
	G[t].emplace_back(n+1,c[t]); //from s to n+1;
	//
	dis[s] = 0;
	priority_queue<pii, vector<pii>,greater<pii> > q;
	q.emplace(0,s);
	while(!q.empty()) {
		auto [di,no] = q.top(); q.pop(); //dis number
		for(auto [v,w]: G[no]) {
			if(dis[no]+w<dis[v]) {
				dis[v] = dis[no] + w;
				q.emplace(dis[v],v);
			}
		}
	}
	if(dis[n+1]>=INF) dis[n+1]=-1;
	cout<<dis[n+1]<<endl;
	return 0;
}

F. Synthesis.

引理. $b$ 序列只会使用 $a$ 中的数字。

Proof. （数学归纳法）

设 $S = \{a_1, a_2, \dots, a_N\}$。我们证明：对于每一个前缀长度 $i$，都存在一个最优的 $b_1 \le b_2 \le \dots \le b_i$（非降情形）使得 $b_1, \dots, b_i \in S$。非增情形完全对偶。

奠基 ($i=1$)：若 $b_1 \notin S$，则令 $x = \max\{y \in S \mid y \le b_1\}$，$y = \min\{y \in S \mid y \ge b_1\}$（若某方向无元素则忽略）。$a_1$ 或者不大于 $x$，或者不小于 $y$，两种情况分别令 $b_1$ 往 $x / y$ 方向移动，$|a_1-b_1|$ 都不增。因此 $b_1$ 某个最优解一定在 $S$ 中。

归纳：假设对于前 $i-1$ 个位置存在最优解满足 $b_1, \dots, b_{i-1} \in S$ 且 $b_1 \le \dots \le b_{i-1}$。

考虑前 $i$ 个位置的某个最优解。固定前 $i-1$ 个位置的取值已属于 $S$，若 $b_i \notin S$，找到 $S$ 中不大于 $b_i$ 的最大值 $L$ 和不小于 $b_i$ 的最小值 $R$。$b_i \in [L,R]$。

$L,R$ 之间不可能有别的 $a$ 元素，否则它可以替换 $L$ 或 $R$。则 $a_i \le L$，或 $a_i \ge R$。

① $a_i \le L$。可以将 $b_i$ 调整到 $L$ 来减小代价。调整前，$L$ 是 $S$ 中 $\le b_i$ 的最大值，$b_{i-1}$ 也是 $S$ 中 $\le b_i$ 的值，因此 $b_{i-1} \le L$。将 $b_i$ 调整到 $L$ 之后显然绝对值更小，并且 $b_{i-1} \le L = b_i$，单调性成立。

② $a_i \ge R$。可以将 $b_i$ 调整到 $R$ 来减小代价。调整前，$b_{i-1} \le b_i \le R$。调整后 $b_{i-1} \le R = b_i$，单调性成立。

③边界。$L,R$ 未必都能找到。

  • 如果 $b_i < S中最小值$，则 $L$ 不存在，$R=S中最小值$，则 $b_{i-1} \le b_i < S中最小值$，与 $b_{i-1} \in S$ 矛盾；
  • 如果 $b_i > S中最大值$，则 $L=S中最大值$，$R$ 不存在，$a_i \le S 中最大值=L$，大大方方把 $b_i$ 降低到 $L$ 即可减少总偏差。

因此总可把 $b_i$ 也调整到 $S$ 中。

由归纳法可知，整个序列存在一个最优解，其所有元素均来自 $S$。对于非增序列 $b_1 \ge b_2 \ge \dots \ge b_N$，对称的论证同样成立。证毕。

这不是数学竞赛，你不需要证明这个引理，只要直觉上感觉正确就可以。

如果某个 $b_i$ 夹在两个相邻的原数组数值X, Y之间，则它的标准值一定小于等于X或者大于等于Y（这之间是没有原数组值/标准值的）。前者把它推到左端X、后者推到右端Y，总代价不会变差，还不会破坏单调性（之前的都在原数组数值上，这个操作不会改变 $b_i$ 和 $a$ 中任何数的大小关系），所以最优解可以只用原数组里出现过的数。 就这样理解吧。

重要的是，有了引理，我们只需考虑 $b$ 的每一项都从 $\{a_1,\dots,a_N\}$ 中选取。遍历到第几个 $a$ 应该是状态的一部分。影响决策的另一个点应该是 $b$ 上一个数用了什么，加入状态——但是好像过于巨大了，因此我们考虑对原数组创建一个有序的副本，用那个数在副本中的下标来指代那个数。

具体地，令 $b$ 为 $a$ 升序排序后的数组，$c$ 为 $a$ 降序排序后的数组。我们分别处理构造非降序列和非增序列，最后取最小代价。

状态。 令 $dp1[i][j]$ 为：考虑 $a$ 的前 $i$ 个元素，构造非降序列，且 $b_i = b[j]$ 时的最小代价。类似地，$dp2[i][j]$：考虑 $a$ 的前 $i$ 个元素，构造非增序列，且 $b_i = c[j]$ 时的最小代价。

转移。 为了使 $b$ 非降，第 $i$ 项取 $b[j]$ 时，第 $i-1$ 项只能取 $b[k]$，$k \le j$。因此$dp1[i][j] = |a_i - b[j]| + \min_{1 \le k \le j} dp1[i-1][k]$。

同理，$dp2[i][j] = |a_i - c[j]| + \min_{1 \le k \le j} dp2[i-1][k]$。

初始条件：$dp1[1][j] = |a_1 - b[j]|$，$dp2[1][j] = |a_1 - c[j]|$。

优化。 直接计算 $\min_{k\le j} dp[i-1][k]$ 会使转移变成 $O(N^3)$。注意到这个最小值是前缀最小值，可以在枚举 $j$ 的同时维护 $pre = \min(pre,\ dp[i-1][j])$。转移形式变为 $dp[i][j] = pre + |a_i - b[j]|$。这样转移复杂度降为 $O(N^2)$。

这个做法也许你会很眼熟。随着状态的变化发生扩展的枚举范围，可以动态维护……是的，这就是本次测试 C. CSP 试题的正解思路。

最终答案即为：

$$ \min\Big(\min_{1\le j\le N} dp1[N][j],\ \min_{1\le j\le N} dp2[N][j]\Big) $$

实现参考（写两遍其实有点丑陋，姑且看吧）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
#define int long long
int N;
int a[2005],b[2005],c[2005];
int dp1[2005][2005],dp2[2005][2005];
signed main() {
	cin>>N;
	memset(dp1,0x3f,sizeof(dp1));
	memset(dp2,0x3f,sizeof(dp2));
	for(int i=1;i<=N;i++) {
		cin>>a[i];
		b[i]=c[i]=a[i];
		dp1[0][i] = dp1[i][0] = 0;
		dp2[0][i] = dp2[i][0] = 0;
	}
	dp1[0][0] = dp2[0][0] = 0;
	sort(b+1,b+N+1);
	sort(c+1,c+N+1,greater<int>());
	for(int i=1;i<=N;i++) {
		dp1[1][i] = llabs(a[1]-b[i]);
		dp2[1][i] = llabs(a[1]-c[i]);
	}
    
	for(int i=2;i<=N;i++) {
		int res = 0x3f3f3f3f3f3f3f3f;
		for(int j=1;j<=N;j++) {
			res=min(res,dp1[i-1][j]);
			dp1[i][j]=res+llabs(a[i]-b[j]);
		}
	}
	int ans1=0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=N;i++) ans1=min(ans1,dp1[N][i]);

	for(int i=2;i<=N;i++) {
		int res = 0x3f3f3f3f3f3f3f3f;
		for(int j=1;j<=N;j++) {
			res=min(res,dp2[i-1][j]);
			dp2[i][j]=res+llabs(a[i]-c[j]);
		}
	}
	int ans2=0x3f3f3f3f3f3f3f3f;
	for(int i=1;i<=N;i++) ans2=min(ans2,dp2[N][i]);
    
	cout<<min(ans1,ans2)<<endl;
	return 0;
}
#
关注我

链接

最新文章

归档

标签

OI1
XCPC1
init1
发电1
可爱1
×