妙妙题

CF369E Valera and Queries

传送门

题意简述

给定条线段，共有次询问，每次询问给定一组点集，询问至少覆盖其中一个点的线段条数。

思路

正难则反。

对于每次询问的点集，我们考虑以其为分割点，转化为一条条线段。例如：这个点集可以转化为这样的线段。

转化完成后按左端点从大到小排序，用树状数组统计答案即可。

P6564 [POI2007] 堆积木KLO

传送门

题意简述

有一串数列，定义一串数列的价值为满足的元素数量，你可以删除其中任意多个元素，使在它后面的元素向前平移。求价值的最大值。

，

思路

我们设表示在这个位置经过修改价值的最大值，那么可以得出这样的转移方程：

最后一个条件转化后即为。

因此，我们将整个序列以排序，用树状数组维护的最大值，以为关键词查询即可。

P2757 [国家集训队] 等差子序列

传送门
双倍经验

题意简述

给定一个排列，判断一个序列中是否有长度大于等于的等差子序列。

思路

首先我们可以将条件转换为：是否有一个长度为的等差子序列。那么我们继续转换：那么就是有一个数，存在一个数，满足和分居它两侧即可。

我们考虑从左到右扫描序列，记录下每一个之前扫描过数的位置，那么只要没有关于当前这个数对称，即存在一个长度为的等差数列。用线段树维护哈希值即可。

CF19D Points

传送门

这种题都不会做，我是不是该退役了

题意简述

有次在一个笛卡尔坐标系上的操作，有三种种类：

1. 加入一个点
2. 删除一个点
3. 查询在点严格右上角的，横坐标最近的，如有多个取纵坐标最近的点的坐标。

保证所有操作合法，即：不会有重复的点，不会删除不存在的点。

，

思路

一开始想成树套树了，死活做不出来……

首先很显然，坐标需要离散化然后就不会了。

我们注意到，查询的点的第一要求是横坐标最近，那么在查询的时候，我们只需要找到最靠左的横坐标，使得它有点在查询的点的右上方即可。我们建一颗线段树，维护横坐标在这个区间内的点的纵坐标的最大值（最开始都是）。对于每个横坐标，我们开一个 set 来维护纵坐标，在插入和删除的时候同步修改线段树上的最大值，在查询的时候线段树上二分即可，差不多像这样：

il int query(int p, int x, int y) {
  if (t[p].l == t[p].r) return (t[p].ma > y) ? t[p].l : -1;
  int res = -1;
  if (x <= mid && t[ls].ma > y) res = query(ls, x, y);
  if (~res) return res;
  if (t[rs].ma > y) res = query(rs, x, y);
  return res;
}

时间复杂度为

ABC219F Cleaning Robot

传送门

题意简述

懒得化简了，直接复制了洛谷翻译。

一个清扫机器人被放置在无限扩展的二维网格的方格上。

给定了一个由四种类型的字符 L、R、U、D 组成的字符串程序。
机器人根据给定的程序，依次读取每个字符，并针对每个字符采取以下行动：

1. 将机器人的当前位置设为方格
2. 根据读取的字符执行以下移动：

• 当读取 L 时：向左移动到方格。
• 当读取 R 时：向右移动到方格。
• 当读取 U 时：向上移动到方格。
• 当读取 D 时：向下移动到方格。

给定一个由 L、R、U、D 组成的字符串和整数。机器人执行的程序是将字符串重复连接次。

一旦机器人访问过的方格（包括机器人的初始位置）就会被清扫。
请输出在机器人执行程序结束后，被清扫的方格的数量。

，

思路

一看到这题的数据范围，我们可以立马发现：暴力是没有前途的废话。

我们发现，每次循环过一次，机器人横坐标的改变量和纵坐标的改变量是一定的，我们不放从这里入手。我们只考虑一次循环，思考：什么时候一个点的贡献（其实就是出现次数）不是？

答案不太好想：我们把循环的左下角看作起点（如果不是左下角，那就旋转它！），将每个点视作在一条斜率为的线上。那么一个点的贡献不是，当前仅当它后面有与它在同一条线上，并且之间的距离容不下次移动的点(应为之后的移动一定会被后面的点覆盖)。我们其实只需要模拟一次循环，便可找到所有点在哪根线上。假设两个点的横坐标分别为，，那么前一个点的贡献即为。我们用 std::set 存储经过的位置，用 std::map 存储每条线段上有哪些点，时间复杂度为。

