一些有意思的 CF 题解集锦

Education Codeforces Round 111

C:Manhattan Subarrays

题意：

给定一个系列点 $(1,b_1),(2,b_2) ,..., (n,b_n)$，
对于三个点 $A,B,C$ ，若存在两点的曼哈顿距离等于该两点与另一点曼哈顿距离的和，则称其为“糟糕”。
对于该系列点的一段连续区间，若其中任意三个点都非“糟糕”，则该子区间是“优秀”的。
求“优秀”子区间的数量。

思路：

本题正解是基于某个数学结论的贪心，具有一定的思维性而不具有普适性，这里记一种比较通用的解法：单调栈+线段树。

题意解析

本题题目大意是给定一系列点 $(i,b_i)$，找出所有的子区间，使得该区间内任意三点 $A,B,C$ 中，任意两点的曼哈顿距离与二者分别到第三点的曼哈顿距离和不等。

原题意思很绕，但你分析一下就可以将其转换为：对于子区间内任意三点的 y 值 $b_x,b_y,b_z$，保证不会单调增，也不会单调减。换句话说，该子区间的最长不上升子序列与其最长不下降子序列的长度不会超过三。

这样一想就会有很多方式可以去维护信息了。

算法解析

由于最长不上升与最长不下降问题是类似的，我们这里只讨论最长不下降问题。

既然我们不能让最长不下降子序列长度为三，那么对于任意一个点 $i$，我们只需要找到恰好使长度为三的点 $l$，之后的点就都满足条件了，那么 i 点对于答案的贡献就是$i-l$。

我们有一个最直观的想法：维护一个 $up[i]$ 表示小于等于 $b_i$ 的点出现的最大位置。很明显，$up[i]$ 可以用单调栈进行维护，这样的话 $up[up[i]]$ 不就是我们要找的答案了吗？

但这明显是有问题的，HACK 数据如下：

5
1 4 5 2 6

对于 $i=5$，$ up[5]=4 , up[4]=1$，而我们发现对于 $i=2,3,5$ 已经构成了长度为三的最长不上升子序列。这种想法的问题在于过于贪心造成了目光短浅。

现在我们要做的就是找一种方法，可以维护当前点之前（换句话说，$j \in [1,i)$ ）所有的 $up[j]$值，并在 $b_j \leqslant b_i$ 的范围内挑一个 $up[j]$ 最大的，那就是我们要的 $l$。

于是我们就维护一个经离散化的权值线段树（你要是会动态线段树那就更好了），在 $b_j$ 的位置上维护其 $up[j]$ 的最大值，当询问至 $i$ 点时，我们只需要查询 $(1,b_i ]$ 中的最大值，就是我们要找的答案了。

细节实现

• 我们仍要注意到，询问第 $i$ 个节点并不意味着最长不上升子序列的第三位必须以 $b_i$ 结束，HACK 数据如下：

  7
  7 4 8 1 4 5 2

  对于 $i=7$，以 $b_7=2$ 结尾的最短不上升子序列是 以 $i=3$ 为首的 $8,5(4),2$ ，然而我们可以注意到对于以 $i=4$ 为首的 $1,4,5$ 已经构成了最长不下降子序列，因此 $l=4$，因此我们应该保证我们求得的$l$应该是不单调递增的。代码对这里进行处理。

• 其次，对于多个小问的题目不能用 memset，会被 TLE 成傻逼。

然后就没了，献上丑陋的代码：

#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
#define inf 2147483647
#define maxn 200010
#define mid (l+r)/2

using namespace std;

int t,n,a[maxn],b[maxn],dn[maxn],up[maxn];
int t_s[maxn*4],t_b[maxn*4];

void build_s(int o,int l,int r)
{
	if (l==r) t_s[o]=0;
else
{
	build_s(o*2,l,mid); build_s(o*2+1,mid+1,r);
	t_s[o]=0;	
}
}

void build_b(int o,int l,int r)
{
	if (l==r) t_b[o]=0;
else
{
	build_b(o*2,l,mid); build_b(o*2+1,mid+1,r);
	t_b[o]=0;
}
}

