P1311 [NOIP2011 提高组] 选择客栈 - 题解
Leo_Anderson
·
·
题解
P1311 [NOIP2011 提高组] 选择客栈
2023/11/17 Fri.
-原题链接-
-题解原文-
题意简述
有 N 个点，包含 K 种颜色，所能接受的最大价格为 P。
\left( 2 \le N \le 2 \times 10^{5} , 1 \le K \le 50 , 1 \le P \le 100 \right)
其中第 i 个点的颜色为 a_i \left( a_i \in \left[ 0,K-1 \right] \right) ，价格为 b_i \left( b_i \in \left[ 0,100 \right] \right) 。
请问存在多少个点对 \left( x,y \right) \left( 1 \le x<y \le N \right) ，使得 a_x = a_y 并且 \exists b_i \le P , i \in \left[ x,y \right]。
题目分析
思路
-
由于点对 \left( x,y \right) 必须符合 a_x = a_y ，所以可以将 K 种颜色拆开处理（具体表现为代码均使用大小为 K 的数组记录数值)，最后将 K 种颜色的方案数加在一起即为总答案方案数。
-
对于每种颜色的方案数，可以利用递推求得，因此可以在数据读入的时候边读入边处理答案（具体解释见下文做法分析）。
做法分析
因为 思路 1，所以我们将 K 种颜色分开处理。
如下图，
**黑横线** 代表所有读入的点，
**红竖线** 代表所有颜色为 $[K]$ 的点，
**绿竖线** 代表所有价值 $\le P$ 的点。
（$hav$，$cor$，$ans$ 均为储存用数组，具体作用见下文）
然后解释 ***思路 2***。
对于上图中的每一个合法点（即红色竖线），只需计算它与它之前的合法点的可构成的所有答案点对的数量，然后将每一个点可构成的答案点对的数量求和即为该种颜色的方案数。
因此我们选择递推求解。
那么如何求每一个点所拥有的答案点对的数量呢？
首先定义一下在图中如何判断一个点对是答案点对：
如果两个**合法点**（红色竖线）间（**包括合法点本身**）存在**至少一个答案点**（绿色竖线，其对应的 $b_i\le P$ ）时，
那么这两个点所组成的点对即为一个**答案点对**。
首先对于图中第 2、3 个合法点进行分析（每两个合法点间都有一个答案点）。
我们不难发现合法点 2 可以和它前面的 1 个合法点组成答案数点对，
因此我们可以得出初步结论：**每一个合法点可构成的答案点对数量即为该点以前所有合法点的数量。**
- 所以我们使用一个数组 $hav$ 记录当前时刻下对应颜色所拥有的合法点的数量。
同时要注意一点：我们要使用的合法点数量是**不包括当前所处理的合法点**的，所以要在当前点的所有数据处理完后再进行 `hav++`。
记录一下每个合法点处理时所对应的 $hav$。
接着我们对第 4 个合法点进行分析（除与上一个合法点间没有答案点外，与其余合法点间都有至少一个答案点）。
此时我们发现仅有前 2 个合法点可以和他组成答案点对！因为第 3 个合法点和第 4 个合法点间不存在答案点！
这个时候答案点对数量与 $hav$ 不相等了。
我们需要别的方式来计算答案点对数量。
保险起见我们再对第 6 个合法点分析一下（一般情况）。
这时我们发现虽然合法点 3、4 间不存在答案点，但是由于合法点 4、5 间存在一个答案点，所以合法点 3、4 也成为了可以与合法点 6 组成答案点对的点。
不难发现这其中存在一个单调不减的答案点对数量。
- 所以我们还需要一个数组 $cor$ 来记录当前的答案点对数量。
通过观察 $hav$ 和 $cor$ 的关系，不难发现特征：
**当处理遇到一个答案点时，就将下一个合法点的 $cor$ 更新为其对应的 $hav$。**
**若从前一个合法点处理到当前合法点的过程中没有出现过答案点，那么当前点的 $cor$ 值继承上一个合法点的 $cor$。**
- 因此我们可以用一个变量 $flag$ 记录离当前处理的合法点最近的一个答案点的位置，用数组 $lst$ 储存每种颜色的最后一个合法点的位置。
若 $ lst_{[K]} \le flag $，则上一个合法点与当前处理的合法点间存在答案点。
最后就是记录答案的 $ans$ 数组。
- 由于我们已经将答案点对数量存进了 $cor$ 数组里，所以新的 $ans$ 即为 $ ans + cor_{[K]} $。
得到最后的状态图：
~~经人工暴力查数量发现，最后的 ans 和当前颜色 [K] 所拥有的所有答案点对数量一致，算法成立。~~
因为边读入边处理，所以每一次处理均为 $O(1)$，总复杂度为 $O(N)$。
最后对所有颜色方案数求和复杂度为 $O(K)$，但 $1 \le K \le 50$，故求和时间可以省略。
因此该做法时间复杂度 $O(N)$，做法可行。
***~~（另：你要是想在处理的时候就把总方案数加起来以节约掉 ans 数组也不是不行）~~***
- - - -
## 主要解答过程
对于当前读入：
1. 对于当前点 $i$，读入其颜色 $a_i$ 和价格 $b_i$。
2. 如果 $b_i\le P$，则将 $flag$ 更新为 $i$。
3. 如果 $lst_{a_i}\le flag$，并且上一个合法点是存在的 $\left( lst_{a_i} \ne 0 \right)$，则将 $cor_{a_i}$ 更新为 $hav_{a_i}$。
4. $ans_{a_i}$ 更新为 $ ans_{a_i} + cor_{a_i}$。
5. $lst_{a_i}$ 更新为 $i$。
6. $hav_{a_i}$ 自增 $1$。
- - - -
## 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
#define lli long long
//#define int long long
#define MAXK 55
int N,K,P;
int hav [MAXK];
int cor [MAXK];
int flag;
int lst [MAXK];
int ans [MAXK];
int outnum=0;
//---------------------
signed main(){//注：signed == int，均表示有符号整数。
cin>>N>>K>>P;
for(int i=1;i<=N;i++){
int a,b;scanf("%d%d",&a,&b);
if(b<=P)flag=i;
if(lst[a]<=flag && lst[a]!=0)cor[a]=hav[a];
ans[a]+=cor[a];
lst[a]=i;
hav[a]++;
}
for(int i=0;i<K;i++)
outnum+=ans[i];
cout<<outnum<<"\n";
return 0;
}
```
**[100pts，AC.](https://www.luogu.com.cn/record/163306438)**