P7116 [NOIP2020] 微信步数 - 洛谷 - 计算机科学教育新生态">P7116 [NOIP2020] 微信步数 - 洛谷 - 计算机科学教育新生态"> P7116 [NOIP2020] 微信步数 - 题解 - TonyYin - Blog
P7116 [NOIP2020] 微信步数

题意

P7116 [NOIP2020] 微信步数 – 洛谷 – 计算机科学教育新生态

给定 $k$ 维场地,场地中的坐标表示为 $(a_1, a_2, \cdots, a_k)$,场地有大小限制 $w$,$1\leq a_i\leq w_i$.

给定 $n$ 个指令构成的指令序列,每个指令用 $(c_i, d_i)$ 表示,代表在第 $c_i$ 维上移动 $d_i\in\{-1, 1\}$。形式化地,若当前位于 $(a_1, a_2, \cdots, a_{c_i}, \cdots, a_k)$,下一步会到 $(a_1, a_2, \cdots, a_{c_i}+d_i, \cdots, a_k)$.

现在,小 $C$ 要从场地中的所有 $P=\prod_{i=1}^k{w_i}$ 个点分别出发,不断重复这个路线,直到其走出场地范围。也就是说,走完 $n$ 步之后,如果小 $C$ 还在场地内,他将回到第 $1$ 步,从头再走一遍。

每执行一次指令代表走一步,求从这 $P$ 个点出发一共走了多少步,对 $10^9+7$ 取模。

若有一天永远走不出场地,输出 $-1$.

测试点编号$n \le$$k \le$$w_i \le$
$1 \sim 3$$5$$5$$3$
$4 \sim 6$$100$$3$$10$
$7 \sim 8$${10}^5$$1$${10}^5$
$9 \sim 12$${10}^5$$2$${10}^6$
$13 \sim 16$$5 \times {10}^5$$10$${10}^6$
$17 \sim 20$$5 \times {10}^5$$3$${10}^9$

题解

分析

如果分别计算每个点的话,那复杂度一定会有一个 $\prod_{i=1}^k{w_i}$,所以把每一维分开考虑。

不妨设我们在考虑第 $i$ 维的情况。对于维度 $i$ 的某个位置 $p\in[1, w_i]$,设 $\operatorname{time}_i(p)$ 表示在仅考虑维度 $i$ 时小 C 走出场地需要的最少步数。如果无论如何都无法走出场地那么 $\operatorname{time}_i(p)=+\infty$ 。

注意这里是仅考虑维度 $i$ 时,不考虑先从其他维度走出场地的情况。

求出 $\operatorname{time}$ 这个函数之后,小 C 从 $(a_1,a_2,\dots,a_k)$ 走出场地需要的步数就是 $\min_{i=1}^k\operatorname{time}_i(a_i)$.

因此,题目最终的答案表示为:

$$
\operatorname{Ans} = \sum_{(a_1, a_2\cdots, a_k)\in \operatorname{Map}}\min_{i=1}^k\operatorname{time}_{i}(a_i)
$$

转化

这样求解的复杂度仍是 $\prod_{i=1}^k{w_i}$ 的,不能接受。对上面的式子改变枚举顺序,可以得到:

$$
\operatorname{Ans} = \sum_{(a_1, a_2\cdots, a_k)\in \operatorname{Map}}\min_{i=1}^k\operatorname{time}_{i}(a_i)=\sum_{i\ge 1}\prod_{j=1}^k(\sum_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i])
$$

$\sum\limits_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i]$ 代表,在仅考虑第 $j$ 维的情况下,第 $j$ 维中走完 $i$ 步还在地图内的坐标个数

$\prod\limits_{j=1}^k(\sum\limits_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i])$ 代表,走完 $i$ 步仍然在场地内的点的个数。根据乘法原理,把每个维度上可行的坐标乘起来,所得到的就是可行点的个数。

最外层枚举 $i$ 表示:走完 $i$ 步仍然在场地内

显然,枚举 $i$,把所有可行点数加起来,得到的就是总步数。

容易发现,对这个式子求和的复杂度不再需要 $\prod_{i=1}^k{w_i}$ 了,下面是一种可行的计算方法。

计算方法

假设我们现在已经求出了所有的 $\operatorname{time}_i(j)$.

首先,我们把所有的 $\operatorname{time}_i(j)$ 拿出来,降序排序,同时存储 $\operatorname{time}_i(j)$ 所处的维度。

for(int i = 1; i <= k; i++) 
    for(int j = 1; j <= w[i]; j++) 
        T[++cnt] = make_pair(Time[i][j], i);
sort(T + 1, T + cnt + 1);

之后,我们按降序遍历 T[],对每维开一个桶,记录当前属于该维度的 $\operatorname{time}_i(j)$ 的个数。

当我们枚举到 $T[i]\neq T[i-1]$ 时,此时所有 $\geq T[i]$ 的 $\operatorname{time}_i(j)$ 已经全部加入到了桶中。

