题解squares 125b arc

原题链接：CF1868B2， 简单版：CF1868B1。 题意 有 \(n\) 个人，第 \(i\) 个人手上最初有 \(a_{i}\) 颗糖。现在每个人可以把自己手中的糖选一些给不多于一个人，同时每个人也只能接受不多于一个人的糖，选出的糖的数量必须是二的次幂。问能否能让每个人最终手上的糖的数量相等 ......

原题链接：ABC239Ex。 题意不多赘述。 看到求期望值，我们想到可以用期望 DP。 设 \(dp_{i}\) 表示最终结果大于等于 \(i\) 时的操作次数的期望值。 那么我们可以得到一个基本的状态转移方程：\(dp_{i}=\frac{1}{n} \times \sum_{j=1}^{n}dp ......

题意 给定一个长度为 \(n\) 的字符串 \(s\)，有 \(m\) 个询问，每次询问最少需要删掉多少个字符才能使 \(l\) 到 \(r\) 组成的字符串当中的每一个前缀和后缀都满足 C 的数量不小于 T 的数量。 思路 因为要满足 C 的数量不小于 T 的数量，我们不妨设字符 C 的位置的值为 ......

原题链接：P6370 思路 题意不多赘述。 首先这道题的 \(60\) 分暴力很好打，直接按题目中的操作做即可，时间复杂度 \(O(nr)\)。 考虑优化暴力。我们会发现很多次石头的起始点为同一列的情况，其实每一次下落的轨迹是差不多的。具体来讲应该是第一次下落的轨迹一定包含了后面每一次的轨迹。所以我 ......

原题链接：斜率。 题意 在一个平面直角坐标系中，给定 \(n\) 个点的横纵坐标，求出哪两个点所构成的连线的斜率最接近 \(\frac{P}{Q}\)。 数据范围：\(n \le 1000000\)。 思路 显然这是一道数学题，不能直接暴力去找答案。 首先我们可以弱化一下题目，求出斜率最接近 \(y ......

显然是一道计数 dp。 dp 状态应该是最难的一部分了，个人认为这种状态设计得比较巧妙。如果像我刚开始一样设 \(dp_{i,j}\) 表示序列中一共有 \(i\) 个数，序列最后一个数为 \(j\) 的合法方案数的话，那么方程就会变得很不好转移，因为我们不知道当前的 \(j\) 和之前的某些数能不 ......

NOIP 模拟赛原题，赛时还是没切。 正解奇偶性。 考虑最终不能走的时候是什么情况，当且仅当图中只剩下两个联通块了。设其中一个联通块的点数为 \(k\)，那么另一个的点数为 \(n - k\)。所以两人一共的操作次数为 \(sum = \frac{n \times (n-1)}{2}-m-k \ti ......

原题链接：P2664。 题意：给定一棵树，每个点都有一个颜色 \(c_{i}\)。对于每一个点 \(i\)，求出 \(\sum_{j=1}^{n}s(i,j)\) 的值。其中 \(s(i,j)\) 表示点 \(i\) 到点 \(j\) 的颜色数量。 路径相关，考虑点分治。 假设当前的重心为 \(u\ ......

复习了一下边带权并查集板子。 设 \(d_{x}\) 表示当前点到它所在连通块根节点的距离。 合并点 \(x\) 和点 \(y\) 所在两个连通块时需要更新 \(d\)。因为将 \(x\) 点所在连通块的根节点的父亲节点设为了 \(y\) 点所在连通块的根节点，所以有 \(x \to y \to F ......

题意：维护两个操作，区间推平，求连续 \(0\) 的个数为 \(x\) 的最前位置。 线段树。 因为需要求连续 \(0\) 的个数，所以维护区间左边连续 \(0\) 的最大个数，区间右边连续 \(0\) 的最大个数以及区间连续 \(0\) 的最大个数。 注意修改的时候要看是修改为 \(1\) 还是修 ......

题意：给定一个长度为 \(n\) 的序列，求最少能将这个序列分成多少段使得任意一段中不存在两个数的积为完全平方数。 一个小 Trick：如果两个数乘起来为平方数，可以先将每个数的平方因子除掉，然后这两个数必然相等。于是这道题被转化为了一个区间不能有相等的值，这就很典了。 设 \(pos_{a_{i} ......

题意：给定一个长度为 \(n\) 的序列，求最少能将这个序列分成多少段使得任意一段中不存在两个数的积为完全平方数。你还可以将其中 \(k(k \le 20)\) 个数修改为任意的值。 一个小 Trick：如果两个数乘起来为平方数，可以先将每个数的平方因子除掉，然后这两个数必然相等。于是可以先将每个 ......

题意：有一个 \(n\) 个点的环，以及两个人。每个人可以向环中任意一个位置放置一个 \(A\) 或者 \(B\)，但是相邻的位置不能相同，不能行动者输。问最终的局面有多少种。 一个结论是：后手必胜。 证明：最终肯定不可能出现两个连续的空格，否则一定可以在其中一个上填 \(A\) 或 \(B\)。所 ......

原题链接：CF713D 题意：给定一个 \(n\times m\) 的地图 \(a\)，\(a_{i}\) 为 \(0\) 或 \(1\)。有 \(t\) 次询问，每次询问给定一个矩形，求出这个矩形中最大的由 \(1\) 构成的正方形的边长是多少。 首先考虑预处理出 \(d_{i,j}\) 表示以 ......

好像不是题解，算是记录。 记一个 Trick：当求路径边权的中位数的最大值的时候，可以先二分一个答案 \(mid\)，然后把大于 \(mid\) 的边设为 \(1\)，否则设为 \(-1\)。这样只需要看路径长度是否大于零就可以判断出有没有中位数大于等于 \(mid\) 的情况了。 当然类似到求一个 ......

题意：求有多少个长度为 \(n\) 的数组 \(a\) 满足以下条件。 条件一：\(l_{i} \le a_{i} \le r_{i}\)。 条件二：\(a_{i}\) 模 \(2\) 等于 \(p_{i}\)。 条件三：\(s \le \sum a_{i} \le t\)。 求答案模 \(mod\ ......

原题链接：ARC168B 题意：有 \(n\) 堆石子，每堆有 \(a_{i}\) 个。每人每次可以取走其中一堆中的 \(x(1 \le x \le k)\) 个。求出一个最大的 \(k\) 使得先手必胜。无解输出 \(0\)，\(k\) 可以取无限大输出 \(-1\)。 一个经典 Nim 游戏的结 ......

这道题比较简单，简述一下思路。 考虑状压 \(DP\)。 设 \(dp_{i,j}\) 表示走到第 \(i\) 个点，之前走过的点的状态为 \(j\) 的环的数量。这里有一个细节，就是我们都钦定每个走过的第一点是整个状态中编号最小的点，这样不会重复计算。 考虑如何进行转移。如果当前点的编号比走过的最 ......

原题链接：P1450 这道题被教练放到了状压 \(DP\) 的题单里面，但是正解却不是状压 \(DP\)，而是背包 \(+\) 神奇容斥，只不过是用到了一些二进制状压的思想。 思路 首先看到题目立马就想到了多重背包，但是时间复杂度肯定接受不了，于是考虑优化背包。我们可以想到一个很神奇的性质：假设只有 ......

原题链接：CF1900D，题意不多赘述。 首先可以将 \(a\) 数组排序，并且枚举中间的那个数 \(a_i\)。那么答案就是 \(\sum_{j=1}^{i-1} \gcd(a_j,a_i)\times (n-i)\)。重点在于求前面的 \(\gcd\)。可以用欧拉反演，但是也可以不用，因为我不会 ......

题意：有一个二维平面直角坐标系，给定一串向某个方向移动 \(1\) 个单位的操作。 有 \(q\) 个询问，对于每个询问给定 \(x,y,l,r\)，问如果倒着做 \(l\) 到 \(r\) 这段区间中的操作，是否会经过 \((x,y)\)。 ds 题。先预处理出 \(sx_i,sy_i\) 表示执 ......

原题链接：P3959 乍一看，感觉像是一道图论的最短路这类的题，但是细想发现用图论似乎不可做。再看到这道题的数据范围 \(n<=12\)，立马就可以想到用状压 \(DP\)，因为数据范围很状压/。 思路 设计状态 首先来考虑状态的设计。如果按状压 \(DP\) 的套路来设的话，设 \(dp_{i,j ......

原题链接：Group Projects 题意 有 \(n\) 个学生，每个学生有一个能力值 \(a_{i}\) 。现在要把这些学生分成一些(任意数量的)组，每一组的“不和谐度”是该组能力值最大的学生与能力值最小的学生的能力值的差。求所有不和谐度之和不超过 \(k\) 的分组方案总数。 思路 根据题目 ......

原题链接：Partition into Groups PS：这是今天上午NOIP模拟赛的T3。 题意 N个小朋友，每个小朋友最多有3个敌对小朋友， 问是否能把他们分成两组，使得这N个小朋友最多只有一个敌对小朋友在一组。 思路 考场上想肯定与二分图有关，最后没想出来，打了15分暴力就走了（最后还只有1 ......

原题链接：CF575A 前言 今天模拟赛考到了这道题，最近正好在学习矩阵，于是就来写了这道题，发现这道题是矩阵快速幂好题。 题意 题意不多赘述，大概就是一个广义斐波那契数列的升级版，可以修改 \(m\) 个系数。 思路 因为题目是求斐波那契数列的第 \(k\) 项，显然用矩阵去维护。又因为题目说了， ......

原题链接：Tautonym Puzzle 前言 这道题是一道很有趣的构造题。我认为这道题的重点在于对题目要求的转化与转化过程中细节的处理。（有些细节问题也困惑了我很久）。 题意 构造一个字符串 \(S\) ，使 \(S\) 的所有子序列中，恰好有 \(N\) 个好串。 好串：一个字符串能分成两个相同 ......

原题传送门：mit 前言 这道题是今天模拟赛T1，赛时只有 \(60\) 分。还有一位巨佬这道题保龄了。 题意 给定一个正整数 \(n\)，将 \(n\) 拆分成 \(k\) 个数之和。（\(k\) 为任意正整数） 求：\(k\) 个数的乘积最大是多少？乘积的期望是多少？ 思路 首先看第一个问题。易 ......

原题链接：P1903 题意 对于一个序列，维护两个操作： 将 \(a_{x}\) 改为 \(p\)。 求 \(l\) 到 \(r\) 中有多少个不同的数 思路 这道题本来是带修莫队的板子的，但是我是使用分块做的。 具体思路挺板的...但是这道题其实有个 \(trick\)。就是我们先预处理记录 \( ......

题意 给定一个数 \(n\)，要求将 \(n\) 表示成一些 \(4^{k}\) 的数之和或差的形式，要求用的数最少，求方案数。 思路 首先看到这道题的数据范围 \(n\le10^{1000}\)，又是求方案数，所以想到用数位 DP。因为每一个数都是 \(4\) 的次幂，显然我们需要讲原数转化为 \ ......

原题链接：P7532 前言 这道题是今天 NOIP 模拟赛的 T1，赛时只有 5 分。 题意 简化一下题意，即在一个 \(n\times n\) 的方阵中，求出有多少个满足条件的连通块，使得： 同一行或列的两点中间没有空 连通块内全是草 可以发现，其实连通块就是一个凸多边形。 思路 很显然，这道题是 ......