题解1525f cf

题意：有一个长为n的带子，可以将它剪为a, b, c三种长度，问最多能剪多少段？ 分析：是一道与完全背包类似的题，但这里要求的是背包正好装满。该怎么解决这一问题？我们可以将f数组全部初始化为-1，状态转移时如果上一个状态不是-1才可以转移。 状态转移方程\(f_{i, j}\)表示前i个物品恰好装满 ......

Link T402161 run Question 亮亮总共要跑 \(n\) 圈，可以分成多次，但是每次跑的圈数必须要比上一次跑的多，求跑完 \(n\) 圈的方案数 Solution 显然动态规划 定义 \(F[i][j]\) 表示一共跑了 \(i\) 圈，最后一次跑了 \(j\) 圈的方案数，转移 ......

题目链接 题目大意： 给定数 \(P\)，寻找能把 \(P\) 整除的最小的斐波那契数，然后输出它是斐波那契数列中的第几个，找不到输出的话就输出 -1 。 分析： 主要代码： a[i]=(a[i-1]+a[i-2])%p 思路： 先将 \(a\) 数组的第一项和第二项都初始化为 1 ，然后判断是不是 ......

题目传送门 题目描述 给定由 1 0 ? 所组成的字符串，你需要用 0 或 1 替换 ?。 我们将 \(s_l,s_{l+1},\dots,s_r\) 反转称为一次操作。 你要使通过“反转”操作使原字符串成为升序的操作次数尽可能的小。 分析 通过观察，我们可以发现一个规律： 若 \(s_i\) 为 ......

题目传送门 这道题是一个很经典的动态规划。 因为合唱队形的身高是从低——高——低来排的，所以就可以利用分治的思想将队形分成两个部分：低——高是最长上升子序列；高——低是最长下降子序列。 这道题其实可以用二分查找来优化，可是这题n≤100，没有必要优化，需优化题详见P1020 导弹拦截。 做法详见代码 ......

题目链接 题目大意 如题，给定 \(N\) 个字符串（第 \(i\) 个字符串长度为 \(M_i\)，字符串内包含数字、大小写字母，大小写敏感），请求出 \(N\) 个字符串中共有多少个不同的字符串。 不知道大家知不知道一个字符串函数，叫 \(insert\) 他是 \(STL\) 库中的一个函数， ......

