cf

[题目链接](https://codeforces.com/problemset/problem/932/D) # 题目 见链接。 # 题解 **知识点：倍增。** 注意到，题目其实要求我们，每次要选最近一个权值大于等于自己的祖先，可以看出固定点生成出来的序列是固定的。因此，考虑设 $f_{i,j} ......

每当我们看到“最大值最小”“路径上的最大最小值”等字眼时，我们就可以考虑并查集。 我们可以尝试把这些问题转化为某种意义上按单调顺序的合并，利用并查集求解答案。以下时两例并查集的巧妙应用。 CF1213G Path Queries 注意“最大权值不大于q”，加上允许离线，我们可以把边按照权值排序，并一 ......

CF708C Centroids 一道换根 DP。 我们可以先找出树的一个重心，那么对于其他所有不是重心的点，它不能成为重心时因为它父亲的那一支节点数大于一半，而可以改造成功，则意味着可以在他父亲那一支里，可以找到子树u，使 $siz[u] \le n/2 && siz[fa]-siz[u] \le ......

## CF1187G *2500 直接按时间分层，建网络流图即可。 ## $\Delta$ CF1354G *2600 由于 $k\le \frac{n}{2}$，我们用 $\log n+O(1)$ 次询问来判定第一个位置是石头还是礼物。 随后考虑倍增，用 $[1,2^i]$ 这个区间来判定 $[2 ......

感觉这三题分开写很浪费，所以合并成了半场 CF 的总结（ ### [CF1835D Doctor's Brown Hypothesis](https://www.luogu.com.cn/problem/CF1835D) 首先你看到这个 $k\geq n^3$ 就在疯狂暗示，也就是说你可以经过每个环 ......

比较套路的拆贡献题。 考虑直接枚举那个 $j$，求有多少包含 $j$ 的上升子序列满足这个子序列最后一个数的后面有大于 $a_j$ 的数。 首先对于 $j$ 前面的选择方案是没有影响的，可以直接拿树状数组 DP 一遍得到。后面的过程我们可以找到从后往前第一个大于 $a_j$ 的数的位置 $x$，那么 ......

水篇题解。 最大值并不好考虑，我们尝试拆贡献，求最大值小于等于 $k$ 的概率，然后将概率差分一下即可得到恰好等于 $k$ 的概率，而最大值小于等于 $k$ 的概率是很容易通过一个 $O(n^2)$ DP 求出来的，但是这样我们还需要再枚举一个 $k$，复杂度 $O(n^3)$，难以接受。 那么我们 ......

### 题意简述 给你一张 $n$ 个点 $m$ 条边的有向图，你需要找出有多少个点对 $(u, v), 1 \le u \le v \le n$，满足存在一条从 $u$ 到 $v$ 的长度为 $k$ 的途径，和一条从 $v$ 到 $u$ 的长度为 $k$ 的途径。 $1 \le n \le 10^ ......

## CF248B Chilly Willy ### 解题过程 经过简单思考，这道题肯定是由规律可循，因为 $n \le 10^5$，只有高精度能存下。 下面是暴力程序对 $n$ 为 $1$ 到 $13$ 时的答案进行求解（$11$ 到 $13$ 超出 int 范围了）。 ![img](https: ......

[题目链接](https://codeforces.com/problemset/problem/383/C) # 题目 见链接。 # 题解 **知识点：DFS序，树状数组。** 我们需要对子树的不同奇偶层加减，用dfn序可以解决子树问题，但是并不能直接分奇偶。 一种比较麻烦的思路是，将dfn序分成 ......

E是补的 太蠢了没想到 期末考完的复健 A. Sasha and Array Coloring 题意：可以给不同数字涂上很多颜色，每个颜色的贡献是同一个颜色内的数字最大值和最小值的差 思路：排序一遍，取头和尾的差 #include<bits/stdc++.h> #define close std:: ......

大难题，但是非常的有意思。思路来自 $\color{black}\text{艾}\color{red}\text{利克斯·伟}$。补充了一点小细节。 ## 题意 对于一个 **可重** 集合 $S$，初始为 $\{1 \dots n\}$，执行以下操作：删除集合中的最大、最小元素 $S_{min}, ......

谁说 $n\le5\times 10^5$，$k\le100$，$p\le100$ 只能 $O(nk)$？我今天就要用 $O(nk\log p)$ 过这个题！ 定义 $f_{i,j}$ 表示前 $j$ 个数，分成 $i$ 段的最小价值和，$s_i$ 表示前缀和（对 $p$ 取模），转移就是 $f_{ ......

我们发现，如果我们把 $\sum_{j a_{i+1}$ 就变成 $b_i>b_{i+1}$。从一个奇怪的递推关系变成了很好的偏序关系。而且我们由此知道序列在任何时候是有序的。 所以，我们把 $a_i-\sum_{j>1); init(i>1)+1,r); sg[i].s=(sg[ir||sg[i] ......

首先，如果 $(x,x+d)$ 可以实现，那么任意的 $(y,y+d)$ 都可以被实现。 也就是，差相等的所有数对等价。 如果 $y\ge x$，显然可以仅通过 $(x+1,y+1)$ 达成目的。所以问题等价于证明 $(x,x+d)$ 与 $(1,d+1)$ 等价。 我们找到一个 $N$ 使得 $2 ......

## CF1746E Joking 交互库最开始给定一个正整数 $n$，并生成一个 $x \in [1, n]$，你的目标是得到交互库中的 $x$。 你可以向交互库提出问题： 提问一个集合 $S$，交互库回答的内容是 $x \in S$ 的真假。该提问次数不能超过限制数 $Q$。 交互库可以骗人，也 ......

有点神仙的。 ## 题意 给定一张 $n$ 个点 $m$ 条边的有向图，有边权，进行 $q$ 次询问（$n,m,q\le 2\times 10^5$，边权为不超过 $10^9$ 的正整数）。 每次询问给定三个参数 $v,s,t(0\le s using namespace std; using LL ......

经典套路。 ## 题意 你将随机生成一个长度为 $k$ 的数组 $a$，其中 $a_i$ 有 $p_i$ 概率为 $1$，否则为 $-1$。定义其前缀和数组 $s_i = \sum\limits_{j = 1}^{i}a_j, i \in [0, k]$。如果前缀和数组的最大值为 $t(t \in ......

比较水的 *2800，但是考察对标记的理解。 有一个比较原始的思路：因为需要让所有数码为 $x$ 的改成 $y$，我们不难想到这样一个做法：对十进制下第 $1,2,3\ldots$ 位各开一棵线段树，每个节点存区间内每种数码的出现次数 $cnt_i$ ，最后用位值原理合并得到答案。 对于区间修改操作 ......

分块。我们先来考虑修改对整块的影响。记值域为 $V=10^5$。 考虑对每一块维护 $V$ 个集合 $S_1,S_2,\cdots,S_V$，第 $i$ 个集合 $S_i$ 维护了区间中所有 $=i$ 的元素的一些信息，并维护区间的最大值 $m$，对于一次操作 $x$： - 若 $m\le 2x$， ......

## 题面翻译 **本题是一道交互题。** **本题需要你编写一个国际象棋中单后杀王的程序，和交互库对弈。** 本题的规则和一般国际象棋中的规则有所不同，请认真阅读。 国际象棋棋盘是 $8\times 8$ 的正方形网格。本题中，所有行从上到下分别编为 $1\sim 8$ 行，所有列从左到右分别编为 ......

## 题面翻译 二元组$ (a,b)$,可以变成$ (a,b+1)$或$ (ab,b)$ 你有初始二元组$ (1,0)$,给你区间$ [l,r]$,和一个整数$ p$,在区间内选一个数$ x$,使$ (1,0)$在不超过$ p$步变化后,第一维的值变成$ x$,求$ x$的个数$ (2 #defin ......

CF1239E Turtle 通过观察我们会发现，第一行一定单调递增，第二行一定单调递减，否则不是最优。再次前提下，乌龟的最优方案只有两种，要么一直向右，最后向下，要么先向下，再一直向右。因此，我们将最小的两个数字放在左上角和右下角，然后把余下数字填入剩余位置，并希望下式最小 显然，这是一个背包问题 ......

不妨设 $a$ 单调递增（无重复），显然如果 $n\le 3$ 答案就是 $0$。 显然答案 $k$ 具有可二分性。也就是说，当 $k #define rep(x,y,z) for(ll x=(y);x=(z);x--) #define debug(format...) fprintf(stderr ......

### 1 题目大意 **1.1 题目翻译：** 给定一个值域为 $[1,n]$ 的函数 $f(x)$，让你求出最小的 $k$，其中 $k$ 满足 $f^{(2k)}(x) = f^{(k)}(x)$。 其实我觉得这题你谷翻译十分到位，建议没读懂题的还是去看你谷翻译罢。 **1.2 数据范围：** ......

[题面](https://www.luogu.com.cn/problem/CF388D) 题意： >给定非负整数 $n$，定义一个自然数集合 $S$ 是好的，当且仅当 $\forall x\in S,x\le n$ 且 $\forall x,y\in S,x\oplus y\in S$，其中 $\ ......

两道题似乎都涉及了一个经典模型： > 在一张有向图上，给定起点 $s$ 和终点 $t$，询问 $s$ 到 $t$ 与 $t$ 到 $s$ 是否均存在一条长度 $=L$ 的路径（$L$ 是一个 $\ge n^3$ 的数）。 首先 $s$ 与 $t$ 必须在同一个 SCC 内（考场上没看到互相可达直接以 ......

感觉不难啊，为什么是 *2800 捏。 先离散化。对每个横坐标开一个 set 存点，插入删除就能做了。查询的时候线段树二分就行了。 更具体地，我们维护区间内纵坐标的最大值，在二分的时候能左就左，不能左就右。 注意这里的右上角是严格大于。 点击查看代码 ``` #include #define int ......

感觉不难啊，为什么是 *2900 捏。 发现这个玩意的本质是最初在 r，每次不动或向左移动一步，进行 l 次操作，求每次停留的格子权值之和的最小值。显然我们只会停留在至多一个格子上，假设停留在 $i$，那么权值之和就是 $\left(l-r+i\right)a_i+\sum\limits_{j=i+ ......

# 题目大意 给出一个长为$2^{K+1}$的序列，每个元素在$[0,4^K)$之间， 在**序列中**找到两个不相交的区间使得二者的异或和相等 $Krk150 因为元素大小是$4^K$级别的，和大小相关的算法（FWT）都没用了，~~所以不如直接随机~~ 发现长度为$2^{K+1}$的序列里有$2^ ......