题解 做法133f abc

4 月 27 日测试题解 最短路专场 T1 ${\color{green}{\text{100pts}}}\text{/100pts}$ 题意 给出 $m$ 个变量与 $n$ 个约束，每个约束形如以下三种中的一种； $x_i - x_j \le w$ $x_i - x_j \ge w$ $x_i - ......

4 月 21 日测试题解 T1 ${\color{green}{\text{100pts}}}\text{/100pts}$ 题意 给出平面上的两条线段，求线段之间的距离。 $\text{|线段端点坐标|} \le 10^4$。 思路 一开始想的是分讨，但是又怕自己写挂了，所以就写了三分套三分。至少 ......

正文 ♦最坏时间复杂度：$\mathcal{O}(\lvert S\rvert)$ 本题十分简单，但请注意两个条件要同时满足。 因为要求分割的次数越少越好，所以只要连续的辅音字母长度不大于 2 就不需要分割。 由于辅音字母太多，只需要标记元音字母即可。 #include<iostream> #inc ......

P4145 上帝造题的七分钟 2 / 花神游历各国 题目描述 分析 一开始在思考有没有一个数学公式来处理每一个开方的操作 但发现数据的$\le 10^{12}$ 那么最多开六次就变成1了（突破口） 这样每一个数的有用操作只有6次 其他就全部是1 很显然，我们可以去记录每一段是否全为1 再用线段树、分 ......

思路 点分树 + 根号重构 + *高速平衡树。 点分树的两种常见用法无非是 直接做和路径有关的暴力 还有 处理这种有关单点和整树的问题，后者的另一个经典题目是 P3241 [HNOI2015]开店。 回到这个题目，处理路径考虑先上点分治，暂时不考虑强制在线的限制。 因为每次加上一个新点，所以可以考虑 ......

为了便于解题，先对 $a$ 数组从小到大进行排序。 首先，根据定义可以得出总价值的表达式： $$ \begin{aligned} W&=\sum\limits_{(u,v)\in E}[a_ua_v+t(a_u+a_v)]\ &=\sum\limits_{(u,v)\in E}a_ua_v+t\su ......

P6818 [PA2013]Działka 前言 我太菜了。。。。 对着 jiangly 大佬的题解研究了一下午研究了一下午才搞出来（泪目。 作为一个蒟蒻，我就详细的讲一下我对与本题的理解。 题意 本题的的题意描述的还是比较明了。 在二维坐标系中，输入 $n$ 个点 $m$ 次询问， 每次询问，给出 ......

非常好题目，爱来自 xc。 看到有向无环图，想到拓扑序。通过拓扑序，可以轻松求出以每个点为起点的最长路 $disS$与每个点为终点的最长路 $disF$。 如何求总共的最长路？在 $disS,disF,disS_u + 1 + disF_v((u,v)\in E)$ 中取最大值即可。注意最后一项，表 ......

前言 数学符号约定： $\dbinom{n}{m}$：表示 $n$ 选 $m$ 。 如非特殊说明，将会按照上述约定书写符号。 题目分析： 考虑题目的问题弱一点的版本，假设此时我们的括号序列是确定的如何求其括号匹配的最深深度。 如果你有些许 dp 基础的话，不难想到如下做法： 考虑位置 $i$，将区间 ......