int find_s(int o,int l,int r,int x,int y)
{
//	printf("%d %d %d -> %d %d\n",o,o<<1,o<<1 |1,x,y);
	if (x<=l && r<=y) return t_s[o];
	if (l>y || r<x) return -1;
	return max(find_s(o*2,l,mid,x,y),find_s(o*2+1,mid+1,r,x,y));
}

int find_b(int o,int l,int r,int x,int y)
{
	if (x<=l && r<=y) return t_b[o];
	if (l>y || r<x) return -1;
	return max(find_b(o*2,l,mid,x,y),find_b(o*2+1,mid+1,r,x,y));
}

void update_s(int o,int l,int r,int x,int k)
{
	if (l==r && l==x) {t_s[o]=max(t_s[o],k);return;}
	if (l>x || r<x) return;
	update_s(o<<1,l,mid,x,k); update_s(o<<1 | 1,mid+1,r,x,k);
	t_s[o]=max(t_s[o<<1],t_s[o<<1 |1]);
}

void update_b(int o,int l,int r,int x,int k)
{
	if (l==r && l==x) {t_b[o]=max(t_b[o],k);return;}
	if (l>x || r<x) return;
	update_b(o<<1,l,mid,x,k); update_b(o<<1 |1,mid+1,r,x,k);
	t_b[o]=max(t_b[o<<1],t_b[o<<1 |1]);
}

int main()
{	
scanf("%d",&t);
while (t--)
{
	scanf("%d",&n);	
	for (int i=1;i<=n;i++) {
		scanf("%d",&a[i]),b[i]=a[i];
	}	
	for (int i=1;i<=n;i++) dn[i]=up[i]=0;
	sort(b+1,b+n+1); int N=unique(b+1,b+n+1)-(b+1);  stack<int> s;
	for (int i=1;i<=n;i++) {  //find the smaller left
		while (!s.empty() && a[s.top()]>a[i]) s.pop();
		if (!s.empty()) up[i]=s.top();	s.push(i);
	}	
	while (!s.empty()) s.pop();
	for (int i=1;i<=n;i++) {  //find the bigger left
		while (!s.empty() && a[s.top()]<a[i]) s.pop();
		if (!s.empty()) dn[i]=s.top();	s.push(i);
	}
//	for (int i=1;i<=n;i++) printf("%d,%d\n",dn[i],up[i]);

	int ans=0,l=0;
	build_s(1,1,N); build_b(1,1,N);
	for (int i=1;i<=n;i++) {
		int p=lower_bound(b+1,b+N+1,a[i])-b;
		int second_s=find_s(1,1,N,1,p),second_b=find_b(1,1,N,p,N);
		l=max(l,max(second_s,second_b));
     //对细节一的处理
     	ans+=i-l;  
		update_s(1,1,N,p,up[i]); update_b(1,1,N,p,dn[i]);
	}
	printf("%d\n",ans);
}
}

Codeforces Round #765

C. Road Optimization

题意：

给你 n 个路障，给定每个路障的坐标 $d_i$ 与 限速 $a_i$，要求在 $d_i$ 至 $d_{i+1}$ 范围内的时长不能小于 $a_i$。
现在可以拆掉至多 k 个，问怎么拆使得全程时间最短。

分析：

考试写了傻卵贪心，快结束时候发现贪不了要 DP。
设 $f[i][j]$ 为 前 i 个路障已经拆了 j 个，你要枚举 可以转移到(i,j) 的状态就挺困难（刷表），但是可以很清楚地找出所有 由该状态转移出的 所有状态（填表）。

for (int i = 1; i <= n+1; i++)
for (int j = 0; j <= k; j++) {
    for (int pos = i+1; pos <= n+1; pos++) {
        f[pos][j+pos-i-1] = min(f[pos][j+pos-i-1], f[i][j] + a[i] * (d[pos] - d[i]));
        //拔掉了 [i+1,pos-1] 内的路牌。
    }
}