「题解 P2282」HNOI2003 历史年份

November 27, 2020

2020   ·   OI   Chinese     ·   pre-university  

强化版 [HNOI2003]历史年份 & 弱化版 拆分数列

我们先来考虑弱化版:

首先进行正向 $dp$:

设 $f_i$ 表示以 $i$ 为结尾的最大前缀的起点下标, $num_{i,j}$ 为下标 $i-j$ 构成的数字. 显然, 这个下标越大 (接近 $i$) , 前缀越小, 得到的答案就越优, 所以:

$f_i=max{j}, j\in [1,i] \& \quad num_{f_{j-1},j-1}<num_{j,i}$

    f1[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        f1[i] = 1;
        for (int j = i; j >= 1; j--)
            if (comp(f1[j - 1], j, i))
            {
                f1[i] = j;
                break;
            }
    }

$comp()$的朴素实现方式:

bool comp(int l, int m, int r)
{
    int len1 = m - l, len2 = r - m + 1;
    int st1 = l, ed1 = m - 1;
    int st2 = m, ed2 = r;
    if (len1 < len2)
    {
        while (st2 - m + 1 <= len2 - len1)
        {
            if (str[st2] != '0')
                return 1;
            st2++;
        }
    }
    if (len1 > len2)
    {
        while (st1 - l + 1 <= len1 - len2)
        {
            if (str[st1] != '0')
                return 0;
            st1++;
        }
    }
    len1 = len2 = min(len1, len2);
    for (int i = 0; i < len1; i++)
        if (str[st1 + i] != str[st2 + i])
            return str[st2 + i] > str[st1 + i];
    return 0;
}

再考虑反向 $dp$:

设 $f_i$ 表示以 $i$ 为起点的最大后缀的终点下标, 显然, 这个下标越大 (接近 $n$) , 后缀越大, 得到的答案就越优, 所以:

$f_i=max{j}, j\in [i,j] \& \quad num_{i,j}<num_{j+1,f_{j+1}}$

但是我们必须考虑到前导零对一个数字的大小是没有影响的, 那么对于第一遍正向 $dp$ 得出的最大的最后一个数, 可以在其前面加上若干个前导零, 这些前导零在 $f$ 数组中指向的下标应该都为 $n$

    int las = n;
    while (las >= f1[n] || str[las] == '0')
    {
        f2[las] = n;
        las--;
    }
    for (int i = las; i >= 1; i--)
    {
        f2[i] = i;
        for (int j = n - 1; j > i; j--)
            if (comp(i, j + 1, f2[j + 1]))
            {
                f2[i] = j;
                break;
            }
    }

那么我们就能完成弱化版了

时间复杂度:

$DP: O(n^2)$

每次比较: $O(n)$

总时间复杂度: $O(n^3)$

当然, 这样的复杂度并不能帮助我们通过其强化版:

$T=1000, n=2000$, 期望时间复杂度$O(Tn)-O(Tnlogn)$

对于原算法考虑进行优化:

  1. 对于第一遍 $dp$, 考虑将每一个确定的 $f_j$ 直接往后更新, 凡是满足 $num_{f[j], j} < num_{j+1, i}$ 的 $f_i$, 均可以被 $j$ 更新, 很显然, 每一次均可更新一个区间 $[i_{min}, n]$

  2. 对于第二遍 $dp$, 考虑将每一个确定的 $f_j$ 直接往前更新, 凡是满足 $num_{i, j} < num_{j+1, f_{j+1}}$ 的 $f_i$, 均可以被 $j$ 更新, 很显然, 每一次均可更新一个区间 $[i_{max}, j]$

以上两步, 均可以使用线段树将 $DP$ 将填表的时间复杂度优化至 $O(nlogn)$

但是我们仍然无法快速得到两次 $DP$ 的 $i_{min}, i_{max}$, 此时我们考虑直接用位数进行比较, 用第一次DP进行举例:

$\because num_{f_{j-1},j-1}<num_{j,i}$

$\therefore (j-1)-f_{j-1}+1 \le i-j+1$ (不考虑前导零)

$\therefore i \ge 2j-f_{j-1}-1$

若考虑前导零, 可以预处理将 $i$ 左边与右边 (包括 $i$) 的第一个非零数字求出来, 表示为 $lasn_i$ 与 $nexn_i$, 那么上式将变为:

$i_{min} = nexn_i + (i - nexn_{f_{i - 1}}) - 1$

注意到推导的前两位并非等价转化, 那么我们再进行一次 $comp(f_{j-1}, j, i_{max})$, 若不合法再往后跳一位即可

这样的话我们的理论时间复杂度就降到了 $O(Tn^2)$, 当然实际上比较函数是完全跑不满的, 再套一个 $O2$ 可能能卡过

这个时候我们再来考虑每一次 $comp$ 函数的优化, 之前考虑的是朴素比较, 但由于我们现在只需要知道两个由数字构成的字串的大小, 不妨考虑哈希算法:

void pre_hash()
{
    num[0] = 0;
    for (int i = 1; i <= n; i++)
        num[i] = (1LL * num[i - 1] * 10 + str[i] - '0') % MOD;
}

inline bool equal(int st1, int st2, int len)
{
    int ed1 = st1 + len - 1, ed2 = st2 + len - 1;
    return (num[ed1] - fac[len] * num[st1 - 1] % MOD + MOD) % MOD == (num[ed2] - fac[len] * num[st2 - 1] % MOD + MOD) % MOD;
}

但是, 他假了！！！

