9.18CF1817题解

A. Almost Increasing Subsequence

题意

给定长度为 \(n\) 一个序列 \(a\) 以及 \(q\) 次询问，每次询问给出 \(l\) 和 \(r\)，找出序列 \(a\) 在 \([l,r]\) 内最长的几乎递增子序列。

对于几乎递增的定义：如果一个序列中不存在连续的三个数 \(x\)，\(y\)，\(z\)，使得 \(x \ge y \ge \ z\)，则这个序列是几乎递增的。

题解

直接找出区间内 \(a_{i-1} \le a_i\le a_{i + 1}\) 个数，区间长度减去这个的个数。

因为连续3个只能选择两个。

前缀和记录一下就可以。

B. Fish Graph

题意

定义“鱼图”为满足以下条件的无向图：

该图包含正好 \(1\) 个环，环上有 \(1\) 个特殊的结点 \(u\)，\(u\) 除了连在环上的 \(2\) 条边外还有正好 \(2\) 条边，每一条边连向一个环外的结点（即，若环的大小为 \(s\)，整个图一共有 \(s+2\) 个结点）。

现在给定一个简单无向图，问该图中是否有一个子图为“鱼图”。一个无向图的子图即为原图中删去若干个点和若干条边所形成的图。如果存在，还需要构造出其中任意一个满足要求的子图。

题解

找环小技巧：

枚举一个点 \(s\)，bfs，记录 \(fa_i\) ，\(fa_i\) 里面全是 \(s\) 相邻的点，表示 \(i\) 被搜索到是从 \(fa_i\) 这个 \(s\) 的邻居搜到的。

若有边 \((u,v)\) 并且 \(fa_u \ne fa_v\) 那么就可以形成一个环。

所以枚举度 \(\ge 4\) 的点暴力找环就完了。

C. Similar Polynomials

题意

给定两个次数为 \(d\) 的多项式 \(A, B\) 在 \(0, 1, 2, \dots, d\) 处的点值对 \(10^9+7\) 取模，保证 \(B(x) \equiv A(x+s) \pmod {10^9+7}\)。求 \(s \bmod 10^9+7\)。

题解

多项式差分

定义差分运算 \(\Delta\) ：

\[\Delta h_i = h_{i + 1} - h_i \]

定义 k 阶差分：

\[\Delta^k h_i = \Delta(\Delta^{k-1}h_{i})=\Delta^{k-1} h_{i + 1} - \Delta^{k-1} h_{i} \]

我们发现连续点值差分一次就会消掉一项，消到只剩两项就是 \(ax+b\)，一项就是 \(-a\)。

然后两个多项式都求一次，就是已知 \(a,ax+b,a(x+s)+b\) 求 \(s\)，这很简单。

D. Toy Machine

题意

有一个长 \(n\) 宽 \(2\) 的矩形游戏机。保证 \(n\) 是奇数。

游戏开始之前，有 \(n - 2\) 个玩具放在第一排中间的 \(n - 2\) 个位置中（两个角除外）。编号从左到右依次为 \(1\) 到 \(n - 2\)。第二行为空，其最左、最右和中心位置是障碍物。你可以控制玩具机向左、向右、向上、向下，分别用字母 \(\texttt L\)、\(\texttt R\)、\(\texttt U\) 和 \(\texttt D\) 表示。

操控时，所有玩具将同时沿相应方向移动，碰到另一个玩具、墙壁或障碍物停止。您的目标是将第 \(k\) 个玩具移动到第一行最左边。给定 \(n\) 和 \(k\)，构造一个最多使用 \(1000000\) 次操作的方案。