Q779’s Blog

CF839C Journey 题解 题目链接：CF839C Journey 题意： 在七大王国里有 \(n\) 个城市和 \(n-1\) 条道路，每条道路连接两个城市，并且通过这些道路我们可以从任何一个城市到达任何一个城市。 cxy 和她的妹纸在第一个城市骑上马，她们要通过这些路开始一次旅行。但是有雾，所以她们看不见她们的马带她们去了哪里。当马抵达一个城市的时候（包括第一个城市），它会去跟当前这个城市相连的城市。但是这是一匹奇怪的马，它只去她们以前没有去过的城市。在每个城市，马以相同的概率移动去上述符合要求的城市，并且当没有这样的城市（可走）时，马就停下了。 每条路的长度都是 \(1\)，旅行从城市 \(1\) 开始，问这次旅行的期望长度（旅行长度的期望值）是多少？你可以通过这个链接来阅读一些关于期望（平均）值的文字。 输入格式： 第一行包含一个整数 \(n\)（\(1 \leq n \leq 100000\)）——城市的数量。 下来是 \(n-1\) 行，这些行中的第 \(i\) 行包含两个整数 \(u\) 和 \(v\)（\(1 \leq u,v \leq n\)，\(u ...

UOJ387 【UNR #3】To Do Tree 题解 题目链接：#387. 【UNR #3】To Do Tree 题意： 有一棵 \(n\) 个节点的有根树，\(1\) 号点为根节点。第 \(i\) 的父节点为 \(f_i\) (\(1\leq f_i < i \leq n\))。你每星期可以选择不超过 \(m\) 个节点删掉，需要保证被删掉的节点是没有父节点的。删完后，会剩下一个森林 (若干棵树)。求最少多少星期才能删完所有的节点。 输入格式： 第一行包含两个正整数 \(n,m\) (\(1\leq m\leq n\le 10^5\))。 第二行包含 \(n-1\) 个正整数 \(f_2,f_3,\cdots,f_n\) (\(1\leq f_i<i\leq n\))。 输出格式： 第一行输出一个整数 \(t\)，表示最少需要的时间。 接下来 \(t\) 行，第 \(i\) 行表示第 \(i\) 星期删的点，其中第一个整数 \(s_i\) 表示这周删的点的个数，接下来 \(s_i\) 个整数分别是这周肝的点的标号。 考虑贪心，每次选出子树大小最大的 \(m\...

洛谷P1021 [NOIP1999 提高组] 邮票面值设计 题解 题目链接：P1021 [NOIP1999 提高组] 邮票面值设计 题意： 给定一个信封，最多只允许粘贴 \(N\) 张邮票，计算在给定 \(K(N+K \le 15)\) 种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值 \(\mathrm{MAX}\)，使在 \(1\) 至 \(\mathrm{MAX}\) 之间的每一个邮资值都能得到。 例如，\(N=3\)，\(K=2\)，如果面值分别为 \(1\) 分、\(4\) 分，则在 \(1\sim 6\) 分之间的每一个邮资值都能得到（当然还有 \(8\) 分、\(9\) 分和 \(12\) 分）；如果面值分别为 \(1\) 分、\(3\) 分，则在 \(1\sim 7\) 分之间的每一个邮资值都能得到。可以验证当 \(N=3\)，\(K=2\) 时，\(7\) 分就是可以得到的连续的邮资最大值，所以 \(\mathrm{MAX}=7\)，面值分别为 \(1\) 分、\(3\) 分。 输入格式： \(2\) 个整数，代表 \(N\)，\(...

洛谷P1038 [NOIP2003 提高组] 神经网络 题解 题目链接：P1038 [NOIP2003 提高组] 神经网络 题意： 人工神经网络（Artificial Neural Network）是一种新兴的具有自我学习能力的计算系统，在模式识别、函数逼近及贷款风险评估等诸多领域有广泛的应用。对神经网络的研究一直是当今的热门方向，兰兰同学在自学了一本神经网络的入门书籍后，提出了一个简化模型，他希望你能帮助他用程序检验这个神经网络模型的实用性。 在兰兰的模型中，神经网络就是一张有向图，图中的节点称为神经元，而且两个神经元之间至多有一条边相连，下图是一个神经元的例子： 神经元〔编号为 \(i\)） 图中，\(X_1 \sim X_3\) 是信息输入渠道，\(Y_1 \sim Y_2\) 是信息输出渠道，\(C_i\) 表示神经元目前的状态，\(U_i\) 是阈值，可视为神经元的一个内在参数。 神经元按一定的顺序排列，构成整个神经网络。在兰兰的模型之中，神经网络中的神经元分为几层；称为输入层、输出层，和若干个中间层。每层神经元只向下一层的神经元输出信息，只从上一层神经元接受信息。...

UOJ228 基础数据结构练习题 题解 题目链接：UOJ228 基础数据结构练习题 题意： cxy 是一个热爱学习的女孩子，今天她想要学习数据结构技巧。 在看了一些博客学了一些姿势后，她想要找一些数据结构题来练练手。于是她的好朋友 q779 给她出了一道题。 给出一个长度为 \(n\) 的数列 \(A\)，接下来有 \(m\) 次操作，操作有三种: 对于所有的 \(i \in[l,r]\)，将 \(A_i\) 变成 \(A_i+x\) 。 对于所有的 \(i \in[l,r]\)，将 \(A_i\) 变成 \(\left\lfloor\sqrt{A_i}\right\rfloor\) 。 对于所有的 \(i \in[l,r]\)，询问 \(A_i\) 的和。 作为一个不怎么熟练的初学者，cxy 想了好久都没做出来。而可怜酱又外出旅游去了，一时间联系不上。 于是她决定向你寻求帮助：你能帮她解决这个问题吗？ 输入格式： 第一行两个数： \(n, m\) 。 接下来一行 \(n\) 个数 \(A_i\) 。 接下来 \(m\) 行中, 第 \(i\) 行第一个数 \(t_i\) ...

贪心算法学习笔记 咕咕咕… 施工中… 一、贪心的基本思想 贪心，显然是：每一步的决策都基于当前最大利益的选择。 什么是利益？利益就是对最终答案的贡献，是实际的贡献。 我们来看一道题：CF1399E1 Weights Division (easy version) 题解 题意： 给定一棵以 \(1\) 号点为根的带权有根树。 在每次操作中，你可以选择一条边 \(i\)，使得这条边的权值 \(w_i\) 变成 \(\lfloor \frac{w_i}{2} \rfloor\) 找到最小操作数，以满足所有从根到叶子的路径的权值之和不超过 \(S\)。 换句话说，如果设 \(w(i,j)\) 为从节点 \(i\) 到节点 \(j\) 的路径的权值，那么你需要使得 \(\sum_{v \in \mathtt{leaves}} w(\mathtt{root},v) \leq S\)，其中 \(\mathtt{leaves}\) 是所有叶子组成的集合。 不知道你们的想法是什么，反正我的初始想法是按「边权 \(\times\) 经过次数」贪心，不过这个是错误的。 正解是按照 「 \(\lef...

洛谷P5372 [SNOI2019]积木 题解 题目链接：P5372 [SNOI2019]积木 题意： 有一块 \(n\) 行 \(m\) 列的网格板， \(n,m\) 都是奇数。网格上平铺着一些 \(1\times 2\) 的积木。积木可以旋转，不能重叠。这些积木共有 \(\frac{nm-1}{2}\) 块，也就是说，网格板上只有一格的空位。 你可以做两种操作： 将一块与空白格相邻（指有公共边）的积木旋转 \(90^\circ\) 到空白格中； 将一块与空白格积木相邻的积木平移至空白格中。 如图所示（被移动的积木颜色较浅）： 请你用以上两种操作将给定的网格板变换为指定的状态。 输入格式： 第一行两个正奇数 \(n,m\) ，分别表示网格的行数和列数。 接下来 \(n\) 行，每行 \(m\) 个字符，描述网格板的初始状态： <表示这个格子是一块积木的左半部分； >表示这个格子是一块积木的右半部分； n表示这个格子是一块积木的上半部分； u表示这个格子是一块积木的下半部分； o表示这个格子是空的。 接下来另外 \(n\) 行，每行 \(m\) 个字符，描...

洛谷P3247 [HNOI2016]最小公倍数 题解 题目链接：P3247 [HNOI2016]最小公倍数 题意： 给定一张 \(N\) 个顶点 \(M\) 条边的无向图（顶点编号为 \(1,2,\ldots,n\) ），每条边上带有权值。所有权值都可以分解成 \(2^a\times 3^b\) 的形式。 现在有 \(q\) 个询问，每次询问给定四个参数 \(u,v,a\) 和 \(b\)，请你求出是否存在一条顶点 \(u\) 到 \(v\) 之间的路径，使得路径依次经过的边上的权值的最小公倍数为 \(2^a\times 3^b\)。 注意：路径可以不是简单路径。 输入格式： 输入文件的第一行包含两个整数 \(N\) 和 \(M\)，分别代表图的顶点数和边数。 接下来 \(M\) 行，每行包含四个整数 \(u,v,a,b\) 代表一条顶点 \(u\) 和 \(v\) 之间、权值为 \(2^a\times 3^b\) 的边。 接下来一行包含一个整数 \(q\)，代表询问数。 接下来 \(q\) 行，每行包含四个整数 \(u,v,a\) 和 \(b\)，代表一次询问。询问内容请参见...

洛谷P5443 [APIO2019] 桥梁 题解 题目链接：P5443 [APIO2019] 桥梁 题意： 圣彼得堡市内所有水路长度总和约 \(282\) 千米，市内水域面积占城市面积的 \(7\%\)。——来自维基百科 圣彼得堡位于由 \(m\) 座桥梁连接而成的 \(n\) 个岛屿上。岛屿用 \(1\) 到 \(n\) 的整数编号，桥梁用 \(1\) 到 \(m\) 的整数编号。每座桥连接两个不同的岛屿。有些桥梁是在彼得大帝时代建造的，其中一些是近期建造的。这导致了不同的桥梁可能有不同的重量限制。更具体地，只有重量不超过 \(d_i\) 的汽车才能通过第 \(i\) 座桥梁。有时圣彼得堡的一些桥梁会进行翻新，但这并不一定会使桥梁承重变得更好，也就是说，进行翻新的桥梁的 \(d_i\) 可能会增加或减少。你准备开发一个产品，用于帮助公民和城市客人。目前，你开发的模块要能执行两种类型的操作： 将桥梁 \(b_j\) 的重量限制改为 \(r_j\)。 统计一辆重为 \(w_j\) 的汽车从岛屿 \(s_j\) 出发能够到达多少个不同的岛屿。 请你回答所有第二种操作的答案。 输...

LOJ2406 「THUPC 2017」母亲节的礼物 / Gift 题目链接：#2406. 「THUPC 2017」母亲节的礼物 / Gift 题意： cxy 喜欢图，尤其是边数不太多的无向简单图。母亲节快到了，cxy 在纸上画了一张有 \(n\) 个节点、\(m\) 条边的无向简单图（即不存在重边、自环），保证每个点只和最多 \(7\) 个点相邻。接着，他想用 \(4\) 种不同的颜色给图中的节点进行染色，作为妈妈的母亲节礼物送给她。 cxy 希望染色之后的图尽量漂亮，他觉得相同颜色的点连成一片不好看。所以，他希望能给每对相邻的节点染上不同的颜色。遗憾的是，cxy 很快发现，在有些图中，这是不可能做到的。他不得不降低要求：每个点相邻的点中，至多有一个点和它的颜色相同。 限制条件放松了，问题也就变得简单了；但是 cxy 忙着做大作业，所以来找你帮忙。现在，请你告诉 cxy，是否能给图中每个点染上一个恰当的颜色，恰好满足 cxy 的要求？如果可以，请你给他指出一种染色方案；否则，只好残忍地告诉 cxy：impossible。 输入格式： 输入有多组数据，第一行一个整数 \(T(1...

SP6779 GSS7 - Can you answer these queries VII 题解 题目链接：SP6779 GSS7 - Can you answer these queries VII 题意： 给定一棵树，有 \(N~(N \le 100000)\) 个节点，每一个节点都有一个权值 \(x_i (|x_i| \le 10000)\) 你需要执行 \(Q~(Q \le 100000)\) 次操作： 1 a b 查询 (a,b) 这条链上的最大子段和，可以为空（即输出 \(0\) ） 2 a b c 将 (a,b) 这条链上的所有点权变为c \((|c| \le 10000)\) 输入格式： 第一行一个整数 \(N\) 接下来一行有 \(N\) 个整数表示 \(x_i\) 接下来 \(N-1\) 行，每行两个整数 \(u,v\) 表示 \(u\) 和 \(v\) 之间有一条边相连 接下来一行一个整数 \(Q\) 之后有 \(Q\) 行，每行诸如 1 a b 或者 2 a b c 输出格式： 对于每一个询问，输出答案。 首先套路地树剖一下，把问题转到区间上。 ...

SP2713 GSS4 - Can you answer these queries IV 题解 题目链接：SP2713 GSS4 - Can you answer these queries IV 题意： 维护一个数据结构，支持： 0 x y 把区间 \([x,y]\) 内的每个数开方，下取整 1 x y 询问区间 \([x,y]\) 的每个数的和 有多组数据，数据以EOF结束，对于每组数据，输出数据的序号，每组数据之后输出一个空行。 不保证给出的区间\([x, y]\) 有 \(x \le y\) ，如果 \(x>y\) 请交换 \(x,y\) 。 数据范围： \(1 \le n,m \le 10^5, \sum a_i \le 10^{18}\) 区间开平方还是比较经典的。因为 \(\sqrt{a + b} \not\Leftrightarrow \sqrt{a} + \sqrt{b}\) ，即开方不具有传递性， 所以我们只能暴力修改。但是因为 \(\sqrt{1} = 1\) ，且 \(\left\lfloor\sqrt[T]{10^{18}}\right\...