题意 有 \(n\) 条鱼，\(m\) 个渔夫，且这 \(m\) 个渔夫都在横坐标轴上，每个渔夫都有一个长度为 \(l\) 的鱼竿，当鱼和渔夫距离小于或等于 \(l\) 时，鱼能被钓到。 并且渔夫 \((x,0)\) 与鱼 \((a,b)\) 的距离（假设为 \(L\) ）满足如下公式 \(|a − ......

这道题是洛谷基础赛的第二题 想必各位都AC了吧 没有AC的现在赶紧去做 题目传送门:传送门(最好别点)点了别怪我没提醒 题目链接:传送门< 点这个 做过的直接看下面就行 「NnOI R2-T2」Glaciaxion 题目描述 冰封的世界可以看作是 $ n $ 块初始时冷冻的冰川，这些冰川被编号为 \ ......

题目传送门 想要做这题，我们要先了解一下最大公约数。 最大公因数，也称最大公约数、最大公因子，指两个或多 个整数共有约数中最大的一个。a，b的最大公约数记为 （a，b），同样的，a，b，c的最大公约数记为（a，b， c），多个整数的最大公约数也有同样的记号。求最大公 约数有多种方法，常见的有质因数分 ......

P5451 [THUPC2018] 密码学第三次小作业 题解 已知 \((e_1, e_2) = 1\)。 \[\begin{matrix}c_1=m^{e_1}\bmod N\\c_2=m^{e_2}\bmod N\end{matrix} \]现在，已知 \(c_1\) ，\(c_2\)，\(e_ ......

自己的套路还是见少了。 思路 考虑扫描线。 每一个颜色的 \(\min\) 具有单调性，这个很好看出来。 可以使用一个单调栈来维护。 这里都是朴素的。 考虑如何维护。 我们发现在通过单调栈维护的时候。 需要支持撤销上一个元素对区间的影响。 我就在这里卡了很久。 我们有一个很暴力的想法。 我们每一次区 ......

支配点对实在是太有意思了。 本质上就是一个合法的减枝。 思路 考虑维护树上路径问题。 容易想到点分治。 考虑在当前的分治中心 \(\text{rt}\)，每个点到当前分治中心的距离为 \(dp_x\)。 求出每一组点对的贡献。 假设每个点对在距离长的那部分贡献，即 \(dp_i>dp_j\)，求出所 ......

思路 设 \(dp_{i,j}\) 表示第 \(i\) 行 \(j\) 列卒走到这里有多少种方式。 卒是可以向右和下走，所以到这个点只能从左或上来，不难得出转移公式：\(dp_{i,j} = dp_{i-1,j}+dp_{i,j-1}\)。 如果马在这个点上或者说马能到这个点上，那么卒不能到这个点， ......

简单模拟题。 思路 枚举每一个地毯，因为后面的会覆盖前面的，所以从正序枚举。如果要求的点的坐标在当前地毯上，则将答案赋值为当前地毯编号。 最后输出答案。 那如果这个点没有地毯呢？答案初始设为 \(-1\)，这样没有地毯覆盖的话，答案不会改变，这样输出答案就会是 \(-1\)。 注意： 记得赋初始值。 ......

思路 我写的好像是动规的做法。 设 \(f_{i,j}\) 表示第 \(i\) 步 \(j\) 个点是否可以走到，值要么为 \(1\)，要么为 \(0\)。最多走 \(n\) 步，因为总共只有 \(n\) 个点，每一步都肯定会多延伸出一个点，要不然就重复计算。 不难得出转移公式： \(f_{i+1, ......

考察了小学奥数知识，不会的请先去学习一下相遇与追及。 思路 两个人相遇的点一定是有周期性的，我们可以先算出一个周期会走多远，而这个距离是两人速度的最小公倍数。 接着需分情况讨论。 如果两人是同向，则为追及，需用距离除以一人的速度减去距离除以另一人的速度。需要取绝对值。 如果两人是反向，则为相遇，需用 ......

时间限制 \(1s\) | 空间限制 \(250M\) 题目大意 题目描述 给定一个数列 \(a_{1…n}\), 如果满足下面条件, 你可以使 \(a_i = a_i + 1\): \(i < n\) 且 \(a_i \leq a_{i+1}\) \(i = n\) 且 \(a_i \leq a_ ......

时间限制 \(2s\) | 空间限制 \(250M\) 题目描述 给你一个序列$ a_1, a_2, \dots a_n $ 。请计算出满足下面条件的 $(i,j) (1 \leq i, j \leq n) $个数 。 $ a_i < i < a_j < j $ . 输入格式 第一行包含一个整数 $ ......

来一发分治题解吧。 感觉和单纯的整体二分还是有一点区别。 虽然整体二分也能看作分治就是了。 思路 首先时光倒流。 删边改为加边。 这没有什么好说的，比较基础。 我们考虑在不断加边时，每两个点是在什么时候变成一个强连通分量里面的。 考虑分治。 首先在 \([l,r]\) 内选取中点 \(\text{m ......

Yet Another Permutation Problem - 洛谷 这题本来很简单，思路我也想到了，但是代码一直没写对，思路也一直换来换去（悲 然而发现最开始的思路是对的 题意 Alex 收到了一个名为 "GCD 排列" 的游戏作为生日礼物。这个游戏的每一轮进行如下操作： 首先，Alex 选择 ......

Epic Transformation - 洛谷 算是今天的题目里边思维难度最高的一道了，但是代码真的简单的要死 题意 你有一个长度为 \(n\) 的序列 \(a\)，你可以对其进行下列操作： 选择 \(i,j\) 满足 \(*a_i\neq a_j*\) 然后删除 \(*a_i,a_j*\) 两个 ......

题目传送门 另：多测不清空，WA两行泪 题意 Burenka正准备去观看一年中最有趣的体育活动 —— 她朋友Tonya组织的格斗锦标赛。 有 n 名运动员参加了大赛，标号分别为为 1，2，... ，n 。第 i 名运动员的实力是 \(a_i（1 \le a_i \le n）\) 。每个运动员的实力是 ......

题目传送门 很奇妙的一道题，我想到了正解，但是又没有完全想到 题意 我们定义 \(f(x)\) 表示取出 \(x\) 在十进制下的位数。( 如 \(f(114514) = 6, \; f(998244353) = 9\) )。形式化讲，就是 \(f(x) = \lfloor \log_{10} x ......

有某位特别爱RE的同学问的老师，由此引发了一场血案 主打的就是一坚持不懈（悲 题意 给出两个正整数 \((x,y)\)，满足 \((x,y),(x+1,y+1),(x+2,y+2),\dots,(x+k,y+k)\) 都是互质的，直到 \((x+k+1,y+k+1)\) 起不互质 问 \(k\) 的 ......

Strong Vertices - 洛谷 题解是个好东西 题意 给定两个数组 \(a\) 和 \(b\)，对此构造一张有向图： 若 \(a_u−a_v≥b_u−b_v\)，则 \(u\) 向 \(v\) 连边。 求所有向其他所有顶点连边的顶点个数，并按从小到大顺序输出它们。 思路 先对原式进行转换： ......

题目传送门 代码一遍AC真的很爽，样例都是一遍过 题意 每个测试点含多组测试数据。 对于每组测试数据 第1行 一个整数 \(n\) ，表示该数据个数 第2行 \(n\) 个整数，你需要判断是否符合题意的数据 对每组数据，你可以对其作若干次（可以为零）如下操作： 选取数据中的一个数 \(a_i\) 将 ......

Ball in Berland - 洛谷 题意 在毕业典礼上，有\(a\)个男孩和\(b\)个女孩准备跳舞，不是所有的男孩和女孩都准备结伴跳舞。 现在你知道\(k\)个可能的舞伴，你需要选择其中的两对，以便使没有人重复地出现在舞伴里，求可能的数量。 思路 暴力 最朴素，也是简单的方法，就是通过暴力组 ......

题目传送门 题意 给定长度为 \(n\) 的字符串 \(s\)，进行 \(c\) 次操作，每次操作将 \(s_l\) 到 \(s_r\) 复制到字符串尾。 全部操作结束后有 \(q\) 次询问，每次询问字符串 \(s\) 的第 \(k\) 位。 数据保证 \(r\) 不超过当前字符串长度，\(k\) ......

给一个长度为 \(n\) 的字符串 \(s\)，\(q\) 次询问，每一次 \(l\) 和 \(r\) 区间内有多少个 \(s_i\) 等于 \(s_{i-1}\)。 \(10^5\) 的数据 \(O(N^2)\) 暴力肯定行不通。于是我们考虑预处理前缀和，处理到 \(i\) 下标以及之前有多少个 ......

插曲 因为本人看错了题面，买看到一个子串只包含一种字母，所以切完 D 和 E 才回来发现很简单。 问题翻译 给你一个长度为 \(N\) 的字符串 \(S\)，由小写英文字母组成。 求 \(S\) 的非空子串中有多少个是一个字符的重复。在这里，作为字符串的两个子串是相等的，即使它们是以不同的方式得到的 ......