Q779’s Blog

CF1491F Magnets 题解 题目链接：CF1491F Magnets 题意： 这是一个交互题。 早苗有 \(n\) 块磁石，编号为 \(1,2,\cdots,n\)。每块磁石的磁极可能是正极，负极，也可能没有磁性。她希望你能帮她找出所有没有磁性的磁石。 万幸的是，你有一台磁力检测仪。你每次可以将每个磁石放在这台机器的左托盘，右托盘或者不放。 机器将会返回此时的磁力强度。设托盘左边有 \(n_1\) 个磁石为正极，\(s_1\) 个磁石为负极，托盘右边中有 \(n_2\) 磁石为正极，\(s_2\) 个磁石为负极，则返回的磁力强度为 $ n_1n_2+s_1s_2-n_1s_2-n_2s_1 $。 如果一次测试中磁力强度的绝对值大于 \(n\)，这台机器就会坏掉。 你需要在 \(n+\lfloor\log_2n\rfloor\) 次测试内找到所有没有磁性的磁石的编号，同时不能弄坏机器。 保证存在至少 \(2\) 块磁石有磁性且至少 \(1\) 块磁石没有磁性。 输入格式： 仅一行，包含一个正整数 \(T\)（\(1\leq T\leq 100\)），表示数据的组数。 ...

洛谷P2396 yyy loves Maths VII 题解 题目链接：P2396 yyy loves Maths VII 题意： 一群同学在和 yyy 玩一个游戏。 每次,他们会给 yyy \(n\) 张卡片，卡片上有数字，所有的数字都是“幸运数字”，我们认为第 \(i\) 张卡片上数字是 \(a_{i}\)。 每次 yyy 可以选择向前走 \(a_{i}\) 步并且丢掉第 \(i\) 张卡片。当他手上没有卡片的时候他就赢了。 但是呢，大家对“厄运数字”的位置布置下了陷阱，如果 yyy 停在这个格子上，那么他就输了。注意：即使到了终点，但是这个位置是厄运数字，那么也输了。 现在，有些同学开始问：yyy 有多大的概率会赢呢？ 大家觉得这是个好问题，有人立即让 yyy 写个程序：“电脑运行速度很快！\(24\) 的阶乘也不过就 \(620\,448\,401\,733\,239\,439\,360\,000\)，yyy 你快写个程序来算一算。” yyy 表示很无语，他表示他不想算概率，最多算算赢的方案数，而且是对 \(10^9+7\) 取模后的值。 大家都不会写程序,只好妥协。 ...

