题解1328e cf

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$ 就在疯狂暗示，也就是说你可以经过每个环 ......

题目传送门：[link](https://www.luogu.com.cn/problem/P2596)。 ## FHQ-Treap 解题的关键在于如何来求出一本书上面有多少本书，但考虑到我们里面没有像权值一样的东西来让我们用按值分裂来完成这个操作，所以考虑用按排名分裂来实现。 我们按照先后顺序把所 ......

比较套路的拆贡献题。 考虑直接枚举那个 $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: ......

UVA12222 山路 题意： - - 一个山路只有一条车道，因此不能有两辆方向相反的车同时在车道内。同时，为了保证安全，车道内不能超车，且同向行驶的车间距必须大于10分钟。现在给你n辆车，三个参数依次表示行驶方向，到达时刻，行驶时间。问如何安排能使最后一个通过的车通过时的时刻最小，输出这个值。 分 ......

[题目链接](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_{ ......

## A.Ekiden Race (450) 题意：$n$ 个人在进行往返跑比赛，其中第 $i$ 个人在回程前的排名是 $i$，总排名是 $p_i$，问有多少个人可能成为回程中跑得最快的人？ 如果对于 $i$，存在某个 $j>i$，使得 $p_j<p_i$，那么 $j$ 在回程途中超过了 $i$，$ ......

小蒟蒻第一次写题解，不好请指出。 ## 思路1 1. 找每个字符串中的 `AB` 的数量； 2. 暴力枚举两个字符串的第一个字符和最后一个字符能否组成 `AB`； 然后就是劈里啪啦敲代码。 ```cpp #include #include using namespace std; struct st ......

小蒟蒻的第二篇题解，有问题请指出。 ## 思路 用三重循环依次找出 `I`、`O`、`I`。 第一个循环找第一个 `I`，若找出，继续第二个循环找 `O`，若找出，最后第三个循环找 `I`，若全部找出，直接输出 `Yes` 返回 $0$ 结束。遍历整个字符串也没有 `I`、`O`、`I` 的话，便输 ......

我们发现，如果我们把 $\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 ......

题目链接：https://www.luogu.com.cn/problem/P3853 题目大意：给出一个递增数组，插入K个值，使其差分数列的最大值最小；值得注意的是，此题中每个数字都是整数 考点：整数二分 错误思路：利用堆排，取最大值直接二分 code： 1 #include<bits/stdc+ ......

## 题目大意 给定一个N个点M条边的带权有向图，求平均值最小的回路。 ## 解法 看到这种题目，~~喜欢打暴力的我~~一下就想到：遍历整个图，找到每一个环，然后算出它们的平均值，最后比较出最小值。然而，呃...，会T飞... **既然我们不能暴力找最小值，那还有什么别的办法吗？** 我们只需要输出 ......

## 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$， ......

看到这种奇怪的操作，首先想到分块。 以下记值域为 $w$，块长为 $B$。 前缀 $\gcd$ 显然单调不增，而且后一个必须是前一个的因数，如果变化至少要减半。因此，我们知道，共有 $\mathcal O(\log w)$ 个不同的前缀 $\gcd$。我们可以接受对这些块暴力，只需要对前缀 $\gc ......

在算法竞赛中，写题解是我们不可或缺的一部分。它不仅能够帮助我们整理思路、总结经验，还可以与他人分享我们的解题思路和代码实现。然而，写一篇较完备的题解往往非常繁琐，需要手动复制粘贴题目链接、题号和AC代码，这不仅费时费力，还容易分散我们的注意力，因为我们写题解的核心内容是对题目的理解以及怎么解决这个问 ......

## 题面翻译 **本题是一道交互题。** **本题需要你编写一个国际象棋中单后杀王的程序，和交互库对弈。** 本题的规则和一般国际象棋中的规则有所不同，请认真阅读。 国际象棋棋盘是 $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 通过观察我们会发现，第一行一定单调递增，第二行一定单调递减，否则不是最优。再次前提下，乌龟的最优方案只有两种，要么一直向右，最后向下，要么先向下，再一直向右。因此，我们将最小的两个数字放在左上角和右下角，然后把余下数字填入剩余位置，并希望下式最小 显然，这是一个背包问题 ......