Q779’s Blog

LOJ6678 礼物 题解 题目链接：#6678. 礼物 题意： 穷愁潦倒的小 B 正在树上漫步，突然接到了小 S 的电话，要他去点 \(y\) 买一些礼物，然而他现在正处于 \(x\) 点，并且他身上并没有钱。 小 L 告诉了他一个绝妙的方法。树上的每个点都有大佬的存在，其中一些大佬会购买或出售（售价与收购价相同）bsoj 权限账号。而且各点 dalao 数量不同，价格也不同，这样的交易能使他赚上一笔差价。小 S 没有告诉他礼物的价钱，他只能赚尽量多的钱。由于小 S 在小 B 的身上装了追踪器，所以他只能走 \(x\) 到 \(y\) 的最短路，而且时间不足，因此这样的交易只能发生一次（指买一次卖一次）。 小 B 这样的大神犇显然已经知道求解方法了，但他为了不被小 S 发现，让你来帮他解决这个问题。 输入格式： 输入第一行是一个整数 \(n\) ，表示树上的点数。 接下来 \(n\) 个正整数，表示每个点上权限号的价格。 接下来 \(n-1\) 行，每行两个整数 \(x, y\) ，表示第 \(x\) 点和第 \(y\) 点有一条边。 接下来一个整数 \(m\) ，表示接下来...

洛谷P5840 [COCI2015]Divljak 题解 题目链接：P5840 [COCI2015]Divljak 题意： Alice 有 \(n\) 个字符串 \({S}_1, {S}_2, \ldots, {S}_n\)，Bob 有一个字符串集合 \({T}\)，一开始集合是空的。 接下来会发生 \(q\) 个操作，操作有两种形式： 1 P：Bob 往自己的集合里添加了一个字符串 \({P}\)。 2 x：Alice 询问 Bob，集合 \({T}\) 中有多少个字符串包含串 \({S}_x\)（我们称串 \({A}\) 包含串 \({B}\)，当且仅当 \({B}\) 是 \({A}\) 的子串）。 输入格式： 第一行一个整数 \(n\)。 接下来 \(n\) 行，第 \(i\) 行一个字符串 \({S}_i\)。 接下来一行一个整数 \(q\)。 接下来 \(q\) 行，每行一个操作。 输出格式： 对每个 2 x 操作，一行一个整数，表示答案。 数据范围： \(1 \leq n,q \leq 10^5\)，字符串由小写字母构成，\(S\) 和 \(P\) 的总长分别...

