Description 如果一个正整数可以被表示为 \(n\) 的若干个不同的非负整数次幂的和，则称这个正整数是特别的。求出第 kk 小的特别的数 Solution 我们拿 \(n=2\) 举例， 序列为 \(2^0,2^1,2^1+2^0,2^2,2^2+2^0,2^2+2^1,2^2+2^1+2^0,2^3\dots\) 我们设二进制位的每一位 \(i\) 表示 \(n^i\) 这一位选不选。 将上述序列表示一下， \(1,10,11,100,101,110,111,1000,\dots\) 将这个二进制序列转化为十进制， \...

Description 给你一个整数 \(n\)，你需要找出两个整数 \(l,r\) 使得 \(l+(l+1)+\dots(r-1)+r=n\)。 Solution 第一眼等差数列，但是 \(-10^{18}\le n \le 10^{18}\) 完全无法枚举完 \(l\),\(r\),所以我们另辟蹊径。 假设 \(n=6\) 当 \(l=1,r=6\) 时，可以写成 \(1+2+3+4+5+6\) 但是我们只想要加和为 \(6\)，怎么办？ \(1+(-1)+2+(-2)+3+(-3)+4+(-4)+5+(-5)+6\) 整理一...

2021.08.27 膜你赛 seq Description 小杜给了小 \(q\) 一个数列，数列长度为 \(n\)，数列元素分别为 $a_1 ,a_2 ,...,a_n $。 小杜跟小 \(q\) 说，数列的元素不能随意改动，但是小杜允许小 \(q\) 对数列做如下操作：选择一个数字 \(i(1<=i<=n)\)，然后将 \(a_i\) 替换成 \(a_i'\) 其中 \(a_i'= a_i \oplus (2^k -1)\)，\(\oplus\) 为异或操作。并且这样的操作次数可以为 \(0\) 到任意多次。 小 \(q\) 不 喜 欢 数 字 \(0\)...

