Q779’s Blog

洛谷P4967 黑暗打击 题解 题目链接：P4967 黑暗打击 题意： 有一群生物 ccj，他们在上次的星系中，发现了一群低等生物，于是想进行一波黑暗森林打击。这群低等生物即是 \(\mathsf{Hilbert}\) 鼹鼠，生活在 \(\mathsf{Hilbert}\) 星球，住在 \(\mathsf{Hilbert}\) 曲线土壤内。 这群生物决定用最傻的办法——灌水，来淹死他们。现在“高等”生物想知道，对于 \(n\) 阶的 \(\mathsf{Hilbert}\)​ 曲线，从上往下灌水，能淹没几个单位面积？ 这是 \(1 \sim 4\) 阶的 \(\mathsf{Hilbert}\) 曲线： \(h_1\)，如最左图所示，是一个缺上口的正方形，这个正方形的边长为 \(1\)。 从\(h_2\) 开始，按照以下方法构造曲线 \(h_i\)： 将 \(h_{i-1}\) 复制四份，按 \(2\times2\) 摆放。 把左上一份逆时针转 \(90^{\circ }\)，右上一份顺时针转 \(90^{\circ }\)，然后用三条单位线段将四分曲线按照左上-左下-右下-...

CF1322B Present 题解 题目链接：CF1322B Present 题意： 给出一个长度为 \(n\) 的数列 \(a\)。其中第 \(i\) 项为 \(a_i\)。 请你求出 \(\bigoplus_{i=1}^{n}\bigoplus_{j=i+1}^{n}(a_i+a_j)\)。其中 \(\oplus\) 表示按位异或操作。 \(2 \leq n \leq 4 \times 10^5\)，\(1 \leq a_i \leq 10^7\)。 输入格式： The first line contains a single integer \(n\) — the number of integers in the array. The second line contains integers \(a_1, a_2, \ldots, a_n\) . 输出格式： Print a single integer — xor of all pairwise sums of integers in the given array. 注意到 \(a_i \le 10^7\) ，...

