P3336 [ZJOI2013]话旧

牛逼啊

分类讨论神题

首先我们明白极小值是什么,人言就是比周围的取值都小的一个函数值

然后我们考虑图形,显然是几个起起伏伏的三角形,但是但凡降就一定能降到0

有个这个关键信息,我们把所有点按照x坐标排序后就可以开始dp了

$f_{i,0/1}$ 表示到点i,点i之前的线段斜率是-1/1,

转移.....分类讨论大赛!

设 $x_1,y_1$ 为上一个点的坐标, $x_2,y_2$ 为这个点的坐标

$(x_2-x_1)==(y_2-y_1)$

说明我们一定是上升的两个点,而且中间全部都是上升段

那么我们只有一种连接方式,就是形成三角形的左侧上升段

$f_{i,1}+=f_{i-1,1}$

如果 $y_1$ 为0,我们点i-1可以作为转折点,方案数 $+f_{i-1,0}$

$(x_2-x_1)==(y_1-y_2)$

说明我们一定是下降的两个点,而且中间全部都是下降段

那么我们有两种连接方式,就是第一种在i-1处达到极大值,第二种在i-1处处于右侧下降段

$f_{i,0}+=f_{i-1,1}+f_{i-1,0}$

接下来分类讨论比较鬼畜,为了方便设 $len=x_2-x_1-y_2-y_1$

其实际意义就是如果我们能达到y=0,达到y=0最长的距离有多少

$len<0$

即我们达到不到0点,但是由于前两种情况都判过了,所以我们这个能够先下降后上升

中间可能有上转折点, $f_{i,0}+=f_{i-1,1}$

如果 $y_1==0$ ,还是可能i-1为转折点, $f_{i,0}+=f_{i-1,0}$

$len=0$

即我们能达到0点,但是不能再多走没用的步了QAQ

上转折下转折点都有可能

下转折点则一定是上升的,但是前者可能上升也可能下降啊

$f_{i,1}+=f_{i-1,1}+f_{i-1,0}$

上转折点一定是下降的,且前者只能上升

$f_{i,0}+=f_{i-1,1}$

len>0

唯一有可能使答案变大的情况

首先我们把len用上下起伏的锯齿代替,即

$____ -> '.'.'.'.'.$

然后里面的边缘有len/2-1个

但是两侧边缘还可能有,左侧能多出一个,右侧也多出一个

$f_{i,0}$ 我们必须拉开右侧锯齿,否则一定会导致是上升段

左侧锯齿,当 $f_{i-1,1}$ 的时候,i-1可以成为转折点,则我们可以选择拉开左侧锯齿

否则我们 $f_{i-1,0}$ 不可能拉开左侧锯齿,否则i-1处极小值不为0

$f_{i,1}$ ....好像必须不能拉开右侧锯齿,然后当 $y2==0$ 时暴毙不能上升

最大值第二问随便解解方程就有了

code:



#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int P = 19940417;
const int MAXN = 1e6 + 7;
int n, m, T, ans;
ll f[MAXN][2];
struct rec {
	int x, y;
	bool operator<(const rec &w)const {
		return x == w.x ? y < w.y : x < w.x;
	}
} a[MAXN], b[MAXN];

inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}

inline ll ksm(ll x, ll y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x % P;
		x = x * x % P;
		y >>= 1;
	}
	return ans;
}

int main() {
	scanf("%d%d", &n, &m);
	a[1].x = a[1].y = 0;
	a[m + 2].x = n;
	a[m + 2].y = 0;
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d", &a[i + 1].x, &a[i + 1].y);
	}
	m += 2;
	int qwq = 0;
	sort(a + 1, a + m + 1);
	for(int i = 1; i <= m; ++i) {
		if(i == 1 || a[i].x != a[i - 1].x || a[i].y != a[i - 1].y) {
			b[++qwq] = a[i];
		}
	}
	m = qwq;
	for(int i = 1; i <= qwq; ++i) {
		a[i] = b[i];
	}
	f[1][0] = 1;//初始化,从1,0是1
	for(int i = 2; i <= m; ++i) {
		int x2 = a[i].x;
		int x1 = a[i - 1].x;
		int y2 = a[i].y;
		int y1 = a[i - 1].y;
		int L = a[i].x - a[i - 1].x - a[i].y - a[i - 1].y;
		ans = max(ans, a[i].y);
		if(x2 - x1 == y2 - y1) {//f[i][1] update
			add(f[i][1], f[i - 1][1]);
			if(y1 == 0)add(f[i][1], f[i - 1][0]);//if 为0,说明我们可以起一个三角形
		} else if(x2 - x1 == y1 - y2) {//f[i][0] update
			add(f[i][0], f[i - 1][0]);
			add(f[i][0], f[i - 1][1]);
			//少讨论拐点为i-1的情况
		} else if(L < 0) {//空中转折,我们发现不能从下面走,否则极小值不为0
			//那么我们从上面走,满足f[i][0],f[i-1][1]
			//但是=0的可能有意思
			add(f[i][0], f[i - 1][1]);
			if(y1 == 0)add(f[i][0], f[i - 1][0]);
		} else if(L == 0) {
			//第一种走法从下面走可以,从上面走也可以
			//对应0,1 ,1,1, 1,0
			//如果是0,我们考虑都不考虑qwq
			add(f[i][0], f[i - 1][1]);
			if(y1 == 0)add(f[i][0], f[i - 1][0]);
			add(f[i][1], f[i - 1][0]);
			add(f[i][1], f[i - 1][1]);
			//注意这个拐点为i-1的情况...少讨论了
		} else if(L > 0) {//落地连接,我们在地面上可以起很多小三角形qwq
			//考虑拉平锯齿
			//如果我们上一个是上升的,则可以拉平的锯齿多一个
			//否则如果上一个是下降的,我们不能拉平边缘那个
			//如果我们这个是下升的,则我们必须拉平右边缘的锯齿?
			//否则我们这个是下降的,我们必须不拉平右边缘的锯齿
			ll a = ksm(2, L / 2 - 1);
			ll b = ksm(2, L / 2);
			add(f[i][0], f[i - 1][1] * b % P);
			add(f[i][0], f[i - 1][0] * a % P);
			if(y2 != 0) {
				add(f[i][1], f[i - 1][1] * b % P);
				add(f[i][1], f[i - 1][0] * a % P);
			}
		}
		if(f[i][0] || y2 == 0)
			ans = max(ans, y2 + (x2 - x1 - y2 + y1) / 2);
		//画画图即可
	}
	printf("%lld %d\n", f[m][0], ans);
	return 0;
}

夏晓光(loveJY)的博客

2020提高组十连测day2