把桶上的数累乘,$\prod_{j=1}^k{\operatorname{sum}_j}=\prod_{j=1}^k(\sum_{t=1}^{w_j}[\operatorname{time}_j(t)\ge T_i])$,就是上面表达式中 $i=T_i$ 时的值,这很显然。

对应到上面 $\operatorname{Ans}$ 的表达式,$i\in[T_{i-1} + 1, T_i]$ 这个范围中的 $\prod_{j=1}^k(\sum_{t=1}^{w_j}[\operatorname{time}_j(t)\ge i])$ 都是相同的。

所以 $\operatorname{Ans} += (T_i – T_{i-1})\times \prod_{j=1}^k{\operatorname{sum}_j}$.

pair<int, int> T[10000010]; //first存Time,second存维度
int sum[MAXK]; //sum[i]代表:维度i下,可选的点的个数
int cnt = 0, ans = 0;
for(int i = cnt; i >= 1; i--) {
	sum[T[i].second]++;
	if(T[i - 1].first != T[i].first) { // >=T[i]的部分已经加入完成
		ll tmp = 1;
		for(int j = 1; j <= k; j++) tmp *= sum[j];
		ans += (T[i].first - T[i - 1].first) * tmp;
	}
}

代码没加取模,时间复杂度 $\mathcal{O}(k\cdot \sum w_i)$.

求 $\operatorname{time}_i(j)$

对每个维度分别求。

设 $\operatorname{step}_{i+n}$ 表示在当前枚举的维度上,在一轮内,移动 $i$ 的距离需要的最小步数。由于 $i$ 不一定非负,所以下表要整体加 $n$.

直接设初始在位置 $0$,遍历指令序列即可求出 $\operatorname{step}$,也能求出遍历一遍序列后移动的距离 $\operatorname{cur}$.

如果在一个周期内,$j$ 就可以走出场地,那么此时 $\operatorname{time}_i(j)$ 已经可以求出了。

如果 $j$ 需要多个周期才能出去,我们考虑先求出这个周期数

不妨设 $j$ 在多个周期后从正方向($>w_i$)离开场地。

设 $j$ 经过若干个整周期后,位置为 $x$,则其可以在一个新的周期中走出场地,当且仅当 $w_i-x+1\leq \operatorname{Maxdis}$.

$\operatorname{Maxdis}$ 代表,在周期内,最多可以向正方向移动多少距离,这不一定等于周期结束时的移动距离

因此,周期数可以表示为:

$$
\operatorname{T}=
\left\lceil
\frac{w_i-j+1}{\operatorname{cur}}
\right\rceil
$$

求出了周期数,就可以直接求值了:

$$
\operatorname{time}_i(j)=\operatorname{T}\times n+\operatorname{step}[(w_i-j+1)-\operatorname{T}\times \operatorname{cur}+n]
$$

$+n$ 的原因前面提到过了。

对于从负方向 $<0$ 离开场地的情况也类似,只需要求出 $\operatorname{Mindis}$ 即可。

$\operatorname{Maxdis}$ 和 $\operatorname{Mindis}$ 可以在求 $\operatorname{step}$ 的时候顺便处理出来。

int step[MAXN << 1];
int Time[MAXK][MAXWI];
for(int i = 1; i <= k; i++) {//第i维
    memset(step, 0x3f, sizeof(step)); step[n] = 0;
    int cur = 0, maxdis = 0, mindis = 0;
    for(int j = 1; j <= n; j++) if(c[j] == i) {
        cur += d[j];
        if(cur > maxdis) maxdis = cur;
        if(cur < mindis) mindis = cur;
        step[cur + n] = min(step[cur + n], j);
    }
    //cur: 走n步,一个周期能移动cur
    for(int j = 1; j <= w[i]; j++) {
        //一个周期就能走到的情况
        if(w[i] - j + 1 + n >= 0 && w[i] - j + 1 <= n) 
            Time[i][j] = min(Time[i][j], step[w[i] - j + 1 + n]);
        if(n - j >= 0) Time[i][j] = min(Time[i][j], step[-j + n]);
        int rest = 0, tim = 0, T;
        //多个周期才能走到的情况
        if(cur > 0) { //向正方向
            rest = w[i] - j + 1;
            T = max(0ll, (rest - maxdis - 1) / cur + 1); //上取整
            tim = T * n + step[rest - T * cur + n];
            Time[i][j] = min(Time[i][j], tim);
        }
        if(cur < 0) { //向负方向
            rest = j;
            T = max(0ll, (rest + mindis - 1) / (-cur) + 1); //上取整
            tim = T * n + step[-rest + T * (-cur) + n];
            Time[i][j] = min(Time[i][j], tim);
        }
    }
}

这样实现的时间复杂度同样为:$\mathcal{O}(k\cdot \sum w_i)$.

参考资料

fight for dream – 洛谷博客

代码

Ubuntu Pastebin

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