CF1582F2 Korney Korneevich and XOR (hard version) 题解 题目链接：Korney Korneevich and XOR (hard version) 题意： 给一个长度为 \(n\) 的序列 \(a_1,a_2,\dots,a_n\) ，寻找在 \(a\) 的所有递增子序列（可以为空）的异或和中出现的数。 输入格式： 第一行一个正整数 \(n\) 表示序列长度。 第二行 \(n\) 个整数表示序列 \(a\) 。 输出格式： 从小到大输出在 \(a\) 的所有子序列（可以为空）的异或和中出现的数。 数据范围： \(1\le n\le10^6,0\le a_i\le5000\)​​ 。 注意到值域 \(V \le 5000\) ，这个范围可以 \(\mathcal{O}(V^2)\) 。 考虑设 \(f_{j,k}\) 表示是否存在结尾小于 \(j\) 且异或和为 \(k\)​​ 的子序列。 设当前枚举的数为 \(a_i(a_i < j \le V)\) ，转移方程为 \[ f_{j, k\oplus a_i} = \lef...

CF1355F Guess Divisors Count 题解 题目链接：Guess Divisors Count 题意： 要求猜一个 \(1\) 到 \(10^9\) 之间的一个数 \(X\)。 你可以询问一个数 \(Q\)（\(1\le Q\le10^{18}\)），然后得到 \(\gcd(X,Q)\)。 请你在不多于 \(22\) 次询问后算出 \(X\) 的因数个数。 注意：设你的答案为 \(d\)，标准答案为 \(r\)，只要满足 \(|r-d|\le7\) 或 \(\frac12\le\frac{r}{d}\le2\) 即算正确。 输入格式： 首先输入一个正整数，数据组数 \(t(1\le t \le 100)\)。 接下来 \(t\) 组数据。 交互格式： 询问：? Q； 回答：! d。（注意每次输出后要刷新缓冲区）。 本题特色：乱搞？ 感觉很多这种类型的题就和快慢刀一样，主打一个迷惑人，其实本质没有那么难。 首先，根据唯一分解定理可知若 \(X = \prod_{i=1}^n p_i^{x_i}\) ，则因数个数为 \(\prod_{i=1}^n\left...

CF1406D Three Sequences 题解 题目链接：Three Sequences 题意： 给定一个序列\(a_1,a_2,\ldots ,a_n\)，长度为 \(n\) 的序列 \(b,c\) 符合以下条件 \(a_i=b_i+c_i\) \(b\) 为不下降序列，\(c\) 为不上升序列，即 \(b_i\geq b_{i-1}, c_i\leq c_{i-1}\) 有 \(q\) 个操作，每次操作可以把 \([l,r]\) 的数增加 \(x\)。求每次操作后最小的 \(\max(b_i,c_i)\) 。 输入格式： 第一行包含一个整数 \(n\)（\(1\leq n\leq 10^5\)）。 第二行包含 \(n\) 个整数 \(a_1,a_2,\ldots,a_n\)（\(1\leq i\leq n\)，\(-10^9\leq a_i\leq 10^9\)）。 第三行包含一个整数 \(q\)（\(1\leq q\leq 10^5\)）。 接下来的每行（共 \(q\) 行）包含三个整数 \(l,r,x\)（\(1\leq l\leq r\leq n, -10^...

CF1572B Xor of 3 题解 题目链接：Xor of 3 题意： 给出一个 \(01\) 序列，一次操作可以选择连续的三个数，把它们都变成它们的异或和。 问能否在 \(n\) 次以内把所有数变成 \(0\)​，输出方案（操作 \(i\) 则修改 \(a_i,~a_{i+1},~a_{i+2}\) ） 输入格式： 多组数据，每组数据给出 \(n\) 和 \(n\) 个数。 输出格式： 有解输出一行 YES ，否则输出 NO 。 如果有解，输出一行表示步骤数（可以不是最少次数），接着一行若干个数表示操作位置 数据范围： \(3 \le \sum n \le 2\times10^5\) 感觉这道题在哪里听过思路了，今天找到原题了。思路还是比较有意思的。（upd.其实是 CF1438D） 因为题目要全部变成 \(0\) ，所以与异或和性质就显得十分关键。 容易发现，每次操作后所有数的异或和不会改变，因此异或和为 \(0\) 是有解的一个必要条件（但是不充分） 首先考虑 \(n\) 为奇数的情况，如果我们在 \(n-2,~n-4,~\cdots,~1\)​ 分别操作一次 此时...

SP277 CTGAME - City Game 题解 题目链接：CTGAME - City Game 题意： 鲍伯是一个战略游戏编程专家。在他的新城市建设游戏中，游戏环境如下：城市是由街道、树木、工厂和建筑物组成的区域。这个地区还没有空余的空间。他的游戏的战略任务是从这些自由空间中赢得尽可能多的租金。要赢得租金，你必须竖立建筑物，它只能是长方形的，尽可能长和宽。鲍伯正试图找到一种方法来建造每一个地区最大的建筑。但是他遇到了一些问题——他不被允许破坏他正在建设的地区已经存在的建筑物、树木、工厂和街道。 每个区域都有其宽度和长度。该地区被划分为等格子单位，你所建单位的租金为 3 美元。 你的任务是帮助鲍伯解决这个问题。整个城市分为K区。每个区域都是矩形的，并且具有不同的网格大小，其长度M和宽度N不同。现有的占用单元用符号R标记。未占用单元用符号F标记。 输入格式： The first line of the input contains an integer K - determining the number of datasets. Next lines contain th...

2024年03月16日 随笔 二月是因为过年的原因没怎么写题。 关于最近做题量变少，其实是因为最近一直在思考一些比较重要的东西 不是在偷懒哦。 很快就会恢复正常更新的。 另外也许会找机会写点什么的。 谁会看这篇随笔啊。

SP6950 CTOI10D3 - A HUGE TOWER 题解 题目链接：CTOI10D3 - A HUGE TOWER 题意： 题目描述 有 \(N(2\le N\le620000)\) 块砖，要搭一个 \(N\) 层的塔，要求： 如果砖 \(A\) 在砖 \(B\) 上面，那么 \(A\) 不能比 \(B\) 的长度 \(+D\) 要长。 问有几种方法，输出 答案模 \(10^9+9\) 的值。 输入格式： 第一行： \(N,D\) 。 第二行： \(N\) 个数，表示每块砖的长度。 输出格式： 方案数。 思路挺有趣的题目。我们会发现，以 \(i\) 为结尾的一些方案可能会从后面得到贡献。 并且我们实际上并不知道也不关心某种方案的结尾是什么构成的，这意味着我们无法从结尾上考虑 因此不妨考虑每个 \(i\) 会在什么时候插入答案序列。 首先先把所有的 \(a_i\) 从小到大排序，然后依次考虑每个 \(i\) 。 容易发现，如果存在一个已经插入的砖块满足 \(a_i \le a_j+d\) ，则 \(i\) 可以插到 \(j\) 的前面 因为我们已经做了排序，记 \(j...

洛谷P4169 [Violet] 天使玩偶/SJY摆棋子 题解 题目链接：P4169 [Violet] 天使玩偶/SJY摆棋子 题意： Ayu 在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了地下。而七年后 的今天，Ayu 却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。 我们把 Ayu 生活的小镇看作一个二维平面坐标系，而 Ayu 会不定时地记起可能在某个点 \((x, y)\) 埋下了天使玩偶；或者 Ayu 会询问你，假如她在 \((x,y)\)，那么她离近的天使玩偶可能埋下的地方有多远。 因为 Ayu 只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为 \(\operatorname{dist}(A,B)=|A_x-B_x|+|A_y-B_y|\)。其中 \(A_x\) 表示点 \(A\) 的横坐标，其余类似。 输入格式： 第一行包含两个整数 \(n\) 和 \(m\)，在刚开始时，Ayu 已经知道有 \(n\) 个点可能埋着天使玩偶， 接下来 Ayu 要进行 \(m\) 次操作。 接下来 \(n\) 行，每行两个非负...

洛谷P4514 上帝造题的七分钟 题解 题目链接：P4514 上帝造题的七分钟 题意： 裸体（裸题）就意味着身体（神题）。 “第一分钟，X 说，要有矩阵，于是便有了一个里面写满了 \(0\) 的 \(n\times m\) 矩阵。 第二分钟，L 说，要能修改，于是便有了将左上角为 \((a,b)\)，右下角为 \((c,d)\) 的一个矩形区域内的全部数字加上一个值的操作。 第三分钟，k 说，要能查询，于是便有了求给定矩形区域内的全部数字和的操作。 第四分钟，彩虹喵说，要基于二叉树的数据结构，于是便有了数据范围。 第五分钟，和雪说，要有耐心，于是便有了时间限制。 第六分钟，吃钢琴男说，要省点事，于是便有了保证运算过程中及最终结果均不超过 \(32\) 位有符号整数类型的表示范围的限制。 第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。” ——《上帝造裸题的七分钟》。 所以这个神圣的任务就交给你了。 输入格式： 输入数据的第一行为 X n m，代表矩阵大小为 \(n\times m\)。 从输入数据的第二行开始到文件尾的每一行会出现以下两种操作： L a...

CF198E Gripping Story 题解 题目链接：CF198E Gripping Story 题意： Qwerty 的船在位置 \((x, y)\)，船上有一个机械臂，其力量为 \(p\)，长度为 \(r\)，即可以拿到质量不超过 \(p\)，距离不超过 \(r\) 的物品。 有 \(n\) 个机械臂散落在平面内，第 \(i\) 个机械臂在位置 \((x_i, y_i)\)，其质量、力量和长度分别为 $m_i,p_i,r_i $。 Qwerty 不能移动他的船，但他拿到某个机械臂后可以将其安装到船上使用，问他最多能获得多少机械臂。 输入格式： 第一行 \(x,y,p,r,n\) ，接下来 \(n\) 行 \(x_i,y_i,m_i,p_i,r_i\) 输出格式： 一行，即答案。 数据范围： \(1\le n \le 2.5\times 10^5,~-10^9 \le x,y,x_i,y_i \le10^9,~1\le p,r,m_i,p_i,r_i\le 10^9\) 如果机械臂 \(i\) 能够帮助拿到 \(j\) ，那么认为 \(i\) 到 \(j\) 有一条有...