专栏文章

题解：T580827 欧冠附加赛

DDoraeman
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miom6hl4
此快照首次捕获于
2025/12/02 21:28
3 个月前
此快照最后确认于
2025/12/02 21:28
3 个月前
查看原文

知识点

本题考察前缀和与单调队列。

知识补充

OI WiKi 前缀和讲解。
OI WiKi 单调队列讲解。
P1886 滑动窗口 /【模板】单调队列；
P1886 滑动窗口 /【模板】单调队列 题解。
单调队列 博客 11；单调队列 博客 22；
单调队列 博客 33；单调队列 博客 44。

简化版题意

可以先求出曼城的每分钟的净胜球（“净胜球”知识科普）。
将题目转化为：扣除长度不超过 KK 的一段区间内的曼城的全部净胜球，要求这个区间内曼城净胜球最小。因为曼城总净胜球固定不变，所以此时剩余的曼城净胜球最大。
注：如果所有符合要求的区间内曼城的净胜球都是正数，就不需要扣除任何区间，因为扣除后曼城总净胜球反而会减少。

形式化题意

由上述简化版题意，可以进一步得到形式化题意。
给定序列：
m={m1,m2,…,mN}，r={r1,r2,…,rN}。m=\{m_1,m_2,\dots,m_N\}，\\ r=\{r_1,r_2,\dots,r_N\}。
规定序列：
a={m1−r1,m2−r2,…,mN−rN}。a=\{m_1-r_1,m_2-r_2,\dots,m_N-r_N\}。
设 SS 为 aleft+1a_{left+1} 到 arighta_{right} 求和。
当以下式子取到最小值时（此处使用 (left+1)(left+1) 方便后续计算），
S=∑i=left+1rightai  (0≤right−(left+1)+1≤K)S=\sum_{i=left+1}^{right}a_i\ \ (0\leq right-(left+1)+1\leq K)
如果 S<0S<0，求以下两个式子的最大值（SS 可能有多个最小值，会对应不同的 left,rightleft,right）。
∑i=1Nmi−∑i=left+1rightmi\sum_{i=1}^{N}m_i-\sum_{i=left+1}^{right}m_i ∑i=1Nri−∑i=left+1rightri\sum_{i=1}^{N}r_i-\sum_{i=left+1}^{right}r_i
注：经计算，这两个式子的差是 ∑i=1Nai−S\sum_{i=1}^{N}a_i-S，在 SS 确定时为定值，所以保证两式能同时取到最大值。
特别地，如果 S>0S>0，直接求 ∑i=1Nmi\sum_{i=1}^{N}m_i 和 ∑i=1Nri\sum_{i=1}^{N}r_i。

前缀和部分

观察上方的简化版题意和形式化题意，可以发现出现了多次“求和”，其中主要是求 m,r,am,r,a 序列的区间和。
如果直接使用循环遍历求区间和，总代码时间复杂度可能达到 O⁡(N2)\operatorname{O}(N^2)，最多获得 4040 分。
如果使用前缀和 (1≤i≤N)(1\leq i\leq N)：
  • M0=R0=A0=0M_0=R_0=A_0=0；
  • Mi=Mi−1+miM_i=M_{i-1}+m_i；
  • Ri=Ri−1+riR_i=R_{i-1}+r_i；
  • Ai=Ai−1+aiA_i=A_{i-1}+a_i。
O⁡(N)\operatorname{O}(N) 预处理求得 M,R,AM,R,A 序列的所有值，并在接下来 O⁡(1)\operatorname{O}(1) 时间复杂度内求出所有区间和。
经过前缀和计算，我们可以将之前的求和式全部转化为前缀和数列中的某个数。具体对应如下：
  • ∑i=1Nai=AN\sum_{i=1}^{N}a_i=A_N；
  • ∑i=1Nmi=MN\sum_{i=1}^{N}m_i=M_N；
  • ∑i=1Nri=RN\sum_{i=1}^{N}r_i=R_N；
  • S=Aright−AleftS=A_{right}-A_{left}。
注：此处要特别注意，S=Aright−AleftS=A_{right}-A_{left} 而非 Aright−Aleft+1A_{right}-A_{left+1}。这个式子与前缀和求区间和相关知识有关。

前缀和（预处理）代码