2021.10.06 T1 Description 众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。 小葱同学最近醉心于动态规划的研究，他苦学百年，已经牢牢掌握了最长上升子序列的知识。小葱对于这种单调不减的序列非常着迷，于是他灵机一动，挥笔写下了一个数 \(𝑥\)，现在小葱同学希望找到一个小于等于 \(𝑥\) 的最大的数，使得这个数的各个数位是单调不减的。求这个数。 Solution 手模几组样例发现答案就是第一个下降位置的前一位减 1 ，然后将其后面的位置都赋为 9. Code /* * @Author: smyslenny * @Da...

2021.10.05膜你赛 T1 Description 众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。 小葱同学最近醉心于动态规划的研究，他苦学百年，已经牢牢掌握了加法和减法是怎么运算的。所以小葱同学造了 \(𝑁\) 个数 \(𝑎_1, 𝑎_2, ⋯ , 𝑎_𝑁\)，他希望对每个数加上或者减去 \(𝐾\)，使得操作之后的最大值减去最小值的差最小。 Solution 考试的时候想出了正解，结果脑子一歪，错失20分。 假设我们给出的序列为 \(\text{1368}，k=3\) 先预处理出 \(+k,-k\) 后的答案。 也就是 ...

2021.08.28 膜你赛 lock Description LYK 想把你的智商锁起来，它出了道神题。 它有一壶水，这壶水的水量在[L,R]中，你只知道 L 和 R 是多少，但你并不知道具体的值是多少。 它有两个容量为无穷大的杯子。它想尽可能把壶里的水均匀的分在两个杯子中。它觉得 这个任务可能太难了，因此它只要求最终两个杯子的水的容量至多相差 1。并且它也不要求 把壶里的水全部倒完，只要求最终剩在壶里的水不超过 1。 LYK 在倒水过程中，不知道这壶水还有多少水，但能知道是否倒完了。 一个最笨的方法是左边倒 1 滴，右边的倒 1 滴，左边再倒 1 滴，这样依次下去，...

2021.09.13膜你赛 T1 Description 小迟生活的城市是一棵树（树指的是一个含有 \(n\) 个节点以及 \(n-1\) 条边的无向连通图），节点编号从 \(1\) 到 \(n\)，每条边拥有一个权值 \(value\)，表示通过这条边的时候你需要交纳的金钱（注意，有可能这个值为负数，也就是说你经过这条边的时候你可以赚钱） 小迟是一个杰出的马路工，他居住在节点 \(s\)，他能够选择任意一个节点 \(m\)，并将从节点 \(s\) 到节点 \(m\) 的简单路径（简单路径指的是不经过同一个节点两次）上的所有边的权值都修改为 \(0\). 现在小迟获得 \(...

2021.09.18 膜你赛 据说是老吕从三区偷的题。 zero Description 给出一个长度为 \(n\) 的操作序列。每个位置为 \(\&\),\(|\),^中的一个。\(\&\) 表示按位与，\(|\) 表示按位或，^ 表示按位异或。 定义一个长度为 \(n+1\) 的 \(01\) 数列(即该数列只包含 \(0\) 和 \(1\))是合法的，当且仅当将该操作序列插入这个长度为 \(n+1\) 的数列后，运算结果为 \(1\)。 具体的讲，如果给出的操作序列为 &|^,将其插入到序列 \(1010\) 中进行运算:\(1\&0...

2021.09.15膜你赛 T1 Description 正的魔法师利用的都是万物众生自然之力。 魔法师正在绘制用于大魔法的魔法聚灵阵，此聚灵阵一共有n个魔力源点，魔力源点与魔力源点之间由一条魔力链相连，每条魔力链上都有一定数量的魔力石，每两个魔力源点之间有且只有一条路径——没错，就是一棵魔法树！ 魔法阵中的两两不同节点会相互呼应，来达到魔力增幅的效果，任意两个点的共振魔力定义为这两个点的路径上每条魔力链上的魔力石的最大值，魔法阵的总增幅效果为魔法阵中所有点对的共振魔力的和。 Solution 最暴力的做法就是用树剖维护最大值，\(n^2\) 枚举点对。但是只有 5...

2021.09.14 膜你赛 T1 Description 给定一个 \(1 \sim n\) 的排列 \(a_i\) 给出 \(q\) 个询问 \((x,m)\) 他想知道： \[\underbrace{a[a[a[…a[x]…]]]}_{m 个 a} \] 的值是多少 Solution 考试的时候写的 \(n^2\) 的做法。 对于每一个点能跳到的下一个点，我们连一条边，最后序列上一定是一个个环的形式， 暴力找到循环节，输出答案，就是输入有些毒瘤。 Code /* * @Author: smyslenny * @Date: 2021...

扫描线学习笔记 前言 之前翻阅网络上的讲解，可能是我太菜了，反正看了几次都没学会，也没敲过，于是这次就认真地学习了一下，发现并不是很难。 引入 给你 \(n\) 个矩形，求这 \(n\) 个矩形的面积并。保证所有的矩形 \(n\leq 10^5,x,y\leq 10^9\) 面积并：平面上所有图形的覆盖面积。 对于这样一道问题，我们如何去求解呢？ 熟悉扫描线的同学可能一眼就看出来这就是一道扫描线的板子题，如果我们不去想用扫描线去求，我们怎么做呢？ 最暴力的办法就是开个二维数组进行染色，最后扫一遍统计答案。但是我们发现，仅仅 \(x,y\) 就有 \(10^9\)...

2021.08.23 膜你赛 count Description 问有几个无序二元组 \((x, y)\) 满足 \(x y ≡ 1 \pmod p\), \(0 ≤ x < P, 0 ≤ y <P\)。 无序二元组是指，如果 \(P = 10\)，\((3, 7)\) 和 \((7, 3)\) 只算一次。 Solution 首先根据 \(xy \equiv 1\pmod p\) 可以得 \(x \equiv \frac{1}{y} \pmod p\) ,\(\frac{1}{y}\) 就是 \(x\) 在 \(\mod p\) 意义下的逆元。一个数有逆元当...

CF213C Description： 输入一个 \(n\times n\) 的矩形，每个 \(a_{i,j}\) 是这个位置的价值。现在要从左上角走到右下角再返回，每个价值只被计算一次，求最大价值和。 Solution: 对于一去一回，直接这么想的话太麻烦了，可以想象成两条去的路径，因为取值都是一样的。 相当于是这么两条路径。 很显然，可以写个四维 dp，设 \(f_{x_1,y_1,x_2,y_2}\) 表示第一个人在 \((x_1,y_1)\) ，第二个人在 \((x_2,y_2)\) 时可以取到的最大值。但是 \(1\leq n\leq...

CF351B Description 两个人 A，B，一个长为 \(n\) 的序列，A 每次选两个相邻元素交换，B 有相等的概率把任意满足 \(p_i<p_{i+1}\) 的 \(p_i\) 和 \(p_{i+1}\) 或 \(p_{i}>p_{i+1}\) 的 \(p_{i}\) 和 \(p_{i+1}\) 交换。 求将序列变成升序的最小值期望步数。 Solution 每一次 A 肯定是交换一个逆序对，而 B 每次有 \(50\%\) 的概率减少一个逆序对，有 \(50\%\) 增加一个逆序对，设 \(f_i\) 表示 \(i\)...