Q779’s Blog

CF1119G Get Ready for the Battle 题解 题目链接：CF1119G Get Ready for the Battle 题意： 敌方有 \(m\) 个军队，血量分别为 \(\mathtt{hp}_1, \mathtt{hp}_2, \cdots, \mathtt{hp}_m\)。你有 \(n\) 个军队，你需要将它们分成 \(m\) 个组，其中第 \(i\) 组有 \(s_i\) 个军队 \((0 \leq s_i \leq n\land \sum s_i = n)\)。 对于每轮攻击，你可以对这 \(m\) 个组中的每个组 \(i\)，指定一个 (唯一确定的) 敌人 \(e = e(i)\)，并对其进行攻击。攻击完毕后，\(\mathtt{hp}'_e \gets \mathtt{hp}_e - s_i\)。如果一轮攻击后 \(\mathtt{hp}'_i \leq 0\)，则认为敌人 \(i\) 已经被打败。 求至少需要几轮攻击，才能打败敌方的所有军队。 输入格式: 第一行包含两个正整数 \(n, m(1 \leq m \leq ...

洛谷P5292 [HNOI2019]校园旅行 题解 题目链接：P5292 [HNOI2019]校园旅行 题意： HNOI2019 day2t1就这么难了，好珂怕 某学校的每个建筑都有一个独特的编号。一天你在校园里无聊，决定在校园内随意地漫步。 你已经在校园里呆过一段时间，对校园内每个建筑的编号非常熟悉，于是你情不自禁的把周围每个建筑的编号都记了下来——但其实你没有真的记下来，而是把每个建筑的编号除以 \(2\) 取余数得到 \(\mathtt{0}\) 或 \(\mathtt{1}\)，作为该建筑的标记，多个建筑物的标记连在一起形成一个 \(\mathtt{01}\) 串。 你对这个串很感兴趣，尤其是对于这个串是回文串的情况，于是你决定研究这个问题。 学校可以看成一张图，建筑是图中的顶点，而某些顶点之间存在无向边。对于每个顶点我们有一个标记（\(\mathtt{0}\) 或者 \(\mathtt{1}\) ）。每次你会选择图中两个顶点，你想知道这两个顶点之间是否存在一条路径使得路上经过的点的标记形成一个回文串。 一个回文串是一个字符串使得它逆序之后形成的字符串和它自己相同，比如...

洛谷P3420 [POI2005]SKA-Piggy Banks 题解 题目链接：P3420 [POI2005]SKA-Piggy Banks 题意： cxy 有 \(n\) 个小猪存钱罐，每个存钱罐只能用钥匙打开或者砸开。cxy 已经把每个存钱罐的钥匙放到了某些存钱罐里。 cxy 现在想买一台汽车于是要把所有的钱都取出来。她想尽量少的打破存钱罐取出所有的钱，问最少要打破多少个存钱罐。 输入格式： 第一行包含一个正整数 \(n (n\le10^6)\) ，表示存钱罐的总数。 接下来的 \(n\) 行，每行一个整数，第 \(i+1\) 行的整数代表第 \(i\) 个存钱罐对应的钥匙放置的存钱罐编号。 输出格式： 输出一行一个整数，表示最少要打破多少个存钱罐。 我们可以把每个存钱罐 \(u\) 向其钥匙所在的存钱罐 \(v\) 建有向边。 不难发现这会形成一个基环内向树（森林），我们只要把环上的一个点敲掉就好了，可以用并查集维护。 时间复杂度 \(\mathcal{O}(n \log n)\) 代码： #include <bits/stdc++.h> using names...

洛谷P3778 [APIO2017] 商旅 题解 题目链接：P3778 [APIO2017] 商旅 题意： 在广阔的澳大利亚内陆地区长途跋涉后，你孤身一人带着一个背包来到了科巴。你被这个城市发达而美丽的市场所深深吸引，决定定居于此，做一个商人。科巴有\(N\)个集市，集市用从 \(1\) 到 \(N\) 的整数编号，集市之间通过 \(M\) 条单向道路连接，通过每条道路都需要消耗一定的时间。 在科巴的集市上，有 \(K\) 种不同的商品，商品用从 \(1\) 到 \(K\) 的整数编号。每个集市对每种商品都有自己的定价，买入和卖出商品的价格可以是不同的。并非每个集市都可以买卖所有的商品：一个集市可能只提供部分商品的双向交易服务；对于一种商品，一个集市也可能只收购而不卖出该商品或只卖出而不收购该商品。如果一个集市收购一种商品，它收购这种商品的数量是不限的，同样，一个集市如果卖出一种商品，则它卖出这种商品的数量也是不限的。 为了更快地获得收益，你决定寻找一条盈利效率最高的环路。环路是指带着空的背包从一个集市出发，沿着道路前进，经过若干个市场并最终回到出发点。在环路中，允许多次经过同...

P=NP? (Easy Version) 这篇文章试图用较为简单的方法 解释什么是 P 问题、NP 问题、NPC 问题 和 NP-Hard 问题。 更为严谨的解释，将在 Hard Version 中描述。目前还在咕咕咕中。 什么是 NP 问题？ \(\mathtt{P}\) ：能在多项式时间内解决的问题。 \(\mathtt{NP}\) ：不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验证的问题。 \(\mathtt{NPC}\) ：即 NP 完全问题。 所有 NP 问题在多项式时间内都能约化到它的 NPC 问题。 因此解决了 NPC 问题，所有 NP 问题也都得到解决。 \(\mathtt{NP-Hard}\) ：NP 困难问题。所有NP问题在多项式时间内都能约化到它的问题（不一定是NP问题）。 多项式时间 简单来说，如果存在正数 \(k\) 使得一个算法时间复杂度为 \(\mathcal{O}(n^k)\) （渐进上界记号），其中 \(n\) 为问题规模（输入的长度），则称这个算法是多项式时间的。 多项式时间的一些常见例子如 \(\math...

树的直径 前置知识：[树的相关概念] 树的直径定义为任意两节点之间最长的简单路径。 注意树的直径是一条链，而不是一个数。 树的直径一般有两种求法：「两遍 dfs」 和 树形dp。 前者只适用于正权图，而后者可以用于任意带权图。 具体地，「两遍 dfs」 算法流程如下： 随便找个节点跑一遍 dfs ，找到距离它最远的节点 \(x\) 。 以节点 \(x\) 为起点再跑一次 dfs ，得到距离 \(x\) 最远的节点 \(y\) 。 链 \(x \leadsto y\) 为原树的直径。 树形dp的方法如下： 钦定节点 \(1\) 为根（如果是无根树的话） 设 \(d_{1,i},~d_{2,i}\) 分别表示以节点 \(i\) 为端点的最长&次长链 随便维护一下，然后求出 \(d_{1,1},d_{2,1}\) （方便起见，记 \(d_1 = d_{1,1},~d_2 = d_{2,1}\) ） 则最后的答案为 \(\max\{d_1,d_1+d_2\}\) 对于有负边权的情况dfs是错的，例如 如果不巧从 \(1\) 开始跑就会挂。因为答案是 4-3-5 。 ...

图论相关概念 是时候写这篇总结了。部分内容还有待考证。 不过大部分都是直接从 参考文献[1] 搬过来的。 图的定义 图 (graph) 是一个二元组 \(G=(V(G), E(G))\) ，其中： \(V(G)\) 是非空集，称为 点集 (vertex set) 。 对于 \(V(G)\) 中的每个元素，我们称其为 顶点 (vertex) 或 节点 (node)，简称 点 。 \(\left| V(G) \right|\) 也被称作图 \(G\) 的 阶 (order)。 \(E(G)\) 为 \(V(G)\) 各节点之间边的集合，称为 边集 (edge set)。 形象地说，图是由若干点以及连接点与点的边构成的。 事实上，我们常用 \(G=(V,E)\) 表示图，其中 \(V\) 表示点集，\(E\) 表示边集。 带权图 若 \(G\) 的每条边 \(e_k=(u_k,v_k)\) 都被赋予一个数作为该边的 权，则称 \(G\) 为 赋权图 或 带权图。 如果这些权都是正实数，就称 \(G\) 为 正权图。 有限图与无限图 设 \(G = (V,E)\) ，则 当 \(V...

CF329C Graph Reconstruction 题解 题目链接：CF329C Graph Reconstruction 题意： 给定一张含有 \(n\) 个点 \(m\) 条边的无向简单图 \(G = \left( V, E \right)\)，其中每个顶点的度数不超过 \(2\)。你需要构造一张新的无向简单图 \(G' = \left( V', E' \right)\)，满足如下条件： \(V' = V, \left| E' \right| = \left| E \right| = m\)。 \(E' \cap E = \varnothing\) ，即原图和新图中没有公共的边。 \(\Delta(G') \le 2\)，即新的图中每个顶点的度数均不超过 \(2\)。 注：其中 \(\Delta (G)\) 表示的是图 \(G\) 的最大度，下文中出现的 \(\delta(G)\) 表示的是图 \(G\) 的最小度。 输出任何一个满足上述三个条件的图 \(G'\)，或指出不存在。 输入格式： 第一行包含...

LOJ6568 「Project Euler 9」特殊勾股数 题解 题目链接：#6568. 「Project Euler 9」特殊勾股数 题意： 一组勾股数由三个自然数组成，\(a < b < c\) ，且 \[ a^2 + b^2 = c^2 \] 例如，\(3^2 + 4^2 = 9 + 16 = 25 = 5^2\)。 给出 \(N\)，请输出所有满足 \(a + b + c = N\) 的勾股数。 输入格式： 只有一行，一个整数 \(N\)。 输出格式： 多行，每行三个整数，\(a, b, c\) ，表示答案。 数据范围： 对于 \(100\%\) 的数据，\(N \leq 10^{12}\)。 想起上次做的圆上的整点，差点开始异想天开了 考虑一组 \(a,b,c\) 是勾股数的充要条件。 不妨设 \(a,b < c\) ，\(a,b\) 大小关系忽略，且 \(\gcd(a,b,c) = 1\) 。 则可以假设 \(a\) 为偶数，\(b,c\) 为奇数。 因为 \(a^2 + b^2 = c^2\) ，若 \(c\) 为偶数，则 \(a,b\) 均...

洛谷P4228 [清华集训2017] 榕树之心 题解 题目链接：P4228 [清华集训2017] 榕树之心 题意： 一棵榕树可以抽象成一棵 \(n\) 个结点的有根树，其中结点编号为 \(1 \sim n\) ，而 \(1\) 号点就是根节点。初始时，树只有一号点，而心也在一号点。之后每一步，树都会长出一个新结点，即某个和当前已经存在的某个结点相邻的结点被加入了树中，之后，心会沿着心到新加结点的简单路径移动一步。这棵 \(n\)个结点的树有很多种生长的顺序，不同的顺序可能会导致最终心的位置不同。现在，Evan和Lyra想知道，哪些结点可能是心在生长过程结束时停留的位置呢？ 例如一棵大小为 \(4\) 的树，连边为 \(\{\langle 1,2 \rangle,\langle 1,3 \rangle,\langle 1,4 \rangle\}\) ，我们有三种不同的生长顺序可以让心分别停留在 \(2,3,4\) 号节点上： 最终停留在 \(2\) 号点： 从1生长出3，心从1移动到3, 从1生长出4，心从3移动回1, 从1生长出2，心从1移动到2. 最终停留在 \(3\) 号点...

CF364D Ghd 题解 题目链接：CF364D Ghd 题意： 定义一组数 \(a_1, a_2, \cdots, a_n\) 的半最大公约数 (Greatest half-common divisor, GHD) 为最大的整数 \(d\)，满足 \(a_1, a_2, \cdots, a_n\) 中至少有 \(\left \lceil \frac{n}{2} \right \rceil\) 个 \(d\) 的倍数。 给定 \(n\) 个正整数 \(a_1, a_2, \cdots, a_n\)，请你求出它们的半最大公约数。 输入格式： 第一行包含一个正整数 \(n~(1\le n \leq 10^6)\)，表示数的个数。 第二行包含 \(n\) 个正整数 \(a_1, a_2, \cdots, a_n(1 \leq a_i \leq 10^{12})\)，表示这 \(n\) 个数的值。 输出格式： 输出一行一个整数，表示这些数的半最大公约数。 前置知识：\(d(10^{12}) \le 6720\) 。 注意到最终的 GHD 的集合 \(S\) 中，一定存在至少一个 \...

洛谷P3275 [SCOI2011]糖果 题解 题目链接：P3275 [SCOI2011]糖果 题意： 幼儿园里有 \(N\) 个小朋友，cxy 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，cxy 需要满足小朋友们的 \(K\) 个要求。幼儿园的糖果总是有限的，cxy 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。 输入格式: 输入的第一行是两个整数 \(N,K\)。接下来 \(K\) 行，表示这些点需要满足的关系，每行 \(3\) 个数字，\(X,A,B\) 。 如果 \(X=1\)， 表示第 \(A\) 个小朋友分到的糖果必须和第 \(B\) 个小朋友分到的糖果一样多； 如果 \(X=2\)， 表示第 \(A\) 个小朋友分到的糖果必须少于第 \(B\) 个小朋友分到的糖果； 如果 \(X=3\)， 表示第 \(A\) 个小朋友分到的糖果必须不少于第 \(B\) 个小朋友分到的糖果； 如果 \(X=4\...