Q779’s Blog

洛谷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\)分 测试包...

洛谷P3243 [HNOI2015]菜肴制作 题解 题目链接：洛谷P3243 [HNOI2015]菜肴制作 题解 题意： \(t\) 组数据，每组要做 \(n\) 个菜，但是需要满足 \(m\) 个限制。 每个限制形如 \((i,j)\) ，指菜肴 \(i\) 要在菜肴 \(j\) 之前做。（这里的 \(i,j\) 都是编号） 在满足所有限制的前提下，要保证编号越小的菜肴越早做。 对于每组数据，求出最优的菜肴制作顺序，或者输出 Impossible! 表示无解 \(m\) 条限制中可能存在完全相同的。 \(1\le t \le 3,~ 1 \le n,m \le 10^5\) 显然建图然后topo，有环就无解。 但是怎么拓扑呢？字典序最小？ 显然，这并不显然是错的 例： \((2,4),~(3,1)\) 字典序最小的算出来的是 2,3,1,4 ，而答案是 3,1,2,4 原因在于字典序最小，不一定能保证 \(1\) 尽可能在前面 即字典序最小，不一定保证编号越小的菜肴越早做 重新考虑怎么做 题目要求编号越小的菜肴越早做 因此标号越大的菜肴就要越晚做 则每个菜肴在它的合法范围内...

模拟赛题讲解[17] 来自 yukuai26 2022-08-08 noi.ac #2772 题目描述： \(\text{ysgh}\) 有一个长度为 \(m\) 的，元素两两不同的序列。 \(\text{emoairx}\) 想要知道这个序列里的元素及其顺序，她用一个神奇的望远镜可以看到序列里的一部分元素及其相对顺序。 他得到了很多组观测数据。 他想要知道这个序列应该是什么样的。 假如存在多组解，输出长度最小的解。 假如还是存在多组解，输出字典序最小的解。 数据保证有解。 输入格式： 第一行一个正整数 \(n\)，表示有多少组观测数据 接下来 \(n\) 行，每行第一个正整数 \(k_{i}\) 表示第 \(i\) 次观测观测到了多少个数据。 这行接下来 \(k_{i}\) 个数描述序列中的 \(k_{i}\) 个元素，需要保证原序列中的这几个元素一定要按照该顺序出现 输出格式： 一行若干个正整数，描述长度最小前提下，字典序最小的合法的序列。 输入1： 3 3 1 3 4 3 2 3 4 2 6 5 输出1： 1 2 3 4 6 5 样例解释 诸如 2 1 3 4 6 5、1 ...

模拟赛题讲解[16] 来自 yukuai26 2022-08-07 noi.ac #2764 题目描述： 紫开始研究特殊的括号序列 这些特殊括号序列的形式是若干个右括号（可以没有）在前，若干个左括号（可以没有）在后。 比如 ((，)))，))( 都是特殊的括号序列 显然刚开始给出的特殊的括号序列都不合法。 紫决定把所有序列首尾相连（按照紫想要的顺序排列)，然后她再删除若干个括号，她希望最终删完括号的序列是一个合法的括号序列。 以下合法的括号序列定义 1、空串是一个合法的括号序列 2、若 \(A,B\) 分别是合法的括号序列，则 \(AB\) 是合法的括号序列 3、若 \(A\) 是合法的括号序列，则 \((A)\) 是合法的括号序列 紫想要知道，她最少需要删除多少个括号。 输入格式： 第一行一个正整数 n，表示有多少个括号序列 接下来 n 行，每行两个非负整数 \(a_{i},b_{i}\) \(a_{i}\) 表示第 \(i\) 个括号序列的右括号数，\(b_{i}\) 表示第 \(i\) 个括号序列的左括号数 输出格式： 一个整数表示最少需要删除多少个括号。 输入1： 3 1...

CF1713A Traveling Salesman Problem 题解 题目链接：CF1713 Traveling Salesman Problem 题意：\(t\) 组数据，每组数据给定 \(n\) 个在坐标轴上的点 \((x_i,y_i)\) ，求最小的路径满足 起点和终点均为 \((0,0)\) 每一步只能走到 \((x+1,y),~(x-1,y),~(x,y+1),~(x,y-1)\)四者中的一个 例如下图 \(1 \le t \le 100,~1\le n \le 100,~-100 \le x_i,y_i \le 100\) 考虑四个方向上距离 \((0,0)\) 最远的所构成的合法矩形（满足走法的矩形） 对矩形进行一定的伸缩，一定能走完所有的点，并且一定是最优的， 例如题目里给出的这个图，如果 \((0,1)\) 有个点，也是可以走到的 显然， \((0,0)\) 也可以走到，然后就没了 时间复杂度 \(O(tn)\) 代码： #include <iostream> #include <string> #include <vector...

