Q779’s Blog

CF1311E Construct the Binary Tree 题解 题目链接：CF1311E Construct the Binary Tree 题意： 要求构造一个 \(n\) 个节点的二叉树（每个节点拥有不超过 \(2\) 个孩子），节点 \(1\) 为根，要使所有节点到根的距离之和为 \(d\) 。要求先判断可不可以构造，如果可以输出 YES ，下一行输出 2 到 n 号节点的父亲节点，否则输出 NO 。有多组询问。 输入格式： The first line of the input contains one integer \(t\) ( \(1 \le t \le 1000\) ) — the number of test cases. The only line of each test case contains two integers \(n\) and \(d\) ( \(2 \le n, d \le 5000\) ) — the number of vertices in the tree and the required sum of depths...

CF1322C Instant Noodles 题解 题目链接：CF1322C Instant Noodles 题意： 有\(t\)组测试数据。 给出一张点数为\(2N\)的二分图，其中右侧的第\(i\)个点有点权为\(c_i\)。 令\(S\)表示左侧点的一个非空点集，设\(f(S)\)表示右侧点中至少与\(S\)中一个点相连的点的点权和。 请你求出，对于所有非空集合\(S\)，\(f(S)\)的\(\gcd\)为多少。 \(1 \leq t,\sum n,\sum m \leq 5\times 10^5\)，\(1 \leq c_i \leq 10^{12}\)。 输入格式： The first line contains a single integer \(t\)(\(1 \leq t \leq 500\,000\)) — the number of test cases in the given test set. Test case descriptions follow. The first line of each case description contai...

CF1324F Maximum White Subtree 题解 题目链接：CF1324F Maximum White Subtree 题意： 给定一棵 \(n\) 个节点无根树，每个节点 \(u\) 有一个颜色 \(a_u\)，若 \(a_u\) 为 \(0\) 则 \(u\) 是黑点，若 \(a_u\) 为 \(1\) 则 \(u\) 是白点。 对于每个节点 \(u\)，选出一个包含 \(u\) 的连通子图，设子图中白点个数为 \(\mathtt{cnt_1}\)，黑点个数为 \(\mathtt{cnt_2}\)，请最大化 \(\mathtt{cnt_1 - cnt_2}\)。并输出这个值。 \(1 \leq n \leq 2 \times 10^5\)，\(0 \leq a_u \leq 1\)。 换根dp简单题，先钦定 \(1\) 为根，然后令 \(a_u = 2a_u - 1\) （即 \(1\) 和 \(-1\) ） 设 \(f_i\) 表示 \(i\) 所在子树的最大值，\(g_i\) 为 \(i\) 为根时的最大值，则 \[ f_u = a_i + \sum_...

CF1325C Ehab and Path-etic MEXs 题解 题目链接：CF1325C Ehab and Path-etic MEXs 题意： 给定一个 \(n\) 个节点 \(n-1\) 条边的树 要求给边重新标注边权 分别为 \(0,1,2...n-2\) 。 然后使得树上任意两点 \(u,v\) 的 \(\mathrm{MEX}(u,v)\) 的最大值最小。 \(\mathrm{MEX}(u,v)\) 是 \(u\) 到 \(v\) 的简单路径没有出现的自然数中最小的数。 输入格式： The first line contains the integer \(n (2 \le n \le 10^5)\) — the number of nodes in the tree. Each of the next \(n-1\) lines contains two space-separated integers \(u\) and \(v\) \(( 1 \le u,v \le n )\) that mean there’s an edge between nodes...

CF1328E Tree Queries 题解 题目链接：CF1328E Tree Queries 题意： 给你一个以 \(1\) 为根的有根树. 每回询问 \(k\) 个节点 \({v_1, v_2 \cdots ,v_k}\) 求出是否有一条以根节点为一端的链使得询问的每个节点到此链的距离均 \(\leq 1\). 只需输出可行性, 无需输出方案。 懒得修题面，输出 YES 或 NO 就好了。 \(2\le n \le 2\times 10^5,1\le ~\sum k \le 2\times 10^5\) 。 钦定 \(1\) 为根，并钦定 \(1\) 的父亲也为 \(1\) ，则合法的点的父亲均在一条链上。 判断一个结点 \(y\) 是否在 \(x\) 的子树内： \[ \mathtt{dfn[x] \le dfn[y] \land dfn[y] < dfn[x] + sz[x]} \] 时间复杂度 \(\mathcal{O}(n + \sum k \log \sum k)\) 代码： #include <bits/stdc++.h> using name...

CF1388C Uncle Bogdan and Country Happiness 题解 题目链接：CF1388C Uncle Bogdan and Country Happiness 题意： 给出一颗根节点为 \(1\) 的树，对于每个节点 \(i\)，有 \(p_i\) 个人的家在节点 \(i\) 上。 一开始所有人都在根节点上，然后每个人会往家沿着最短路走。 每个人出发时有一个心情，可能是好心情也可能是坏心情，在经过一条边时，心情可能由好变坏，但是不可能由坏变好。 每个点有一个幸福检测器，最后的检测结果为：所有经过该节点的人中，好心情的人数减坏心情的人数。 现在给出 \(h_i\)，问有没有可能最后每个节点的检测结果恰好为 \(h_i\)。 输入格式： 第一行一个整数 \(t\) 表示有多少组数据。 每组数据中，第一行两个整数 \(n,m(1 \le n \le 10^5 , 0 \le m \le 10^9)\)，表示节点数和总人数。 第二行 \(n\) 个整数表示 \(p_i(0 \le p_i \le m,\sum p_i = m)\)。 第三行 \(n\) 个整...

CF1369D TediousLee 题解 题目链接：CF1369D TediousLee 题意： 首先，我们定义 RDB 为一棵具有特殊性质的树，它有一个级别 \(\mathtt{level}\)。 一个级别为 \(1\) 的 RDB 是一个单独的节点。 接着，对于所有 \(i>1\)，级别为 \(i\) 的 RDB 的构成方法如下。 先求出级别为 \(i-1\) 的 RDB，然后对于该 RDB 中的每个节点 \(x\)。 如果 \(x\) 没有孩子，那么给他加上一个孩子。 如果 \(x\) 只有一个孩子，那么给他加上两个孩子。 如果 \(x\) 已经有了超过一个孩子，那么我们跳过节点 \(x\)。 以下是 \(1\le n \le 3\) 的所有 RDB 接下来，我们定义一个 claw （见下图），它也是一棵具有特殊性质的树，并且将节点 \(1\) 称为这个 claw 的中心，其他的称为底部节点。 现在，给出一个级别为 \(n\) 的 RDB，初始时他上面的所有节点都为绿色，你可以进行一些操作。 对于每次操作，你需要在给出的 RDB 中找到一个 claw，...

CF1263D Secret Passwords 题解 题目链接：CF1263D Secret Passwords 题意： 给定\(n\)个字符串 - 如果存在一个或多个字母同时在字符串\(a\)和\(b\)中出现 这\(a\)和\(b\)就被分在同一组 - 如果\(a\)和\(c\)在同一组 \(b\)和\(c\)在同一组 则\(a\)和\(b\)也在同一组 问所有的字符串最后被分成几组。 输入格式: The first line contain integer \(n (1 \le n \le 2 \times 10^5)\) — number of passwords in the list. Next \(n\) lines contains passwords from the list – non-empty strings \(s_i\) , with length at most \(50\) letters. Some of the passwords may be equal. It is guaranteed that the total length o...

洛谷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]...