比赛地址

X: Yet Another Die Game

显然是 $6$ 和 $5$ 轮着来,直接算一下即可。

代码

Card Eater

我们可以用这个操作来每次消掉两张有重复的牌。最后可能会有只剩一张有重复,这时只能牺牲掉一张没有重复的。

代码

Snuke Line

考虑某种商品 $i$。

  • 如果 $r_i-l_i+1> d$,那么这种商品一定能够被买到。
  • 如果 $r_i-l_i+1\leq d$,那么这种商品只会被买到一次。

将所有商品按 $r_i-l_i+1$ 从小到大排序,从小到大枚举 $d$,对于所有 $r_i-l_i+1\leq d$ 的商品都将 $[l_i,r_i]$ 加上 $1$,然后枚举 $d$ 的倍数统计即可得到第二部分的答案,再加上 $r_i-l_i+1>d$ 的商品数即可求出答案。

用树状数组实现区间加、单点查询即可。复杂度 $\mathcal{O}(n\log n)$。

代码

Solitaire

考虑插入完后整个双端队列的样子,可以发现是一个 V 的形状。

考虑整个删除序列应该有一些什么性质。可以得到这样三条:

  • 第 $k$ 位是 $1$。
  • 前 $k-1$ 位可以划分为两个单减的序列。
  • 两个单减序列中至少有一个的最小值比后 $n-k$ 位的最大值大。

如果我们已经确定了前 $k-1$ 位,那么后面的方案数为 $2^{n-k-1}$。我们只考虑怎么算前面。

设 $dp_{i,j}$ 表示前 $i$ 位最小值为 $j$ 的方案数。考虑转移。首先下一位填 $[1,j-1]$ 是可行的,因为这时可以接在某个序列的后面;如果填 $>j$ 的数,那么只能填最大的没有被填过的数,最小值不变。因此有

$$ dp_{i,j}=\sum_{k\geq j} dp_{i-1,k} $$

后缀和优化即可做到 $\mathcal{O}(n^2)$。注意一些奇奇怪怪的边界问题。

这个东西应该可以像 NOI2018 冒泡排序一样优化到 $\mathcal{O}(n)$。

代码

最后修改:2020 年 09 月 16 日 08 : 32 PM