Q779’s Blog

[ARC060E] Tak and Hotels 题解 题目链接：[ARC060E] Tak and Hotels 题意： 一条笔直的公路上有 \(N\) 个旅店，第 \(i\) 个旅店的坐标是 \(x_i\) 高桥君旅行时有如下习惯： 他一天最多行走长度不大于 \(L\) 的路程 他一定会选择一家旅店作为自己一天行程的终点 现在他有 \(Q\) 组行程计划，对于每一组计划，他会从 旅店a 旅行到 旅店b \((a \neq b)\) 。你现在需要帮助他，求出每一组计划所需的最小天数 数据范围： \(2 \leq N \leq 10^5, 1 \leq L \leq 10^9, 1 \leq Q \leq 10^5\) \(1 \leq x_1<x_2<\cdots<x_N \leq 10^9,~x_{i+1}-x_i \leq L\) 题解标签写的倍增，结果进来是板子题。。 考虑倍增。设 \(f(i,j)\) 表示从第 \(i\) 个点出发，走 \(2^j\) 步能到达的最远的节点，转移如下： \[ f(i, j)=f(f(i, j-1), j-1) ...

[ABC044D] Digit Sum 题解 题目链接：[ABC044D] Digit Sum 题意： 对于任意非负整数 \(x\) 和 \(m(2\le m)\) ，定义 \(f_m(x)\) 为 \(x\) 在 \(m\) 进制下的各位数字之和。 例如\(f_{10}(87654)=8+7+6+5+4=30,~f_{100}(87654)=8+76+54=138\) 。给定两个整数 \(x\) 和 \(n\) 。 你需要计算是否存在某个 \(m\ge 2\) 使得 \(f_m(x)=n\) 。 如果存在，输出最小的满足条件的 \(m\) ；如果不存在，输出 \(−1\) 。 数据范围： \(1 \le x,n \le 10^{11}\) 设 \(x\) 化为 \(m\) 进制后为 \(\overline{x_1x_2\dots x_t}\) 不难发现当 \(t \ge 3\) 时， \(m\le \sqrt{x}-\epsilon,\epsilon \in \mathbb{N}\) 例如当 \(t=3\) 时，设 \(x\) 化为 \(m\) 进制后为 \(\overli...

[ABC044C] Tak and Cards 题解 题目链接：[ABC044C] Tak and Cards 题意： 高桥君有 \(N\) 张不同的卡片，还有一个整数 \(A\) ，第 \(i\) 张卡片上写着整数 \(x_i\)。 现在要从中选出若干张卡片，使得它们上面写的数的平均值为 \(A\)。求合法的选择方案数。 卡片相同而顺序不同的，视作同一种方案。 保证输入的数均是不大于 \(50\) 的正整数。 设 \(f(i,j,k)\) 表示前 \(i\) 个数选了 \(j\) 个且和为 \(k\) 时的方案数，则 \[ f(i,j,k) = f(i - 1, j, k) + f(i - 1, j - 1, k - x_i) \] 每次转移都从 \(i-1\) 到 \(i\) ，且 \(j,k\) 倒序枚举不会转移错误，因此考虑滚动数组。 然后我们只需要枚举所有合法的 \((j,k)\) ，加上他们的答案就好啦~ 时间复杂度 \(\mathcal{O}(n^4)\) 代码： #include <bits/stdc++.h> using namespace std; ...

[ARC059F] Unhappy Hacking 题解 题目链接：[ARC059F] Unhappy Hacking 题意： Sig已经自己组装了一台键盘。为了达到极致的简单性，这个键盘上只有三个按键：0 键、1 键和退格键。 一开始，他在使用这个键盘的纯文本编辑器。该编辑器始终显示一个字符串（可能为空）。在编辑器启动后，此字符串为空。当按下键盘上的每个键时，字符串发生以下更改： 0 键：在字符串的右侧插入一个数字 0。 1 键：在字符串的右侧插入一个数字 1。 退格键：如果字符串为空，则不发生任何变化。否则，删除字符串的最右边的字母。 Sig启动了编辑器，并总共按下了这些键\(N\)次。结果，编辑器显示一个字符串\(s\)。找出按下这些键的方式的数量，对\(10^9+7\)取模。 \(1 \le N \le 5\times 10^3,1\le |s| \le N\) ，且 \(s\) 仅由 0 和 1 构成。 “人不能两次踏进同一条河流。” 每次按下按键的那个人都不是上一次按下按键的那个人（大雾） 设 \(f_{i,j}\) 表示按第 \(i\) 次按键后匹配了 \(...

[ARC059E] Children and Candies 题解 题目链接：[ARC059E] Children and Candies 题意： 给出 \(N,C,A_i,B_i\) ，求 \[ \sum_{x_1=A_1}^{B_1} \sum_{x_2=A_2}^{B_2} \ldots \sum_{x_N=A_N}^{B_N} f\left(x_1, x_2, \ldots, x_N\right) \] 其中 \(f\) 定义为 \(\prod x_1^{a_1}x_2^{a_2}\cdots x_N^{a_N}\) ，其中 \(\sum_{i}a_i=C\) 。 \(1 \le N,C \le 400,~1 \le A_i \le B_i\le 400(1\le i\le N)\) 容易发现 \(n\) 自增一次对答案的影响可以通过 \(n\) 的答案得到（这行是废话） 考虑设 \(f_{i,j}\) 表示前 \(i\) 个人，发了 \(j\) 个糖果（就是那个 \(\sum_i a_i\)）的答案，则 \[ f_{i,j} = \sum_{k = 0}^{j}f_...

[ARC059D] Unbalanced 题解 题目链接：[ARC059D] Unbalanced 题意： 给出长度为 \(n\) 的字符串 \(s\) 求区间 \([l, r]\) ，其中 \(l < r\) ，使得该子串中有一种字母出现的次数严格大于该子串长度的一半 输入格式： 一行，字符串 \(s\) 输出格式： 如果有解，输出 \(l,r\) 。如果没有符合条件的子串，输出两个 \(-1\) 数据范围： \(1\le n \le 10^5\) 。 容易发现形如 awa 和 aa 的串串都合法，并且所有合法的串的子串中至少有其中一种 那么我们只需要找到这样子的串然后直接输出就好啦！ 所以这题到底是 D 还是 B 啊（好像这场从 C 开始排序的） 时间复杂度 \(\mathcal{O}(n)\) 代码：（太短了我都不知道怎么写比较好看了） #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int &...

洛谷P8967 追寻 | Pursuit of Dream 题解 题目链接：P8967 追寻 | Pursuit of Dream 题意： 在 \(n\) 维空间中有一个梦想。这梦想坐落在 \((d_1, d_2, \ldots, d_n)\) 的地方。而你从 \((0, 0, \ldots, 0)\) 开始，开启寻梦的旅程。 你的步伐轻缓，每一步只能走一个单位长度。你并不知道你的梦想位于哪里，所以你只能随机选择 \(n\) 个正方向中的一个，然后向这个方向走一步。也就是说，在 \([1, n]\) 中均匀随机选择一个正整数 \(h\)，然后，使你在第 \(h\) 维的坐标变成原来的坐标加一。 然而，天有不测风云。在你走每一步的过程中，你会有 \(p = \sum_{i = 1}^k p_i\) 的概率散入天际，并开始一段新的旅程。你会在 \(k\) 个地点中的一个重新开始这段旅程，其中第 \(i\) 个地点的坐标是 \((a_{i,1}, a_{i,2}, \ldots, a_{i,n})\)，从这里重新开始的概率为 \(p_i\)。 那么，期望下，你离到达这个梦想还需要多少...

洛谷P8941 [SSOI 2023 easy Round] D. Goodbye 2022 题解 题目链接：P8941 [SSOI 2023 easy Round] D. Goodbye 2022 题意： 给定 \(n,k,p\)，求有多少有序 \(p\) 元组 \((a_1,a_2,\cdots,a_p)\) 满足 \(\forall i \in [1,p]\)，\(a_i\in [1,n]\)。 \(\forall i\in [1,p)\)，\(\operatorname{popcount}(a_i\oplus a_{i+1})=k\)。 \(\forall i,j\in[1,p],i\neq j\)，\(a_i\neq a_j\)。 答案对 \(998244353\) 取模。 其中 \(\operatorname{popcount}(x)\) 表示 \(x\) 在二进制表达下 \(1\) 的个数。 \(\oplus\) 表示按位异或操作。 两个有序 \(p\) 元组 \((a_1,a_2,\dots,a_p)\)，\((b_1,b_2,\dots,b_p)\) 不...

洛谷P9066 [yLOI2023] 腐草为萤 题解 题目链接：P9066 [yLOI2023] 腐草为萤 题意： 夜幕降临，在树林中的一条平直的小径上，萤火虫们受到夜晚的呼唤，纷纷外出行动。 将小径视作数轴，一开始，共计 \(n\) 只萤火虫在数轴的一些整点上，从左到右依次标号为 \(1 \sim n\)，第 \(i\) 只萤火虫的初始坐标为 \(x_i\)。每个萤火虫有不同的亮度值，\(i\) 号萤火虫的亮度为 \(a_i\)。 在任意时刻，对任意存活的萤火虫 \(i\)，它会按如下规则飞行： 在当前仍存活的萤火虫中，找到与 \(i\) 相邻的萤火虫（可能是一只或两只）中亮度最大的一只，记其编号为 \(j\)。如果 \(a_i < a_j\)，则 \(i\) 会朝着 \(j\) 飞行，否则 \(i\) 留在原地。 这里两只萤火虫『相邻』的定义是：若两只萤火虫之间不存在任何仍存活的萤火虫，则它们相邻。 萤火虫飞行的速度均为每秒一个单位长度。 萤火虫生命短暂，当两只萤火虫相遇之时（即两个萤火虫的坐标相同时），亮度值较低的萤火虫将耗尽生命，在小径上消失。显然，最后只会剩...

洛谷P8940 [SSOI 2023 easy Round] C. 不见故人 题解 题目链接：P8940 [SSOI 2023 easy Round] C. 不见故人 题意： 给定 \(n, k\) 和序列 \(\{a_n\}\)，你同时有一个临时变量 \(x\)，你可以进行以下操作若干次（也可以是 \(0\) 次），一次操作的流程是： 1. 选定一个区间 \([l,r]\)，\(\forall i\in[l,r]\)，\(x\leftarrow \gcd(a_l,a_{l+1},\cdots,a_r)\)。 2. \(\forall i\in[l,r]\)，\(a_i\leftarrow x\)。 简而言之，你每次可以选定一个区间并将其中每个数变成这个区间的 \(\gcd\)。 一次操作的代价是 \(r-l+1+k\)，现在你希望把这个序列的每个数都变成相等的，求最小代价和。 输入格式： 第一行两个非负整数 \(n,k\)。 第二行 \(n\) 个数，表示 \(\{a_n\}\)。 输出格式： 一行一个数，表示答案。 数据范围： 对于所有数据，保证 \(1\leq n\leq...

洛谷P9869 [NOIP2023] 三值逻辑 题解 题目链接：P9869 [NOIP2023] 三值逻辑 题意： 小 L 今天学习了 Kleene 三值逻辑。 在三值逻辑中，一个变量的值可能为：真（\(\mathtt{True}\)，简写作 \(\mathtt{T}\)）、假（\(\mathtt{False}\)，简写作 \(\mathtt{F}\)）或未确定（\(\mathtt{Unknown}\)，简写作 \(\mathtt{U}\)）。 在三值逻辑上也可以定义逻辑运算。由于小 L 学习进度很慢，只掌握了逻辑非运算 \(\lnot\)，其运算法则为： \[ \lnot \mathtt{T} = \mathtt{F}, \lnot \mathtt{F} = \mathtt{T}, \lnot\mathtt{U} = \mathtt{U} \] 现在小 L 有 \(n\) 个三值逻辑变量 \(x_1,\cdots, x_n\)。小 L 想进行一些有趣的尝试，于是他写下了 \(m\) 条语句。语句有以下三种类型，其中 \(\gets\) 表示赋值： \(x_i \gets v...

hdu5573 Binary Tree 题解 题目链接：hdu5573 Binary Tree 题意： 老青蛙国王住在一棵无限大树的根部。根据法律，每个节点应该连接到下一级的确切两个节点，形成一棵完全二叉树。 由于国王精通数学，他为每个节点设置了一个数字。具体来说，树的根部，国王所在的地方，是 \(1\) ，称 \(f_{\text{root}} = 1\)。 对于每个节点 \(u\)，标记为 \(f_u\)，左孩子是 \(f_u \times 2\)，右孩子是 \(f_u \times 2+1\)。国王看着他的树王国，感到满意。 时间飞逝，青蛙国王生病了。根据古老的黑暗魔法，国王可以通过收集 \(N\) 个灵魂宝石来延续 \(N\) 年寿命。 最初国王没有灵魂宝石，现在他在根部。他将向下走，选择左孩子或右孩子继续前行。每次到达节点 \(x\) 时，节点上的数字为 \(f_x\)（记住 \(f_{\text{root}}=1\) ），他可以选择增加灵魂宝石的数量 \(f_x\)，或者减少 \(f_x\)。 他将从根部开始，访问确切 \(K\) 个节点（包括根部），并按照指示进行...