模拟赛题讲解[15] 来自 yukuai26 2022-08-07 noi.ac #2763 题目描述： 幻想乡有 \(n\) 个建筑，每个建筑里住了一些居民。 有一些双向道路连接居民的家，共有 \(n-1\) 条道路，恰好让所有居民的家能够互相到达。 其中标号为 \(i\) 的建筑居住了 \(i\) 名幻想乡的居民。 现在居民想要互相拜访，但是一次拜访需要花费 \(\text{dis}(u,v)\) 的代价，其中 \(u,v\) 分别是两人所在的建筑，\(\text{dis}\) 表示这两个建筑之间的最短路。 ⑨想要知道, 所有幻想乡人都拜访其他人所需要的代价之和。 答案对 \(10^9+7\) 取模。 输入格式： 第一行一个整数 \(n\)。 接下来 \(n-1\) 行, 每行 \(2\) 个整数 \(n-1\) 个整数描述 \(n-1\) 条道路。 输出格式： 一个整数，表示总花费之和。 输入1： 5 1 2 2 3 2 4 1 5 输出1 184 数据范围： 对于 \(30\%\) 的数据，满足 \(n≤200\) 对于 \(60\%\) 的数据，满足 \(n≤3000\...

模拟赛题讲解[14] 来自 yukuai26 2022-08-06 noi.ac #2755 题目背景 \(\text{yukuai26}\) 喜欢算术，但他又菜又爱玩，所以需要你的帮助 题目描述： 小明给你 \(n\) 个正整数，他想取一些数加起来（可以取 \(0\) 个数），问能得到的最大的能被 \(3\) 整除的和是多少 输入格式： 第一行一个整数 \(n\) 第二行 \(n\) 个正整数, 表示小明给你的 \(n\) 个正整数 输出格式： 一个整数，表示最大的能被 \(3\) 整除的和 输入1： 4 1 2 3 4 输出1： 9 输入2： 3 693 647 550 输出2： 1890 数据范围： 总共 \(10\) 个测试点 对于测试点 \(1,2\)，\(n \leq 3\) 对于测试点 \(3\)，\(n \leq 10\) 对于测试点 \(4,5\)，保证小明给你的数只有 \(3\) 的倍数 对于测试点 \(6\)，保证小明给的数对 \(3\)取模为 \(0\) 或 \(1\) 对于测试点 \(7\)，\(a_i \leq 100\) 对于所有测试点 \(n \l...

模拟赛题讲解[13] 来自 yukuai26 2022-08-06 noi.ac #2757 据说是从JOI搬过来的，赛时有位巨佬18min就A了 Orz 题目描述： 橙 —- 作为幽幽子大人的朋友的使者, 非常贪玩, 也喜欢思考有趣 的问题。 她在冥界思考一个有趣的问题, 希望赶到的灵梦能够解答。 一个字符串由 \(\tt{a,b,c}\)三种字母组成, 它最多能分成多少个 \(\tt{abc}\) 和 \(\tt{cbc}\) 的子序列呢? 具体的, 一个字符串 \(str\) 可以由选择 \(3\) 个位置 \(i < j < k\) 使得 \(s_i,s_j,s_k\) 依次连接组成 \(\tt{abc}\) 或 \(\tt{cbc}\) ， 这样算分出一个字符串, 接着把 \(3\) 个位置上的字母删掉, 剩下的字母重新组成新的字符串并接着提取。 输入格式： 第一行一个正整数 \(n\) 表示字符串的长度 接下来一个长度为 \(n\) 的字符串, 保证由 \(\tt{a,b,c}\) 组成 输出格式： 一行一个数，表示最大能分成的个数 输入1： 6 abcb...

模拟赛题讲解[12] 来自 yukuai26 2022-08-06 noi.ac #2756 题目描述： 曾经有一个 oj 叫做 bzoj, 里面有一题 bzoj1002 叫狼抓兔子 由于 1002 过于有名且显眼，很多人 A 掉了他，每 A 一次兔子就会少一只，兔子死亡惨重，救救兔子! 兔子为了反击策划了一次行动。 刚开始狼在二维平面上的 \((0,0)\) ，他希望走到 \((10^7,0)\)，而有 n 只兔子分为处于位置 \((x_{i},y_{i})\)。 当狼与某只兔子的欧几里得距离\(\leq p\) 时（\(p\)可以视为一个无限接近于 \(0\) 的正实数, 事实上可以理解为狼和兔子非常非常接近)，兔子就会干扰狼，这样狼会被干扰 \(t\) 秒， 随后这只兔子完全任务就会离开。 兔子的目标是使得狼受到尽可能被更多的兔子干扰。 已知狼和兔子运动速度都为 1m/s。另外狼和兔子都知道所有动物的实时位置和实时速度方向。 现在围观的 yukuai26 想知道，假如兔子和狼都绝对聪明，狼会受到多少次兔子的干扰 输入格式： 第一行两个非负整数 \(n,t\) ，表示兔子的个...