洛谷P3336 [ZJOI2013]话旧题解

题目链接：P3336 [ZJOI2013]话旧

题意：小林跟着银河队选手去了一趟宇宙比赛，耳濡目染，变得学术起来。回来后，他发现世界大变样了。比丘兽究级进化，成了凤凰兽；金先生因为发了一篇 paper，一跃成为教授，也成为了银河队选拔委员会成员。

一日，小林与金教授聊天。金教授回忆起过去的岁月，那些年他学过的电路原理。他曾经对一种三角波很感兴趣，并且进行了一些探究。小林感到很好奇，于是金教授就将课题形式化地说了一遍。

有一定义在 $[0,N]$ 的连续函数 $f(x)$，其中 $N$ 是整数，满足 $f(0)=f(N)=0$，它的所有极值点在整数处取到，且 $f(x)$ 的极小值均是 $0$。对于任意的 $0$ 到 $N-1$ 间的整数 $I$，$f(x)$ 在 $(I, I+1)$ 上是斜率为 $1$ 或 $-1$ 的一次函数。

金先生研究的是，若他知道其中 $K$ 个整点的函数值，那么：

有多少个函数满足条件？

满足条件的函数中，$f(x)$ 的最大值，最大能是多少？

小林思考了一下，便想出了很好的算法。那么作为经过多年训练的你呢？

输入格式

第一行包含两个用空格隔开的整数 $N,K$。接下来 $K$ 行，每行两个整数，表示 $x_i$ 和 $f(x_i)$。

输出格式

一行两个整数，分别对应两个问题的答案。考虑到第一问答案可能很大，你只要输出它除以 $19940417$ 的余数。

输入输出样例

输入 #1
2 0
输出 #1
1 1
输入 #2
6 9
4 2
4 2
2 0
4 2
6 0
5 1
2 0
0 0
0 0
输出 #2
1 2
说明/提示

对于 $10\%$ 的数据，$N \leq 10$。

对于 $20\%$ 的数据，$N \leq 50$。

对于 $30\%$ 的数据，$N \leq 100$，$K \leq 100$。

对于 $50\%$ 的数据，$N \leq 10^3$，$K \leq 10^3$。

对于 $70\%$ 的数据，$N \leq 10^5$。

另有 $10\%$ 的数据，$K=0$。

对于 $100\%$ 的数据，$0 \leq N \leq 10^9$，$0 \leq K \leq 10^6$。

题目说了极小值为 $0$ ，说明每次下降都是直接一口气到底的

从文字中可以看出题目保证了有解（不然怎么输出最大值）

考虑设计状态 $dp[i][0/1]$ 表示是需要访问到 $i$ 结点时的路径是向上还是向下的

$dp[i][1] \to dp[i+1][0]$

显然延长左右的两条路径，可得零点 $a,b$

然后在 $a,b$ 间反复横跳便可以相连了

设 $a,b$ 间的距离为 $2k$ ，则方案数为 $2^{k-1}$

如下图 $(2k=6)$
```
\          /
 \        /
  \/\/\/\/
```
观察到其形成了 $4$ 个 \/ 的结构，不妨其为齿孔
```
\          /
 \  /\    /
  \/  \/\/
```
注意到此时除了两侧的齿孔不可扩展以外，其余均可扩展

故方案数为 $2^2 = 4$
$dp[i][0] \to dp[i+1][0]$

不妨将 $i$ 与其向上的路径看作一个点，则又可以确定两个零点 $a,b$

而此时左侧的齿孔也可以扩展了，而右侧的仍不可，故方案数为 $2^k$

如下图 $(2k=4)$
```
/\        /
  \      /
   \/\/\/
```
扩展左侧齿孔会变成
```
 /\      /
/  \    /
    \/\/
```
故方案数为 $2^2 = 4$
$dp[i][1]\to dp[i+1][1]$

与上一种情况类似，将 $i+1$ 与其向下的路径看作一个点

右侧的齿孔可以扩展，而此时左侧的不可，故方案数为 $2^k$
$dp[i][0] \to dp[i+1][1]$

考虑将 $i+1$ 与其向下的路径看作一个点

则此时左侧的齿孔可以扩展，而右侧的不可以

故方案数为 $2^k$

然而有些情况会导致 $k<0$ ，因此要特判一下

还有一些特殊的情况，比如 $i+1$ 恰好在 $i$ 的向上/下的路径上，也需要特判

然后最大值的求解，根据贪心，一定先选掉所有的上升

设有 $a$ 个上升， $b$ 个下降，则有

$\begin{cases} a+b = x_2-x_1 \\ a-b = y_2-y_1 \end{cases}$

则最大值为

$y_1+a = \dfrac{1}{2}(x_2+y_2-x_1 + y_1)$

但是要注意，如果可以选择向上，一定有 $dp[i][0]\ne0$

因此对于所有的 $i$ 到 $i+1$ 的转移，都额外计算一下先走到底再上升的情况，即

$\dfrac{1}{2}(x_2+y_2-x_1-y_1)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N (int)(1e6+15)
const int p=19940417;
int n,k,mx;
void add(int &a,int b){a=((a+b%p)%p+p)%p;}
int qpow(int a,int b)
{
    int ans=1,base=a%p;
    while(b)
    {
        if(b&1)ans=ans*base%p;
        base=base*base%p;
        b>>=1;
    }
    return ans;
}
struct node
{
    int x,y;
}a[N];
bool operator<(node a,node b)
    {return a.x<b.x;}
bool operator==(node a,node b)
    {return a.x==b.x&&a.y==b.y;}
int dp[N][2];
signed main()
{
    read(n);read(k);
    for(int i=1; i<=k; i++)
        read(a[i].x),read(a[i].y);
    a[++k]={0,0};a[++k]={n,0};
    sort(a+1,a+1+k);k=unique(a+1,a+1+k)-a-1;
    dp[1][1]=1;
    for(int i=1; i<k; i++)
    {
        int d=(a[i+1].x-a[i].x-a[i+1].y-a[i].y)>>1;
        mx=max(mx,(a[i+1].x+a[i+1].y-a[i].x-a[i].y)>>1);
        if(dp[i][0])mx=max(mx,(a[i+1].x+a[i+1].y-a[i].x+a[i].y)>>1);
        if(a[i+1].y-a[i].y==a[i].x-a[i+1].x)
            add(dp[i+1][1],dp[i][0]+dp[i][1]);
        else if(a[i+1].y-a[i].y==a[i+1].x-a[i].x)
            add(dp[i+1][0],dp[i][0]+(a[i].y?0:dp[i][1]));
        else if(d<0)
            add(dp[i+1][1],dp[i][0]);
        else if(d==0)
            add(dp[i+1][0],dp[i][0]+dp[i][1]),add(dp[i+1][1],dp[i][0]);
        else
        {
            int c=qpow(2,d-1);
            if(a[i+1].y)add(dp[i+1][0],(dp[i][1]+2ll*dp[i][0]%p)%p*c);
            add(dp[i+1][1],(dp[i][1]+2ll*dp[i][0]%p)%p*c);
        }
    }
    printf("%lld %lld\n",dp[k][1],mx);
    return 0;
}