CPP
// 进球前缀和 
for(int i=0; i<n; i++)
    M[i+1] = M[i] + (s[i] == 'M'),
    R[i+1] = R[i] + (s[i] == 'R');
		
// 净胜球前缀和 
for(int i=1; i<=n; i++)
    a[i] = M[i] - R[i];

单调队列部分

求和问题解决后，我们迎来了第二大问题：求所有 SS 的最小值。
如果遍历所有符合条件的 left,rightleft,right，时间复杂度达到 O⁡(N2)\operatorname{O}(N^2)，超时。
这时候就要用到单调队列了。
根据例题 P1886，我们可以了解到：单调队列可以在 O⁡(N)\operatorname{O}(N) 时间复杂度内，求出数列中各个长度为 KK 的区间的最小值（或最大值）。

知识点转化

只求到长度为 KK 的区间的最小值还不够，还有一步。
我们求的是 S=Aright−AleftS=A_{right}-A_{left} 的最小值。为了使 SS 最大，可以对于所有 ArightA_{right}，都求出 AleftA_{left} 的最大值，此时原式 SS 取到最小。

单调队列·实现方法

遍历 AA 数列得到每个 Aright=A1,A2,…,ANA_{right}=A_1,A_2,\dots,A_N，并同时求以 ArightA_{right} 为结尾的长度最大为 (K+1)(K+1) 的区间内的最大值，作为 AleftA_{left}。
即 Aleft=min⁡{Aright−K,Aright−K+1,…,Aright}A_{left}=\min\{A_{right-K},A_{right-K+1},\dots,A_{right}\}（此数列长度恰好为 KK）。
注：整数 leftleft 的取值区间的长度是 (K+1)(K+1) 而非 KK。
根据 SS 的式子，我们实际上要扣除 A[left+1,right]A_{[left+1,right]} 这个区间，left+1left+1 的取值区间的长度是 KK，且以 rightright 结尾。
使用区间长度计算公式（区间长度 == 右边界 −- 左边界 +1+1）写成：0≤right−(left+1)+1≤K0\leq right-(left+1)+1\leq K。
解得：right−K≤left≤rightright-K\leq left\leq right。
使用双端队列 qq，q.front() 记录 leftleft。

移除出界元素

由前文，因为 right−K≤left≤rightright-K\leq left\leq right，所以，当 left<right−Kleft<right-K 时，我们就认定它“出界”，删除这个元素。
注 1：所有的 leftleft 都从各个 rightright 之前的双端队列中获得，而 rightright 从小到大考虑。不会出现 left>rightleft>right 的情况，故不考虑。
注 2：在 for 循环中，每次变量 rightright 自增 11，与之对应的 leftleft 最多也就只会有 11 个出界，所以写 if 即可，不用写 while。
于是我们就可以写：
CPP
// 1.出队·移除出界元素 
if(!q.empty() && left<right-K)
    q.pop_front();

维护单调递增

直接按照模板写。
CPP
// 2.出队·维护单调递减 
while(!q.empty() && A[i] >= A[q.back()])
    q.pop_back();

新元素加入

C
// 3.入队·新元素加入 
q.push_back(i);

区间求和·记录最大值

对于每个 ArightA_{right}，使用单调队列求得长度为 K+1K+1 的区间内最大的 AleftA_{left} 之后，求得到了当前 SS 的最小取值。
即：S=Aright−AleftS=A_{right}-A_{left}。
用 minimini 记录 SS（净胜球）的最小值，如果 S<miniS<mini，就更新 minimini 为 SS，最后求出扣除的最小的曼城净胜球 minimini。
如果这个最终值 mini>0mini>0，说明扣除的曼城净胜球最少也是正数，也就是说整场比赛对曼城都是有利的，不需要扣除任何区间，直接输出 MN,RNM_N,R_N 作为答案。

进球最大值

求出最优净胜球还没有结束。还有最后一步：在曼城净胜球最大的情况下，最大化曼城进球（也即最大化皇马进球）。
转变思路：最大化两队进球，即在 SS 为最小值时，最小化两队扣除的进球。
也可以写成：在 S=Aright−AleftS=A_{right}-A_{left} 为最小值时，最小化 Mgoal=Mright−MleftM_{goal}=M_{right}-M_{left} 和 Rgoal=Rright−RleftR_{goal}=R_{right}-R_{left}。
更新这两个值需要分两种情况讨论：
  1. 如果当前的 S<miniS<mini，此时新的 SS 一定更优。先考虑求 SS 的最小值，所以直接同步更新； CPP
    Mgoal = M[right] - M[left];
