题解

CF1896D 如果只有单次询问其实可以双指针，但是这个难以进行拓展。 考虑找点性质。 发现 \(a_i,v\in\{1,2\}\)，从值域上下手。发现若存在和为 \(S\) 的方案，则一定有和为 \(S-2\) 的方案，因为可以直接 \(-2\) 或 \(-1-1\)。 然后就变为找最大的和为奇/ ......

11.16（C0389） 100+10+50=160，rk3。 本来 BC 都应该写出来的。 A：dp 或 贪心 都可以，贪心直接从下往上覆盖即可。 B： 注意：这里的 \(\oplus\) 指的是按位或。 合法条件可以化简为：\(\oplus_{i=1}^{p}a_i = \oplus_{i = ......

我们先将柿子变成 \(\frac{1}{2}(dis_{x,y}+dep_{x}+dep_{y})-dep'_{lca'}\) 考虑边分治，枚举断边，我们将一个点在第二棵树上的点权看成是 \(v_x=d_x+dep_x\)，答案就为 \(v_x+v_y+dep'_{lca'}\) 对于每次边分治将分 ......

Problem - D - Codeforces Split - 洛谷 我现在水平好烂，再做下去自信心就全败没了 先考虑 \(Q=1\) 怎么做？ 两种做法： 暴力枚举分界点，左右判断 暴力枚举 \(\max\limits_{i=l}^{x} a_i\)，找到最靠右边的分界点位置 \(x\)，判断是 ......

[ABC267F] Exactly K Steps 题解 思路 首先发现，如果对于查询 \((u, k), k > 0\) 可行，那么对于 \((u, k - 1)\) 也一定可行，因为往回走一步就可以了，所以对于一个点可以找到离它最远的点，根据直径的结论，这个点一定是直径的端点之一。 为了方便做， ......

manacher + exKMP + 二分。 感觉是最粗暴的方法，想出来之后自己硬莽了 4k，荣获题解区最长。 Solution 约定：下文所提及到的所有的回文串，均指奇长度回文串。 显然把题目拆成两个部分，中间的回文串，以及两边相同的连续子串。考虑一下从哪个入手比较好。 忘记是咋想的了，易得从两边 ......

[SNOI2019] 网络 题解 最喜欢这道题。 简要题意 给一颗 \(n\) 个节点的树和一个参数 \(d\)，定义两个节点 \(x,y\) 之间的距离为 \(x\) 到 \(y\) 的简单路径上的边数。 定义一个树上连通块的权值为连通块中任意两点的距离之和。定义一个树上连通块的直径为连通块中任意 ......

Problem - 1887C - Codeforces Minimum Array - 洛谷 有点被降智了/ll 首先区间修改显然先转化成差分序列单点修改。 显然对于相同的操作序列，\(a_i\) 的取值对答案无影响，因此我们可以先让 \(a_i\) 全部取 \(0\)，最后再加回来即可 假如说操 ......

题目链接：https://www.luogu.com.cn/problem/B3647 floyd算法：https://oi-wiki.org/graph/shortest-path/#floyd-算法 示例程序： #include <bits/stdc++.h> using namespace s ......

思路 假设原题目中的 \(n\) 在本文中为 \(num\)，则原长方形的长 \(m = f_{num + 1}\) 和宽 \(n = f_{num}\)。 显然对于最初始的长方形，显然是要将一个 \(f_{num} \times f_{num}\) 的长方形丢进去的，并且要么放最左边，要么放在最右 ......

我们考虑暴力咋做，每次得到一个森林之后，必定是从最大的树上摘一棵子树，挪到最小的树上，所以此时的答案为 \(max(siz_{mx}-x,siz_{mn}+x,siz_{次大值} )\)，于是发现 \(x=\frac{siz_{mx}-siz_{mn}}{2}\) 时答案最优，所以只需找到这个值的前 ......

