cf

题面 给一个 \(n\) 个点的图，每个点 \(i\) 有点权 \(a_i\)，初始图上没有边，你可以进行如下操作若干次： 若 \(S_i+S_j\ge i\times j\times c\)，添加一条边 \((i, j)\)。其中 \(S_i\) 表示 \(i\) 所在连通块的点权和，\(c\) ......

给定一棵以 \(1\) 为根的有根树，支持以下两种操作共 \(q\) 次： 加入一个点； 子树内点权加。 \(q \le 5 \times 10^5\)。 最傻逼的一集，怎么会有这么简单的 d2f。 不难发现每个点存在的时间区间构成时间轴上的一段后缀，于是我们可以将所有操作离线下来，先把完整的树建出 ......

CF1891F A Growing Tree 更好的阅读体验 有点诈骗。好多人都写的 LCT，但是这题其实连树剖都不需要。提供一个简单的单 \(\log\) 小常数做法。 动态加点是假的，可以离线下来得到最后树的结构，记一下 dfn 序。 一个操作对一个点有可能贡献当且仅当操作在加点之后进行。 所以 ......

CF551E 卧槽,lzh最爱的分块!卧槽,lzh最爱的分块!卧槽,lzh最爱的分块!卧槽,lzh最爱的分块! 维护懒标,散块重构。 unordered_map<long long,int> 会 TLE unordered_map<long long,bool> 会 AC #include<cstd ......

Restoring Map 星空蚁来了秒了。 人与人的智力是有差距的。 刷再多的CF智力不行就是不行。 OI这种需要智力的游戏不适合我。 我还是更适合对智力要求低一点的。 比如和妹子贴贴。 但是也没有妹子。 life is hard. 这类树的构造似乎可以从边缘情况想起,比如 CF1844G 但是这 ......

题目描述 Archaeologists found some information about an ancient land of Treeland. We know for sure that the Treeland consisted of $ n $ cities connected b ......

Two Rooted Trees 题面翻译 题目描述 你有两棵有根树，每棵树都有 \(n\) 个结点。不妨将这两棵树上的点都用 \(1\) 到 \(n\) 之间的整数编号。每棵树的根结点都是 \(1\)。第一棵树上的边都是蓝色，第二课树上的边都是红色。我们也称第一棵树是蓝色的，第二棵树是红色的。 对 ......