注意处理和负数的情况。

CF940F Machine Learning

传送门

题意简述

给定一个数组，支持两种操作：

1. 修改一个位置的值
2. 查询这段区间内元素出现次数的。

思路

看到对一些区间进行与出现次数相关的查询以及数据范围，我们不难想到带修莫队的做法。那怎么查找出现次数的值呢？呃，其实直接从开始枚举就行了，因为这个的和是平方级别的，那么答案一定是在级别的。

视，同阶，时间复杂度为。

P4211 [LNOI2014] LCA

传送门

题意简述

（我就直接复制题面了）

给出一个个节点的有根树（编号为到，根节点为）。

一个点的深度定义为这个节点到根的距离。

设表示点的深度，表示与的最近公共祖先。

有次询问，每次询问给出，求，对取模。

思路

这道题要用到我一个不会的经典套路：两个点之间 lca 的深度，就是在其中一个点到根节点的路径上整体加，然后求另一个点到根节点的路径上权值和。但是如果暴力这样做的话，复杂度为，无法通过本题。如何优化？

我们注意到每次要求的是一段连续区间与某个点的 lca 深度之和，我们不难想到对这个区间差分（为什么我想不到），直接从到全加上，那么两次询问答案的差即为最终答案。

将询问离线下来后树剖 + 线段树即可，时间复杂度为。

[AGC040C] Neither AB nor BA

传送门

题意简述

给定一个正偶数，求出长度为的， 由 A，B，C，组成的，能够被以下方式完全删除的字符串个数，对取模。

删除方式：删除两个相邻的，不是 AB 或 BA 的字符。

思路

这道题要用到一个 Trick：奇偶染色（我瞎胡的名字）。具体的，我们对于一个假想的字符串，把它偶数位上的 A 换成 B，B 换成 A，那么删除条件就转换为了：不能是两个 A 或 两个 B 一起删除。我们设 A 的个数为，B 的个数为，在不考虑 C 的情况下，最后会剩下个字符。设 C 的个数为，那么能够被完全删除的充要条件为。注意到，带入解得。我们考虑容斥，计算或大于的字符串个数，因为同时只能满足一个条件，因此个数为。最终答案即为。

[AGC052B] Tree Edges XOR

传送门

题意简述

给你一棵有个节点的树，保证为奇数。每条边上有一个边权和一个目标边权，每次可以选择一条边，

将与这条边有公共点的所有边的边权都异或上这条边的边权，求能否把所有的变为。

，

思路

首先我们手玩一下，发现什么是不容易变的？就是一条路径的异或和，只要一个端点不是选定的那条边的一个端点，那么异或和就是不变的。那么我们用上一个经典（真的经典吗？）Trick：将边权转为点权。但这里不是简单的一一对应，而是将一个点的点权设为从根到这个点的路径和，那么一条路径的异或和就被转化为了两个端点的权值的异或。我们继续手玩，发现这样一个事实：对于一条边的操作，相当于交换两个点的点权。好，现在你兴冲冲的按照这个去写，判断两棵树的点权集合是否相等，尽管你感觉有些不对劲。一交，好，WA 了。哪里不对劲？在于根节点：它的权值应该保持为。

现在该这么处理？我们仔细思考一下为什么根节点是特殊的。答案是显然的（真的吗）：因为它没有向上的边。这并不好办，我们在它上面接个虚拟节点不就是了？那么现在的问题是：这个点到根节点的边权应该是多少？我们考虑一下这条边对每个点的点权的影响，其实就是都异或上一个边权。因为是奇数，那么点权的异或和就会异或上一个边权。那么，如果这条边的边权不是以建树点权的异或和和以建树点权的异或和的异或，那么肯定是无法达成目标的。但是这只是一个必要条件，所以求出这个边权之后还要判断两棵树的点权集合是否相等，时间复杂度为。

CF1641D Two Arrays

传送门

题意简述

给定个长为的序列，保证序列内部元素互补相同。每个序列有一个权值。求出最小的，使得和的个元素互不相同。若无解，输出。

，，

思路

做不出来，鉴定为：题做少了。

