sorting 1839d ball cf
CF449D Jzzhu and Numbers
CF449D Jzzhu and Numbers 黄金定律:给定序列求答案,但答案与序列顺序无关的题目,要么考虑把序列转权值序列,要么对序列排序。 二进制题按大小排序看起来就没啥用,那就转成权值序列。即,设 $c(i)$ 表示 $i$ 在 $a$ 中的出现次数。同时设 $V$ 为 $a$ 的值域。 ......
CF 1360E-Polygon,1300,思维题
CF 1360E-Polygon 如果一个 1 不是在最右边或最下边,则一定有一个 1 在他的紧邻着的下边或右边,否则不合法。 太妙了。 #include <iostream> using namespace std; const int N = 1e2 + 10; int T, n; char a ......
cf-div2866-D
题目链接:https://codeforces.com/contest/1820/problem/D 比赛的时候读错题了,没看见他切一刀之后会把其中一个放进盒子里(也就是不能再切了)。 思路:首先原来的大矩形的其中一边肯定在盒子里的小矩形的其中一边里(也就是说答案最多只有两种),我们先找出最大的长和 ......
CF做题小记
资历太浅,没法给出什么高质量的内容( 本博客所记录的题目最低难度是 Div.2 的 C 题。 1.CF1768C. Elemental Decompress 显然,按照最大值从小到大排序之后会轻松很多。基本思路是这样,首先优先将第一个排列的值赋为最大值,然后选取第二个排列中能够使用的最小值。如果第一 ......
CF题解
D. Guess the Permutation 2000 逆序性质 二分 https://codeforces.com/contest/1589/problem/D 题解:首先我们可以二分查找i的位置:当1->x逆序对>0,则在i右,否则在左,log(n)次询问。找到i的位置后,我们发现逆序对有如 ......
CF 1526B I Hate 1111, 1400
I Hate 1111, 1400 数论题应该要有一个重要思想:打表。这题我可以打表发现 1099 之后的数是连续出现的。 赛瓦韦斯特定理:a, b 为大于 1 的正整数, gcd(a, b) = 1, ax + by = c, 最大使得方 程无正整数解的数为 c = ab - a- b。 ......
CF 476B Dreamoon and WiFi
Dreamoon and WiFi 一个简答的组合数学题。开始想弄一个很妙的做法,但是我理解不了,或者说理解困难,半天没搞出来,然后试着还是用朴素好想的做法做吧,结果马上做出来了。 选择朴素的做法时还是有个地方想不清楚,分类讨论 + 举例一下子清楚了。 ......
CF1646E Power Board 题解
题目链接:https://codeforces.com/contest/1646/problem/E 题目大意: 有一个 $n \times m$ 的矩阵,其中第 $i$ 行第 $j$ 列的格子中的数字是 $i^j$。 问:矩阵中存在多少个不同的数? 解题思路: 可以很明显地发现,第 $1$ 行的数 ......
CF1728D
博弈论dp模板题 首先我们可以先确定dp状态 dp[round][L][R][0/1]表示第round轮,现在字符串为[L~R],上一轮的人取了左边还是右边 然后发现round是可以由字符串L~R确定而来的,因为每一轮只删除一个数,因此可以优化round这维 我们令dp[L][R][0/1]=1为 ......
Uva--679 Dropping Balls(二叉树的编号)
记录 23:28 2023-4-16 https://onlinejudge.org/external/6/679.pdf reference:《算法竞赛入门经典第二版》例题6-6 二叉树,这里是完全二叉树,使用模拟的方式应该会TLE(虽然我用模拟的方式也TLE了,但不是这个原因,下面会提到原因) ......
【JS】- 排序浅记(sort)
字母或数字,默认排序顺序为按字母升序 和 array.reverse() 配合可以实现倒序 array.sort() 在对象数据中,使用函数进行规则配置 var array = [{ num: 4 }, { num: 2 }, { num: 3 }]; // 从小到大 array.sort((a, ......
CF R866 div.2
A 当一个"_ "的右边没有“^”时,答案增加,发现这对于中间的序列是充分必要的。 当位置 $1$ 为 "_"时,我们必须在其前面加一个"^";当整个字符串为 "^"时,特判一下答案。 B 发现给定01串当全是“1”时,我们直接输出 $nn$。考虑一般的情况,我们发现将面积表示出来 $S=a+b,a ......
CF题解
D. AB Graph 2000 构造 https://codeforces.com/problemset/problem/1481/D 题解:由于只有两种边,我们可以枚举较小结构的特性并循环来构造整体解。对于任意两个点,[u->v,v->u]只有4种情况,对于[1,1],[0,0]直接得解,可以循 ......
CF1816F Xor Counting - dp - 分治 -
题目链接:https://codeforces.com/contest/1816/problem/F 题解: 一道有趣的题。 首先发现 $m=1$ 和 $m\geq 3$ 时结论是平凡的。$m=1$ 时结论显然,下面讨论一下 $m\geq 3$ 时: 首先可以构造 $[x, (n-x)/2, (n- ......
CF1815C
1 解法 设 $f_i$ 为 $i$ 最多出现多少次,那么一个限制 $(u,v)$ 可以写成 $f_u \leq f_v +1$,把 $f$ 看做最短路中的 $dis$ 数组,上面的式子就是在图上连一条从 $u$ 到 $v$ 边权是 $1$ 的边,由于边权都是 $1$,所以可以直接用 $\text{ ......
题解 CF1090D【Similar Arrays】
一道简单构造题。 如果 $m=\frac{n(n-1)}{2}$,此时任意两个数都要有偏序关系,但是又要求第二个数列有两个数相等,因此无解。 否则一定有解。不难想到构造两个数列使它们几乎完全相等。可以找到两个没有偏序关系的下标 $(i,j)$,在第一个数列中分别赋值为 $n-1,n$,在第二个数列中 ......
训练记录-cf-di2-866(A-C)
手速场 但是wa了两发 血亏 上蓝了 纪念一下( 不过我还是菜鸡 什么都不会orz A. Yura's New Name 题意:要形成^^或者^_^的笑脸 最少加多少个^ 思路:特判单个^输出1 单个_输出2 首是_ +1 尾是_ +1 其次计算连续的__ ans加上cnt-1个 #include< ......
「解题报告」CF1129D Isolation
水题,但是调了好久 qwq 显然是 DP,出现次数显然分块,那就数据结构优化 DP 呗。 我们可以维护出当前点到每个点这段区间内有多少个出现次数为 $1$ 的数,这个右端点每拓展一位修改的左端点一定是连续的区间。分块维护这个东西,如果是散块暴力重构暴力加,如果是整块那给整块打个加标记。 发现,加标记 ......
Ian and Array Sorting
题目链接 题目描述: To thank Ian, Mary gifted an array $a$ of length $n$ to Ian. To make himself look smart, he wants to make the array in non-decreasing order ......
CF1592F2 题解
题意 传送门 给定一个 $n$ 行 $m$ 列的目标矩阵,矩阵元素只有 W 或 B ,并且你有一个初始矩阵,元素全为 W 。 现在你可以矩阵实施以下操作: 使用一块钱,选定一个包含 $(1,1)$ 的子矩阵,把矩阵中的元素全部反转( W 变 B , B 变 W )。 使用三块钱,选定一个包含 $(n ......
「解题报告」CF983E NN country
水点简单数据结构题! 考虑从两个点开始往上跳,每次肯定尽可能跳到最浅的点。两个点跳到再跳一步就能到达 lca 的位置的时候,此时再看看有没有路径连接这两个点,如果有那么一步就可以跳到,否则就要跳到 lca 再跳一步,两步跳到。跳的过程显然可以用倍增处理。 然后我们考虑处理出每个点能跳到的最浅的点。假 ......
题解 CF1764G Doremy's Perfect DS Class (Extra)
题解 CF1764G Doremy's Perfect DS Class (Extra) 题意 交互库有一个 $1\sim n$ 的排列 $p$,你每次可以想交互库给定三个整数 $l,r,k(1\le l\le r\le n,1\le k\le n)$,交互库会返回 $\lfloor p_l/k\r ......
「解题报告」CF1528F AmShZ Farm
$$
\begin{matrix}
\text{Countin' is what to do}\\
\text{Countin's when I think of you}\\
\text{Countin's what clears my soul}\\
\text{Countin's what ... ......
CF1163F Indecisive Taxi Fee
删边最短路 这篇题解的特点 其实其他的题解都有几处证明跳跃的点。比如,怎么证明删边最短路只强制经过一条边就足够,而不需要强制经过两条,三条边呢?这个结论的证明并不如想象中简单,而且我想读者阅读完其它题解后也很难意识到这个结论只在 无向正权图 上成立,只要负权 / 零权 / 有向,这个结论就立刻失效了 ......
「解题报告」CF960G Bandit Blues
无脑的 APJ 用最无脑的方法解题!!!~~做了两天图论脑子爆炸后的 apj 寻求精神慰藉~~ 首先考虑 $n$ 一定是从前往后的最大值与从后往前的最大值,这样我们只需要求出长度为 $n$,有 $k$ 个前缀最大值的排列数量,记作 $f_{n, k}$。 考虑每次将当前排列中的最大值与最大值后面的排 ......
CF1473D 题解
题目传送门 题目分析 线段树、前缀和、$\text{ST}$ 表题解都有了,我补一发猫树题解吧。 由于每次操作只能将大小改变成跟原来差 $1$,所以只需要知道这段操作中的最大值和最小值,最后所求的答案的范围就被卡住了。对于每一次操作,我们把操作序列拦腰斩断,那么分别求两边的范围,最后减去重复的部分即 ......
CF1758D 题解
前言 题目传送门! 更好的阅读体验? 用一种非常麻烦的做法把自己写自闭了,和题解区不一样,但是方法困难很多。 思路 代码 属于混乱邪恶了,凑合着看看。 #include <iostream> #include <cstdio> #include <cmath> using namespace std ......
Lecture#10 Sorting & Aggregation Algorithms
接下来将学习使用我们现在学习的 DBMS 组件来执行查询。 我们今天要讨论的算法都是基于 Disk 的,即查询的中间结果也需要存储到磁盘中。我们需要使用 Buffer Pool 去实现这些算法,要最大化磁盘连续 I/O。 Query Plan:算子组织成树形结构,数据从叶子节点流向根节点,根节点的输 ......
CF R864 div2
A 发现最劣的方案就是把其中一个围起来,答案为 $4$,当 $x=1/x=n/y=1/y=m$ 时答案有可能为 $2/3$ 分类讨论即可 B 要将原图形变为中心对称,若$(x,y)!=(n-x+1,n-y+1)$我们必须操作,若步数有剩,剩余步数是偶数时对一个方块一直操作即可;剩余步数为奇数时,我们 ......
CF698F Coprime Permutation 题解
题意 给定一个未填满的数组 $p$,求有多少种 $1\sim n$ 的排列 $p$ 满足对于任意 $i<j$,都有 $[\gcd(i, j)=1]=[\gcd(p_i, p_j)=1]$,答案对 $10^9+7$ 取模。 题解 部分参考这篇题解(感觉这篇题解应该是目前为止最详细的吧)。 记 $P$ ......