Q779’s Blog

洛谷P2572 [SCOI2010] 序列操作 题解 题目链接：P2572 [SCOI2010] 序列操作 题意： cxy 最近收到了一个 \(01\) 序列，序列里面包含了 \(n\) 个数，下标从 \(0\) 开始。这些数要么是 \(0\)，要么是 \(1\)，现在对于这个序列有五种变换操作和询问操作： 0 l r 把 \([l, r]\) 区间内的所有数全变成 \(0\) 1 l r 把 \([l, r]\) 区间内的所有数全变成 \(1\) 2 l r 把 \([l,r]\) 区间内的所有数全部取反，也就是说把所有的 \(0\) 变成 \(1\)，把所有的 \(1\) 变成 \(0\) 3 l r 询问 \([l, r]\) 区间内总共有多少个 \(1\) 4 l r 询问 \([l, r]\) 区间内最多有多少个连续的 \(1\) 对于每一种询问操作，cxy 都需要给出回答，聪明的程序员们，你们能帮助她吗？ 输入格式： 第一行两个正整数 \(n,m\)，表示序列长度与操作个数。 第二行包括 \(n\) 个数，表示序列的初始状态。 接下来 \(m\) 行，每行三个整...

洛谷P1438 无聊的数列 题解 题目链接：P1438 无聊的数列 题意： 维护一个数列 \(a_i\)，支持两种操作： 1 l r K D：给出一个长度等于 \(r-l+1\) 的等差数列，首项为 \(K\)，公差为 \(D\)，并将它对应加到 \([l,r]\) 范围中的每一个数上。即：令 \(a_l=a_l+K,a_{l+1}=a_{l+1}+K+D\ldots a_r=a_r+K+(r-l) \times D\)。 2 p：询问序列的第 \(p\) 个数的值 \(a_p\)。 输入格式： 第一行两个整数数 \(n,m\) 表示数列长度和操作个数。 第二行 \(n\) 个整数，第 \(i\) 个数表示 \(a_i\)。 接下来的 \(m\) 行，每行先输入一个整数 \(\mathtt{op}\)。 若 \(\mathtt{op}=1\) 则再输入四个整数 \(l,r,s,d\)； 若 \(\mathtt{op}=2\) 则再输入一个整数 \(p\)。 输出格式： 对于每个询问，一行一个整数表示答案。 数据范围： \(0\le n,m \le 10^5,~-200\le...

CF1387B2 Village (Maximum) 题解 题目链接：CF1387B2 Village (Maximum) 题意： 村里 \(n\) 个房子构成了一个 \(n\) 点 \(n-1\) 条边的树结构（下标从 \(1\) 开始），每条边长度均为 \(1\)。一开始每个房子里分别有一个村民。 现在所有村民都需要搬家（改变自己所在的点），搬家后依然需要满足每个房子里有且只有一个村民。也就是说，如果原本位于点 \(i\) 的村民搬到了点 \(v_i\)，那么应当满足： 对于任意点 \(i\)，有 \(i \neq v_i\)。 对于任意两个不同的点 \(i\) 与 \(j\)，有 \(v_i \neq v_j\)。 村民 \(i\) 搬家的花费是点 \(i\) 到点 \(v_i\) 的树上距离（即树上二点间相隔的边数），总花费为所有村民花费之和。求总花费的最大值及其方案。 输入格式： 第一行一个正整数 \(n\)，表示树的点数。 接下来 \(n-1\) 行每行二整数 \(a\) 和 \(b\)，表示树上有一条连接 \(a\) 和 \(b\)，长度为 \(1\) 的边。...

CF1393D Rarity and New Dress 题解 题目链接：CF1393D Rarity and New Dress 题意： cxy 要从一块 \(n\times m\) 的布料上裁一块菱形做裙子（不是给自己做。 这一块布料由 \(n\times m\) 个颜色块组成，要满足裁下的菱形必须由若干相同的颜色块组成。 求有多少种裁法。 注：一个方格也算一个菱形。 Examples of proper dress patterns: Examples of improper dress patterns: The first one consists of multi-colored scraps, the second one goes beyond the bounds of the piece of fabric, the third one is not a square with sides forming a \(45^{\circ}\) angle with sides of the piece of fabric. Rarity wonders ho...

洛谷P2132 小Z的队伍排列 题解 题目链接：P2132 小Z的队伍排列 题意： cxy 想给班里的同学拍一张合影（尤其是给妹纸拍），为此需要先让大家排好队伍。她希望大家站成 \(k\) 排，并规定了每排的人数，保证每一排的人数都不多于后面一排的人数。 这时 cxy 发现队伍看起来还是乱糟糟的，原因是大家的身高互不相同。于是，她希望排头对齐，每位同学都比自己正后方的同学以及排头方向的同学矮。 排完以后，善于思考的 cxy 还想知道一共有多少种排法。 例如，大家排成 \(3\) 排，且从后往前每排分别是 \(3,2,1\) 人，就有以下 \(16\) 种排法（每个数代表将所有同学身高从高到低排序后该同学的排名）： \[ \begin{array}{llllllllllllllll} 123 & 123 & 124 & 124 & 125 & 125 & 126 & 126 & 134 & 134 & 135 & 135 & 136 & 136 & 145 & ...

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