Q779’s Blog

CF1416B Make Them Equal 题解 题目链接：Make Them Equal 题意： 给出一个序列 \(a\)，求出一个长度不超过 \(3n\) 的操作序列，使序列 \(a\) 中每个元素相等。 定义一次操作为：选出 \((i,j,x)\) 三元组，满足 \(i,j\) 为序列合法下标，\(x\) 为 \(10^9\) 以内非负整数，令 \(a_i\gets a_i-x\cdot i,a_j\gets a_j+x\cdot i\)。 必须保证操作过程中的任意时刻序列 \(a\) 中每个元素都非负。 输出时先输出操作次数 \(k\)，然后输出 \(k\) 行操作序列。 数据组数 \(t\le10^4\)，序列长度 \(\sum n\le10^4\)，元素大小 \(1\le a_i\le10^5\)。 感觉这种题目很喜欢找到一种，就像游戏机制一样的性质，使劲钻空子。 首先如果 \(n \not\mid \sum a_i\) 一定无解，因为最终每个数一定会变成平均数。 注意到 \(i=1\) 的自由度最高，如果所有的多余的值都放在 \(i=1\) 上那么这道题就非...

note[15] 题：数论函数 \(F(x)\) ，在 \(1\) 到 \(n\) 里随机选 \(k\) 个数，可以重复选/不可以重复选，\(F\) 值之和的期望？ 解： 不可以重复选： \[ \begin{aligned} \mathbb{E}(X) & =\mathbb{E}\left(\sum_{i=1}^k F\left(c_i\right)\right) \\ & =\sum_{i=1}^k \mathbb{E}\left(F\left(c_i\right)\right) \\ & =k \sum_{i=1}^n \frac{1}{n} \cdot F(i) \\ & =\frac{k}{n} \sum_{i=1}^n F(i) \end{aligned} \] 可以重复选： \[ \begin{aligned} \mathbb{E}(X) & =\mathbb{E}\left(\sum_{i=1}^n c_i \cdot F(i)\right) \\ & =\sum_{i=1}^k \mathbb{E}\left(c_...

洛谷P2388 阶乘之乘 题解 题目链接：P2388 阶乘之乘 题意： 求出 \(1!\times 2!\times 3!\times 4!\times \cdots \times n!\) 的末尾有几个零。 输入格式： 一行，一个整数 \(n(n\le 10^8)\)。 输出格式： 输出答案，表示零的个数。 很经典的一道题，先说一下 \(\mathcal{O}(n)\) 的小学生解法： 注意到 \(n!\) 中 \(5\) 的个数显然小于 \(2^i\) 的个数，于是我们只需要统计每个阶乘里有多少个 \(5\)​ 即可 scanf("%lld",&n); for(int i=1; i<=n; i++) { int tmp=i; while(tmp%5==0)sum++,tmp/=5; ans+=sum; } printf("%lld\n",ans); // 本代码写于 2021-03-08 下面说一下更快的解法。考虑把刚才的结论写成式子。 令 \(f(n)=\sum_{i=1}^{\infty}\left\lflo...

CF1385F Removing Leaves 题解 题目链接：Removing Leaves 题意： 给定一棵树（无环的连通图），由 \(n\) 个顶点组成。这棵树是无根树——它只是一个没有环的连通无向图。 在一次移动中，你可以选择恰好 \(k\) 个叶子（叶子是指连接到仅一个其他顶点的顶点）与同一个顶点相连，并移除它们及与它们相连的边。也就是说，你选择这样的叶子 \(u_1, u_2, \dots, u_k\)，使得存在边 \((u_1, v)\)，\((u_2, v)\)，\(\dots\)，\((u_k, v)\)，然后移除这些叶子及这些边。 你的任务是找出如果你以最优方式移除叶子，你可以执行的最大移动次数。 你需要回答 \(t\)​ 个独立的测试用例。 省流： 给定一棵树，定义一次操作为”删除拥有同样父亲的 \(k\) 个叶节点”。请问最多能够进行多少次操作。 输入格式： 输入的第一行包含一个整数 \(t\) (\(1 \le t \le 2 \cdot 10^4\)) — 测试用例的数量。然后是 \(t\) 个测试用例。 每个测试用例的第一行包含两个整数 \(n\)...

CF1385D a-Good String 题解 题目链接：a-Good String 题意： 定义：字符串s 为一个c-好串（c 为一个字符）时，必须满足： 当\(|s| = 1\) ，\(s = c\) 当\(|s| > 1\), \(s\) 的左半部分为全为 \(c\)，右半部分为一个 (c+1)-好串 或者 \(s\) 的右半部分为全为 \(c\)，左半部分为一个 (c+1)-好串 其中 \(|s|\) 代表 字符串 \(s\) 的长度。 举个例子：当 \(s=\) cdbbaaaa 时，\(s\) 是一个 a-好串 现在，给你一个字符串 \(s\) \((|s| = 2^k)\) 问最少替换多少个字符，使其为一个 a-好串。 额，不知道这题要讲什么，就是一道简单的分治题，只要按照题目意思就好了。 时间复杂度 \(\mathcal{O}(n \log n)\) ，计算详见主定理（本题唯一难点？） 代码： #include <bits/stdc++.h> using namespace std; #define int long long #define...

CF1313D Happy New Year 题解 题目链接：Happy New Year 题意： 做圣诞老人是一件很难的事。有时你不得不面对困难的情况。 今天圣诞老人在度假的时候，有 \(m\) 个孩子排在他面前。我们把他们从 \(1\) 到 \(m\) 编上号。圣诞老人知道 \(n\) 个咒语。每个咒语给编号从 \(L_i\) 到 \(R_i\) 的每个孩子一颗糖果。 题目保证如果将全部的咒语都用一次，每个孩子至多收到 \(k\) 颗糖果。 如果一个孩子得到的糖果量是偶数（可能为零），那么他（或她）会很伤心。不过，其他孩子（收到奇数个糖果的孩子）会很高兴。 请问圣诞老人最多能使多少个孩子快乐。 输入格式： The first line contains three integers of \(n\) , \(m\) , and \(k\) ( \(1 \leq n \leq 100\,000, 1 \leq m \leq 10^9, 1 \leq k \leq 8\) ) — the number of spells, the number of children and ...

CF1304C Air Conditioner 题解 题目链接：Air Conditioner 题意： 一个餐馆中有个空调，每分钟可以选择上调 \(1\) 个单位的温度或下调 \(1\) 个单位的温度，当然你也可以选择不变，初始的温度为 \(m\) 。 有 \(n\) 个食客，每个食客会在 \(t_i\) 时间点到达，他所能适应的最低温度是 \(l_i\) ，最高温度是 \(r_i\) ，他只会在 \(t_i\) 时刻逗留。 如果温度不在食客的适应范围内，他就会不舒服，请你判断，空调能否使得 \(n\) 位来就餐的食客都感到舒服。 本题多组数据，数据组数不大于 \(500\)。 \(1\le n\le 100\)，\(-10^9\le m,l_i,r_i\le 10^9\)，\(1\le t_i\le 10^9\)​ 。 鉴于 \(l_i,r_i\) 的范围，我们不可能（也不需要）求出具体的调节方案。 设 \([l,r]\) 表示当前能达到的区间，初始 \(l = r= m\) 。 每经过 \(t\) 分钟，当前能到达的区间就变成了 \([l - t, r + t]\) 。 ...

CF1408F Two Different 题解 题目链接：Two Different 题意： 你被给定一个整数 \(n\)。 你应该找到满足以下条件的一组配对列表 \((x_1, y_1)\)，\((x_2, y_2)\)，…，\((x_q, y_q)\) （\(1 \leq x_i, y_i \leq n\)）。 让我们考虑某个函数 \(f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) （我们定义 \(\mathbb{N}\) 为正整数集）。换句话说，\(f\) 是一个为一对正整数返回正整数的函数。 让我们创建一个数组 \(a_1, a_2, \ldots, a_n\)，其中 \(a_i = i\) 初始值。 你将执行 \(q\) 次操作，第 \(i\) 次操作中你将： 赋值 \(t = f(a_{x_i}, a_{y_i})\) （\(t\) 是一个临时变量，仅用于接下来的两个赋值）; 赋值 \(a_{x_i} = t\); 赋值 \(a_{y_i} = t\)。 换句话说，你需要同时将 \(a_{x_i}\) 和 \(...

CF1338D Nested Rubber Bands 题解 题目链接：Nested Rubber Bands 题意： 给定一棵 \(n\) 个点的树，第 \(i\) 条边连接 \(u_i\) 和 \(v_i\)。 你需要将每一个节点画成一个二维平面上闭合几何图形，当且仅当 \(u\) 和 \(v\) 之间有边相连，这两个点对应的几何图形边界相交（注意包含不算边界相交）。 我们定义一个序列 \(a_1,a_2,\ldots,a_k\) 是好的，当且仅当对于任意的 \(2\le i\le k\)，\(a_{i-1}\) 所对应的几何图形完全包含 \(a_i\) 所对应的几何图形。 求好的序列最长可以是多少。 上图的答案是 \(4\) ，一种构造如下图所示 输入格式： The first line contains integer \(n\) \((3 \le n \le 10^{5})\) — the number of vertices in tree. The \(i\) -th of the next \(n-1\) lines contains two integer...

CF1404C Fixed Point Removal 题解 题目链接：CF1404C Fixed Point Removal 题意： 令 \(a_1, \ldots, a_n\) 为一个包含 \(n\) 个正整数的数组。 在一次操作中，你可以选择一个位置 \(i\) 使得 \(a_i = i\)，并从数组中移除 \(a_i\)（移除后，剩余部分被拼接起来）。 \(a\) 的权重定义为你能移除的最大元素数量。 你必须回答 \(q\) 个独立的查询 \((x, y)\)：在将 \(a\) 的前 \(x\) 个元素和最后 \(y\) 个元素替换为 \(n+1\)（使它们无法被移除）后，\(a\) 的权重是多少？ 输入格式： 第一行包含两个整数 \(n\) 和 \(q\) \((1 \le n, q \le 3 \cdot 10^5)\)——数组的长度和查询的数量。 第二行包含 \(n\) 个整数 \(a_1\), \(a_2\), …, \(a_n\) \((1 \leq a_i \leq n)\)——数组的元素。 接下来的 \(q\) 行中的第 \(i\) 行包含两个整数 \(x...

CF1438D Powerful Ksenia 题解 题目链接：Powerful Ksenia 题意： Ksenia拥有一个由 \(n\) 个正整数组成的数组 \(a\)，分别为 \(a_1, a_2, \ldots, a_n\)。 在一次操作中，她可以执行以下操作： 选择三个不同的索引 \(i,j,k\)，然后 同时将 \(a_i, a_j, a_k\) 全部更改为 \(a_i \oplus a_j \oplus a_k\) ，其中 \(\oplus\) 表示按位异或操作。 她希望在最多 \(n\) 次操作中使所有 \(a_i\) 相等，或者确定这样做是不可能的。她不会主动请求您的帮助，但请帮助她！ 输入格式： 第一行包含一个整数 \(n\) \((3 \leq n \leq 10^5)\)——数组 \(a\) 的长度。 第二行包含 \(n\) 个整数，\(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^9)\) ——数组 \(a\) 的元素。 输出格式： 根据是否可以在最多 \(n\) 次操作中使所有元素相等，在第一行打印YE...

CF1401E Divide Square 题解 题目链接：CF1401E Divide Square 题意： 给定一个 \(10^6\times10^6\) 的正方形，\(n\) 条横线和 \(m\) 条竖线穿过了它，求这些线把正方形分成了多少个部分。 保证不存在两条线段在同一条线上，并且每个线段至少与正方形的一条边相交。 输入格式： 第一行包含两个整数 \(n\) 和 \(m\) ( \(0 \leq n, m \leq 10^5\) ) —— 水平线段和垂直线段的数量。 接下来的 \(n\) 行包含水平线段的描述。第 \(i\) 行包含三个整数 \(y_i\)、\(lx_i\) 和 \(rx_i\) \((0 < y_i < 10^6,~0 \leq lx_i < rx_i \leq 10^6)\)，表示该线段连接 \((lx_i, y_i)\) 和 \((rx_i, y_i)\)。 接下来的 \(m\) 行包含垂直线段的描述。第 \(i\) 行包含三个整数 \(x_i\)、\(ly_i\) 和 \(ry_i\) \((0 < x_i < 1...