Rgoal = R[right] - R[left];
  2. 如果当前的 S=miniS=mini，此时 SS 已经取到最小值，新的 (left,right)(left,right) 所对应的 Mgoal,RgoalM_{goal},R_{goal} 可以考虑。其可能更优，所以用 min⁡\min 函数或比较大小求出更小值（即更优值）。 CPP
    Mgoal = min(M[right]-M[left], Mgoal);
Rgoal = min(R[right]-R[left], Rgoal);
    或写成： CPP
    if(M[right]-M[left] < Mgoal){
    Mgoal = M[right] - M[left];
    Rgoal = R[right] - R[left];
}

特判

最后不要忘记有趣的 #1\#1 测试点呀！
通过使用 DeepSeek，豆包，百度体育等进行搜索，可以找到 这场欧冠 1/81/8 决赛附加赛（其实题目里也有）。
进入这个网址后，可以发现打进 22 球未能获胜的球员就是——哈兰德！
哈兰德，2000.7.212000.7.21 出生于英国，是一名挪威足球运动员，现在（2025.7.312025.7.31）效力于曼彻斯特城足球俱乐部。
他的全名是：Erling Braut Haaland。
注：Erling Haaland 是错误答案，因为题目要求写出全名。
注意：虽然测试点 #2∼20\#2\sim20 的第一行字符串都不含空格，但是测试点 #1\#1 的第一行是 Who is H?，存在空格，所以要注意读入处理。有以下两种写法。
CPP
string s; getline(cin, s); //读入整行 
if(s == "Who is H?"){
    cout << "Erling Braut Haaland";
    return 0;
}
CPP
string s; cin >> s; // 读到空格就停止 
// 此时 s = "Who" 
if(s == "Who"){
    cout << "Erling Braut Haaland";
    return 0;
}

AC 代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6+5;

int M[MAX_N], R[MAX_N], A[MAX_N];

int main(){
	string s; getline(cin, s);
	// 特判1
	if(s == "Who is H?"){
		cout << "Erling Braut Haaland";
		return 0;
	}
	int n = s.size();
	int k; cin >> k;
	
	// 进球前缀和 
	for(int i=0; i<n; i++)
		M[i+1] = M[i] + (s[i] == 'M'),
		R[i+1] = R[i] + (s[i] == 'R');
		
	// 特判2 
	if(k == 0){
		cout << M[n] << ':' << R[n];
		return 0;
	}
		
	// 净胜球前缀和 
	for(int i=1; i<=n; i++)
		A[i] = M[i] - R[i];
		
	deque <int> q; 
	int mini = INT_MAX, 
		Mgoal = 0, Rgoal = 0,
        left, right;
	for(int i=1; i<=n; i++){
		// 单调队列操作
		// 1.出队·移除出界元素 
    	if(!q.empty() && q.front() < i-k)
			q.pop_front();
 		// 2.出队·维护单调递减 
		while(!q.empty() && A[i] >= A[q.back()])
			q.pop_back();
		// 3.入队·新元素加入 
		q.push_back(i);
		
		// 避免空队列 
		if(q.empty()) continue;

        int l = q.front(), r = i; // 扣除区间[l+1,r] (求和) 
		// 净胜球前缀和区间 
		int dif = A[r] - A[l],
			mg = M[r] - M[l], rg = R[r] - R[l];
		// 更新答案 
		if(dif < mini) // 区间内曼城净胜球更少, 扣除 
			mini = dif,
			Mgoal = mg, Rgoal = rg,
			left = l, right = r;
		else if(dif == mini)
			Mgoal = min(mg, Mgoal),
			Rgoal = min(rg, Rgoal),
			left = l, right = r;
			// 净胜球相同情况下, 扣除的进球越少越好(进球多) 
	}
	
	int Msum = 0, Rsum = 0;
	
	// 如果扣除的曼城净胜球是负数  
	if(mini < 0) 
		Msum = Mgoal,
		Rsum = Rgoal;
	
	// 扣除 
	int Mans = M[n] - Msum,
		Rans = R[n] - Rsum;
		
	cout << Mans << ':' << Rans;
}

