Q779’s Blog

CF1204C Anna, Svyatoslav and Maps 题解 题目链接：CF1204C Anna, Svyatoslav and Maps 题意： 对于 \(n(n \le 100)\) 个点有向无环图，给出一个由 \(m(m \le 10^6)\) 个点组成的的路径 \(p\)（不保证是简单路径，但保证对于 \(1 \le i < m,p_i\) 与 \(p_{i+1}\) 之间有边）， 要求从 \(p\) 中选出一个最短的子序列 \(v\)（假设长度为 \(k\) ），满足 \(v_1=p_1,v_k=p_m\) ，并且 \(p\) 是按顺序经过 \(v\) 的最短路径之一。 输入格式: The first line contains a single integer \(n\) ( \(2 \le n \le 100\) ) — the number of vertexes in a graph. The next \(n\) lines define the graph by an adjacency matrix: the \(j\) -th cha...

CF1209D Cow and Snacks 题解 题目链接：CF1209D Cow and Snacks 题意： \(n\) 种小吃，\(k\) 个客人，每个人喜欢两种编号不同的小吃。但是每种小吃在小吃店里只有一坨。 客人按顺序进入小吃店，会买走所有她喜欢且仍在店铺里的小吃。如果一个客人买不到任何一束小吃，那么她就会十分沮丧导致变成肥宅。现在你可以自己安排这 \(k\) 个人的顺序，使得肥宅的数量最小。 注意，只拿到一种小吃的客人不会变成肥宅。 输入格式： The first line contains integers \(n\) and \(k\) ( \(2 \le n \le 10^5\) , \(1 \le k \le 10^5\) ), the number of snacks and the number of guests. The $ i $ -th of the following \(k\) lines contains two integers \(x_i\) and \(y_i\) ( \(1 \le x_i, y_i \le n\) , \(x_i...

MacOS vscode 缺省源&配置文件 MacOS 的 vscode 配置。ubuntu 的到时候再说。 缺省源 更新日期：2022年11月02日 { // Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and // description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are: // $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the // same ids a...

洛谷P8818 [CSP-S 2022] 策略游戏 题解 题目链接：P8818 [CSP-S 2022] 策略游戏 题意： 小 L 和小 Q 在玩一个策略游戏。 有一个长度为 \(n\) 的数组 \(A\) 和一个长度为 \(m\) 的数组 \(B\)，在此基础上定义一个大小为 \(n \times m\) 的矩阵 \(C\)，满足 \(C_{i j} = A_i \times B_j\)。所有下标均从 \(1\) 开始。 游戏一共会进行 \(q\) 轮，在每一轮游戏中，会事先给出 \(4\) 个参数 \(l_1, r_1, l_2, r_2\)，满足 \(1 \le l_1 \le r_1 \le n\)、\(1 \le l_2 \le r_2 \le m\)。 游戏中，小 L 先选择一个 \(l_1 \sim r_1\) 之间的下标 \(x\)，然后小 Q 选择一个 \(l_2 \sim r_2\) 之间的下标 \(y\)。定义这一轮游戏中二人的得分是 \(C_{x y}\)。 小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明...

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...