ARC068 vp记录

A. X: Yet Another Die Game

题意：一个 \(6\) 面骰子，对面的两个点数和为 \(7\)。初始的时候任意的一个面朝上，接下来每一轮可以翻转骰子到相邻的一面，并获得此面的得分（那一面的点数即是得分），问至少要几轮才可以获得够 \(x\) 分。

\(1\le x\le 10^{15}\)

直接在 \(5,6\) 之间翻来翻去即可，四则运算。

B. Card Eater

有一堆牌共 \(n\) 张，每张牌上有一个数字 \(a_i\)。 每次可以取出其中 \(3\) 张，丢掉数字最大的和数字最小的牌，把中间那张再放回牌堆。 要求最后所有剩余牌上的数字互不相同，求最多能剩几张牌。

\(1\le n\le 10^5\) 且为奇数，\(1\le n\le 10^5\)

上界为每种数都保留一个，发现选择两个相同的数时总会消去一个该数字，然后消去剩下一个。如果多出来的数字个数是偶数那么两两消除，否则多消除一个。

C. Snuke Line

题意：\(m\) 个点，\(n\) 个区间 \([l_i,r_i]\)。对于每个 \(d(d\in [1,m])\)，求多少个区间内包含 \(d,2d,3d,...\) 中至少一个点。

\(1\le n\le 3\times 10^5,\space 1\le m\le 10^5\)

考虑 \(d\) 从 \(1\) 到 \(m\) 枚举，然后动态修改 \(\lfloor\frac xd \rfloor\) 的所有 \(x\)，更新答案。由于一个 \(x\) 的 \(\lfloor\frac xd\rfloor\) 种类个数是 \(O(\sqrt x)\) 的，时间复杂度 \(O(n\sqrt m)\)。

D.

题意：将 \(1\sim n\) 按顺序加入双端队列（每次可加头可加尾），再把所有数一个一个删除（每次可删头可删尾），求有多少种删除序列，使得 \(1\) 是第 \(k\) 个被删的。

当 \(k=n\) 时，双端队列中 \(1\) 最后一个删除，他把队列分成左右独立的两部分，相当于删除序列中 \(2\sim n\) 这些数可以分成两个下降的子序列。考虑计算这个，相当于 \(\text{LIS}\) 长度不超过 \(2\)，（这里倒序 dp 是为下面做铺垫）设 \(f[i,j]\) 表示填写了 \(i\sim n-1\)，若 \(j>1\) 则 \(\text{LIS}=2\) 且 \(j\) 是最小开头数字，若 \(j=1\) 则 \(\text{LIS}=1\)。

这个容易 dp。

当 \(k<n\) 时，我们的序列划分长这样：

我们的算的一定和 \(\text{LIS}\le 2\) 的限制差的不远。

猜结论：令数字 \(1\) 右边的 \(\text{LIS}=1\)，然后向左边原封不动地 dp。

会发现是正确的，前缀和优化，\(O(n^2)\)。