平时做的个人感觉比较好的杂题会放到这

# [HEOI2016/TJOI2016] 序列

# 题目描述

佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。

玩具上有一个数列，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有变化的可能性，她想请教你，能否选出一个子序列，使得在任意一种变化和原序列中，这个子序列都是不降的？请你告诉她这个子序列的最长长度即可。

# 分析

首先对于这道题我们肯定能想到是想要满足两个状态之间能进行转移，必须保证前一个点的最大值要小于等于后面这个点的最小值，那么加上这个限制，转移方程也就是

$f[i] = f[j] + 1 (1\leq j \lt i \;\; \wedge \;\;mx[j] <= mn[i])$

然后就成了一个三维偏序问题，直接 $CDQ$ 带个数据结构或者是树套树即可

# [AGC024D] Isomorphism Freak

# 题面翻译

给定一棵点数为 $n$ 的无根树。对于两个点 $u,v$, 若有以 $u$ 为根与以 $v$ 为根树同构，则染上同一种颜色.

可以给这棵树加若干点，问加完点后树最少能有多少种颜色，以及在最少颜色的情况下最少有多少个叶子节点.

# 分析

他要让我们去求最少需要多少种类的颜色，我们考虑对于一棵树想要让颜色最少肯定是要让树的最深的深度最小，然后每一层保证所有点成为根都能使得树是同构的，那么我们直接把同一层深度的点都变成加点之前最多的点的结构即可，那么我们最后所需要的点的数量就是树的深度，然后直接 $dfs$ 一遍，然后记录一下每一层儿子最多的点，然后对于其他点补全即可

# [AGC004D] Teleporter

# 题面翻译

有 $n$ 个城市，每个城市有一个传送点，都可以传送到唯一的另外一个城市，保证从任何位置出发经过若干次传送之后能够到达 $1$ 号城市。现在希望修改一些点的目的地，使得从任何一点出发在传送 $K$ 次之后恰好都能到达 $1$ 号城市，求最少要改变目的地的城市的数量。

# 分析

对于一号节点，我们可以直接让他指向自己即可，如果不指向自己，那么一号节点肯定要与其他节点构成一个环，那么这个环上是肯定有点到不了一号节点的，然后我们考虑怎么去保证绕 $k$ 次到达 $1$ ，其实也比较好像，我们会发现有了 $1$ 的这个自环，我们只用构造出一个以 $1$ 为根的，且所有子树的深度是不超过 $k-1$ 的即可，既然我们要求最小值，那么直接把深度大于的 $k - 1$ 的树分开即可。

# [JSOI2007] 重要的城市

# 题目描述

参加 jsoi 冬令营的同学最近发现，由于南航校内修路截断了原来通向计算中心的路，导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向计算中心的路，却没有使路程增加，因为可以找到同样长度的路作替代。其实，问题的关键在于，路截断的地方是交通要点。

同样的情况也出现在城市间的交通中。某些城市如果出了问题，可能会引起其他很多城市的交通不便。另一些城市则影响不到别的城市的交通。jsoi 冬令营的同学发现这是一个有趣的问题，于是决定研究这个问题。

他们认为这样的城市是重要的：如果一个城市 c 被破坏后，存在两个不同的城市 a 和 b（a, b 均不等于 c），a 到 b 的最短距离增长了（或不通），则城市 c 是重要的。

jsoi 冬令营的同学面对着一张教练组交给他们的城市间交通图，他们希望能找出所有重要的城市。现在就请你来解决这个问题。

# 分析

# Funny Game

# 题面翻译

一个长度为 N 的序列 $a_i$ ，双方轮流操作

每次的操作是选择一个长度大于 $1$ 的前缀，计算它的和 $s$ ，然后用 $s$ 替换它的前缀，同时当前玩家获得 $s$ 的分数。

当只剩下一个元素，游戏结束。

双方均想最大化 自己的分数 - 对手的分数，计算这个值。

# 分析

我们设 $f[i]$ 表示先手取完前 $i$ 个数之后的最大的差值，转移的式子即为

$f[i] = \max(f[i + 1], a[i + 1] - f[i + 1])$

因为我们如果不选第 $i + 1$ 个数就是 $f[i + 1]$ ，如果是选了，那么后手就会复制先手的操作，那么此时的贡献即为 $a[i + 1] - f[i + 1]$

# [yLOI2020] 灼

# 题目描述

在一条数轴上有 $n$ 个虫洞，第 $i$ 个虫洞的坐标为 $x_i$。进入这些虫洞的任意一个都可以直接到达勒本星球拯救扶苏。飞船到达数轴所在直线上后，会因为磁场的效应失去操控能力，飞船每秒会等概率向左或向右移动一个单位长度。

灼闻羽非常焦急，他给出了 $q$ 个飞船进入数轴所在直线的初始坐标，对于每个坐标，他想知道期望需要多少秒才能到达一个虫洞。

如果你计算出的期望是个分数，你需要求出这个分数对 $998244353$ 取模的答案。有关分数取模的定义你可以参考「提示」中的内容。

为了避免输出过大，你只需要输出四个整数，分别表示你所有回答（对 $998244353$ 取模之后，下同）的按位异或之和、你共有多少次回答的答案是奇数，你的所有答案中的最大值、你的所有答案中的最小值。