numbers lonely 1423k cf
CF870F
感觉完全没有 *2700? 看到题,猜测 \(\max dis\) 不会很大,于是按照路径种类分类讨论一下路径 \((i,j)\)。下设 \(f_i\) 为最小质因数,并且更下面的情况不包括上面的情况。 \(\gcd(i,j)>1\) 这种显然 \(dis=1\),数量则为 \(\sum\limit ......
CF1866K
李超线段树二次离线。 容易发现,将和某个点 \(x\) 相邻的边权翻若干倍后,直径所在位置有两种可能:经过或不经过该点。不经过可以跑一次直接求,否则还要分类讨论一下。 \(\operatorname{deg}_x=1\) 那么它会作为直径的一个端点。 否则 直径会从一条边进,另一条边出。 前者是简单 ......
CF119D
还是一道很综合的 string 练手题。 先来分析一下,将 \(B\) 按照答案分成三段,三段与 \(A\) 都有什么关系。 第一段:\(A\) 的一个子串。 第二段:\(A\) 的一段后缀翻转。 第三段:\(A\) 的一段前缀翻转。 我们大概率是要枚举其中一个的,其中第三段都能用 \(A,B\) ......
CF1217F
强制在线是诈骗,还是很有意思的。 首先,如果没有强制在线就是一个 SGT 分治板子。强制在线看起来做不了,但是发现 \(lastans=0/1\)。这启示我们不同的加边可能性不会太多。考虑先记录两种加边可能。 容易发现,如果当前时刻 \(j\) 可能操作 \((u,v)\),上一次可能的时刻是 \( ......
CF119D
还是一道很综合的 string 练手题。 先来分析一下,将 \(B\) 按照答案分成三段,三段与 \(A\) 都有什么关系。 第一段:\(A\) 的一个子串。 第二段:\(A\) 的一段后缀翻转。 第三段:\(A\) 的一段前缀翻转。 我们大概率是要枚举其中一个的,其中第三段都能用 \(A,B\) ......
CF1178H
cdqz 两道题都很有意思啊!顺便是第一篇 *3500 题解。 先考虑第一问。 显然有单调性,所以可以二分。cdqz 这是二分专题吗 Lemma 1:所有操作都在 \(0\) 和 \(t\) 时刻进行。 Proof:这是若干个一次函数,最大或最小值都会在端点处取得。所以是显然的。 接下来你就要使你在 ......
CF1055F Tree and XOR
这道题代码虽然比较短,但花了我整整一天才过,太菜了 这是 CF241B 的加强版,但是有点不同,因为 CF241B 后半部分求前 \(k\) 大的和没法优化了,而这道题能把前面的求第 \(k\) 小时间复杂度优化到单 log ,但是需要注意这道题开 trie 完全开不下,所以肯定没法 trie 上二 ......
CF1883G2 Dances (Hard Version)
Problem - D2 - Codeforces Dances (Hard Version) - 洛谷 Hint1: 对于 \(C[i]\) 的答案上界和下界分别是多少? Hint1.1: 记 \(C[i]_1\) 时的答案 \(ans\),答案范围显然是 \([ans,ans+1]\) Hint ......
CF1889C2 Doremy's Drying Plan (Hard Version)
Problem - C2 - Codeforces Doremy's Drying Plan (Hard Version) - 洛谷 很好的一道 \(dp\) 题,无论是 \(dp\) 状态还是优化都很思维 我们设 \(dp_{i,j}\) 表示考虑了前 \(i\) 个城市,第 \(i\) 个城市干 ......
CF1761E Make It Connected记录
题目链接:https://codeforces.com/contest/1761/problem/E 题意简述 以邻接矩阵的形式给你一张无向图。你可以执行如下操作: 选定节点 \(u\)。对所有其它节点 \(v\),翻转 \(u\) 与 \(v\) 的连边状态。 给出一种花费操作最少的方案,使图连通 ......
CF1726G A Certain Magical Party
CF1726G A Certain Magical Party 聚会上有 \(n\) 个人,第 \(i\) 个人有一个开心指数 \(a_i\) 。 每个人都有一种确定的个性,这种个性可以用一个二进制整数 \(b\) 来表示。如果 \(b=0\) ,那么意味着如果他将一个故事讲给一个开心指数比他低的人 ......
CF241B Friends
异或粽子的加强版,时间复杂度是 \(O(n log^2 w)\) ,其中 \(w\) 是值域 \(2^{30}\) ,原来的是和 \(k\) 有关的,相当于是 CF241B 的代码通过不了异或粽子,异或粽子的代码通过不了 CF241B(雾 先考虑一个整体的思路,求前 \(k\) 大,先需要求第 \( ......
CF1881F Minimum Maximum Distance 题解
因为白点对 \(f_i\) 没有贡献,所以可以重构出一棵原树的子树,使得所有的叶子都为标记点且标记点数量不变(没有删去标记点)。因为没有标记被删去且结构不变,所以这棵树的答案与原树答案相同。 现在,对于所有节点,到它距离最大的标记点一定在叶子上。那么问题就变为:求出树上任意一点到所有叶子节点的最大距 ......
Codeforces Round 651 (Div. 2)C. Number Game(数学思维数论)
C. Number Game 我们考虑那些状态是必胜态 我的回合时n为奇数(除1外),直接除以n则必胜 下面偶数的情况稍复杂 偶数我们能进行的操作只有除以一个奇数,需要考虑怎么把当前状态变为对手的必败态 偶数一定含2的因子,\(n=2^k*q,q为奇数\) 当\(k=1时如果q\)是一个质数那么只能 ......
『LeetCode』2. 两数相加 Add Two Numbers
『1』迭代法 class Solution { // Iteration // N is the size of l1, M is the size of l2 // Time Complexity: O(max(M, N)) // Space Complexity: O(max(M, N)) if ......
CF1912H Hypercatapult Commute记录
题目链接:https://codeforces.com/problemset/problem/1912/H 题意 有 \(n\) 个城市,\(m\) 个人。第 \(i\) 人想从城市 \(a_i\) 移动到 \(b_i\)。每个城市每天可以使用至多一次传送胶囊,可以将任意数目的人从该城市传送到任意一 ......
[CF17E] Palisection 题解
[CF17E] Palisection 题解 思路 直接统计相交的字符串很难数,考虑正难则反。 用总共的回文串对数减去相离的回文串个数。 设总共有 \(tot\) 个回文串,用 manacher 跑出来每个位置的最大回文半径后,使用差分的技巧保存两个数组: \(f_i\) 表示以 \(i\) 为开头 ......
CF187A 题解
原题传送门 题目大意 如题意翻译。 思路分析 很水的一道题目,可以将第一个排列 \(a\) 看作最终排列,接下来每输入一个数,让它与 \(a_m\) 进行比较,直到两个排列相同。 最后看题目范围,\(1≤n≤2\times10^5\),时间复杂度 \(\mathcal{O(n)}\),空间复杂度 \ ......
CF1912L 题解
原题传送门 题目大意 有一个仅有 0 和 L 构成的序列,求出一种方案,使得左部分的 0 数量不等于右部分的 O 数量,且左部分的 L 数量不等于右部分的 L 数量,若不存在输出 -1。 思路分析 首先看题目范围,\(2≤n≤200\),数据很小,考虑暴力。 可以使用字符串截取函数 s.substr ......
[Codeforces] CF1579C Ticks
CF1579C Ticks 题意 \(n \times m\) 的棋盘,左上角和右下角坐标分别为 \((1, 1), (n, m)\),一开始每个格子为白色。 每次操作可以选择一个格子 \((x, y)\) 以及左上角和右上角方向的 \(d\) 个连续格子染成黑色,并将其称为一个大小为 \(d\) ......
[Codeforces] CF1817A Almost Increasing Subsequence
CF1817A Almost Increasing Subsequence 题意 给定长度为 \(n\) 一个序列 \(a\) 以及 \(q\) 次询问,每次询问给出 \(l\) 和 \(r\),找出序列 \(a\) 在 \([l,r]\) 内最长的几乎递增子序列。 对于几乎递增的定义:如果一个序列 ......
[Codeforces] CF1811E Living Sequence
CF1811E Living Sequence 这道题洛谷题解的思路比我的更好,可以参考一下题解,但是没人提到我这种做法 题意 给定一个正整数 \(k\) \((1\le k\le10^{12})\),请你输出第 \(k\) 个数字里没有 4 的正整数。 思路 设 \(f_i\) 表示前 \(10^ ......
CF1740H MEX Tree Manipulation
CF1740H MEX Tree Manipulation 定义一棵树上每个节点的值为其所有儿子的值的 MEX,叶子节点的值为 \(0\)。 现在有一个初始只有节点 \(1\) 的树,每次输入一个 \(x_i\) 代表加入一个点 \(i+1\),它的父亲为 \(x_i\),求加入这个点之后树上所有点 ......
CF1178G The Awesomest Vertex
CF1178G The Awesomest Vertex 给定一棵根为 \(1\) 的有根树,每个节点有两个权值 \(a[i]\) 和 \(b[i]\) 。定义 \(R(v)\) 为 \(v\) 祖先的集合(包括自己),则一个节点 \(v\) 有多棒取决于其真棒程度,真棒程度是这样定义的: \[\l ......
CF1519F Chests and Keys
CF1519F Chests and Keys 给定 \(n,m\) 表示存在 \(n\) 个宝箱和 \(m\) 把钥匙,第 \(i\) 把钥匙需要 \(b_i\) 元,第 \(i\) 个宝箱内部有 \(a_i\) 元。 现在进行一场游戏,Bob 是本场游戏的玩家,而 Alice 则是场景布置者,A ......
CF1746E2 Joking (Hard Version) 题解
非常厉害的一道交互题。 思路 由于交互库会说谎,我们考虑把两次询问划分成一组。 结论:假如一个集合在两次询问中都为不成立,那么这个集合也就一定不成立。 证明显然,因为这两次中总有一次时真话。 那么我们就可以想到一个比较暴力的想法。 每一次把集合划分为四个,\(S_{0,0},S_{0,1},S_{1 ......
CF1914 D Array Collapse 题解
Link CF1914 D Array Collapse Question 初始给出一个数组 \(\{P\}\) ,数组中每个值都不相同,我们可以选中 \(P\) 数组中连续的一段,然后删除除了最小值以外的所有元素,求删除多次(包括 \(0\) 次)后,剩下的数组的数量 Solution 当时就没怎 ......
[Ynoi2007]rfplca/[CF1491H] Yuezheng Ling and Dynamic Tree
题目描述 给定一棵大小为 \(n\) 的 \(1\) 为根节点的树,树用如下方式给出:输入 \(a_2,a_3,\dots,a_n\),保证 \(1\leq a_i<i\),将 \(a_i\) 与 \(i\) 连边形成一棵树。 接下来有 \(m\) 次操作,操作有两种: 1 l r x 令 \(a_ ......
CF1673C Palindrome Basis の 题解
这道题非常板,如你所见,大概思路是打表回文数加上完全背包求方案数,但是需要注意取余问题。 从英文题面上(题目翻译没有给出数据范围)可以看到 \(1 \leq n \leq 4 \cdot 10 ^ {4}\),所以只要用完全背包来预处理这一范围即可。如果你还是不懂,可以去搜完全背包字样并学习该算法。 ......
Nacos启动:[NACOS HTTP-POST] The maximum number of tolerable server reconnection errors has been reached
一、表象 二、分析 源码: public HttpRestResult<String> httpPost(String path, Map<String, String> headers, Map<String, String> paramValues, String encode, long re ......