题解 P3336 【[ZJOI2013]话旧】

renfei147 · 2019-10-30 18:38:30 · 题解

Dalao的题解过于简明扼要，蒟蒻看不懂。。思考了很久，好不容易想明白了，写篇详细题解

首先某咕题面有误，评论区喊了很久都没人修正。。原题题面为f(x)的极小值均是0（最小值均是0是bzoj上话旧2的题面）

然后这题可能无解，但看上去数据保证有解，所以下面的讨论都是在默认有解的前提下进行的

首先显然这个函数应该长这样，一旦开始下降就一定要降到0

因为一旦下降就不能中途上升，所以当前在上升还是下降对接下来的转移是有影响的吗，于是我们要把当前是在上升还是下降记入状态，记f[i][0/1]为到第i个点为止且第i个点为上升/下降（即上一个点在这个点下面/上面）。

那么第一个点应该算是上升点还是下降点呢？我们发现后面的零点都是下降点，所以第一个点也是下降点会比较和谐（下文有科学的解释）

考虑相邻两个点，记左边的点为(x_1,y_1)，右边的点为(x_2,y_2)，图中红色的线段记为len=x_2-x_1-y_1-y_2

可以发现只有当len\geq0时两边才能碰到底后再连接，len<0时只能“空中连接”

我们分别考虑两种情况：

空中连接

又可分为三种情况

在同一条上升线段上。后一个点肯定为上升点。如果前一个点是零点，那么上升下降均可，否则必须为上升点。
在同一条下降线段上。后一个点肯定为下降点，前一个点上升下降均可
先升后降。后一个点肯定为下降点，如果前一个点是零点，那么上升下降均可，否则必须为上升点。

if(x1-x2==y1-y2)
{
    add(f[i][0],f[i-1][0]);
    if(y1==0)add(f[i][0],f[i-1][1]);
}
else if(x1-x2==y2-y1)
{
    add(f[i][1],f[i-1][0]+f[i-1][1]);
}
else if(len<0)
{
    add(f[i][1],f[i-1][0]);
    if(y1==0)add(f[i][1],f[i-1][1]);//仔细想想会发现这个if是不必要的，这种情况在前面已经处理掉了
}

各种情况的连接方式都是唯一的，所以空中连接不会使答案变大。

落地连接

不同与空中连接，落地连接会使答案大大增大。

需要考虑四种情况。

最简单的情形是前一个点下降，后一个点上升

我们需要统计len上有多少不同的方案。首先我们让len上的图像上图那样构成一个个的“齿”，齿和齿之间就形成了一个个的“齿缝”。每个齿缝都可以进行一次“上拉”操作：

手玩一下可以发现每个拉齿缝的方案和最终形状是一一对应的。齿缝有\frac{len}{2}-1个，方案数即为2^{\frac{len}{2}-1}

然后考虑两个点都上升，这时我们可以把下图中红箭头所示的位置也看成一个齿缝，使每个拉齿缝的方案和最终形状再次一一对应。齿缝多了一个，所以方案数为2^{\frac{len}{2}}。如果把第一个点看作是上升点，那么这里会多算，所以第一个点必须是下降点。

最后考虑后一个点下降。

可以发现虽然少了一个齿，但多考虑了一个齿缝，所以刚才的两个式子仍然适用。需要注意如果后面一个点是零点，那么不能作为下降点。

另外len>0的时候也是可以空中连接的，但这就是“前一个点上升，后一个点下降，且所有齿缝都上提”的情况，不用单独考虑

综合四种情况，代码如下

ll t=(2*f[i-1][0]+f[i-1][1])*qpow(2,len/2-1)%mod;
if(y2>0)add(f[i][0],t);
add(f[i][1],t);

于是这题就被我们切掉啦！

才没有呢，我们还要求出最大值。。。显然要取最大值的话每两个相邻点之间的区间都是先尽量上升再下降，设有a格为上升，b格为下降，那么\left\{\begin{aligned}&a+b=x_2-x_1\\&a-b=y_2-y_1\end{aligned}\right.，最大值为y_1+a=\frac{1}{2}(x_2-x_1+y_1+y_2)

于是这题就真的被我们切掉啦！

完整代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=19940417;
const int MAXK=1000010;
struct Point
{
    int x,y;
};
bool operator<(const Point& a,const Point& b){return a.x<b.x;}
bool operator==(const Point& a,const Point& b){return a.x==b.x;}
Point p[MAXK];
ll f[MAXK][2];
ll qpow(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b%2)ret=ret*a%mod;
        b/=2;
        a=a*a%mod;
    }
    return ret;
}
inline void add(ll &x,ll y)
{
    x=(x+y%mod)%mod;
}
int main()
{
    int n,k,tmax=0;
    scanf("%d%d",&n,&k);
    p[k+1].x=n;
    for(int i=1;i<=k;i++)scanf("%d%d",&p[i].x,&p[i].y);
    sort(p,p+k+2);
    k=unique(p,p+k+2)-p-1;
    f[0][1]=1;
    for(int i=1;i<=k;i++)
    {
        int x1=p[i-1].x,y1=p[i-1].y;
        int x2=p[i].x,y2=p[i].y;
        int len=x2-x1-y1-y2;
        tmax=max(tmax,x2-x1+y1+y2);
        if(x1-x2==y1-y2)
        {
            add(f[i][0],f[i-1][0]);
            if(y1==0)add(f[i][0],f[i-1][1]);
        }
        else if(x1-x2==y2-y1)
        {
            add(f[i][1],f[i-1][0]+f[i-1][1]);
        }
        else if(len<0)
        {
            add(f[i][1],f[i-1][0]);
            if(y1==0)add(f[i][1],f[i-1][1]);
        }
        else if(len==0)
        {
            add(f[i][1],f[i-1][0]);
            if(y1==0)add(f[i][1],f[i-1][1]);
            add(f[i][0],f[i-1][0]+f[i-1][1]);
        }
        else
        {
            ll t=(2*f[i-1][0]+f[i-1][1])*qpow(2,len/2-1)%mod;
            if(y2>0)add(f[i][0],t);
            add(f[i][1],t);
        }
    }
    printf("%lld %d\n",f[k][1],tmax);
    return 0;
}