CF238 Codeforces Round 148 (Div. 1) CF238A link CF238A题意 给出两个整数 \(n,m\)，现在问你有多少个序列 \(a\) 满足： 序列长度为 \(n\)。 \(a_i\in[0,2^m-1]\) \(\forall 1\le i\le j \l ......

HNOI2017 影魔 对于两种贡献，都只用考虑左边第一个比自己大的，和右边第一个比自己大的数，分别记为 \(l_i、r_i\) 对于询问一，每个数对 \((l_i,r_i)\) 构成全部情况 对于询问二，可以拆分成 \(x=l_i\) 时，\(y \in [i+1,r_i-1]\) ，以及 \(y ......

Problem - 1051E - Codeforces Vasya and Big Integers - 洛谷 感谢女队提交记录推荐给我的一道题 \(Orz\) 首先 \(O(n^2)\) 的 \(dp\) 是 simple 的，如果你没看出来你可能是像我一样把题目看错了 设 \(dp_i\) 表 ......

Description 有 \(n\) 条河和 \(m+1\) 个交汇处构成一棵以 \(0\) 号点（即大海） 为根的树。 每条河有各自的名称。对于一个交汇处，从它流出的干流的名称是流入这个交汇处的各个支流的名称之一。一条河流的长度是以它为名称的河流的长度之和。对于一个可能的命名方案，一条河流的排名 ......

题意 设 \(S\) 为一个可重数集，满足所有元素均为非负整数。你可以对 \(S\) 进行若干次（可以为 \(0\) 次）如下操作：选择一个非负整数 \(x\) 满足 \(x\) 至少在 \(S\) 中出现了 \(2\) 次，在 \(S\) 中删除一个 \(x\)，并将 \((x-1)\) 或 \( ......

原文链接：https://gaoyubo.cn/blogs/3ecd1562.html 一、双指针 27. 移除元素 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 ......

原文链接：https://gaoyubo.cn/blogs/141ec005.html 一、双指针 151. 反转字符串中的单词 给你一个字符串 s ，请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 ......

原文链接：https://gaoyubo.cn/blogs/141ec005.html 一、双指针 151. 反转字符串中的单词 给你一个字符串 s ，请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 ......

[题目传送门](https://www.luogu.com.cn/problem/P2446)# 解法由题可知，一个城市$u$保护城市$v$，所以建一条边$u \to v$表示城市$u$保护城市$v$，因为题目说保证有解，所以建的图一定是一个**有向无环图$DAG$** 。再在此基础上求出最短路径。 ......

博客园。 我们会发现，\(2\) 和 \(3\) 的火柴个数是一样的，\(9\) 和 \(0\) 的火柴个数是一样的。 所以只有在 \(12\) 到 \(13\) 这样是合法的，自己推一下可以知道，最多只有连续两个。 而在 \(l\) 到 \(r\) 的长度大于 \(9\) 的时候可以直接输出 \( ......

CF1178H题解 分成两个问题解决 问题一：最小时间 发现具有单调性，于是二分，考虑怎么 \(check\) ，画几个函数图像之后看出，在最终时刻最大的\(n\) 个点，在 \(0\) 时刻必然要可以取到 问题二：最小交换次数 正常费用流建图，初始，终止时各一个，前缀和优化建边 具体的，是在排过序 ......

[Pinely Round 3 (Div. 1 + Div. 2) - Codeforces](https://codeforces.com/contest/1909) $$ \color{purple}\large\textbf{世界上只有一种真正的英雄主义，} $$ $$ \color{red}... ......

⭐Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333） 前言: 好的,比赛的时候给比赛忘了，少跑二十多分钟，好在这次题目都比较简单，也算是迅速赶上了 顺带一提，为了赶时间貌似没有一题是用C++写的…… 模拟只会猜题意，贪心只能 ......

⭐AtCoder Beginner Contest 334 前言: 比赛题目链接 --按照惯例只写了主要部分的代码-- 特别说明：Rust有一个竞赛用的输入库，并且写ABC是可以用的，但是平时写洛谷是用不了的，所以我自己写了一个cin(),凑活能用，代码见下： 读输入函数 fn cin() -> S ......

P1496 火烧赤壁 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 我们首先先看数据，n<=20000，数据不多，但是范围大（-10^9<=Ai,Bi<=10^9），这时，就可以用离散化了。但是在这里我们会遇到区间重合的问题（也可以使用区间合并），如下图 本题的题意是让我们求出燃 ......

[ABC265F] Manhattan Cafe 题解 思路解析 很有思维难度的一道题。思路是dp，\(f[i][j][k]\) 表示已经计算了 \(i\) 维，距离点 \(p\) 的距离为 \(j\) ，距离点 \(q\) 的距离为 \(k\) 时的整点 \(r\) 个数，由此可见我们的每一维都可 ......

A - Christmas Present 简单题。 void slv() { int a = Read<int>(), b = Read<int>(); if (a > b) Puts("Bat"); else Puts("Glove"); return; } B - Christmas Tree ......

设 \(f_i\) 表示假设只有编号为 \(1\sim i\) 的点，此时的答案。\(f_n\) 即为所求。 显然有： \[f_i=\min\limits_{i-k\le j < i}\{f_j+dis(s\to j+1\to j+2\to\cdots\to i)\}+dis(i\to s) \]当 ......

先求出初始时绿连通块数量。 枚举每个红色格子，将其染成绿色本应增加一个绿连通块，但是它每与一个绿连通块相邻，就又会减少一个绿连通块。根据上述规则可以求出每个红色格子染绿后的绿连通块数量，求平均值即可。 时间复杂度 \(O(nm)\)。 // Problem: E - Christmas Color ......