题解loathesome p2903 baler

\(\texttt{E F}\) 忘（不）记（会）写了。 A Yet Another Dividing into Teams 题解 题目大意 有一个长度为 \(n\) 的序列 \(a_1,a_2,\cdots,a_n\)，将他们分为若干组，使得每一组没有两个数的差为 \(1\)，使分的组数尽可能少。 ......

这道题其实很简单 要让两数和为 \(k\) 的倍数，需要满足以下两条件之一： 两数都是 \(k\) 的倍数 两数的余数和为 \(k\) 因此，我们可以先统计出余数 再按上述条件算出共有多少组，即可得到答案 注意： 当 \(k\) 为偶数时，余数为 \(k/2\) 的数要两两配对，不要多算 这里统计的 ......

这题其实不难。 两人最佳的方案就是先说对方会的词。 不难证明，设先手会说 \(n\) 个单词，后手会说 \(m\) 个单词， 若 \(n>m\)，则先手胜，若 \(n<m\)，则后手胜。 那如果 \(n=m\) 呢？ 假设两人都会说的单词数为 \(k\)， 那么一番推理发现，当两人说了 \(k-1\ ......

这题其实不难 但如果用暴力，肯定过不了 所以我们得想另一种办法 我们发现，只有 \(1\) 异或 \(0\) 的值为 \(1\) 例如： \(1\) , \(0\) , \(1\) 两两异或的和为 2 其实就是每个 \(0\) 与每一个 \(1\) 异或时，\(sum\) 要加 \(1\) 所以，我 ......

这是让我最崩溃的一道橙题了。 整整 11 次提交才 AC。 这道题有几个要点必须注意： 判断日期是否合理。 按顺序输出。 判断重复的日期。 首先，我们来看怎么判断日期是否合理。 我们知道大月有 \(31\) 天，小月有 \(30\) 天，二月看平年闰年。 所以，我们可以写出这样的代码： bool c ......

这道题其实不难。 \(\gcd(i,j)=1\)，其实就是 \(i\) 与 \(j\) 互质。 如果 \(i\) 与 \(j\) 不互质，那么我们一定要让 \(a_i\) 与 \(a_j\) 相同，只有这样，才能使 \(a\) 序列中的最大值最小化。 所以，我们可以使用埃氏筛法，当筛到质数时，给它和 ......

这道题其实并不难。 题目大意是这样的：已知两个序列 \(r\) 和 \(b\)，求出合并后的最大前缀和。 很好发现：答案就是 \(r\) 和 \(b\) 各自的最大前缀和之和。 但要注意：\(r\) 和 \(b\) 可以什么都不取，因此 \(maxa\) 和 \(maxb\) 初始要赋值为 \(0\ ......

主要讲一下每一题的做法以及思考方式。 感觉难度薇 \(T1-T3-T2\) 。但是都不算难。 \(T1\) 题目描述 Jimmy 最近迷上了一款叫做方块消除的游戏。游戏规则如下：\(n\) 个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻方块颜色相同，则这两个方块属于同一区域）。为简化 ......

这道题其实不难。 \(\gcd(i,j)=1\)，其实就是 \(i\) 与 \(j\) 互质。 如果 \(i\) 与 \(j\) 不互质，那么我们一定要让 \(a_i\) 与 \(a_j\) 相同，只有这样，才能使 \(a\) 序列中的最大值最小化。 所以，我们可以使用埃氏筛法，当筛到质数时，给它和 ......

更好的阅读体验 题意 题目链接 （洛谷翻译） 给出 \(n\) 个点，和每个点的度 \(d_i\) 让你构造出一张无向图满足以下两条性质： 点 \(1\) 到点 \(i\) 仅有 唯一 一条最短路。 点 \(1\) 到点 \(i\) 的最短路长度大于等于点 \(1\) 到点 \(i-1\) 的最短路 ......

这道题其实不难，只是一道非常简单的模拟题。 我们发现，每顺时针转动 \(4\) 次、镜面对称 \(2\) 次、逆时针旋转 \(4\) 次，就变回原来的样子了。 所以，在操作前，我们可以让 \(x\gets x\bmod4\)，\(y\gets y\bmod2\)，\(z\gets z\bmod4\) ......

题意 给定长度为 \(n\) 的序列 \(a\) 和常数 \(d\)，输出一个最长的 \(a\) 的子序列，使得相邻两项的差的绝对值大于等于 \(d\)。 \(n\le10^5\) 题解 数据结构优化 DP 的板子题了吧。 首先，这道题看上去就很 LIS，我们尝试着用类似 LIS 的思路去做。 设 ......

题解 accoders::NOI 5510【飞翔的胖鸟（fly）】 problem 求 \(f(x)=\frac{ah}{\sin(x)}+bx\) 在 \((0,\frac\pi 2]\) 上的最小值。 solution \(\sin'(x)=cos(x); \cos'(x)=-\sin(x)\) ......

题解 accoders::NOI 5508【漂亮大厨（cook）】 part 1 区间加 \(x\)，区间询问有多少个数字 \(\leq y\)。\(n,m\leq 10^5,x\leq 200,y\leq 10^7\)。 考虑 P5356 [Ynoi2017] 由乃打扑克 的做法，分块，块内按照值 ......

Description 有 \(n\) 个区间，第 \(i\) 个区间为 \([l_i,r_i]\)。保证 \(l_1<l_2<\cdots<l_n\) 且 \(r_1<r_2<\cdots<r_n\)。其中一部分区间是特殊的，输入会给定。 如果第 \(i\) 个区间和第 \(j\) 个区间相交，那 ......

题如其名，确实挺经典的。 我们称边权在输入中给定的边为特殊边，其它边为平凡边。称特殊边涉及到的点为特殊点，其它点为平凡点。 显然，对于连续的若干平凡点 \([l,r]\)，他们内部的最优连边方式就是连成一条链，花费 \(r-l\) 的代价。我们先把这样的代价加到答案中，然后将极长连续平凡点缩成一个点 ......

LG 任意时刻每个点最多被一条线段覆盖 暴力删每条线段是对的 插入 \([l,r]\) 时需要删除的线段要么被 \([l,r]\) 包含，要么覆盖 \(l\) 或 \(r\) 性质非常强所以做法非常多 一种比较神奇的：对于两条线段 \([l_{1},r_{1}],[l_{2},r_{2}]\)，定义 ......

题解 accoders::NOI 5511【漂亮轰炸（bomb）】 http://47.92.197.167:5283/contest/406/problem/4 BZOJ3252 是弱化版。 problem 一棵树，边带权。\(Q\) 次询问，给定 \(k\) 和一个首都点，选择 \(k\) 条路 ......

显然，询问的答案即为 \(x\) 所在的极长的满足颜色均在 \(\mathbb{A}\) 内的连续段的权值和。如果我们能维护对颜色的单点修改，以及求出某个位置所在极长连续段的左右端点 \(l,r\)，只需要树状数组即可求出答案。 一个朴素的想法是对每种颜色开一棵线段树，单点修改是平凡的，极长连续段左 ......

CF814E 其实是对这篇 题解 的一些理解。 Part 1 不难发现最终图大致长这样： 考虑一棵最短路树，以结点 1 为根，往下每一层有若干个结点，表示最短路距离相同的一些编号连续的结点。 其中每一层内部可以自由连边。 除了每层内部的连边和树边，其余边不合法。 Part 2 考虑第 \(i\) 层 ......

这题一看就不是计算几何，考虑区间 DP。 设凸多边形的 \(n\) 个顶点依次为 \(P_1,P_2,\cdots,P_n\)。 设 \(f_{i,j}\) 在 \(i < j\) 时表示 \(P_i,P_{i+1},\cdots,P_{j-1},P_j\) 组成的多边形的直径的平方，在 \(i > ......

好题。 后面的操作会覆盖前面的操作，这东西不好处理，我们不妨时光倒流，将问题转化为一个位置一旦被填了数，就再也不会变了。如果解决了这个问题，只需将操作序列倒过来，就得到了原问题的解。 显然，所有 \(x_i=y_i=2\) 的操作会最先被执行，所有 \(x_i=y_i=1\) 的操作会最后被执行。只 ......

AtCoder 天下一プログラマーコンテスト2014 本戦 高橋君 题意 给定 \(n, k\)，求 \[\sum\limits_{i = 0}^{k}\dbinom{n}{i} \]多测，\(1 \le n, k, T \le 10^5\)。 题解 可以考虑使用莫队求解，下文讲述如何移动指针。 \ ......

思路 定义 \(dp_i\) 表示将前 \(i\) 个分为若干段的价值总和。容易得到状态转移方程： \[dp_i = \sum_{j = 1}^{i - 1}{dp_j \times (\max_{k = j + 1}^{i}\{a_k\} - \min_{k = j + 1}^{i}\{a_k\} ......

题目描述 给你一个正整数数 \(n\)，问你它是不是多边形数 \(K\)，如果是，设 \(K_1\) 是最小的 \(K\)，\(K_2\) 是次小的 \(K\)，输出 \(K_1\) 和 \(K_2\)。 具体思路 我们主要来看上面这张表里有什么规律。 性质 1：\(1\) 是任何一个多边形数。 性 ......

\(d<n\le 2e5,m\le 10,1\le p\le 10^9,0\le a_i\le 1e9\) 每个位运算之间独立，所以我们可以构造一个 \(\{2^{k-1},2^{k-1}.....\}\) 和一个 \(\{0,0,0...\}\) 的数组，让他们倍增去做如上运算，最后用他们把 \( ......

思路 定义 \(dp_i\) 表示将前 \(i\) 个分为若干段的价值总和。容易得到状态转移方程： \[dp_i = \sum_{j = 1}^{i - 1}{dp_j \times (\max_{k = j + 1}^{i}\{a_k\} - \min_{k = j + 1}^{i}\{a_k\} ......

Typo Descreption 求反转一个不合法的括号序列中的一位使其成为一个合法序列的方案数（保证方案一定存在） Solution 其实也就是一道较复杂的模拟题 先判断哪一类括号数量更多，因为一定是将数量多的括号改成数量少的才有可能变为合法序列，这里就先用左括号举例 记录每个位置时没有配对的左括 ......

题目传送门 本题共有两种方法，分别是递归深搜和动态规划 方法一：递归深搜 Solution 从小到大一一枚举每一个划分的数，。只要找到一种方案就记录，具体细节代码中有注释。 Code #include <bits/stdc++.h> using namespace std; int n,k,ans; ......

A Equalize Prices Again 题解 题目大意 \(n\) 个商品，每个商品价格为 \(a_i\)，求一个最小的价格 \(x\)，使得不亏本（即 \(\sum\limits_{i=1}^n{(a_i-x)}\ge0\)）。 解题思路 输出平均数向上取整（即 \(\left\lceil ......