可能是我的模数或进制写的太弱了, 所以单哈希就这样被卡了, 于是最后改了个双哈希终于勉强过了

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int MAXN = 2e3 + 5;
const ll MOD1 = 1e9 + 7, MOD2 = 19260817;

int T, n;
char str[MAXN];
ll num1[MAXN], num2[MAXN], fac1[MAXN], fac2[MAXN];
int f1[MAXN], f2[MAXN];
int nexn[MAXN], lasn[MAXN];

class SegmentTree
{

#define sn segTree[node]

    struct TreeNode {
        int l, r;
        int lson, rson;
        int data;
    } segTree[MAXN << 2];

    void pushdown(int node)
    {
        if (sn.data)
        {
            segTree[sn.lson].data = max(segTree[sn.lson].data, sn.data);
            segTree[sn.rson].data = max(segTree[sn.rson].data, sn.data);
            sn.data = 0;
        }
    }

public:

    void build(int node, int l, int r)
    {
        sn.l = l;
        sn.r = r;
        sn.data = 0;
        if (l != r)
        {
            sn.lson = node << 1;
            sn.rson = node << 1 | 1;
            int mid = (l + r) >> 1;
            build(sn.lson, l, mid);
            build(sn.rson, mid + 1, r);
        }
    }

    int ask(int node, int pos)
    {
        if (sn.l == sn.r)
            return sn.data;
        pushdown(node);
        int mid = (sn.l + sn.r) >> 1;
        if (pos <= mid)
            return ask(sn.lson, pos);
        else return ask(sn.rson, pos);
    }

    void change(int node, int l, int r, int val)
    {
        if (l > sn.r || r < sn.l)
            return;
        if (l <= sn.l && r >= sn.r)
            sn.data = max(sn.data, val);
        else {
            pushdown(node);
            change(sn.lson, l, r, val);
            change(sn.rson, l, r, val);
        }
    }
} stree;

inline bool equal(int st1, int st2, int len)
{
    int ed1 = st1 + len - 1, ed2 = st2 + len - 1;
    bool res1 = (num1[ed1] - fac1[len] * num1[st1 - 1] % MOD1 + MOD1) % MOD1
             == (num1[ed2] - fac1[len] * num1[st2 - 1] % MOD1 + MOD1) % MOD1;
    bool res2 = (num2[ed1] - fac2[len] * num2[st1 - 1] % MOD2 + MOD2) % MOD2
             == (num2[ed2] - fac2[len] * num2[st2 - 1] % MOD2 + MOD2) % MOD2;
    return res1 & res2;
}

bool comp(int l, int m, int r)
{
    int st1 = l, ed1 = m - 1;
    int st2 = m, ed2 = r;
    st1 = nexn[st1];
    st2 = nexn[st2];
    int len1 = ed1 - st1 + 1, len2 = ed2 - st2 + 1;
    if (len2 <= 0)
        return 0;
    if (len1 <= 0)
        return 1;
    if (len1 != len2)
        return len1 < len2;
    int le = 0, ri = len1 - 1, res = -1;
    while (le <= ri)
    {
        int mid = (le + ri) >> 1;
        if (equal(st1, st2, mid))
        {
            res = mid;
            le = mid + 1;
        }
        else ri = mid - 1;
    }
    return str[st1 + res] < str[st2 + res];
}

void pre_pow()
{
    fac1[0] = 1LL;
    for (int i = 1; i <= 2000; i++)
        fac1[i] = 1LL * fac1[i - 1] * 10 % MOD1;
    fac2[0] = 1LL;
    for (int i = 1; i <= 2000; i++)
        fac2[i] = 1LL * fac2[i - 1] * 11 % MOD2;
}

void pre_hash()
{
    num1[0] = 0;
    for (int i = 1; i <= n; i++)
        num1[i] = (1LL * num1[i - 1] * 10 + str[i] - '0') % MOD1;
    num2[0] = 0;
    for (int i = 1; i <= n; i++)
        num2[i] = (1LL * num2[i - 1] * 11 + str[i] - '0') % MOD2;
}

void deal_zero()
{
    for (int i = n, j = n + 1; i >= 1; i--)
    {
        if (str[i] != '0')
            j = i;
        nexn[i] = j;
    }
    for (int i = 1, j = 0; i <= n; i++)
    {
        if (str[i] != '0')
            j = i;
        lasn[i] = j;
    }
}

int main()
{
    pre_pow();
    while (scanf("%s", str + 1) != EOF)
    {
        n = strlen(str + 1);
        pre_hash();
        deal_zero();
        stree.build(1, 1, n);
        stree.change(1, 1, n, 1);
        f1[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            int nex = nexn[i] + (i - nexn[f1[i - 1]]) - 1;
            if (!comp(f1[i - 1], i, nex))
                nex++;
            stree.change(1, nex, n, i);
            f1[i] = stree.ask(1, i);
        }
        int las = lasn[f1[n] - 1];
        stree.build(1, 1, n);
        stree.change(1, las + 1, n, n);
        f2[n] = n;
        for (int i = n - 1; i >= 1; i--)
        {
            f2[i] = max(i, stree.ask(1, i));
            int fir = i - (f2[i + 1] - nexn[i + 1]);
            if (!comp(fir, i + 1, f2[i + 1]))
                fir++;
            fir = lasn[fir - 1] + 1;
            if (fir < 1) fir = 1;
            stree.change(1, fir, i - 1, i);
        }

        for (int i = 1; i <= n; i++)
        {
            int j = i;
            while (j <= f2[i] && j <= n)
                putchar(str[j++]);
            i = j - 1;
            if (i != n) putchar(',');
        }
        putchar('\n');
    }
    return 0;
}