P3336 [ZJOI2013]话旧

P3336 [ZJOI2013]话旧

题意:

\(f(x)\) 为定义在 \([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\) 个整点的函数值，那么:

1. 有多少个函数满足条件？
2. 满足条件的函数中，\(f(x)\) 的最大值，最大能是多少？

思路:

第一问:
https://www.luogu.com.cn/blog/renfei147/solution-p3336
第二问:
https://untitled0.blog.luogu.org/p3336

实现:

#include <bits/stdc++.h>
using namespace std;
const int mod = 19940417;
typedef long long ll;
ll ksm(ll a, ll b)
{
    ll res = 1 % mod;
    while (b)
    {
        if (b & 1)
            res = (res * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return res;
}

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    vector<pair<int, int>> ve(k + 2);
    for (int i = 1; i <= k; i++)
        scanf("%d%d", &ve[i].first, &ve[i].second);
    ve[k + 1].first = n, ve[k + 1].second = 0;
    sort(ve.begin() + 1, ve.end());
    auto it = unique(ve.begin(), ve.end());
    ve.erase(it, ve.end());
    vector<vector<ll>> f(k + 2, vector<ll>(2, 0));
    f[0][1] = 1;

    int tmax = 0; // 记录最大值
    for (int i = 1; i <= ve.size() - 1; i++)
    {
        int x1 = ve[i - 1].first, y1 = ve[i - 1].second;
        int x2 = ve[i].first, y2 = ve[i].second;
        int x0 = x1, y0 = y1;
        if (!f[i - 1][0])
        {
            x0 = x1 + y1, y0 = 0;
        }
        tmax = max(tmax, (x2 - x0 + y0 + y2) / 2);
        int len = x2 - x1 - y1 - y2;

        // 在同一条上升线段上
        if (x1 - x2 == y1 - y2)
        {
            f[i][0] = (f[i][0] + f[i - 1][0]) % mod;
            if (y1 == 0)
                f[i][0] = (f[i][0] + f[i - 1][1]) % mod;
        }
        else if (x1 - x2 == y2 - y1) // 在同一条下降线段上
        {
            f[i][1] = (f[i - 1][0] + f[i - 1][1]) % mod;
        }
        else if (len < 0) // 先升后降
        {
            f[i][1] = (f[i][1] + f[i - 1][0]) % mod;
            if (y1 == 0)
                f[i][1] = (f[i][1] + f[i - 1][1]) % mod;
        }
        else if (len == 0)
        {
            f[i][1] = (f[i][1] + f[i - 1][0]) % mod;
            if (y1 == 0)
                f[i][1] = (f[i][1] + f[i - 1][1]) % mod;
            f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
        }
        else
        {
            ll t = (2 * f[i - 1][0] + f[i - 1][1]) % mod * ksm(2, len / 2 - 1) % mod;
            if (y2 > 0)
                f[i][0] = (f[i][0] + t) % mod;
            f[i][1] = (f[i][1] + t) % mod;
        }
    }
    printf("%lld %d\n", f[ve.size() - 1][1], tmax);
    return 0;
}