CF1073E Segment Sum 题解 题目链接：CF1073E Segment Sum 题意： 给定 \(l,r,k\) ，求 \([l,r]\) 有多少个数满足「不包含超过 \(k\) 个数码」，输出他们的和 \(\bmod {998244353}\) 。 \(0 \le k\le 10,~1\le l ,r \le 10^{18}\) 做了这题才发现自己对数位dp的掌握很烂 其实很水，用个状态 st 记录每个数码是否出现过 设 \(f_{i,j}\) 表示只考虑前 \(i\) 位（从低位向高位计数），数码状态为 \(j\) 的数字的个数 设 \(g_{i,j}\) 表示只考虑前 \(i\) 位（从低位向高位计数），数码状态为 \(j\) 的数字的和 则 \[ f_{i,j} = \sum f_{i-1,j^{\prime}}\\ \\g_{i,j} = \sum 10^{i-1} \times d \times f_{i-1,j^{\prime}} + g_{i,j^{\prime}} \] 其中 \(d\) 表示第 \(i-1\) 位要填啥， \(j^{\pri...

SP10606 BALNUM - Balanced Numbers 题解 题目链接：SP10606 BALNUM - Balanced Numbers 题意： 一个数被称为是平衡的数 当且仅当对于所有出现过的数位（即 \(0\) 到 \(9\) ） 每个偶数出现奇数次，每个奇数出现偶数次。 给定 \(A,B\)，请统计出 \([A,B]\) 内所有平衡数的个数。 \(1\leq A\leq B\leq 10^{19}\) 数位dp就是套板子，然后我现在还没记住板子（ 考虑记录每个数的奇偶性，用状态 st 表示 第 \(i(1\le i \le 9)\) 位为 \(0\) 表示出现次数为偶，否则为 \(1\) 再记录一个 vis ，表示这个数是否出现了 这两个东西可以压到一个 pair 里，这样方便开数组（和其他题解学的 因为这道题是统计出现次数的，所以前导零会影响计数 所以还要记录一下有没有前导零，代码里用 qd0 表示了（ 最后 check 一下状态啥的，就好了（ 代码： #include <iostream> #include <string> #includ...

UOJ66 新年的巧克力棒 题解 题目链接：#66. 新年的巧克力棒 题意：马上就要到羊年了，羊村一片欢腾，懒羊羊则懒洋洋地躺在草坪上吃新年的巧克力棒。 他手上的巧克力棒是个由 \(n\) 个巧克力单元格组成的长度为 \(n\) 的长条，现在懒羊羊想把巧克力棒掰开成一个个小单元格。 初始时懒羊羊会把这根巧克力棒丢在草坪上，然后每次懒羊羊会从草坪上拿起一根长度大于 \(1\) 的巧克力棒，然后从某两个相邻的单元格的间隙处掰开变成两根巧克力棒，然后把这两根巧克力棒丢在草坪上。懒羊羊初始愉悦值为 \(0\)，每次掰开巧克力棒后如果这两根巧克力棒长度相等，那么懒羊羊将提升 \(1\) 点愉悦值。 当然，草坪上全是长度为 \(1\) 的巧克力棒时懒羊羊就会停止操作。现在懒羊羊想知道，他能获得的愉悦值最多是多少？ 设 \(f_i\) 表示长度为 \(i\) 的巧(áo)克(lì)力(gèi)能获得的最大价值，则 \[ f_i = \max\limits_{1 \le j < i}\left\{f_j + f_{i-j} + [j=i-j]\right\} \] 然后这东西是 \(O...

洛谷P2292 [HNOI2004] L 语言 题解 题目链接：P2292 [HNOI2004] L 语言 题意： 标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。 一段文章 \(T\) 是由若干小写字母构成。一个单词 \(W\) 也是由若干小写字母构成。一个字典 \(D\) 是若干个单词的集合。我们称一段文章 \(T\) 在某个字典 \(D\) 下是可以被理解的，是指如果文章 \(T\) 可以被分成若干部分，且每一个部分都是字典 \(D\) 中的单词。 例如字典 \(D\) 中包括单词 \(\texttt{is},\texttt{name},\texttt{what},\texttt{your}\)，则文章 \(\texttt{whatisyourname}\) 是在字典 \(D\) 下可以被理解的，因为它可以分成 \(4\) 个单词：\(\texttt{what},\texttt{is},\texttt{your},\texttt{name}\)，且每个单词都属于字典 \(D\)，而文章 \(\texttt{whatisyo...

洛谷P1305 新二叉树 题解 题目链接：P1305 新二叉树 题意： 输入一串二叉树，输出其前序遍历。 输入1： 6 abc bdi cj* d** i** j** 输出1： abdicj 虽然是大水题，但是有个解法还是很妙的 利用前序遍历的性质，它的子树一定在它后面。 直接贴代码了，感觉很妙： #include <iostream> #include <string> #include <vector> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> #include <random> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)() int n; string s,t; signed main() &#...

洛谷P1229 遍历问题 题解 题目链接：P1229 遍历问题 题意： 我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树： 所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。 输出可能的中序遍历序列的总数，结果不超过长整型数。 首先这个遍历方式都知道吧 前序遍历：根左右 后序遍历：左右根 等等，如果根只有一个儿子怎么办？ 好问题，我们并不知道他到底是左儿子还是右儿子 根据乘法原理，设有 \(k\) 个结点 \(u_i\) 满足 \(\left|\left\{v \mid v \in \text{son}(u)\right\}\right|=1\) 则答案为 \(2^k\) 。直接 \(O(n^2)\) 跑一下就好啦！ 代码： #include <iostream> #include <string> #include...

洛谷P1983 [NOIP2013 普及组] 车站分级 题解 题目链接：P1983 [NOIP2013 普及组] 车站分级 题意： 一条单向的铁路线上，依次有编号为 $1, 2,, n $ 的 \(n\) 个火车站。每个火车站都有一个级别，最低为 \(1\) 级。现有若干趟车次在这条线路上行驶，每一趟都满足如下要求：如果这趟车次停靠了火车站 \(x\)，则始发站、终点站之间所有级别大于等于火车站 \(x\) 的都必须停靠。（注意：起始站和终点站自然也算作事先已知需要停靠的站点） 例如，下表是 \(5\) 趟车次的运行情况。其中，前$ 4$ 趟车次均满足要求，而第 \(5\) 趟车次由于停靠了 \(3\) 号火车站（ \(2\) 级）却未停靠途经的 \(6\) 号火车站（亦为 \(2\) 级）而不满足要求。 现有 \(m\) 趟车次的运行情况（全部满足要求），试推算这 \(n\) 个火车站至少分为几个不同的级别。 对于 \(100\%\) 的数据，\(1 \le n, m \le 1000\)。 考虑建图。 对于一趟车，我们把所有「不停靠的站」向「停靠的站」连一条有向边 即边...

模拟赛题讲解[20] 来自 AprilGrimoire 2022-08-09 noi.ac #2775 题目描述： 小 Z 想出几道送分题。 小 Z 有一列脑洞（共 \(m(m \leq 10^9)\) 个）。脑洞分为白色与黑色，白色脑洞会让题目难度降低，黑色脑洞会让题目难度提高。因为小 Z 很懒，她决定将脑洞分为连续的若干段，将每段缝合成一道送分题。为了达到雨露均沾的送分效果，小 Z 希望每段中黑色脑洞所占的比例相同。小 Z 想知道她最多能缝合出几道题？ 输入格式： 第一行一个整数 \(n(n \leq 10^6)\) 接下来 \(n\) 行按顺序描述了小 Z 的脑洞。其中第 \(i\) 行一个正整数 \(r_i\) 和字符 \(w_i\)。这表示接下来有连续 \(r_i\)个颜色为 \(w_i\) 的脑洞（ W 代表白色，B 代表黑色）。 输出格式： 一行一个整数，表示小 Z 最多能缝合出的题目数。 输入1： 1 B 1 W 2 W 2 B 1 W 1 B 输出1： 3 输入2： 1 W 2 W 1 B 2 B 1 W 4 B 1 B 2 B 1 B 1 B 输出2： 1 输...

模拟赛题讲解[19] 来自 yukuai26 2022-08-08 noi.ac #2771 题目背景： \(\text{yukuai26}\) 喜欢爬山，所以他选择绕着山跑圈 题目描述： \(\text{yukuai26}\) 会跑一个环形路径，每个路径有一个高度 \(h\)，他会顺时针或者逆时针沿着路径跑，一旦确定方向就不会换方向。 由于他喜欢爬山，所以如果前一次跑步时上坡，他希望下一次是下坡，同样的，如果前一次跑步时下坡，下一次他希望是上坡，并且他不希望重复经过同一地点，所以他跑过所有点时就会停下来。 现在 \(\text{yukuai26}\) 想知道，他最多可以跑过多少点呢？ 一句话题意，给你一个环，环上每个点有一个高度，你要找到其中最长的一条路径 \(d_1,d_2....d_l\) , 满足 \(d_i\)和 \(d_{i+1}\) 相邻且所有 \(d_i\) 互不相同，且 \(h_{d_1} \leq h_{d_2} \geq h_{d_3} \leq h_{d_4}...\)或者 \(h_{d_1} \geq h_{d_2} \leq h_{d_3} \geq ...

模拟赛题讲解[18] 来自 yukuai26 2022-08-08 noi.ac #2773 题目背景： 搞个大新闻. jpg 题目描述： 你来到了幻想乡。首先你准备搞一个大新闻，获得文文的报道并变得出名，你决定对幻想乡的股票系统下手。 你通过猪脚光环了解到了接下来 \(n\) 天的股票价格 \(a_i\)，你每天可以买一个股票或卖出一个股票或者什么都不做，一天只能干一件事。 那么为了搞个大事情，你希望赚的钱最多，那么你最多能获得多少钱呢？ (注意到最终手上的股票不能算钱, 并且你可以暂时亏损) 输入格式： 第一行一个整数 \(n\)，表示天数 接下来一行 \(n\) 个数，表示每天股票的价格 输出格式： 一行一个数，表示最大能挣的钱 输入1： 9 10 5 4 7 9 12 6 2 10 输出1： 20 输入2： 20 3 1 8 1 7 9 5 6 5 3 5 8 2 7 9 3 2 3 8 4 输出2： 41 数据范围： 打包测试 测试包 1: \(n \leq 15,~55\) 分 测试包 2: \(n \leq 100,~a_i \leq 100 ,~10\)分 测试包...