首先注意到总的数组个数很少，但值域很大，显然首先要离散化。然后我们发现可以使用 std::bitset 来记录每个数字在哪几个序列中出现过，时间复杂度为，但这样空间会爆（然后就不会了）。这道题需要用到平衡复杂度的 Trick。具体的，我们令，只有出现次数大于等于的数我们才在 std::bitset 里统计出现位置，小于的我们直接暴力统计，时间复杂度为，足以通过本题。

CF618F Double Knapsack

传送门

题意简述

给定两个长为的序列，，保证序列中每个元素的大小都在与之间。求能否找到两个序列的两个子集，使得它们的和相等，无解输出。

思路

妙妙构造题。

我们注意到值域等于，想想能利用这一点做什么。首先，我们大胆猜测一定有解（虽然确实一定有解）对两个序列做两个前缀和。我们假设，以此来进行接下来的分析。

对于，我们找到使得的第一个位置，那么一定有。一共有对，但只有个取值，那么一定会有重复的，那么在这两对位置之间的元素和相同，我们通过双指针找出每队即可，的情况同理，时间复杂度为。

P4587 [FJOI2016] 神秘数

传送门

题意简述

定义一个可重集的神秘数为不可以被集合内元素累加表示出来的最小的数。现在给你一个长度为的序列，多次询问，求出一段区间内的神秘数是多少。

，

思路

很有意思的一道题。

我们先不考虑在序列上的询问，想想给了你一个可重集，我们如何求出这个可重集的神秘数。我从小到大加入数字，假如当前可以表示的数的范围是，新加入的数是，假如，那么神秘数就是，否则能够表示的数的范围就是。我们想想如何把这个方法扩展到序列上。我们假设当前能够表示的最大值为，假如这个序列内小于等于的数之和大于，那么答案一定可以扩大到这些数的和，我们可以用主席树维护这个求和的过程。看上去时间复杂度很假，但我们发现这个更新过程是一个类似于斐波那契数列的扩展过程，所以时间复杂度大概是

CF342E Xenia and Tree

传送门

题意简述

给定一棵个节点的树，初始时一号节点被染了色。组操作，将一个点染色，或是询问离某个点最近的被染色的点的距离。

思路

万物皆可根号分治，记录以下这个套路。

我们把个操作划为一组，对于每组操作分开处理。对于每一组内的染色操作我们记录下来，最后统一用 bfs 更新树上每个点到染色点的最近距离，时间复杂度为。对于每一次的询问操作，我们已经有了在这一组操作之前到被染色的点的最短距离，我们只需要算同组操作中在这次询问之前被染色的点到这个点的距离，取最小值即可，时间复杂度为，取时取到最优复杂度。

QOJ 1271 In Search of Gold

传送门

题意简述

组数据，给定一个个节点的树，每条边有两个权值、，要求选出恰好条边权值为，其余条边权值为，求得到的树的直径的最小值。

，，，，

思路

打模拟赛时遇见的题目，感谢 qyzy 大佬 教我做法，感觉这种二分套 dp 的思路还挺有用的，特此记录下来。

我们首先考虑二分半径长度，那么就把问题转化成了一个判定性问题。我们设表示在的子树内选择了条边的权值为，到点的最长链长度的最小值。设当前的点为，目前遍历的儿子节点为，那么可以写出转移方程（这里用代码表示）：

void dfs(int u, int fa, i64 x) {
  f[u][0] = siz[u] = 0; // 初始化
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].v, a = e[i].a, b = e[i].b;
    if (v == fa) continue;
    dfs(v, u, x);
    int nsiz = std::min(siz[u] + siz[v] + 1, K);
    for (int j = 0; j <= nsiz; ++j) ml[j] = inf64; // 避免转移出现冲突
    for (int j = 0; j <= siz[u]; ++j) {
      for (int k = 0; k <= siz[v] && k + j <= K; ++k) {
        // 只有出现的最长链长度不超过限制才可以转移
        if (f[u][j] + f[v][k] + a <= x) chmin(ml[j + k + 1], std::max(f[u][j], f[v][k] + a));
        if (f[u][j] + f[v][k] + b <= x) chmin(ml[j + k], std::max(f[u][j], f[v][k] + b));
      }
    }
    for (int j = 0; j <= nsiz; ++j) f[u][j] = ml[j];
    siz[u] = nsiz;
  }
  return ;
}

