题意给定一棵树，现要求在树上选若干个点（不能不选），使得任意两点间的距离严格大于 2，求选择方案数。
思路这题肯定是上位绿了。
考虑树上 dp。题目要求距离严格大于 2，那么也就是距离最小的两个点距离大于 2。考虑 LCA 不为其中之一的两点 ，如果需要从以 为根的子树中选点，那么只需求 间的距离即可。如果这个距离等于 2，那么 至少有一个不能选，如果大于 2，那么全部可选。
设计状态...
题意给定 个三元组 ，定义心情值为 ，需要按照 到 的顺序执行以下操作：
若 ，那么 ；
否则 。
给定 次查询，每次查询给定一个整数 ，要求求出初始心情值为 时，最终的心情值。
。
思路本场总结：E < D。
我们发现，如果 ，那么一定会减少到 以下，且如果数据开满，那么心情值会在 以内上下乱跳。而 ，所以我们可以预处理出 到 以内的从 ...
题意给定一棵大小为 的树，现在要选取一些点，使得这些点间的距离均为直径长度。求选取方案数。
思路由直径的性质：直径具有共同的中点，我们可以从中点下手。
若直径长度为偶数，要使每个节点的距离均为直径长度 ，那么任意两点在以中点为根的情况下的 LCA 都应该为这个中点。且选取的点均为深度为 的叶子节点。
那么，设中点为 ，那么 的每个儿子子树中，均只能选择一个节点。我们可以记录以 为根的...
题意给定 种云服务计划，每个计划可以在第 到第 天使用，每天可以提供 个 CPU，每个 CPU 的价格是 。现在每天需要 个 CPU，求最小价格，如果某一天达不到 个，那么就取最大的数量。
思路首先，我们一定是优先选择价格小的 CPU 进行购买。如果我们将天数作为下标，用线段树维护，那么不难发现，这样做空间炸的一点不剩。所以我们需要换一个想法。
观察到，价格、个数在 以内，所以...
题意给定一个序列 ，规定长度为 的合法子序列如下：
其元素总和在长度为 的子序列中最大；
其字典序最小。
给定 次查询，每次查询给定 ，要求输出长度为 的合法子序列的第 个元素。
思路首先观察性质。注意到，这个序列一定由前 大元素构成，而题目要求字典序尽量小，那么一定是选择下标尽量小的，所以，我们先按照大小为第一关键字、下标为第二关键字排序。
然后考虑如何解决查询。发现，每次...
题意给定一个字符串，有两种操作：
1 l r x 表示将 区间内的字符整体循环右移 位；
2 l r 判断 区间内是否包含长度大于 1 的回文子串。
思路如果我们直接判断是否包含回文子串，那么比较不好做。我们先来观察性质，题目并没有要求求出长度，所以我们挑最好求的来做。长度大于 1 的回文串都可以缩成 2 种：长度为 2 或 3 的回文串。下面来分类讨论：
长度为 2 的回文串，...
题意有 台轮盘。第 台轮盘（ ）上写有 个整数 ，每次支付 日元可以玩一次。每玩一次第 台轮盘，会等概率随机选出 到 之间的一个整数 ，获得 分。
每次轮盘获得的分数相互独立。
Takahashi 想要获得至少 分。Takahashi 会采取使得在获得至少 分之前所支付金额尽可能小的策略。并且，Takahashi 每次玩轮盘时，可以根据之前所有轮盘的结果选择下一次要玩的...
题意给定一个整数 ，有一个 的排列 ，下标从 开始。最初 。
现在需要对数列进行操作。具体地，移动由另一个 的排列决定：
在每一步中， 。
每一步有两种分类方式：
若数对 满足： 且 ，则 在同一组中。
若数对 满足： 且 ，则 在同一组中。
对于每个步骤，可以任意选择分类方式。要求对于两个不同的步骤，满足如果分类方式相同，那么对于每个 都满足其所属...
弱化版 NOI（雾？
HN-0416 战绩可查（？
总结：NOI 出题人被贬。以后大家感冒都给我去吃连花清瘟。
Day 0晚上发烧，吃感冒药睡了一觉，结果更严重了，求安慰555.
Day 1早上起来没一点力气，搞完各种事情吃完早饭出发。CJ 并不远，但是也不近，开车 30 min。
七点左右出发，7:45 左右到。到之后去 711 买了口罩，包装怎么是长条的，农村入没见过社会了 /...
题意给定长为 的序列 ，每个元素有两种指标：数值 和 颜色 。其初始状态为 。有 次操作：
1 l r x 将区间 中所有 指标 的元素按原下标提取出，求其颜色段个数，即极长的颜色相同的连续段数量。
2 a c 在序列 末尾插入元素 。
有强制在线。
思路这题放模拟赛 T4 真是太好了。没人切出来。
数据结构。
颜色段数量问题，可以想到线段树区间合并维护。具体地，对于每...