彩蛋

这道题还有另外一种解法，稍做介绍。
其实这种方法与上文中的正解类似。
在新解法中，我们从皇马净胜球角度出发，转化题意：
通过前缀和、单调队列，求出长度不超过 KK 的区间内皇马的净胜球之和的最大值，并将这个区间扣除。同理，此时剩余的部分皇马净胜球最小，也即曼城净胜球最大。再最大化进球数。
注：如果所有区间中皇马净胜球之和的最大值是负数，就说明所有区间内曼城都占优，不需要扣除任何区间。
b={r1−m1,r2−m2,…,rN−mN}b=\{r_1-m_1,r_2-m_2,\dots,r_N-m_N\}，
改为求 S′=∑i=leftrightbiS'=\sum_{i=left}^{right}b_i 的最大值，以及此时以下两个式子的最大值。
∑i=1Nmi−∑i=leftrightmi\sum_{i=1}^{N}m_i-\sum_{i=left}^{right}m_i ∑i=1Nri−∑i=leftrightri\sum_{i=1}^{N}r_i-\sum_{i=left}^{right}r_i
如果 S′<0S'<0，直接求 ∑i=1Nmi\sum_{i=1}^{N}m_i 和 ∑i=1Nri\sum_{i=1}^{N}r_i 的值。

代码调整

代码主要需要更改的部分如下：
  1. 更改 AA 数组的值（与原值刚好相反）；
  2. 维护双端队列单调递减而非单调递增；
  3. 记录每次 S′S' 的最大值而非最小值；
  4. S′<0S'<0 时特殊处理。

新代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;

int M[N], R[N], a[N];

int main(){
	string s; getline(cin, s);
	// 特判1
	if(s == "Who is H?"){
		cout << "Erling Braut Haaland";
		return 0;
	}
	int n = s.size();
	int k; cin >> k;
	
	// 进球前缀和 
	for(int i=0; i<n; i++)
		M[i+1] = M[i] + (s[i] == 'M'),
		R[i+1] = R[i] + (s[i] == 'R');
		
	// 特判2 
	if(k == 0){
		cout << M[n] << ':' << R[n];
		return 0;
	}
		
	// 净胜球前缀和 
	for(int i=1; i<=n; i++)
		a[i] = R[i] - M[i];
		// 改成计算皇马净胜球 
		
	deque <int> q; 
	int maxi = INT_MIN, 
		Mgoal = 0, Rgoal = 0,
        left, right;
	for(int i=1; i<=n; i++){
		// 单调队列操作
		// 1.出队·移除出界元素 
    	if(!q.empty() && q.front()<i-k)
			q.pop_front();
 		// 2.出队·维护单调递增  
		while(!q.empty() && a[i] <= a[q.back()])
			q.pop_back();
		// 3.入队·新元素加入 
		q.push_back(i);
		
		// 避免空队列 
		if(q.empty()) continue;

        int l = q.front(), r = i; // 扣除区间[l+1,r] (求和) 
		// 净胜球前缀和区间 
		int dif = a[r] - a[l],
			mg = M[r] - M[l], rg = R[r] - R[l];
		// 更新答案 
		if(dif > maxi) // 区间内皇马净胜球增加, 扣除 
			maxi = dif,
			Mgoal = mg, Rgoal = rg,
			left = l, right = r;
		else if(dif == maxi)
			Mgoal = min(mg, Mgoal),
			Rgoal = min(rg, Rgoal),
			left = l, right = r;
			// 净胜球相同情况下, 扣除的进球越少越好(进球多) 
	}
	
	int Msum = 0, Rsum = 0;
	
	// 如果扣除皇马净胜球是正数 
	if(maxi > 0) 
		Msum = Mgoal,
		Rsum = Rgoal;
	
	// 扣除 
	int Mans = M[n] - Msum,
		Rans = R[n] - Rsum;
		
	cout << Mans << ':' << Rans;
}

声明

本篇题解同时也是 T606108 欧冠附加赛-XRX 的题解，但 T606108 数据未更正。
需要将以上 AC 代码的第 33 行：
CPP
const int MAX_N = 1e6+5;
调整为如下代码即可 AC。
CPP
const int MAX_N = 1.1e6+5

结尾

完结撒花！
作者：Doraeman。
完成时间：2025.8.12025.8.1。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...