Q779’s Blog

洛谷P4229 某位歌姬的故事 题解 题目链接：P4229 某位歌姬的故事 题意： IA 是一名会唱歌的女孩子。 IOI2018 就要来了，IA 决定给参赛选手们写一首歌，以表达美好的祝愿。这首歌一共有 \(n\) 个音符，第 \(i\) 个音符的音高为 \(h_i\)。IA 的音域是 \(A\)，她只能唱出 \(1\sim A\) 中的正整数音高。因此 \(1\le h_i\le A\)。 在写歌之前，IA 需要确定下这首歌的结构，于是她写下了 \(Q\) 条限制，其中第 \(i\) 条为：编号在 \(l_i\) 到 \(r_i\) 之间的音符的最高音高为 \(m_i\)。在确定了结构之后，她就可以开始写歌了。不过她还是想知道，一共有多少种可能的歌曲满足她的所有限制？她听说你还有 9 个月就要去 IOI 了，于是希望你帮她计算一下这个值。 输入格式： 输入的第一行包含一个整数 \(T(T\le 20)\)，代表测试数据的组数。 每组数据的第一行包含三个正整数 \(n,Q,A\)。接下来 \(Q\) 行，每行三个整数 \(l_i,r_i,m_i\)，表示一条限制。保证 \(1\...

CF1187E Tree Painting 题解 题目链接：CF1187E Tree Painting 题意： 给定一棵 \(n\) 个节点的树，初始全是白点。 要求你做 \(n\) 步操作：每一次选定一个与一个黑点相隔一条边的白点将它染成黑点，然后获得该白点被染色前所在的白色联通块大小的权值。第一次操作可以任意选点。 求可获得的最大权值。 输入格式： The first line contains an integer \(n\) — the number of vertices in the tree ( \(2 \le n \le 2 \cdot 10^5\) ). Each of the next \(n - 1\) lines describes an edge of the tree. Edge \(i\) is denoted by two integers \(u_i\) and \(v_i\) , the indices of vertices it connects ( $1 u_i, v_i n $ , $ u_i v_i$ ). It is guaran...

洛谷P1402 酒店之王 题解 题目链接：P1402 酒店之王 题意： 小红花酒店的老板 cxy 想成为酒店之王，本着这种希望，第一步要将酒店变得人性化。由于很多来住店的旅客有自己喜好的房间色调、阳光等，也有自己所爱的菜，但是该酒店只有 \(p\) 间房间，一天只有固定的 \(q\) 道不同的菜，每个房间只能住一位客人，每道菜也只能给一位客人食用。 有一天来了 \(n\) 个客人，每个客人说出了自己喜欢哪些房间，喜欢哪道菜。但是很不幸，可能做不到让所有顾客满意（满意的条件是住进喜欢的房间且吃到喜欢的菜）。 要怎么分配，能使最多顾客满意呢？ 输入格式： 第一行给出三个整数，分别表示表示 \(n,p,q\)。 之后 \(n\) 行，每行 \(p\) 个整数，只可能是 \(0\) 或 \(1\)，第 \(i\) 行第 \(j\) 个数表示第 \(i\) 个人喜不喜欢第 \(j\) 个房间（\(1\) 表示喜欢， \(0\) 表示不喜欢）。 之后 \(n\) 行，每行 \(q\) 个整数，只可能是 \(0\) 或 \(1\)，第 \(i\) 行第 \(j\) 个数表示第 \(i\) 个...

模拟退火 学习笔记 模拟退火挺没有正确性的。真的是个玄学。 基本思想：如果新的状态的解更优则修改答案，否则以一定的概率接受新状态，这个概率为 \(\exp(\frac{-\Delta E}{t})\) 。 考前学学这个 ++rp 。 P1337 [JSOI2004] 平衡点 / 吊打XXX 求 \(n(n \le 10^3)\) 个点的带权类费马点。 三角形的不带权费马点就是 \(PA + PB + PC\) 取到最小值的点 \(P\) 。 #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f void up(int &x,int y) { x < y ? x = y : 0; } void down(int &x,int y) { x > y ? x = y : 0; } #define N ((int)(1e3+15)) int n,x[N],y[N],w[N]...

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'\)，或指出不存在。 输入格式： 第一行包含...