题解：P17325 [ICPC 2018 Nanjing R] Huge Discount
lailai0916
·
·
题解
题意简述
给定一个只含 0,1,2 的数字串。每次可以删除一对相邻且不同的数字。对每个后缀求能够得到的最小价格，并输出所有价格之和。
解题思路
对字符串 t，记数字 d 的出现次数为 c_d(t)，定义它相对其余数字的数量优势：
b_d(t)=2c_d(t)-|t|
每次删除两个不同数字，相当于把两个不同种类的字符配对。若 b_d(t)>0，其他字符总数不足以与全部 d 配对，所以至少会剩下 b_d(t) 个 d。反复让 d 与相邻的其他字符消去，并在剩余部分继续归纳，可以恰好只留下这些 d。
若没有数字超过一半，偶数长度字符串可以全部删空。奇数长度字符串至少留下一个字符，但不会被迫留下两个以上的同种字符。
因此，一个后缀 t 的最小价格先分成三类：
-
-
- 两者均不为正且 |t| 为偶数时，最小价格是 0。
只剩 |t| 为奇数且 b_1(t),b_2(t)\le0 的情况。此时最小价格只可能是 0 或 1。若首位就是 0，保留它并处理后面的偶数长度部分，价格一定可以降到 0。
设首位不是 0。价格能够降到 0，当且仅当存在一个奇数长度后缀 u，满足：
-
-
-
先证必要性。若 t 最后只剩 0，选择一个最终被保留的 0，令 u 从它开始。u 自身不能被迫留下 1 或 2，所以满足第二条。设 u 之前的偶数长度前缀为 p，则：
b_d(t)-b_d(u)=b_d(p)
再证充分性。第三条说明 $p$ 中的 $1$ 和 $2$ 均不超过其余字符总数，所以 $p$ 可以消成空串或若干个 $0$。$u$ 以 $0$ 开头，且其中的 $1,2$ 也都不占多数，所以它同样可以只留下 $0$。两部分合起来，$t$ 的价格为 $0$。若不存在这样的 $u$，奇数长度又不能删空，最小价格就是 $1$。
从右向左枚举 $t$，并维护所有满足前两条的候选后缀 $u$。每个候选对应二维点：
$$
(b_1(u),b_2(u))
$$
当前只需查询是否存在一个点同时满足两个坐标不小于 $(b_1(t),b_2(t))$。这是动态二维支配查询。
把第一坐标反向映射为：
$$
q(x)=n-x+1
$$
使用树状数组维护每个前缀中出现过的最大第二坐标。插入点 $(x,y)$ 时，在位置 $q(x)$ 更新值 $y+n+1$；查询当前点时，计算 `ask(q(x))`。候选的第一坐标不小于当前值，当且仅当它的映射位置不大于当前查询位置。若前缀最大第二坐标也不小于当前 $y$，所需候选就存在。
最后还要累加最长可达 $10^5$ 位的价格。由 $k$ 个相同数字 $d$ 组成的价格，会让十进制的第 $1$ 至第 $k$ 个低位各增加 $d$。在低位在前的数组上做区间差分，处理完全部后缀后求前缀和，再统一向高位进位即可。
每个后缀进行常数次树状数组操作，时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。
## 正确性证明
若某个数字超过字符串长度的一半，每次删除至多消去一个该数字，故至少剩下它的数量优势；通过不断与其他数字配对可以达到这个下界。没有多数数字时，偶数长度可以完全配对，奇数长度只能留下一个字符。前三类后缀的最小价格因此正确。
对剩余奇数后缀，前述三条件的必要性来自任取一个最终保留的零，并把它之前、之后分别观察；充分性来自两部分都能消成空串或纯零串。故价格为零与存在支配候选点完全等价，不存在时最小正价格只能是 $1$。
树状数组查询覆盖所有第一坐标不小于当前值的已插入候选，并返回其中最大的第二坐标。因此，它判定成功当且仅当存在同时满足两维不等式的候选。候选只在首位为零、长度为奇数且两个优势不为正时插入，恰好对应判定中的前两条。
差分数组给每个后缀的最小价格逐位增加正确的数字，十进制进位保持数值不变。因此，最终输出就是所有后缀最小价格之和。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=300005;
int tr[N],ans[N];
void add(int x,int v)
{
for(;x<N;x+=x&-x)tr[x]=max(tr[x],v);
}
int ask(int x)
{
int res=0;
for(;x;x-=x&-x)res=max(res,tr[x]);
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin>>n>>s;
int x=0,y=0;
for(int i=n-1;i>=0;i--)
{
x+=s[i]=='1'?1:-1;
y+=s[i]=='2'?1:-1;
if(x>0)
{
ans[1]++;
ans[x+1]--;
}
else if(y>0)
{
ans[1]+=2;
ans[y+1]-=2;
}
else if((n-i)&1)
{
int p=n-x+1;
if(s[i]=='0')add(p,y+n+1);
else if(ask(p)<y+n+1)
{
ans[1]++;
ans[2]--;
}
}
}
for(int i=1;i<N-1;i++)ans[i]+=ans[i-1];
for(int i=1;i<N-1;i++)
{
ans[i+1]+=ans[i]/10;
ans[i]%=10;
}
int p=N-1;
while(p>1&&!ans[p])p--;
for(int i=p;i;i--)cout<<ans[i];
cout<<'\n';
return 0;
}
```