前言 建议大家看一下我对于 D1 的题解（传送门）后再看本题解，本题解是基于那篇题解的基础上书写的。 数学符号约定 $\dbinom{n}{m}$：表示 $n$ 选 $m$ 。 如非特殊说明，将会按照上述约定书写符号。 题目分析 首先引用一下 D1 的答案：$\displaystyle\sum_{i ......

不难发现一个较简单的网络流模型： 源点向所有糖果 $i$ 连 $a_i$ 的容量； 所有糖果向所有人 $i$ 连 $b_i$ 的容量； 所有人 $i$ 向汇点连 $c_i$ 的容量。 但第二步中建出的边数达到了惊人的 $O(nm)$，显然过不去。 考虑优化。从最大流角度优化较困难，由于最大流等价于最 ......

Problem StatementYou are given a string $S$ consisting of lowercase English letters. Print the number of non-empty strings $T$ that satisfy the follow ......

前言 题目传送门！ 更好的阅读体验？ 刚学分治就来写篇题解纪念一下，其实和平面最近点对一样的（总共四倍经验！）。 思路 根据 P7883 的分治思路，这题我们可以考虑用相似的方法解决。 首先将点集按 $x$ 坐标从小到大排序。然后分治。 对于 $\left[l, r\right]$ 区间，分治为 $ ......

解析 传送门 一道简单的tarjan题 题意：在无向图中找一些点，这些点组成的的点集记为$V$ ，使得去掉任意一个点，剩下的每一个点都可以到达$V$中任意一个点，求点集$V$的大小的最小值及其方案数。 去掉一个点，很自然的联想到割点，那么考虑一下割点在不在备选集合中。 如图，显然可以看出，在割点上设 ......

2023-02-20 题目 题目传送门 翻译 翻译 难度&重要性(1~10):4.5 题目来源 AtCoder 题目算法 最短路 解题思路 我们枚举每一对点 $(u_i,v_i)$ 间的距离小于等于 $t$，那么只要在 $u_i$ 加一次油就可以直接到 $v_i$ 了，距离设为 $1$；若大于 $t ......

2023-02-18 题目 题目传送门 翻译 翻译 难度&重要性(1~10):5 题目来源 AtCoder 题目算法 状压dp 解题思路 我们令 $S$ 表示当前箱子状态，$P_i$ 表示第 $i$ 把钥匙能开的箱子。 设 $f_S$ 表示开启当前状态箱子的最小花费。 能得到转移方程: $f_{P_ ......

2023-02-17 题目 题目传送门 翻译 翻译 难度&重要性(1~10):4 题目来源 AtCoder 题目算法 dp,字符串 解题思路 看到求两个完全相同的子串时，我们可以发现其与求最长公共子串相似，只不过是在同一个字符串中求。因此我们可以使用求最长公共子串类似的 dp 转移。设 $f_{i, ......

2023-02-13 题目 题目传送门 翻译 翻译 难度&重要性(1~10):6 题目来源 AtCoder 题目算法 贪心 解题思路 用了两个 multiset a 和一个 set s，一个 multiset 用来记录用来存还剩哪些数没生成，另一个用来存已经生成了哪些数，然后后面放数的时候就枚举第二 ......

比赛地址 这把真不在状态，麻了，看来还得再练 A. A-characteristic 题意：给出n和k，要求构造只含1和-1数组a，存在k对(i,j)（i≠j），有a[i]*a[j]=1 Solution 令构造的数组有x个1和y个-1，那么其对于答案的贡献有 $$ x*(x-1)/2+y*(y-1 ......

2023-02-13 题目 题目传送门 翻译 翻译 难度&重要性(1~10):4 题目来源 AtCoder 题目算法 双向链表 解题思路 $1.$ 当我们用从小到大的顺序来求解时，把原来求过的都直接跳过，不用再进行重新求解，以此来降低时间的复杂度。 $2.$ 在我们每次更新时，比当前小的数都已经被跳 ......

2023-02-03 题目 题目传送门 翻译 翻译 难度&重要性(1~10):6 题目来源 AtCoder 题目算法 数位dp 解题思路 $1.$ 当 $2x\leq y$，有$y-x>y% x$； $2.$ 当 $2x>y$，有$y-x=y% x$。 $3.$ $y\oplus x\geq y-x ......

题面链接 简要题意 给定一个序列，区间 .map([](int x) { x = x * x % p; });，区间求和。 p 给定，为小质数。$N,M\le 10^5$。 题解 而把一个数看作一个点，向其平方取模连一条边，则最终必然构成一个基环森林，注意到 $P$ 很小，每个数经过 $11$ 次迭 ......

2023-02-02 题目传送门 翻译 难度&重要性(1~10):4 题目来源 AtCoder 题目算法 数学，贪心 解题思路 记这个数列的和为 $sum$。那么对于每一次操作，$sum$ 的值都不会改变。最后的答案，也一定是 $sum$ 的因数。 那么我们枚举一下 $sum$ 的因数，然后判断一下 ......

前言 本文中 $S[i,j]$ 表示取 $S$ 中 $i$ 到 $j$ 位置连接成的子串。 补充知识：本原平方串 定义：一个字符串 $S$ 是本原平方串，当且仅当其循环节长度为 $\frac{|s|}{2}$。 性质：字符串 $S$ 的子串中本原平方串的个数至多为 $n \log n$。 不会 $\ ......

一、题目描述： n 个点，m 条边，带边权。起点为 1，终点为 n。 求最小割以及在最小割的情况下的最少割的边数。 2<=n<=32,1<=m<=1e3。 二、解题思路： 第一问很好求解，直接最大流即可。 第二问想不出来，看了题解把我震惊了！ 设边 i 原本的边权为 w[i]，现在我们令新边权 v[ ......

~~谨以此题解纪念我的20次提交~~。 题目大意 给一个整数 $x$ 和 进位次数 $k$，求一个数 $y$ 使得列竖式计算 $x+y$ 时正好产生 $k$ 次进位。 思路 ~~（最开始是想正着搞的，但是怎么也调不出来）~~提供一种倒着做的做法。 首先有几个结论： 产生进位 $=$ 给前一位 $+1 ......

前言 数学符号约定 $a,b,p$：表示任意自然数。 $F_x$：表示广义斐波那契数列的第 $x$ 项。 $f_x$：表示普通斐波那契数列的第 $x$ 项. 如非特殊说明，将会按照上述约定书写符号。 题目分析 首先引入一条定理： 普通斐波那契数列在模 $m$ 意义下纯循环，且循环节为 $O(m)$。 ......

一、题目描述： n 个点，m 条边，给定起点 s 和终点 t ，求最少删去几个点后，s 和 t 不连通。 注意，s 和 t 不能删掉。1<=n<=100，1<=m<=600; 二、解题思路： 刚刚学了最大费用流，知道最大流等于最小割。但此题割的不是边，是点。 我们需要将将割点转化为割边。把一个点切成 ......

AtCoder ABC ABC238 Editorial ARC AGC CodeForces Div4 Div3 Div2 Div1 Luogu GF 模拟赛 游记 GDOI2023 游记 ......

D. Frog Traveler 1900 dp gq！ https://codeforces.com/contest/1602/problem/D 题解：我们可以通过类似bfs的过程找到每个点的能到达的所需步数最小的点，完成更新，但每个点能被哪些点到达很难判断，故我们反过来考虑，如果我们能得到从n ......