050c arc 111 lcm

题意 对于一个长度为 \(N\) 的序列 \(H\)，可以通过如下方式构造一个序列 \(P\)： 若存在 \(j \in \left[1, i\right)\)，使得 \(H_j > H_i\)，则 \(P_i = \max\limits_{j \in \left[1, i\right) \land ......

Problem StatementWe have a sequence of $N$ positive integers: $A_1,A_2,\cdots,A_N$. You are to rearrange these integers into another sequence $x_1,x_2 ......

Problem StatementThere are $2N$ integers written on a blackboard. The $i$-th integer is $A_i$. Alice and Bob will play a game consisting of $N$ rounds ......

题意 给定一个长度为 \(N\) 的序列 \(A\)，按照下列方式生成一个长度为 \(N\) 的序列 \(X\)： \(\forall i\in[1,n]\)，\(X_i\) 在 \([1,A_i]\) 中的整数中均匀随机生成。 求其最长上升子序列长度的期望，对 \(10^9+7\) 取模。 \(1 ......

[ARC098F] Donation 题解 题目描述 给定一张 \(n\) 点，\(m\) 边的无向图，到达一个点需要拥有 \(a_i\) 的权值，对于一个点操作需要消耗 \(b_i\) 的权值，询问最少需要多少权值才能够对每个点都进行一次操作（权值在任何时候都不能小于 \(0\)）。 题目分析 提 ......

这是一道容易想假的题（个人认为）。 首先有一个转化，我们发现直接删边不好做，我们考虑如果已经知道这条唯一路径该怎么做。我们画完图后发现，保留的图一定会是路径中的点挂着若干个路径以外的点，并且这些点可以任意互相连边，路径中不同点挂着的点集一定不能互相连边。 但是直接枚举这条路径会超时，这时候我们发现， ......

题意 对于一个只含有 A，C，T，G 的字符串 \(s\), 定义其为匹配的当且仅当其中 A 的数量和 T 的数量相等，C 的数量和 G 的数量相等。 给定一个长度为 \(N\) 的字符串 \(S\)，求其有多少个非空子串是匹配的。 \(1 \le N \le 5000\)。 题解 \(\mathc ......

题意 有 \(N\) 个区间 \([a_i,b_i](a_i<b_i)\)，都是 \([1,2n]\) 内的整数且互不相同（\(a_i\ne b_j,a_i\ne a_j,b_i\ne b_j\)）。 现在给定一些 \(a\) 和 \(b\) 的值，剩下不知道的用 \(-1\) 表示。问是否存在一种 ......

题意 给定 \(N,K\) 和 \(M\)。对于每个大小在 \([1,N]\) 中的 \(x\)，求每个元素大小在 \([1,N]\) 中，平均数为 \(x\) 且相同元素不超过 \(K\) 个的可重集的数量，对 \(M\) 取模。 \(1 \le N,K \le 100\)，\(M\) 为质数。 ......

[ARC159F] Good Division 题解 首先对于题目要求的划分方式转化一下，转化为划分的每一段都没有 绝对众数，可以证明这与题目中的要求是完全等价的，证明如下： 充分性：考虑构造一种操作方法，就是每次操作都消去一个出现次数最多的数，按照这样操作可以保证每次操作之后该区间仍然不会出现绝对 ......

ARC167 A. 题目明示，让每组的和尽可能平均就是平衡。 那相当于 \(a\) 升序排序后，前 \(2(n-m)\) 个数首尾配对成组，其余数单独成组即可。 题解有一个值得借鉴的技巧，补 \(0\) 使得 \(a\) 长度为 \(2m\)。 \(\color{green}{\checkmark} ......

题解 [ARC149B] Two LIS Sum 大胆猜结论，按照 \(a\) 数组为关键字进行排序，求更改后 \(b\) 的 \(LIS\) 。 证明：每次移动，都有 \(a\) 中增加一个长度， \(b\) 中贡献可能为 \(\{-1,0,1\}\) ， 总体贡献为 \(\{0,1,2\}\) ......

这道题目千岩万转，需要用到多次转化，其中有一些转化较为常见，有一些则需要思考。 首先观察原问题：给定数列 \(a\)，对于所有 \(1\sim n\) 的排列 \(p\)，构建一张只有 \(j-i\le k\) 的 \((i,j)\) 之间有权值为 \(\max\{a_{p_i}, a_{p_j}\ ......

blog。很牛的题，想了差不多一个小时。 经典结论 此处 \(S\to T\) 表示状态 \(S\) 可以变成状态 \(T\)。 \(\textbf{Conclusion: }\) 若 \(\forall S\to T\to P\) 都有 \(S\to P\)，则 \(S\) 为必胜态。（用中文讲： ......

仅存不会的题。 AtCoder [ARC099B] Snuke Numbers 一种题目：要求 列出 前 \(k\) 小 的所有满足条件的数。 这时候有个 Trick：可以考虑求一个 \(f(n)\) 表示 \(\ge n\) 的最小的满足条件的数。这样就可以从 \(f(1)\) 出发跳 \(k-1 ......

AtCoder-ARC114_A Not coprime \(50\) 内的质数只有 \(15\) 个，可能的答案也就只有 \(2^{15}\) 个，直接枚举。 提交记录：Submission - AtCoder AtCoder-ARC114_B Special Subsets 就是 \(i\) 与 ......

Description 给定正整数 \(n\) 和长度为 \(n\) 的序列 \(x_i,y_i\)，保证 \(x_i\) 单调递增。你要构造 \(m\) 个区间 \([L_i,R_i]\)（\(m\) 由你指定），使每个 \(x_i\) 恰好被 \(y_i\) 个区间包含。 最大化 \(\min_ ......

104.二叉树的最大深度 1、后续遍历递归法 class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if root is None: return 0 left_depth = self.maxDepth(root. ......

质量很大，孩子很喜欢🥰 上来就感觉很神秘，要决策的东西有点多，起点，交钱，还有每个点的限制，应该没法做。 所以直接考虑倒过来，假设我们最后还剩下 \(w\) 元，去判断能不能反着跑完。如果能跑完答案就是 \(w+\sum b\)。 一开始其实并不知道这样对不对，先看一看有没有更好的条件。假设一开始 ......

shaber round。 A 显然都会变成 1。枚举穿过 1 的那次操作在哪，剩下两边的答案直接算出来就行。 B 不会。 C 完全子图 的判定，直接考虑建立补图。那么补图一定是一张二分图。染色判定。 如果我们划分为了 \(n=x+y\) 两个大小的完全子图那么答案就是 \(\frac{x(x-1) ......

板刷自 ARC104 起所有 ARC 的 \(\text{C}\sim\text{E}\) 题。 进度：https://kenkoooo.com/atcoder/#/table/lsj2009。 ARC104 https://atcoder.jp/contests/arc104/tasks/arc1 ......

A 直接 \(a_i\gets a_i-i\) 做中位数就行。 B 这我都不会？？？ 不能嗯二分答案。考虑相当于枚举三个数 \(i<j<k\) 算 \(s_i,s_j-s_i,s_k-s_j,s_n-s_k\)，然后枚举 \(j\)，显然 \(i,k\) 的最优决策点是单调的。直接双指针啊啊。 C ......

A 枚举其中一个，然后发现剩下两个的限制非常强，用一个桶统计同余类大小即可。 B 谔谔构造。 考虑 \(n=\log 10^6\)，大概可以猜一下这个题是想让我们搞一个二进制构造。 先造一条 \(0\sim 2^{\log L}-1\) 的链，然后再往 \(N\) 连即可。 C 基础组合题。不是很懂 ......

答案大于max{ai}可以直接计算 主要考虑小于的情况 直接计算gcd很困难，不妨枚举x|gcd 那么对于ai来说 假设 x(k-1)<ai<=xk,那么 ai就需要xk-ai次操作，那么我们对于一个x，只需枚举k计算区间数的个数即可算出需要的操作数。 复杂度O(nlnn) 这种套路就是取模转化成减 ......

题目描述： 定义 \(n-\)可爱序列 指无限长的由 \(\{1,2...,n\}\) 组成的序列。同时 \(a_1,a_2...\)满足以下条件: 1.第 \(n\) 个及以后的元素是相同的，即若 \(\forall i,j\geq n,a_i=a_j\) 。 2.对于每个位置 \(i\)，紧随第 ......

发现还没有和我一样的做法。 觉得 B 比 A 好想的多。 令 \(A_i\) 为 \(a_i\) 变成 \(A\) 的倍数最少次数，\(B_i,C_i,AB_i,AC_i,BC_i,ABC_i\) 同理。 那么我们就有 \(A_i=(A-A\bmod {a_i})\bmod A\)，其他同理。 这一 ......

略带一点思维吧。 个人认为比 B 难想。 先来考虑弱化版的题面： Case 1 如果 \(X\) 串和 \(Y\) 串都没有字母 C，如何判断是否有解？ 观察操作，我们能发现这个操作的本质实际上是让一个位于前面的字母 A 挪到其后面的任意的位置，并且前后两个 A 的相对位置不会发生改变。 所以，如果 ......

Arcs on a Circle 首先，一个非常自然的想法是尝试断环成链。怎么断呢？我们发现，选择最长线段的起点处截断是个非常好的选择，因为不可能有一个线段完全覆盖它。这之后，一个紧接着的想法就是 DP。 假如把描述中的全部“实点”改成“整点”的话，那么这题是比较 trivial 的，可以通过随便状 ......

[ARC072E] Alice in linear land 首先，一个 trivial 的想法是记 \(f_i\) 表示第 \(i\) 步前离终点的距离，于是 \(f_i=\min\Big(f_{j-1},|f_{j-1}-d_i|\Big)\)。 然后，我们设 \(f_i'\) 表示在修改第 \ ......

[ARC127F] ±AB 给定整数 \(a,b,v,m\)，保证 \(a\perp b\). 初始有一个数 \(x=v\)，可以不断令其加上或减去 \(a\) 或 \(b\). 过程中必须有 \(x\in[0,m]\)，问 \(x\) 有多少种可能的取值。 多测。\(T\le 10^5\)，\(1 ......