BZOJ4964 加长的咒语 题解 题目链接：BZOJ4964 加长的咒语 题意： VictBr发现是他上一次念的咒语是假的！咒语是由且仅由 ( 和 ) 构成的一段连续的字符串，一个咒语合法当且仅当这个咒语的任意一个前缀都满足 ( 的个数不少于 ) 的个数，且整个串的 ( 和 ) 的个数相等。 VictBr的膜法书上只有一长度为 \(n\) 的仅由 ( 和 ) 构成的字符串。长者告诉他世界上所有咒语都在这本膜法书中。 在长者的教诲下，Victbr学会了假的念咒术，然后他向世界上最强的OIer们发出挑战，在欢声笑语中打出GG。为了战胜他们，Victbr写出了更长的膜法书，并再次向最强的OIer们发出挑战。你能回答出他的问题么？ 具体的问题是：每次询问膜法书中的一个片段，求这个片段中最长的咒语的长度。 输入格式： 第一行两个正整数 \(n,m\) ，分别表示字符串长度和询问个数。 接下来一行一个长度为 \(n\) 的仅由 ( 和 ) 组成的字符串。 接下来 \(m\) 行, 每行两个整数 \(x,y\) ，表示询问的片段的左右端点。下标从 \(1\) 开始。 满足 \(1 \leq...

Sparse Table（ST 表）学习笔记 很少写算法和数据结构的讲解，但是 ST 表还是有必要写一下的，这里面细节很多。 稀疏表（ST 表）是一种常用的 RMQ 数据结构，适合于不带修改的可重复贡献问题 所谓可重复贡献问题，是指对于运算 \(\operatorname{opt}\) 有 \(x \operatorname{opt} x = x\) 的区间询问，例如 \(\max,\min,\gcd\) 等 ST 表基于倍增的思想，可以做到 \(\mathcal{O}(n \log n)\) 预处理，\(\mathcal{O}(1)\) 回答询问。注意，不支持修改。 定义 \(f(i,j)\) 为区间 \([i,i + 2^j -1]\) 的最大值，显然 \(f(i,0) = a_i\) 。考虑转移 \(j > 0\) 的情况 \[ f(i,j) = \max\left\{f(i,j-1),~f(i + 2^j, j - 1)\right\} \] 对于询问 \([l,r]\) ，我们记 \(k = \left\lfloor \log_2 (r - l + 1)\righ...

洛谷P2053 [SCOI2007] 修车 题解 题目链接：P2053 [SCOI2007] 修车 题意： 同一时刻有 \(N\) 位车主带着他们的爱车来到了汽车维修中心。 维修中心共有 \(M\) 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。 现在需要安排这 \(M\) 位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。 输入格式： 第一行有两个数 \(M,N\)，表示技术人员数与顾客数。 接下来 \(N\) 行，每行 \(M\) 个整数。第 \(i+1\) 行第 \(j\) 个数表示第 \(j\) 位技术人员维修第 \(i\) 辆车需要用的时间 \(T_{i,j}\)。 输出格式： 最小平均等待时间，答案精确到小数点后 \(2\) 位。 数据范围： \(2\le M\le 9\)，\(1\le N\le 60\)，\(1\le T\le 10^3\)。 考虑一个工人修 \(k\) 辆车的花费。假设这 \(k\) 辆车的花费为序列 \(T\) ，则 \[ \mathrm{ans} ...

洛谷P4163 [SCOI2007]排列 题解 题目链接：P4163 [SCOI2007]排列 题意： 给一个数字串 \(s\) 和正整数 \(d\) ，统计 \(s\) 有多少种不同的排列能被 \(d\) 整除（可以有前导 \(0\)）。例如 \(123434\) 有 \(90\) 种排列能被 \(2\) 整除，其中末位为 \(2\) 的有 \(30\) 种，末位为 \(4\) 的有 \(60\) 种。 输入格式： 输入第一行是一个整数 \(T\)，表示测试数据的个数，以下每行一组 \(s\) 和 \(d\)，中间用空格隔开。\(s\) 保证只包含数字 \(0,1,2,3,4,5,6,7,8,9\)。 输出格式： 每个数据仅一行，表示能被 \(d\) 整除的排列的个数。 数据范围： \(s\) 的长度不超过 \(10\)，\(1\le d\le 1000\)，\(1\le T\le 15\)。 直接暴力不知道卡不卡得过，我感觉不行。 这道题我们可以把原字符串中的字符看作一个可重集然后状压dp。 设 \(f_{S,j}\) 表示用了集合 \(S\) 的数字，且此时模 \(d\...

CF441E Valera and Number 题解 题目链接：CF441E Valera and Number 题意： 给出一个数 \(x\)，对它进行 \(k\) 次操作，每次操作： 以 \(p \%\) 的概率对它乘以 \(2\)。 以 \((100 - p) \%\) 的概率对它加上 \(1\)。 求该数最终二进制下末尾 \(0\) 个数的期望。 输入格式： The first line of the input contains three integers \(x,k,p(1\le x\le 10^{9}, 1\le k\le 200, 0\le p\le 100)\) . 输出格式： Print the required expected value. Your answer will be considered correct if the absolute or relative error doesn’t exceed \(10^{-6}\) . 设 \(f_{i,j}\) 表示 \(x\) 经过执行过 \(i\) 次后， \(x+j\) 的期望答案...

CF477D Dreamoon and Binary 题解 题目链接：CF477D Dreamoon and Binary 题意： 一天，cxy 在地上发现一个巨大的整数 \(x\) ，然后想把它写成二进制形式。 cxy 凭借她娴熟的技巧，将整数 \(x\) 变成了它的二进制形式。现在, 她想要用下列方式来打印这个数： 一开始, 她有一个整数 \(n=0\) ，然后, 她可以以任何顺序、次数没有限制地执行如下两种操作: 将 \(n\) 打印到已经打印的字符串的右边，如果 \(n>0\), 则不打印前导 \(0\) 。 将 \(n\) 自增 \(1\ (n \leftarrow n+1)\) 。 cxy 认为，如果一串操作序列可以成功地打印出（没有前导 0 的）\(x\) 且以操作1结束，则这串操作序列是理想的。cxy 想知道一共有多少种理想操作序列，以及最短的理想操作序列的长度。 由于答案可能很大，请模 \(10^9+7\) 输出。 输入格式： 输入共一行，包含一个二进制形式表达的正整数 \(x(x < 2^{5000})\) 。 输出格式： 第一行输出理想操作...

证明一个数是无理数 例1：证明 \(\sqrt{2}\) 是无理数。 证明：若 \(\sqrt{2}\) 是有理数，则设它等于 \(\frac{m}{n}~(m,n \in \mathbb{N}_+\land \gcd(m,n) = 1)\) 则 \((\frac{m}{n})^2=\sqrt{2}^2=2\) ，即 \(\frac{m^2}{n^2}=2\) ，可知 \(m^2=2n^2\) ，因此 \(m\) 是偶数。 设 \(m=2k(k \in \mathbb{Z})\) ，则 \(m^2=4k^2=2n^2\) ，可知 \(n^2=2k^2\) ，因此 \(n\) 是偶数。 因为 \(m,n\) 互质，矛盾，所以 \(\sqrt{2}\) 不是有理数，它是无理数。\(\square\) 例2：证明 \(\mathrm{e}\) 是无理数。 证明：由麦克劳林级数可知： \(e = \sum_{i = 0}^{+\infty} \frac{1}{i!}\) ，不知道可以看这篇 假设 \(\mathrm{e} = \frac{a}{b} (a,b \in \mathbb{N...

CF797F Mice and Holes 题解 题目链接：CF797F Mice and Holes 题意： 走廊可以看作是一个一个数轴，上面有 \(n\) 个老鼠和 \(m\) 个洞，第 \(i\) 个老鼠的坐标是 \(x_i\) ，第 \(j\) 个洞的坐标是 \(p_j\) ，可以容纳 \(c_j\) 个老鼠。 如果第 \(i\) 个老鼠去洞 \(j\) ，当然，它需要走 \(\left|x_i-p_j\right|\) 的距离，求所有老鼠都到达某个洞最小距离和。 输入格式： 第一行包含两个正整数 \(n, m(n, m \leq 5000)\), 分别表示老鼠和洞的数量。 第二行包含 \(n\) 个整数 \(x_1, x_2, \cdots, x_n\left(-10^9 \leq x_i \leq 10^9\right), x_i\) 表示第 \(i\) 个老鼠的坐标。 接下来的 \(m\) 行中, 第 \(j\) 行有两个正整数 \(p_j, c_j\left(-10^9 \leq p_j \leq 10^9, 1 \leq c_j \leq 5000\right...

洛谷P2471 [SCOI2007] 降雨量 题解 题目链接：P2471 [SCOI2007] 降雨量 题意： 我们常常会说这样的话：“\(X\) 年是自 \(Y\) 年以来降雨量最多的”。它的含义是 \(X\) 年的降雨量不超过 \(Y\) 年，且对于任意 \(Y < Z < X\)，\(Z\) 年的降雨量严格小于 \(X\) 年。例如 2002、2003、2004 和 2005 年的降雨量分别为 \(4920\)、\(5901\)、\(2832\) 和 \(3890\)，则可以说“2005 年是自 2003 年以来最多的”，但不能说“2005 年是自 2002 年以来最多的”由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。 输入格式： 输入仅一行包含一个正整数 \(n\)，为已知的数据。以下 \(n\) 行每行两个整数 \(y_i\) 和 \(r_i\)，为年份和降雨量，按照年份从小到大排列，即 \(y_i<y_{i+1}\)。下一行包含一个正整数 \(m\)，为询问的次数。以下 \(m\) 行每行包含两个数 \(Y\) 和 \(X\)，即询问...

洛谷P3638 [APIO2013] 机器人 题解 题目链接：P3638 [APIO2013] 机器人 题意： VRI（Voltron 机器人学会）的工程师建造了 \(n\) 个机器人。任意两个兼容的机 器人站在同一个格子时可以合并为一个复合机器人。 我们把机器人用 \(1\) 至 \(n\) 编号。如果两个机器人的编号是连续的，那么它们是兼容的，可以合并成一个复合机器人。最初这 \(n\) 个机器人各自都只有唯 一的编号。而一个由两个或以上的机器人合并构成的复合机器人拥有两个编号， 分别是构成它的所有机器人中最小和最大的编号。 例如，\(2\) 号机器人只可以与 \(1\) 号或 \(3\) 号机器人合并。若 \(2\) 号机器人与 \(3\) 号机器人合并，可构成编号为 \(2\sim 3\) 的复合机器人。如果编号为 \(2\sim 3\) 的复合机器人与编号为 \(4\sim 6\) 的复合机器人合并，可构成编号为 \(2\sim 6\) 的复合机器人。当所有机器人合 并以后则构成 \(1\sim n\) 复合机器人。 工程师把这 \(n\) 个机器人放在了一个封闭的房...