题解 AT2650 【guruguru】

sky_of_war · 2019-05-23 16:38:55 · 题解

对于从a走到b来说

• 若选择的x=a 或 a+1，那么不会使步数减少

• 若选择的x=a+2，会使步数减少1

• 若选择的x=a+3，会使步数减少2

问题就变成了给区间[l,r]加首项为1，公差为1的等差数列

也就是给位置l 的元素加1，位置l+1的元素加2，位置l+2的元素加3……位置r的元素加r-l+1

令\text{cnt}[l]加1,\text{cnt}[r+1]减r-l+1+1，\text{cnt}[r+2]减r-l+1

对\rm cnt做一遍前缀和，得到差分数组

再做一遍前缀和，可以得到本身的值

这个被称为二阶差分

两遍前缀和后的\rm cnt数组就是把位置选在x，会使原本的步数减少多少

取最大的一个，总步数减它就是答案

时间复杂度O(n)

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;

const int MAXN = 1e5 + 10;
int n, m, first[MAXN], tot, d[MAXN], s, t;

struct edge { int from, v, w; } e[20 * MAXN];
struct Node
{
    int x, d;
    bool operator <(const Node &b)const
    {
        return d > b.d;
    }
}cyc;
priority_queue<Node> q;
inline void insert(int u, int v, int w)
{
    tot++; e[tot].v = v; e[tot].w = w; e[tot].from = first[u]; first[u] = tot;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (register int i = 1; i <= n; i++)
        for (register int j = 0; j <= 9; j++)insert(i, ((i - 1) * 10 + j) % n + 1, j);
    for (register int j = 1; j <= 9; j++) insert(0, j + 1, j);
    s = 0; t = 1;
    memset(d, 0x3f, sizeof d);
    d[s] = 0; q.push((Node) { s, d[s] });
    while (!q.empty())
    {
        cyc = q.top(); q.pop();
        if (cyc.d != d[cyc.x])continue;
        register int x = cyc.x;
        for (register int i = first[x]; i; i = e[i].from)
            if (d[e[i].v] > d[x] + e[i].w)
            {
                d[e[i].v] = d[x] + e[i].w;
                q.push((Node) { e[i].v, d[e[i].v] });
            }
    }
    return cout << d[t], 0;
}