D1. Divan and Kostomuksha (easy version) 记dpidp_idpi​表示把gcd⁡{\gcd}gcd为i{i}i的一组数放到前面的贡献，cnti{cnt_i}cnti​表示含有因子i{i}i的数的个数。 状态转移方程有：dpi=max(dpi,dpd+cnti∗...

考虑最简单的情况，如果三个数a、b、c(a<b<c){a、b、c(a<b<c)}a、b、c(a<b<c)，有b−a<=c−b{b-a<=c-b}b−a<=c−b，那么这三个数是非terrible{terrible}terrible的；反之是ter...

在bbb中选出n{n}n个数aia_iai​，这个子序列是好的当且仅当能找到满足如下条件的x{x}x： a1(2∗x1+a1−1)2+a2(2∗x2+a2−1)2+...+an(2∗xn+an−1)2=0{\frac{a_1(2*x_1+a_1-1)}{2}+\frac{a_2(2*x_2+a_2-...

题解 拍照 从1∼n{1\sim n}1∼n和从n∼1{n\sim 1}n∼1分别跑一遍最长上升子序列，枚举最高的人i{i}i时，计算1∼i{1\sim i}1∼i和n∼i{n\sim i}n∼i之和，取和最大的i{i}i。（枚举最高的人i{i}i时要保证i{i}i被选到，所以要分别从前和从后跑一遍...

假设当前置顶了x{x}x条信息，学生i{i}i对信息mi{m_i}mi​的期望贡献如下： 如果mi{m_i}mi​没被置顶，那么贡献为0 如果mi{m_i}mi​被置顶了，那么选出1{1}1条信息包含mi{m_i}mi​的概率为1x{\frac{1}{x}}x1​，选出ki{k_i}ki​条信息包含...

使得长度大于等于k{k}k的路径包括至少2种颜色，也就是说只要考虑长度为k{k}k的路径。 长度为k{k}k的分为一组，相邻点的边染上1，组内的路径最长是k−1{k-1}k−1 长度为k∗2{k*2}k∗2的分为一组，属于同一组内的两个点间还没有染色的边都染上颜色 2，颜色全为2的路径，最长为k−1...

对每个数先分解质因数，每个质因数就能单独计算。那么对于同一个质因子，我们发现问题可以转为合法括号序列问题。 定义l[i]{l[i]}l[i]表示以第i{i}i个数字结尾时，对于所有左端点pos<=l[i]{pos<=l[i]}pos<=l[i]的pos{pos}pos，pos∼i{...

考虑是把b{b}b序列中的元素插入到a{a}a序列中，b{b}b序列插入的相对位置一定是值小的在前面。 对bi<bj,i<j{b_i<b_j,i<j}bi​<bj​,i<j，当前得到ans{ans}ans对逆序数，bi、bj{b_i、b_j}bi​、bj​之间值在...

假设dp[n][x]{dp[n][x]}dp[n][x]为有n{n}n个人活着，每个人的体力值范围为1∼x{1\sim x}1∼x的方案数。 考虑以下几种情况： 当n==2{n==2}n==2时，只有两个人的体力值相同时才满足条件，dp[n][x]=x{dp[n][x]=x}dp[n][x]=x 当...

我们发现k{k}k可以是答案的前提是线段的长度总和不超过n{n}n。即k∗(k+1)2≤n\frac{k*(k+1)}{2}\le n2k∗(k+1)​≤n，k≤447k\le 447k≤447 令dpi,jdp_{i,j}dpi,j​表示长度为jjj的段的最大和，同时我们已经考虑了后缀iii上所有...