最终有解的话，只需要判定的值是否合法即可。注意到这是一个树形背包的形式，我们采用上下界优化，单组数据时间复杂度即为。

[AT_CF_2018_Final_I] Homework

传送门

题意简述

给定个任务，有两个属性、，表示所需的时间为，所得分数为。给定，求最短的时间，使得所得分数大于等于。

，，，

思路

我们先来考虑一个更广为人知的问题：如果时间已经确定，那么能得到的分数的最大值是多少？这就是 P3188 。但那道题的数据范围更小，这迫使我们研究这道题与 P3188 的不同之处：时间的值一定正好是的次方。这提醒我们要考虑从低位合并为高位的情况。我们不难想到一个从低位向高位贪心的方法：假设时间第位的二进制表示为，我们就选择要占用时间的分数最大值（容易证明这样一定可以使得高分所需的时间最短）；无论这一位选不选，我们都要把剩下的需要时间的分数贪心的从大到小两两合并，组成需要时间的一组分数，如果最后还剩下一组分数，直接把它的时间视为即可，这样也显然是不劣的。那么我们只需要二分时间，即可求出所需的时间最小值。为什么这个具有单调性？因为更大的时间一定可以通过等价的调整（例如，转为从之后的位数得到分数）使得每一位上得到的分数都不降，正确性显然。设答案的上界为，如果预先排序，我们可以通过归并的方式做到，不过使用优先队列的也可通过。

P7482 不条理狂诗曲

传送门

题意简述

给定一长为的非负整数序列，定义表示从的区间内选择互不相临的数之和的最大值，求。

，

思路

我们考虑分治。

对于一个区间，设区间的中点为，有三种子区间需要考虑：右端点没超过的，左端点没超过的，以及横跨的。对于前两种我们可以递归下去来计算，那么只要考虑怎么计算横跨的区间就可以了。具体而言，我们需要先 dp 求出以下四个值：

• 表示从向左一直到，在可以选择的情况下能选择的和的最大值。

• 表示从向右一直到，在可以选择的情况下能选择的和的最大值。

• 表示从向左一直到，在不可以选择的情况下能选择的和的最大值。

• 表示从向右一直到，在不可以选择的情况下能选择的和的最大值。

那么对于一个这样的区间，它的答案即为。我们考虑拆贡献，假如最终答案选择的是左边，意味着，移项得到。于是我们得到这样一个做法：让所有的数按照的值从小到大排序，对于的每个数，我们二分找出的个数，那么对于前个位置对应的答案为，对于剩下的位置对应的答案为。通过维护的前缀和，的后缀和，我们就在的时间内解决了这个问题。

P6845 [CEOI2019] Dynamic Diameter

传送门

题意简述

有一颗个节点的边带权的树，次询问，每次更改一条边的边权，求直径的长度。

本题强制在线

，，

思路

好妙的题啊。

我们考虑两点之间距离的表达式：，我们需要求出的就是这个的最大值。我们把整个树放到欧拉序上，设每个点第一次出现的位置为，最后一次出现的位置为，那么就是之间深度的最小值。那么我们可以使用线段树，维护一个序列上，容易证明这样一定选出的是一条简单路径。当然，答案要与深度的最大值取，时间复杂度为。

CF280D k-Maximum Subsequence Sum

传送门

题意简述

给定一个长度为的序列，有次操作，要求支持两种操作：

1. 单点修改。

2. 询问区间内选出至多个互不相交的子段和的最大值。

，，，

思路

小清新数据结构题。

注意到很小， 我们不妨考虑对于一次询问直接暴力的取次，但每次取最大子段和不一定最优，如何解决？通过翻阅题解，我们了解到可以借用费用流的思想，每次取完一次区间之后将这个区间内的所有数取反，那么如果重复选了这个区间的一部分就相当于撤销这个选择。容易证明这样不会取出包含的区间，同时类比费用流的反流我们可以证明这样做的正确性，那么我们只需要维护区间最大子段和及其位置，区间最小子段和及其位置，以及合并需要的一系列元素即可用线段树解决这个问题，时间复杂度为。如果封装得当的话，代码很好写。