Q779’s Blog

CF689D Friends and Subsequences 题解 题目链接：CF689D Friends and Subsequences 题意： 给定序列 \(a\) 和序列 \(b\)，长度均为 \(n\)。问有多少组 \((l,r)\)，满足 \(1\le l\le r\le n\) 且 \(\displaystyle \max_{i=l}^r a_i=\min_{i=l}^r b_i\) \(1\le n\le 2\times 10^5\)，\(|a_i|,|b_i|\le 10^9\)。 输入格式： The first line contains only integer \(n\) (\(1\leq n\leq 200000\)). The second line contains \(n\) integer numbers \(a_{1}, a_{2}, \ldots, a_{n}\) (\(-10^9 \leq a_i \leq 10^9\)) — the sequence \(a\). The third line contains \(n\) int...

CF1228C Primes and Multiplication 题解 题目链接：CF1228C Primes and Multiplication 题意： 首先先介绍一些涉及到的定义： 定义 \(\mathbb{P}(x)\) 表示x的质因子集合。举例来说，\(\mathbb{P}(140) = \{2, 5, 7\}\)，\(\mathbb{P}(169) = \{13\}\)。 定义 \(g(x, p)\) 表示存在一个最大的 \(k \in \mathbb{N}_+\) ，使得 \(x\) 可以被 \(p^k\) 整除（ 即\(p^k \mid x \ \land\ p^{k+1}\not\mid x\) ），那么 \(g(x, p) = p^k\) 。举例来说： \(g(45, 3) = 9\) （ \(45\)可以被 \(3^2 = 9\) 整除但是不能被 \(3^3=27\) 整除） \(g(63, 7) = 7\) （ \(63\) 可以被 \(7^1 = 7\) 整除但是不能被 \(7^2=49\) 整除） 定义 \(f(x, y)\) 表示所有 \(g...

洛谷P4046 [JSOI2010]快递服务 题解 题目链接：P4046 [JSOI2010]快递服务 题意： 「飞奔」快递公司成立之后，已经分别与市内许多中小企业公司签订邮件收送服务契约。由于有些公司是在同一栋大楼内，所以「飞奔」公司收件的地点（收件点）最多只有 \(m\) 点（\(1,2,\dots,m\)），因此「飞奔」仅先行采购了三辆货车并聘用了三名司机，每天早上分别从收件地点 \(1,2,3\) 出发。而在与客户的服务契约中有明确订约：「飞奔」必须在客户提出邮件寄送要求的隔天派人至该公司（地点）收件。 为了能更有效率的服务客户并节省收件时间，该公司设立了收件服务登记网站，客户如有邮件需要寄送，必须在需要收件的前一天就先上网登记。为了节省油量，「飞奔」就利用晚上先行安排三位司机隔天的收件路线。每位司机至各地点收件的顺序应与各公司上网登记的顺序相符且必须能在最省油的情况下完成当天所有的收件服务。因此每位司机有可能需要在不同时间重复到同一地点收件，或不同的司机有可能需在不同的时间点前往同一地点收件。 如下面范例二（收件公司地点依序为：4 2 4 1 5 4 3 2 1）所示...

UVA12716 GCD等于XOR GCD XOR 题解 题目链接：UVA12716 GCD等于XOR GCD XOR 题意： 求 \[ \sum_{1 \le a \le n}\sum_{1 \le b \le a} \left[\gcd(a,b) = a \oplus b\right] \] 其中 \(1 \le n \le 3\times 10^7\) 令 \(c = \gcd(a,b)\) ，则 \(a - b \le a \oplus b = c\) 令 \(a = k_1c,~ b = k_2c~(k_1 > k_2)\) 则 \(a - b = (k_1 - k_2) c \Rightarrow a - b \ge c\) 则 \(a - b = c = a\oplus b\) 。这样枚举 \(a,c\) 就可以啦~ 时间复杂度 \(\mathcal{O}(n \log n)\) 代码： #include <bits/stdc++.h> using namespace std; // #define int long long // #define ...

UVA11806 Cheerleaders 题解 题目链接：UVA11806 Cheerleaders 题意： 你有一个\(n \times m\) 的网格图，现在你要将 \(k\) 个人放在网格中，满足一下条件： 网格图的四个边都至少有一个人。 每个格子上不能有两个人。 每个人必须都有位置。 四个角的人可以同时算作在两个边上。 求合法方案数。 输入格式： The first line of input contains a positive integer \(T \leq 50\), which denotes the number of test cases. \(T\) lines then follow each describing one test case. Each case consists of three nonnegative integers, \(2 \leq M,N \leq 20\) and \(K \leq 500\). Here \(M\) is the number of rows and \(N\) is the number of...

洛谷P5157 [USACO18DEC]The Cow Gathering P 题解 题目链接：P5157 [USACO18DEC]The Cow Gathering P 题意： 奶牛们从世界各地聚集起来参加一场大型聚会。总共有 $ N $ 头奶牛， $ N-1 $ 对奶牛互为朋友。每头奶牛都可以通过一些朋友关系认识其他每头奶牛。 她们玩得很开心，但是现在到了她们应当离开的时间了，她们会一个接一个地离开。她们想要以某种顺序离开，使得只要至少还有两头奶牛尚未离开，所有尚未离开的奶牛都还有没有离开的朋友。此外，由于行李寄存的因素，有 $ M $ 对奶牛 $ (a_i,b_i) $ 必须满足奶牛 $ a_i $ 要比奶牛 $ b_i $ 先离开。注意奶牛 $ a_i $ 和奶牛 $ b_i $ 可能是朋友，也可能不是朋友。 帮助奶牛们求出，对于每一头奶牛，她是否可以成为最后一头离开的奶牛。可能会发生不存在满足上述要求的奶牛离开顺序的情况。 输入格式： 输入的第 $ 1 $ 行包含两个空格分隔的整数 $ N $ 和 $ M $ 。 输入的第 $ 2 i N $ 行，每行包含两个整数 $...

CF480D Parcels 题解 题目链接：CF480D Parcels 题意： 有 \(n\) 件包裹，每个包裹是一个盒子，都有它自身的质量和载重 (即它上方能承受的最大质量)。cxy 最近得到了一个新的包裹处理系统，这个系统以如下方式工作。初始时，有一个（可以堆放盒子的）平台，它的载重为 \(S\)，接下来，你能以如下的规则在平台上堆放盒子： 如果平台是空的，你可以将盒子堆放在平台上，否则，你只能在新的盒子放在最高的盒子上面。 任何时刻，（平台上）所有盒子的总质量不能超过 \(S\) （即平台的载重）。 对任意一个盒子，任何时刻，在它上面的所有盒子的总质量不能超过这个盒子的载重。 并且你只能取走当前位于最上面的盒子（即形成栈型结构）。 系统接收到了这 \(n\) 件包裹，已知第 \(i\) 个包裹在时刻 \(\text{in}_i\) 出现，它的质量和载重分别为 \(w_i,s_i\)，每个包裹都有它的价值，其中第 \(i\) 个包裹的价值为 \(v_i\)。然而，为了获得（赚得）这 \(v_i\) 的价值，这个系统要求它刚好在时刻 \(\text{out}_i\) ...

洛谷P3451 [POI2007]ATR-Tourist Attractions 题解 题目链接：P3451 [POI2007]ATR-Tourist Attractions 题意： 给出一张有 \(n\) 个点 \(m\) 条边的无向图，每条边有边权。 你需要找一条从 \(1\) 到 \(n\) 的最短路径，并且这条路径在满足给出的 \(g\) 个限制的情况下可以在所有编号从 \(2\) 到 \(k+1\) 的点上经过。 每个限制条件形如 \(r_i, s_i\)，表示经过 \(s_i\) 之前必须曾经过 \(r_i\) 。 输入格式： 第一行三个整数 \(n,m,k\)。 之后 \(m\) 行，每行三个整数 \(p_i, q_i, l_i\)，表示在 \(p_i\) 和 \(q_i\) 之间有一条权为 \(l_i\) 的边。 之后一行一个整数 \(g\)。 之后 \(g\) 行，每行两个整数 \(r_i, s_i\)，表示一个限制条件。 输出格式： 输出一行一个整数，表示最短路径的长度。 数据范围： \(2\le n\le2\times10^4,~1\le m\le2\ti...

CF526D Om Nom and Necklace 题解 题目链接：CF526D Om Nom and Necklace 题意： 已知长度为 \(n\) 的字符串 \(s\)，对于 \(s\) 的每一个前缀子串（即对于每一个 \(i\)，\(s\) 中从第 \(1\) 个字符到第 \(i\) 个的所有字符组成的字符串，\(1\leq i\leq n\)），如果满足 \(\texttt{ABABA...BA}\) 的形式（\(A\)、\(B\) 可以为空，也可以是一个字符串，\(A\) 有 \(k+1\) 个，\(B\) 有 \(k\) 个），则请输出 \(1\)；否则输出 \(0\)，注意：\(n\) 和 \(k\) 给定。 输入格式： The first line contains two integers \(n\), \(k\) (\(1\leq n,k\leq 10^6\)) — the number of beads on the thread that Om Nom found and number \(k\) from the definition of the...

LOJ6669 Nauuo and Binary Tree 题解 题目链接：#6669. Nauuo and Binary Tree 题意： Nauuo 是一个喜欢二叉树的女孩子（cxy 就不一样，她喜欢妹纸）。 这天，她创造了一个有 \(n\) 个节点的二叉树。节点的编号从 \(1\) 到 \(n\) ，其中 \(1\) 是二叉树的根节点。 不过，她不记得这棵二叉树具体长什么样子了，她只记录了二叉树上任意两个节点之间的距离。你可以通过向她询问有关距离的信息来还原这棵二叉树，两个节点之间的距离定义为它们之间最短路上的边数。 你可以向 Nauuo 询问不超过 \(30000\) 次有关距离的信息。你只需要告诉她 \(2\sim n\) 号节点的父亲的编号就可以了。 交互方式 最开始，交互器会向标准输入中输入一个正整数 \(n\)。 接下来，你可以通过标准输出向交互器询问两个节点之间的距离。 对于一次询问，你需要输出一行 ? u v 表示你想让 Nauuo 告诉你节点 \(u\) 和节点 \(v\) 在这棵二叉树上距离，然后换行并刷新缓存。 在每次询问后，交互器会向标准输入中输入一...

CF1174F Ehab and the Big Finale 题解 题目链接：CF1174F Ehab and the Big Finale 题意： 这是一道交互题。 你有一棵 \(n\) 个节点的有根树，\(1\) 号点是根节点。这棵树中有一个隐藏的节点 \(x\) ，你需要通过询问把 \(x\) 找出来。你可以进行如下两种询问： 1、\(d\) \(u\) \((1\le u\le n)\)。交互库会返回节点 \(u\) 和 \(x\) 的距离。 2、\(s\) \(u\) \((1\le u\le n)\)。交互库会返回从 \(u\) 到 \(x\) 的路径上第二个点的标号。注意，你询问的 \(u\) 必须是 \(x\) 的祖先，否则会 Wrong Ans。 你需要在不超过 \(36\) 次询问之内找出 \(x\) 。\(x\) 是预先设定好的，不会随着询问而改变。 输入格式： The first line contains the integer \(n ( 2 \le n \le 2 \cdot 10^5)\) — the number of nodes in th...

LOJ6671 EntropyIncreaser 与 Minecraft 题解 题目链接：#6671. EntropyIncreaser 与 Minecraft 题意： 求方程 \(\left|x_1\right|+\left|x_2\right|+\cdots+\left|x_n\right| \leq p\) 的整数解的组数。 输入格式 共一行, 包含两个正整数 \(n, p\left(n \leq 10^6 ; p \leq 10^9\right)\) ，含义见题目描述。 输出格式： 输出一行一个整数, 表示方程的整数解的组数模 \(10^9+7\) 的值。 注意到除了 \(0\) 以外每个整数都会提供两次贡献，考虑枚举 \(0\) 的个数 \(n-k\) ， 那么剩下的数要求绝对值大于 \(0\) ，这样方案数要先乘上符号位的 \(2^k\) 。 设 \(y_i = x_i + 1\) ，其中 \(x_i \ge 0\) ，则需要求如下方程的方案数： \[ \sum_{i=1}^k y_i \leq p \Rightarrow \sum_{i=1}^k x_i \le...