Q779’s Blog

洛谷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\) ，表示兔子的个...

模拟赛题讲解[11] 来自 xpp 2022-08-04 noi.ac #2731 题目描述： xpp在玩祖玛游戏，他心血来潮想根据祖玛游戏出一个题。 给一个序列 \(a_1,a_2,\dots,a_n\) ，你每次可以选择相同且相邻的三个数删除他们，如果序列中存在这样相同且相邻的三个数，xpp将不断将他们删除，xpp想知道最后序列中还剩几个数呢？ 输入格式： 第一行一个正整数 \(T(1\le T\le 10)\) 表示数据组数。 对于每组数据，第一行一个正整数 \(n\) 表示序列长度，第二行 \(n\) 个正整数表示 \(a[1\dots n]\)。 输出格式： 对于每组数据输出一行，表示答案。 输入1： 2 7 1 1 1 2 2 2 3 8 1 2 2 2 1 1 3 2 输出1： 1 2 数据规模： 对于 \(30\%\) 的数据，\(3\le n\le 10,~1\le a_i\le 10\) 对于 \(60\%\) 的数据，\(3\le n\le 10^3,~1\le a_i\le 10^3\) 对于 \(100\%\) 的数据，\(1\le a_i\le 10^...

模拟赛题讲解[10] 来自 xpp 2022-08-03 noi.ac #2723 题目描述 lzr给了xpp一个字符串 \(s\) 和一个字符串 \(t\) ，xpp想通过 \(s\) 构造出 \(t\) ，构造方式为xpp每次选择 \(s\) 的一个子序列，放到当前串的后面，xpp想知道他需要构造多少次才能构造出 \(t\) 呢？ 输入格式 第一行一个数 \(T\) 表示数据组数。 对于每组数据第一行一个字符串 \(s\) ，第二行一个字符串 \(t\) ，含义见题目描述 输出格式 每组数据输出一行表示次数。如果不能输出 \(-1\)。 输入1： 3 aabce ace abacaba aax ty yyt 输出1： 1 -1 3 数据规模： 对于 \(30\%\) 的数据， \(\texttt{字符串长度} \le 100\) 对于 \(100\%\) 的数据，\(\texttt{字符串长度} \le 10^5,~1\le T\le 10\) 题解： 暴力的解法就是遍历 \(t\) ，然后维护一个指针 \(p\) 在 \(s\) 上跳 仔细观察可以发现，如果 \(s=\tt...

CF553A Kyoya and Colored Balls 题解 题目链接：CF553A Kyoya and Colored Balls 题意： 一个袋子中有 \(n\) 个彩球，他们用 \(k\) 种不同的颜色染色。颜色被从 \(1\) 到 \(k\) 编号。同一种颜色的球看成是一样的。现在从袋中一个一个的拿出球来，直到拿完所有的球。对于所有颜色为 \(i(1 \le i \le k-1)\) 的球，他的最后一个球总是在编号比他大的球拿完之前拿完，问这样情况有多少种，答案对 \(10^9+7\) 取模。 输入单组测试数据。 第一行给出一个整数 \(k(1 \le k \le 1000)\)，表示球的种类。 接下来 \(k\) 行，每行一个整数 \(c_i\)，表示第 \(i\) 种颜色的球有 \(c_i\) 个 \((1 \le c_i \le 1000)\)。 球的总数目不超过 \(1000\)。 发烧真的无聊所以就写写题目啥的吧23333 考虑依次插入每种颜色的球，不妨设现在要插入的球颜色为 \(i\) ，有 \(x_i\) 个 设 \(n_i\) 为之前已经插入的球...

初赛复习 较为笼统而简洁的概括。 考试只要细心，不会的猜，就能过线。 IT发展历史 第一台计算机：ENIAC，1946年 应用：计算，数据储存处理，通信，辅助工作等 第一个程序员：Ada（女），有为此命名的程序语言 图灵奖（计算机），菲尔兹奖（数学），诺贝尔奖（物化生经济文学和平） ACM（美国计算机学会）IEEE（电气电子工程师学会）CCF（懂得都懂） 图灵奖由ACM设立，获得图灵奖的华人学者只有姚期智一人，名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵，是计算机界最负盛名、最崇高的一个奖项，有“计算机界的诺贝尔奖”之称。 计算机组成 冯诺依曼结构： 输入设备：将信息输入进计算机的是输入设备 输出设备：将计算机的信息输出给人的是输出设备 特例：触摸屏既是输入设备又是输出设备 CPU字长：32位/64位 （CPU一次能并行处理的二进制位数，一定是8的倍数） 位（Bit）：一个01 字节（Byte）：八个01 1PiB=1024TiB, 1TiB=1024GiB, 1GiB=1024KiB, 1KiB=1024Byte, 1Byte=8Bit 1Mib=1024Kib, ...