本文章记录了各种原创题（2021 级信息社团成员原创）。

E

题目描述

E 国有一条数轴，上面共 $n$ 条线段，其端点范围为 $1\sim5000$ 的正整数。现在 E 国国王给了 $q$ 个询问，每次询问一个闭区间，求区间内有多少完整的线段。对于一个区间，完整的线段定义为其左右端点均包含在区间内。

输入输出格式

输入的第一行为两个正整数 $n,q$ 。

接下来 $n$ 行，每行两个数字 $l_i,r_i$ ，表示左端点为 $l$ ，右端点为 $r$ 的线段。

接下来 $q$ 行，每行两个数字 $L_i,R_i$ ，表示询问闭区间 $[L_i,R_i]$ 。

输出 $q$ 行整数，为所求答案。

数据范围与来源

$n,q\le10^{7}$ ，所有线段端点范围为 $1\sim5000$ ，所有数均为正整数。

来自 yz 所做题的一个子问题。

E ex

题目描述

E ex 国有一条数轴，上面刚开始共 $n$ 条线段，其端点范围为 $1\sim5000$ 的正整数。现在 E 国国王给了 $q$ 个形如 p l r 的操作：

若 $p>0$ ，表示插入左端点为 $l$ ，右端点为 $r$ 的线段 $p$ 条；
若 $p<0$ ，表示删除左端点为 $l$ ，右端点为 $r$ 的线段 $p$ 条（保证合法）；
若 $p=0$ ，表示询问一个闭区间 $[l,r]$ ，求区间内有多少完整的线段。

对于一个区间，完整的线段定义为其左右端点均包含在区间内。

输入输出格式

输入的第一行为两个正整数 $n,q$ 。

接下来 $n$ 行，每行两个数字 $l_i,r_i$ ，表示左端点为 $l$ ，右端点为 $r$ 的线段。

接下来 $q$ 行，每行三个数字 $p,l,r$ ，表示一个操作。

对于每个 $p=0$ 的操作输出一行整数，为所求答案。

数据范围与来源

$n,m\le10^{5}$ ，所有线段端点范围为 $1\sim5000$ ，所有数均为正整数。

来自 yz 所做题的一个子问题，然后 yz 使之带修。

题解： $f(i,j)=f(i+1,j)+f(i,j-1)-f(i+1,j-1)+a(i,j)$ 。

F

题目描述

F 国居民喜欢玩贪吃蛇。现在，有一个居民发明了一个贪吃蛇的变种游戏。

现在，有一个长度为 $1$ 的贪吃蛇，位于一个 I 形管道，如下图：

| | |
|-+-|
| | |
|-+-|
| | |
|-+-|
| | |
|-+-|
| | |
|-+-|
|o|o|
\---/

图中，o 表示蛇的头部。由图可知，蛇的合法起始位置有两个，管道粗两个单位，向上无限延伸。

贪吃蛇可以向上下左右任意四个方向延伸自己的身体（要求不能超出管道或延伸到身体所在位置）。例如，下图为一个合法的局面（箭头 < > ^ v 表示延伸方向，o 表示头部）：

| | |
|-+-|
| | |
|-+-|
|>|v|
|-+-|
|^|v|
|-+-|
|^|o|
|-+-|
|^| |
\---/

你需要求出若现在贪吃蛇长度为 $n$ ，不同的局面有多少种。答案对 $p$ 取模。

两个局面不同，当且仅当将这两个局面用上图字符画形式表示时，在某个位置的字符不同。

输入输出格式

输入的第一行为两个正整数 $n,p$ 。

输出一个整数，为所求答案。

数据范围与来源

$n\le10^{16},p\le2147483647$ ，所有数均为正整数。

来自 zzw。

题解： $f(i)=f(i-1)+f(i-2)+[i \bmod 2=0]$ 。

F ex

题目描述

F 国居民喜欢玩贪吃蛇。现在，有一个居民发明了一个贪吃蛇的变种游戏。

