题面链接 题解 题目意思有点不好懂，其实就是在数列中找到与 $A_{i-1}$ 相邻的两项来限制 $A_i$ 的值，问方案数。 首先凭感觉，感觉越往后面的数可能的情况是更少的，整体呈收束趋势。 我们设用来更新 $A_i$ 的 $L$ 和 $R$ 为 $L_i$ 和 $R_i$ ,根据定义有 $L_{i-1} \leq A_{i-1} \leq R_…

题目链接 题解 先介绍一个东西：多重集(multiset)的全排列（这里是特殊情况，即选的元素个数不超过任意集合中元素个数的情况） 我们定义集合的集合为多重集，比如我有 $a_1$ 个 $1$ ， $a_2$ 个 $2$ …… $a_n$ 个 $n$ 。 那么写成多重集就是 [latex]\left\{\left\{a_1·1\right\},\l…

题目链接 题解 $f[i][j]$ 表示 当前串为第j个位置到第i个位置的串的方案数 $O(n^3)$ 做法 $ f[i][j]=\sum_{j-k< i-j}f[j][k]$ 若 $s(k+1,j)< s(j+1,i),j-k=i-j$ 则 $f[i][j]+=f[j][k]$ $O(n^2)$ 做法 考虑 $O(1)$ check …

题目大意 给你一个长度为n的数组，你需要更改里面各项的值使得它们两两互质。 代价为改后数字与原始值的差值的绝对值。求最小代价。 题解 这个题解算是在分享做题的心路历程，比较磨叽，可以只看黑体字部分 一开始都已经弃疗了（别一开始就放弃啊喂!）准备打一个暴力骗点分…… 于是就打算枚举每一项，对于每一项枚举每一个可能值。 枚举值肯定有范围的，不能可在in…

T1 引子（水箱） 非常简单的模拟题目，错误点有两处： 1. 没有读入多位数字 2. 出现顺序和编号无关 然就是从1号水箱，开始递归，优先从箱底的水管递归下去，然后输出自身的编号。 [crayon-67eae5fe51822890538656/] T2 可爱精灵宝贝 一道区间dp题，考场上写挂了，最后10分钟乱搞居然也有60分，考试完调了一下，有9…

T1 求三角形的最大面积 题目大意：给你一个由多个三角形组成的大三角形，其中有些三角形缺失了，求出剩下部分最大的三角形。 毒瘤题，dp很好想，被特殊情况坑了。 首先上三角和下三角都要算一遍（其实就是反过来再找一遍） 就拿上三角来说，我们很容易就知道它的高度就是min(左，右)+1，但是实际上还要考虑一些特殊情况 比如下面这种情况： 输入的时候是这样…

T1 不老的传说 题目大意：有n个石头环成一圈，每次染色能染1-k个连续石头，问多最少多少次能染成目标状态 这道题真的是各种既视感，环的话直接变成两倍的链就OK了，之后就是区间dp [latex]f[i][j][/latex]表示(i,j)对i,j一段染色的最少次数 初始化就是[latex]f[i][j]=\begin{cases}1&i=j\\ …

题目大意：两个人玩牌，他们各有m(<=100)张牌，输入牌上的数字(<=50)，有n(<=50)轮回合，每回合他们从自己牌中随机选1张，牌上的数字加入答案后放回牌组中。问n回合后第一个人赢的概率是多少（保留6位小数）？ 我当时居然还想随机模拟最后输出答案（显然精度不够），然而随机数生成我用的是rand*rand()，搞得分…

题目大意：有一棵 n 个节点的树，每条边长度为 1，颜色为黑或白。 可以执行若干次如下操作：选择一条简单路径，反转路径上所有边的颜色。 对于某些边，要求在操作结束时为某一种颜色。 给定每条边的初始颜色，求最小操作数，以及满足操作数最小时，最小的操作路径长度和。 没想到还有人Day3能考285分 orz %%% 这道题看了题解也有点迷（主要是太短了）…

传送门 一看到求什么“最大的最小值”，“最小的最大值”就马上想到二分（还有可能是单调队列） 再仔细看看题目，貌似没什么头绪，但答案似乎存在单调性，果断二分。 答案肯定在0到n范围内。 设[latex]f[i][/latex]为做到第[latex]i[/latex]个作业时所需要花的最短时间。 假如我们可以空[latex]k[/latex]道题（二分…