CF1333E Road to 1600 题解
CF1333E Road to 1600 题解 题目链接:Road to 1600 题意: 埃戈尔希望在著名的国际象棋门户网站 ChessForces 上达到 1600 分的评分,他需要你的帮助! 在你开始解决问题之前,埃戈尔想提醒你国际象棋棋子的移动方式。国际象棋中的车沿直线方向上下左右移动,可以移动任意多的格子,并且可以随时停下来。皇后可以在所有垂直和对角线方向上任意距离移动。你可以参考下面的示例图。 为了达到目标,埃戈尔应该研究下一个主题: 有一个 \(N \times N\) 的棋盘。棋盘的每个格子里都有一个从 \(1\) 到 \(N^2\) 的数字,且所有格子中的数字都是不同的。 一开始,有一个棋子站在编号为 \(1\) 的格子上。注意,这个格子已经被视为访问过了。之后的每一步移动遵循以下规则: 在所有尚未访问过且棋子可以通过一步到达的格子中,它会前往编号最小的那个格子。 如果所有可到达的格子都已经访问过但仍有未访问的格子,那么棋子会传送到尚未访问的编号最小的格子。如果发生此步骤,棋子会支付 1 个 vun 的费用。 如果所有格子都已访问,过程停止。 埃戈尔应该...
SP2124 FCTRL4 - Last Non-Zero Digit of Factorials 题解
SP2124 FCTRL4 - Last Non-Zero Digit of Factorials 题解 题目链接:FCTRL4 - Last Non-Zero Digit of Factorials 题意: 多组数据,每次给出一个正整数 \(n(n \le 10^{100})\) ,求 \(n!\) 最后一位非零数字。 例如 \(5! = 1\times 2 \times 3 \times 4 \times 5 = 120\) ,它的最后一位非零数字是 \(2\) 。 好像我是这题代码最短的,只有 202B 。 记 \(a = \left\lfloor\frac{n}{5}\right\rfloor,~b = n - 5\times \left\lfloor\frac{n}{5}\right\rfloor\) ,并记 \(L(n)\) 为 \(n!\) 最后一位非 \(0\) 数字,则 \[ \begin{aligned} L(n) &= 5\times 10\times 15\times \cdots\times (1 \times 2 \times 3 \tim...
洛谷P5319 [BJOI2019] 奥术神杖 题解
洛谷P5319 [BJOI2019] 奥术神杖 题解 题目链接:P5319 [BJOI2019] 奥术神杖 题意: Bezorath 大陆抵抗地灾军团入侵的战争进入了僵持的阶段,世世代代生活在 Bezorath 这片大陆的精灵们开始寻找远古时代诸神遗留的神器,试图借助神器的神秘力量帮助她们战胜地灾军团。 在付出了惨痛的代价后,精灵们从步步凶险的远古战场取回了一件保存尚完好的神杖。但在经历过那场所有史书都视为禁忌的“诸神黄昏之战”后,神杖上镶嵌的奥术宝石已经残缺,神力也几乎消耗殆尽。精灵高层在至高会议中决定以举国之力收集残存至今的奥术宝石,并重金悬赏天下能工巧匠修复这件神杖。 你作为神术一脉第五百零一位传人,接受了这个艰巨而神圣的使命。 神杖上从左到右镶嵌了 \(n\) 颗奥术宝石,奥术宝石一共有 \(10\) 种,用数字 0123456789 表示。有些位置的宝石已经残缺,用 . 表示,你需要用完好的奥术宝石填补每一处残缺的部分(每种奥术宝石个数不限,且不能够更换未残缺的宝石)。古老的魔法书上记载了 \(m\) 种咒语 \((S_i,V_i)\) ,其中 \(S_i\) 是一个...
洛谷P4094 [HEOI2016/TJOI2016] 字符串 题解
洛谷P4094 [HEOI2016/TJOI2016] 字符串 题解 题目链接:P4094 [HEOI2016/TJOI2016] 字符串 题目描述 qry 过生日的时候,她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为 \(n\) 的字符串 \(s\),和 \(m\) 个问题。qry 必须正确回答这 \(m\) 个问题,才能打开箱子拿到礼物,升职加薪,出任 CEO,嫁给高富帅,走上人生巅峰。 每个问题均有 \(a,b,c,d\) 四个参数,问你子串 \(s[a..b]\) 的所有子串和 \(s[c..d]\) 的最长公共前缀的长度的最大值是多少?qry 并不擅长做这样的问题,所以她向你求助,你该如何帮助她呢? 输入格式 输入的第一行有两个正整数 \(n,m\),分别表示字符串的长度和询问的个数。 接下来一行是一个长为 \(n\) 的字符串。接下来 \(m\) 行,每行有 \(4\) 个数 \(a,b,c,d\),表示询问 \(s[a..b]\) 的所有子串和 \(s[c..d]\) 的最长公共前缀的最大值。 输出格式 对于每一次询问,输出...
洛谷P3295 [SCOI2016] 萌萌哒 题解
洛谷P3295 [SCOI2016] 萌萌哒 题解 题目链接:P3295 [SCOI2016] 萌萌哒 题意: 一个长度为 \(n\) 的大数,用 \(S_1S_2S_3 \cdots S_n\)表示,其中 \(S_i\) 表示数的第 \(i\) 位, \(S_1\) 是数的最高位。 告诉你一些限制条件,每个条件表示为四个数 \(l_1,r_1,l_2,r_2\) ,即两个长度相同的区间,表示子串 \(S_{l_1}S_{l_1+1}S_{l_1+2} \cdots S_{r_1}\) 与 \(S_{l_2}S_{l_2+1}S_{l_2+2} \cdots S_{r_2}\) 完全相同。 比如 \(n=6\) 时,某限制条件 \(l_1=1,r_1=3,l_2=4,r_2=6\) ,那么 \(123123\),\(351351\) 均满足条件,但是 \(12012\),\(131141\) 不满足条件,前者数的长度不为 \(6\) ,后者第二位与第五位不同。问满足以上所有条件的数有多少个。 输入格式: 第一行两个数 \(n\) 和 \(m\),分别表示大数的长度,以及限制条件...
洛谷P5341 [TJOI2019] 甲苯先生和大中锋的字符串 题解
洛谷P5341 [TJOI2019] 甲苯先生和大中锋的字符串 题解 题目链接:P5341 [TJOI2019] 甲苯先生和大中锋的字符串 题意: 大中锋有一个长度为 \(n\) 的字符串,他只知道其中的一个子串是祖上传下来的宝藏的密码。 但是由于字符串很长,大中锋很难将这些子串一一尝试。 这天大中锋找到甲苯先生算命,但是甲苯先生说:“天机不可泄漏”。 在大中锋的苦苦哀求下,甲苯先生告诉大中锋:“密码是在字符串中恰好出现了 \(k\) 次的子串”。 但是大中锋不知道该怎么做,在大中锋再三的恳求下,甲苯先生看其真诚,又告诉他:“在恰好出现了 \(k\) 次的子串中,你去按照字串的长度分类,密码就在数量最多的那一类里”。 大中锋为了尝试这个密码,想让你帮忙找出子串长度出现次数最多的长度数(如果有多个输出最长长度)。 输入格式: 第一行一个正整数 \(T\) ,表示有 \(T\) 组测试数据。 接下来 \(T\) 行每行包含一个字符串和一个正整数 \(k\) 。 输出格式: 一共输出 \(T\) 行,每行一个整数表示在出现 \(k\) 次的子串中出现次数的最多的长度。 如果不存在子串...
洛谷P3975 [TJOI2015] 弦论 题解
洛谷P3975 [TJOI2015] 弦论 题解 题目链接:P3975 [TJOI2015] 弦论 题意: 为了提高智商,qry 开始学习弦论。 这一天,她在《String theory》中看到了这样一道问题: 对于一个给定的长度为 \(n\) 的字符串,求出它的第 \(k\) 小子串是什么。你能帮帮她吗? 输入格式: 第一行是一个仅由小写英文字母构成的字符串 \(s\)。 第二行为两个整数 \(t\) 和 \(k\) , \(t\) 为 \(0\) 则表示不同位置的相同子串算作一个。 \(t\) 为 \(1\) 则表示不同位置的相同子串算作多个。 \(k\) 的意义见题目描述。 输出格式: 输出数据仅有一行,该行有一个字符串,为第 \(k\) 小的子串。若子串数目不足 \(k\) 个,则输出 \(-1\)。 数据范围: \(1\leq n \leq 5 \times 10^5,~0\leq t \leq 1,~1\leq k \leq 10^9\)。 \(\mathcal{Part}\ 0\) 看题解区全是 SAM 的解法,少有的 SA 解法也都是 \(\mathcal...
洛谷P5854 【模板】笛卡尔树 题解
洛谷P5854 【模板】笛卡尔树 题解 题目链接:P5854 【模板】笛卡尔树 题意: 给定一个 \(1 \sim n\) 的排列 \(p\),构建其笛卡尔树。 即构建一棵二叉树,满足: 每个节点的编号满足二叉搜索树的性质。 节点 \(i\) 的权值为 \(p_i\),每个节点的权值满足小根堆的性质。 输入格式: 第一行一个整数 \(n\)。 第二行一个排列 \(p_{1 \dots n}\)。 输出格式: 设 \(l_i,r_i\) 分别表示节点 \(i\) 的左右儿子的编号(若不存在则为 \(0\))。 一行两个整数,分别表示 \(\operatorname{xor}_{i = 1}^n i \times (l_i + 1)\) 和 \(\operatorname{xor}_{i = 1}^n i \times (r_i + 1)\)。 数据范围: 对于 \(100\%\) 的数据,\(1 \le n \le 10^7\)。 笛卡尔树的构建非常简单,我们只需要维护一个单调栈即可。 虽然很简单,但是笛卡尔树在一些题目中还是很有用的,原因就在于它可以线性构建。 时间复杂度...
AT_arc101_c [ARC101E] Ribbons on Tree 题解
AT_arc101_c [ARC101E] Ribbons on Tree 题解 题目链接:AT_arc101_c [ARC101E] Ribbons on Tree 题意: 给定一个大小为 \(n(2\le N\le 5000)\) 的树,保证 \(n\) 为偶数。 您需要给树上的点两两配对,对于一组点对 \((u,v)\),在树上将 \(u\leadsto v\) 的路径染色。 定义一个配对方案合法当且仅当所有边都有颜色,求方案数对 \(10^9+7\) 取模。 输入:第一行 \(n\) ,接下来 \(n-1\) 行 \(u,v\) 表示无向边 \(u,v\) 。输出:一行答案。 先考虑一个 \(\mathcal{O}(n^3)\) 的 dp。 设 \(f(u,i)\) 为 \(u\) 子树中有 \(i\) 个点要向上匹配的方案数。 那么这就是一个树上背包,转移考虑枚举 \(u\) 子树内的点数 \(i\) , \(v\) 子树内的点数 \(j\) 和匹配的对数 \(k\) \[ f_{\rm now}(u,i + j-2k) = \sum_{1\le k \le j ...
洛谷P3225 [HNOI2012] 矿场搭建 题解
洛谷P3225 [HNOI2012] 矿场搭建 题解 题目链接:P3225 [HNOI2012] 矿场搭建 题意: 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口,使得无论哪一个挖煤点坍塌之后,其他挖煤点的工人都有一条道路通向救援出口。 请写一个程序,用来计算至少需要设置几个救援出口,以及不同最少救援出口的设置方案总数。 输入格式: 输入文件有若干组数据。 每组数据的第一行是一个正整数 \(N\ (N \le 500)\),表示工地的隧道数。 接下来的 \(N\) 行每行是用空格隔开的两个整数 \(S\) 和 \(T\),表示挖煤点 \(S\) 与挖煤点 \(T\) 由隧道直接连接。 输入数据以 \(0\) 结尾。 输出格式: 对于每组数据,输出一行。 第 \(i\) 行组数据以 \(\verb!Case i: !\) 开始(注意大小写,\(\verb!Case!\) 与 \(\verb!i!\) 之间有空格,\(\verb!i!\) 与 \(\verb!:!\)...
AT_abc343_g [ABC343G] Compress Strings 题解
AT_abc343_g [ABC343G] Compress Strings 题解 题目链接:AT_abc343_g [ABC343G] Compress Strings 题意: 给你 \(N\) 个由小写字母组成的字符串 \(S_1, S_2, \ldots, S_N\) 。 找出一个母串使得它包含所有这些字符串作为它的子串,最小化该母串的长度并输出。 数据范围:\(1 \leq N \leq 20,~\sum |S_i| \leq 2 \times 10 ^ 5\) 。 考虑状压dp。首先记 \(a_{i,j}\) 为 \(i,j\) 的最长公共子串的长度,这个可以用 kmp 跑出来。 设 \(f(i,S)\) 为当前选了 \(S\) 的字符串,最后一个选的字符串是 \(i\) 时的最小值。 这里要求 \(S\) 中的字符串不存在相互包含的情况,也可以用 kmp 跑出来。 那么 \[ f(j, S \cup \{j\}) \,\operatorname{\big\downarrow}\, f(i,S) + \operatorname{len} i - a_{i,j} \]...
洛谷P2322 [HNOI2006] 最短母串问题 题解
洛谷P2322 [HNOI2006] 最短母串问题 题解 题目链接:P2322 [HNOI2006] 最短母串问题 题意: 给定 \(n\) 个字符串 \((S_1,S_2,...,S_n)\) , 要求找到一个最短的字符串 \(T\),使得这 \(n\) 个字符串 \((S_1,S_2,...,S_n)\) 都是 \(T\) 的子串。 输入格式: 输入文件第一行是一个整数 \(n\),表示给定的字符串个数。 接下来 \(n\) 行,每行有一个全由大写字母组成的字符串。 输出格式: 输出文件只有一行,为找到的最短的字符串 \(T\)。 在保证最短的前提下,如果有多个字符串都满足要求,那么必须输出按字典序排列的第一个。 数据范围: 对于 \(100\%\) 的数据,\(n \leq 12\),每个字符串的长度不超过 \(50\)。 由于本题要求输出字典序最小的方案,所以这题状压dp会比较麻烦。 注意到超级小的数据范围,考虑暴力出奇迹,即 bfs 所有可能的情况。 检验的话,考虑将题目给的串建一个 AC 自动机,然后预处理出每个节点包含了那些串。 由于一般的写法都是建字典图,所以...


![洛谷P5319 [BJOI2019] 奥术神杖 题解](/qwq/img/p163.webp)
![洛谷P4094 [HEOI2016/TJOI2016] 字符串 题解](/qwq/img/p215.webp)
![洛谷P3295 [SCOI2016] 萌萌哒 题解](/qwq/img/p213.webp)
![洛谷P5341 [TJOI2019] 甲苯先生和大中锋的字符串 题解](/qwq/img/p26.webp)
![洛谷P3975 [TJOI2015] 弦论 题解](/qwq/img/p72.webp)

![AT_arc101_c [ARC101E] Ribbons on Tree 题解](/qwq/img/p175.webp)
![洛谷P3225 [HNOI2012] 矿场搭建 题解](/qwq/img/p220.webp)
![AT_abc343_g [ABC343G] Compress Strings 题解](/qwq/img/p134.webp)
![洛谷P2322 [HNOI2006] 最短母串问题 题解](/qwq/img/p216.webp)

![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p214.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)