rounding maximum 1857b cf

https://codeforces.com/contest/1842 C题很像leetcode上买股票那几题的套路，直接dp就行 \(z=max\{i-j+1+g[j-1] (a[i]=a[j]) \}\),g[j]表示以i结尾的最大值，很显然可以将跟j有关的项分离出来，然后对于每种ai维护最大值 ......

analysis 看到这个类似差分的样子，想着对它进行转化，通过对题目给出的式子进行变形，我们可以得到下面的式子。 \[a_i = b_i \bigoplus b _ {i + 1} \]\[\begin{aligned} b_{i+ 1} &= b_i \bigoplus a_i \\ &= b_ ......

LG9753 CF1223F 我们称一个字符串是可消除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。 You are trying to push array elements to the stac ......

summarization 有一个长为 \(n\) 的排列 \(p\), 现有甲乙两人轮流执行操作，甲是先手： 甲每次可以交换 \(p\) 中相邻的两个数 \(p_i,p_{i+1}\) 乙每次等概率执行下面两种操作的一种： 选择一对 \(p_i,p_{i+1}\)，且 \(p_i\le p_{i+ ......

不妨认为 \(n,q\) 同阶。 考虑根号重构。如果没有第 3 种操作的话，我们每 \(\mathcal O(\sqrt n)\) 操作整体更新一次，每个询问只需要考虑块内的修改所在置换环上有多少 \([l,r]\) 内的数。这个是容易 \(\mathcal O(n\sqrt n)\) 做的。 然后 ......

A 读了 10min 题，做题 7min/cf，傻逼题。 B 没啥思维难度，但是中间电脑死机了/ll，傻逼题。 C 考虑到每次操作会把 \(x\) 转到 \(a_n\) 的位置上，然后记搜即可。 D 考虑每次将 \(k\) 插入一个位置并满足最优只有在 \(a_i\geq k\geq a_{i+1} ......

\(A. Secret Sport\) https://codeforces.com/contest/1894/submission/231748875 \(B. Two Out of Three\) https://codeforces.com/contest/1894/submission/23 ......

CF1436E Complicated Computations 题目描述： 求一个数列的所有子区间的 mex 值的 mex 某个数组的 mex 是这个数组中没有包含的最小正整数。 数据范围： \(1\leq n\leq 10^5,1\leq a_i\leq n\) 思路： 分析一下题目的流程，他先 ......

Paths on the Tree 贪心题，因为对于每一个儿子，经过的路径数之差少于 \(1\)，所以这道题可以理解为先把所有路径均分，然后把剩下的按照权值大小依次分布给那些儿子。 那么儿子传给父亲的权值又是如何处理呢？ 首先，我们需要把父亲首先传递过来的 \(k\) 条路径均分，然后把剩下的最大路 ......

\(D. XOR Construction\) 首先观察 $ b_1 \oplus b_2=a_1, b_2 \oplus b_3=a_2 \ldots $ ，发现 \(b_1 \oplus b_{j+1}=\bigoplus^{j}_{i=1}a_i\) ，那么自然的想到如果第一个数字确定，后面的 ......

貌似没有线段树做法。 记\(s\)为\(a\)的前缀和数组。 对于一个确定的右端点 \(r\) 和左端点 \(l\)，它对于答案的贡献是 \(s_r-s_{l-1}-max\{a_i\},l\le i\le r\) ，如果枚举右端点，令 \(c_l=s_{l-1}+max\{a_i\},l\le i ......

here 首先根据题意，我们不难有数字是连续的这种感悟。 而且限制是值域上的，从下标入手发现难以突破，便从值域上入手。 从小到大考虑每个数字，然后dp，可以参考这篇题解。 至于方案的输出，有两种情况。 只有自己\(i\)和\(i-1\)，直接输出即可。 有自己和\(i-1\)的环，定义print输出 ......

https://codeforces.com/problemset/problem/1446/C 断断续续想了挺久的，还发现看错题了。 首先一个显然的结论是不会成环，证明显然。 突破口在于从高位往低位考虑，我们按照最高一位的值分成两类，一类是这一位为0，另一类为1，那么显然在我们不进行任何操作的时候 ......

太菜了只会四个 A 题意：给定一个长度为 \(n\) 的数组 \(a\) ，你可以将他随便重排，问是否能让它满足 \(a_i + a_{i+1}=a_{i+1}+a_{i+1}=.......=a_{n-1}+a_n\) 。 首先如果 \(a\) 中的元素种类超过 \(2\) 个，那么这个序列是不可 ......

https://codeforces.com/contest/1856/problem/E2 结论是显然的，关键是有一些科技在里面 bitset+二进制优化 具体分析可以参考https://codeforces.com/blog/entry/98663 简而言之就是可以通过\(O(\frac{C\s ......

题目链接 Tree Painting 题面翻译 给定一棵 \(n\) 个点的树 初始全是白点 要求你做 \(n\) 步操作，每一次选定一个与一个黑点相隔一条边的白点，将它染成黑点，然后获得该白点被染色前所在的白色联通块大小的权值。 第一次操作可以任意选点。 求可获得的最大权值 思路 假如说，第一次我 ......

题目传送门 题目大意 给定 \(n\) 个数，每个数的因数个数不超过 \(7\)，求最少选出多少个数能使得乘积为一个完全平方数。 无解输出 \(-1\)。 思路 约数个数定理：对于 \[n=\prod^{k}_{i=1}p_i^{a_i} \]\(n\) 的正约数个数为 \(\prod^{k}\li ......

CF1583G Omkar and Time Travel 想清楚了就不难。 首先我们考察一下性质，一次 time leap 之后只有包含于 \((a_i, b_i)\) 的区间会被重置，考虑这样一件事情：设 \(f_{l,r}\) 表示从 \(l\) 左边走到 \(r\) 右边的 time lea ......

### $\text{Description}:$ 给定一个长为 $s$ 序列 $a$，如果 $a_1 = \min_{i=1}^{r} a_i$。令 $a_{s + 1} = a_1$，有 $\forall i ,\left | a_i-a_{i+1} \right | =1$，我们称这个序列是良 ......

[NSSRound#11 Basic]ez_enc ABAABBBAABABAABBABABAABBABAAAABBABABABAAABAAABBAABBBBABBABBABBABABABAABBAABBABAAABBAABBBABABABAAAABBAAABABAABABBABBBABBAAABB ......

对于浮点数的运算中，两个带小数点的数值进行运算会出现不确定的尾数。 例如 0.1+0.2其结果为： x=0.1y=0.2print(x+y,'x的类型是：',type(x)) #所得的值为0.30000000000000004 #要想使得没有不确定的尾数，使用round函数print(round(x ......

维护序列，支持： 区间异或 查询区间子集异或值种数（包含空集） \(n\le 2\times 10^5\)，\(1\le q\le 4\times 10^4\)，值域 \([1,10^9]\)，TL=7s. 经典题。 操作 2 相当于查询区间线性基大小。 由于不能维护区间异或，作差分 \(b_i=a ......

年轻人的第一个 *3500。抄题解的。 考虑选出一个字段 \([l, r]\) 然后计算可以产生贡献的地方。那么就是 \(\underset{i \in [l, r]} \max pre_i + 1\) 和 \(\underset{i \in [l, r]} \min suf_i - 1\) ，称其 ......

都 3202 年了，我还是永远喜欢正向计数（bushi）。 显然是 CF1336F 弱化版。值得一提的是，在 standing 上有一个老哥，交了一份很神奇的代码，好像拼了 CF1336F 的 std，然后拼了两份，一减就求得答案。 考虑分类计数，目前我们有两条链 \(x \to y\) 和 \(p ......

A 手玩一下就能出来的东西吧，粘个核心代码。 if(x > y) ww(x), wl; else if(x + k >= y) ww(y), wl; else ww(y * 2 - x - k), wl; B 观察性质，一定是将数组排序后，从 \(1 \sim n\) 为横坐标，从 \(n + 1 ......

analysis 观察性质，一定是将数组排序后，从 \(1 \sim n\) 为横坐标，从 \(n + 1 \sim n * 2\) 为纵坐标。所得距离应为横坐标之差的和和纵坐标之差的和。 核心代码。（手玩一下也能出来。） read(n); sum = 0; fos(i, 1, n * 2) rea ......

cf797e 还是暴力，将不同的询问根据k分开，然后bfs，建出一棵树，然后dfs。 时间复杂度：O（能过） 稍微口胡分析一下 大概是 \(min(1,q[1])*n/1 +min(2.q[2])*n/2+min(3,q[3])*n/3+.....\) qi表示第k=i的询问个数 因为每一种k它最多 ......

cf1582F2 对于每种数可以维护一个列表v[x]，表示到当前位置，最后一个数小于等于x，能够取到的值，对于当前的数ai，我们可以用v[ai]中的值x与ai异或，来更新v[ai+1],v[ai+2]后面的值。 然后就是有两个优化，每次我们更新完后，都对v[a[i]]清空，因为只有两个相同数之间的数 ......

这题怎么才 \(\color{red}*2600\) 啊，我觉得有 $\color{maroon} *3000+ $，太菜了 /ll。 来一个官方题解做法，复杂度稍劣还要离线，被爆了 /ll。题解区大佬说哈希狗都不写。 洛谷 CF 给出一棵 \(n\) 个点的树，边上有字母。\(q\) 次询问，每次 ......

或许赛时根本不需要证明贪心的正确性。 我们发现 \(c\) 对于问题的影响不大，我们可以将每个 \(a_i\) 除以 \(c\)，就转化为了 \(c=1\) 的情况。 一个自然的贪心是用 \(1\) 作为中心点去连接其他的所有点，这需要两条结论保证其正确性： 结论一： 如果当前图中还可以连边，点 \ ......