题意 给定\(n\)个栈，栈的大小分别为\(k_i\)，每个栈内元素\(\in[1,n]\)，记从第\(i\)个栈开始的答案为\(ans_i\)，流程：若栈\(i\)为空，答案为\(i\)；否则弹出栈顶元素\(x\)，并前往栈\(x\)，继续刚才的操作。 \(n\le 10^5,\sum k_i\l ......

传送门 description 见洛谷翻译 solution 考虑分析一下不等式 \(x_i+x_j\leq 1\)。 如果 \(x_i,x_j\leq 0.5\)，一定成立； 如果 \(x_i,x_j>0.5\)，一定不成立； 如果 \(x_i,x_j\) 中一个 \(>0.5\)，一个 \(\l ......

CF1490G Old Floppy Drive 首先判断是否可以在第一圈就符合题意，记录前缀和 \(sum\) 和 \(mx\) 数组，其中 \(mx_{i}\) 为 \(sum\) 从起点到 i 的最大值，即 \(mx_{i}=\max(mx_{i-1},sum_{i})\)。 显然如果在第一圈 ......

D. Queue f[i]表示第i个F需要多少时间才能让所有的M都移到她后面，那么我们考虑转移，分为两种情况。 第i个F和第i-1个F挨着，那么显然f[i]=f[i-1]+1 假如中间隔着一些M， 可以分为两种情况，假如i可以在i-1完成之前追上它，那么就是f[i-1]+1，否则就说明 i一直在进行 ......

D. Pawn 感觉这种dp套路似乎非常常见，我们可以设 f[i][j][x]表示走到(i,j)，当前的值为f[i][j][x]*k+x ,也就是我们将余数x作为放在状态中。 #include<cstdio> #include<algorithm> #include<cstring> #includ ......

传送门 description 给定正整数 \(n,m\) 和集合 \(S\)，满足 \(S\) 中元素互不相同且都是小于等于 \(m\) 的正整数。每次进行如下操作 从集合 \(S\) 中随机选取一个数记作 \(x\) 从 \(S\) 中删去 \(x\) 如果 \(x+1\leq m\) 且 \( ......

啊啊啊每次补完题都感觉这题我场上应该是能想出来的啊！ 考虑简化问题：若每个栈内只有一个元素，how。 此时我们发现所有栈之间构成了一个内向基环树。且环是没有用的，因为我们在环上走一圈之后仍然会回到原点。所以不妨把所有环边删除，此时每棵树的答案即为树根。 而对于原问题，同理，我们可以考虑不断找环，每找 ......

容易想到 dp：设 \(dp_{i,p}\) 表示前 \(i\) 天，强制第 \(i\) 天 dry，并且一共消除了 \(p\) 个区间的答案。 转移时可以考虑枚举前面的决策 \(j\)，此时有转移方程： \[dp_{i,p}=\max(dp_{j,p-w})+1 \]其中 \(w\) 为满足 \( ......

不妨考虑什么时候会无解！ 显然当原序列 \(0,1\) 数量不同，或者序列总长为奇数时会无解！ 否则我们设 \(l=1,r=n\)！开始回文配对！ 如果配上了就直接删掉！并把左右端点向内移动！ 如果两者都是 \(0\)，就在末尾加上 \(01\)！都是 \(1\) 就加最前面！ 以在末尾加入举例！此 ......

一开始不会先跳 C 了！差点满盘皆输！ 设 \(i<j\)，则 \(i,j\) 合并可以看作 \(a_i\leftarrow a_i+a_j\) 后删掉 \(j\)！此时和初始局面本质相同！所以不妨先只看初始局面！ 不等式右侧和下标有关！显然若右侧 \(i,j\) 中只要有一个是 \(1\)，就会让 ......

[CF1601F]Two Sorts link:https://codeforces.com/problemset/problem/1601/F Description 有一个数列 \(\{a_1, a_2, \ldots, a_n\}\) 是一个 \(1 \sim n\) 的排列，且所有的数都按照 ......

CF1592F1 Alice and Recoloring 1 CF1592F2 Alice and Recoloring 2 Part1 很容易发现，其实二和三操作是没有用的. 对于二操作，可以用一操作进行类似于求二维前缀和的方式实现，需要进行一操作至多 \(2\) 次，花费为 \(1+1=2\) ......

题目 给出一个 \(n*m\) 的矩阵，每次交换两个等大的矩阵，输出 \(q\) 次操作后的矩阵 分析 维护向右和向下的指针，考虑最后输出只需要从每行的头指针向右跳， 那么修改实际上是将矩阵左边一列、上面一行、最后一行和最后一列向右下指针交换 时间复杂度 \(O((n+m)Q)\) 代码 #incl ......

CF283E 答案即为 \(\binom{n}{3}\) 减去不合法环数。 一个三元环中最多1个点出度为2,所以出度为 x 的点会造成 \(\binom{x}{2}\) 个不合法的环。 \(\Omicron(nm)\) 的做法就是枚举 i,判断 i 与 n 个点连边是否反向(0,1表示)。 然后可以 ......

Problem - 1890D - Codeforces 这个式子左边是加法，右边是乘法，很不好算 但其实是降智题，不过同时也是我不擅长的找性质 因为式子左边是加法而不是乘法，因此像类似于并查集那样求出当前每个联通块内 \(\sum a_i\) 等价于固定一个点从这个点的联通块向外扩展。 \(i\) ......

\(\text{「CF715E」Complete the Permutations}\) \(\text{Link}\) \(\text{Describe}\) 给定长为 \(n\) 的且部分确定的置换 \(p,q\)。定义 \(p,q\) 距离为通过交换 \(p\) 任意两项变为 \(q\) 的最 ......

洛谷题面 CF1810G 分析 考虑最大前缀和满足两个条件，就是所有前缀和都不超过，以及一定有一个等于。 那么就要保证它能达到最大值且一直不能高于它 设 \(dp[i][j][0/1]\) 表示前 \(i\) 个数离达到最大值还需要 \(j\) 且未/已经达到过最大值。 初始化就是 \(dp[0][ ......

A Distance 直接枚举C点x坐标暴力判断 #include<bits/stdc++.h> using namespace std; int xa,ya,xb,yb; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.t ......

来一点更清楚的、实现方面的东西。 做法同 这篇，他的实现很优美但略微繁琐了些。 枚举 \(T\) 的形态，发现这个匹配不过是把每个 \(T\) 中当前点的儿子塞进一个 \(S\) 中当前点的儿子内。于是 \(f_{u, v}\) 表示 \(S\) 中 \(u\) 匹配 \(T\) 中 \(v\) 且 ......

分析 看到这个题就想到了二维偏序。 你们很自然地，以 \(b\) 为第一关键字降序排序，当有若干个片 \(b\) 相等时，我们发现由于 \(a < b\)，所以排到最后的片一定能把这些 \(b\) 相等的片都统计上，而前面的片能否统计是依赖于 \(b\)，所以考虑如何让后面的片更好统计，显然 \(a ......

CF512D 聪明的想法。 首先对于同一个 i 必定保留最大的赋值操作,并且顺序为赋值-加-乘。 并且我们最终答案是所有元素的乘,那么乘操作对答案作贡献很好写就是乘的值。 那么我们想办法把余下两种操作用乘操作表示。 把大于 \(va_i\) 的赋值操作变成加操作,因为乘之前对于某个 i 一定加的越多 ......

考虑出现次数都是 \(k\) 的倍数存在必要条件：区间总和为 \(k\) 的倍数。 如果给每个正整数 \(i\) 都赋随机数 \(a_i\) 并对每次查询求区间和，错误的概率大概为 \(\frac{1}{k}\)。 跑 \(30\sim 40\) 次即可，时间复杂度为 \(O(Tn\log n)\) ......

看错题看成只能交换相邻节点颜色了/fn 每次操作交换两个节点颜色，可以转化为统计最终合法颜色序列相比开始，最少有多少个红点变成黑点。 可以考虑一个类似树形 dp 的过程，对于每个节点我们钦定下它会被哪个节点“笼罩”，同时由于黑点数量有限，我们还需要记录下子树内已经用了多少个黑点。 设“笼罩”节点 \ ......