Q779’s Blog

CF526D Om Nom and Necklace 题解 题目链接：CF526D Om Nom and Necklace 题意： 已知长度为 \(n\) 的字符串 \(s\)，对于 \(s\) 的每一个前缀子串（即对于每一个 \(i\)，\(s\) 中从第 \(1\) 个字符到第 \(i\) 个的所有字符组成的字符串，\(1\leq i\leq n\)），如果满足 \(\texttt{ABABA...BA}\) 的形式（\(A\)、\(B\) 可以为空，也可以是一个字符串，\(A\) 有 \(k+1\) 个，\(B\) 有 \(k\) 个），则请输出 \(1\)；否则输出 \(0\)，注意：\(n\) 和 \(k\) 给定。 输入格式： The first line contains two integers \(n\), \(k\) (\(1\leq n,k\leq 10^6\)) — the number of beads on the thread that Om Nom found and number \(k\) from the definition of the...

ChatGPT 辅助写题解的技巧 q779 你是不是不写题跑来写这种东西了啊？ 施工中，咕咕咕… 一、公式格式问题 有些题，比如洛谷爬的 CF 题，它的行内公式都是 $ abc $ 的格式 然后我的博客是不支持这样写的，仅支持 $abc$ ，即没有空格的写法 比如我下一篇文章（也就是我正在写的题解），它的文本就是这么样。 我们可以让 ChatGPT 来搞定这种智障的事： 把下面的文本中形如 $ x $ 的部分全部替换成 $x$ 如图： 然后这个傻fufu的 ChatGPT 好像不能输出两种语言的混合文本。 事实上确实如此，它似乎只会单语言的文本，不过这不重要，至少它还帮我修了 <= 这种东西。 二、复制题面 有些网页，比如OI中转站，用简悦没法正确识别题面，可以用以下方式生成题面： 帮我修一下下面的文本，修成 markdown 文本，并且使用行内公式： <这里贴上直接复制后乱掉的 markdown 文本> 生成如下： 题目描述 有一棵 $n$ 个节点的有根树，$1$ 号点为根节点。第 $i$ 的父节点为 $f_i$ ($1\leq f_i < i ...

LOJ6669 Nauuo and Binary Tree 题解 题目链接：#6669. Nauuo and Binary Tree 题意： Nauuo 是一个喜欢二叉树的女孩子（cxy 就不一样，她喜欢妹纸）。 这天，她创造了一个有 \(n\) 个节点的二叉树。节点的编号从 \(1\) 到 \(n\) ，其中 \(1\) 是二叉树的根节点。 不过，她不记得这棵二叉树具体长什么样子了，她只记录了二叉树上任意两个节点之间的距离。你可以通过向她询问有关距离的信息来还原这棵二叉树，两个节点之间的距离定义为它们之间最短路上的边数。 你可以向 Nauuo 询问不超过 \(30000\) 次有关距离的信息。你只需要告诉她 \(2\sim n\) 号节点的父亲的编号就可以了。 交互方式 最开始，交互器会向标准输入中输入一个正整数 \(n\)。 接下来，你可以通过标准输出向交互器询问两个节点之间的距离。 对于一次询问，你需要输出一行 ? u v 表示你想让 Nauuo 告诉你节点 \(u\) 和节点 \(v\) 在这棵二叉树上距离，然后换行并刷新缓存。 在每次询问后，交互器会向标准输入中输入一...

CF1174F Ehab and the Big Finale 题解 题目链接：CF1174F Ehab and the Big Finale 题意： 这是一道交互题。 你有一棵 \(n\) 个节点的有根树，\(1\) 号点是根节点。这棵树中有一个隐藏的节点 \(x\) ，你需要通过询问把 \(x\) 找出来。你可以进行如下两种询问： 1、\(d\) \(u\) \((1\le u\le n)\)。交互库会返回节点 \(u\) 和 \(x\) 的距离。 2、\(s\) \(u\) \((1\le u\le n)\)。交互库会返回从 \(u\) 到 \(x\) 的路径上第二个点的标号。注意，你询问的 \(u\) 必须是 \(x\) 的祖先，否则会 Wrong Ans。 你需要在不超过 \(36\) 次询问之内找出 \(x\) 。\(x\) 是预先设定好的，不会随着询问而改变。 输入格式： The first line contains the integer \(n ( 2 \le n \le 2 \cdot 10^5)\) — the number of nodes in th...

LOJ6671 EntropyIncreaser 与 Minecraft 题解 题目链接：#6671. EntropyIncreaser 与 Minecraft 题意： 求方程 \(\left|x_1\right|+\left|x_2\right|+\cdots+\left|x_n\right| \leq p\) 的整数解的组数。 输入格式 共一行, 包含两个正整数 \(n, p\left(n \leq 10^6 ; p \leq 10^9\right)\) ，含义见题目描述。 输出格式： 输出一行一个整数, 表示方程的整数解的组数模 \(10^9+7\) 的值。 注意到除了 \(0\) 以外每个整数都会提供两次贡献，考虑枚举 \(0\) 的个数 \(n-k\) ， 那么剩下的数要求绝对值大于 \(0\) ，这样方案数要先乘上符号位的 \(2^k\) 。 设 \(y_i = x_i + 1\) ，其中 \(x_i \ge 0\) ，则需要求如下方程的方案数： \[ \sum_{i=1}^k y_i \leq p \Rightarrow \sum_{i=1}^k x_i \le...

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\) 的期望答案...