现在，有一个长度为 $1$ 的贪吃蛇，位于一个 L 形管道，如下图：

| | |
|-+-|
| | |
|-+-|
| | |
|-+-|
| | |
|-+-+---------
| | | | | | |
|-+-+-+-+-+-+-
|o| | | | | |
\-------------

图中，o 表示蛇的头部。由图可知，管道粗两个单位，向上、右无限延伸。

贪吃蛇可以向上下左右任意四个方向延伸自己的身体（要求不能超出管道或延伸到身体所在位置）。例如，下图为一个合法的局面（箭头 < > ^ v 表示延伸方向，o 表示头部）：

| | |
|-+-|
| | |
|-+-|
|>|v|
|-+-|
|^|v|
|-+-+---------
|^|>|>|v|o|<|
|-+-+-+-+-+-+-
|^| | |>|>|^|
\-------------

你需要求出若现在贪吃蛇长度为 $n$ ，不同的局面有多少种。答案对 $p$ 取模。

两个局面不同，当且仅当将这两个局面用上图字符画形式表示时，在某个位置的字符不同。

输入输出格式

输入的第一行为两个正整数 $n,p$ 。

输出一个整数，为所求答案。

数据范围与来源

$n\le10^{7},p\le2147483647$ ，所有数均为正整数。

来自 zzw 的加强版。

F neo

题目描述

F 国居民喜欢玩贪吃蛇。现在，有一个居民发明了一个贪吃蛇的变种游戏。

现在，有一个长度为 $1$ 的贪吃蛇，位于一个 I 形管道，如下图：

| | |
|-+-|
| |x|
|-+-|
| | |
|-+-|
|x| |
|-+-|
| | |
|-+-+
|o|o|
\---/

图中，o 表示蛇的头部，x 表示障碍物。由图可知，蛇的合法起始位置有两个，管道粗两个单位，向上无限延伸。障碍物的数目为 $m$ 。

贪吃蛇可以向上下左右任意四个方向延伸自己的身体（要求不能超出管道、延伸到身体所在位置、延伸到障碍物）。例如，下图为一个合法的局面（箭头 < > ^ v 表示延伸方向，o 表示头部）：

| | |
|-+-|
|o|x|
|-+-|
|^|<|
|-+-|
|x|^|
|-+-|
| |^|
|-+-+
| |^|
\---/

你需要求出若现在贪吃蛇达到了高度 $n$ ，不同的局面有多少种。答案对 $p$ 取模。

高度被定义为距离管道底部的距离，单位为一个方格。如，初始位置高度为 $1$ ，字符画第三行的障碍物高度为 $5$ 。

贪吃蛇的高度被定义为贪吃蛇的达到最高高度的身体部位的高度，如，字符画中贪吃蛇达到了高度 $5$ 。

两个局面不同，当且仅当将这两个局面用上图字符画形式表示时，在某个位置的字符不同。

输入输出格式

输入的第一行为三个正整数 $n,m,p$ 。

接下来 $m$ 行，每行两个整数 $a_i,b_i$ ，表示高度为 $a_i$ 的位置有障碍物，若 $b_i=0$ 则在左边，否则在右边。

输出一个整数，为所求答案。

数据范围与来源

$n\le10^{10^6},m\le10^6,p\le10^6$ ，所有数均为正整数。

来自 zzw。

题解：与 $2$ 的幂有关。

本文作者：Yurchiu,zzw

本文链接：https://yz-hs.github.io/5f360e6b7b7d/

版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。

OI 动态规划 Idea

最后更新：2023-08-21, 23:18:20

By Yurchiu.

随机文章回味旧文

博客信息

文章数目

158

[Idea] Ideas2

E

题目描述

输入输出格式

数据范围与来源

E ex

题目描述

输入输出格式

数据范围与来源

F

题目描述

输入输出格式

数据范围与来源

F ex

题目描述

输入输出格式

数据范围与来源

F neo

题目描述

输入输出格式

数据范围与来源