题目链接 大意：给你两个数     n   ,   k    n,k   n,k，让你求出有序三元组     (   a   ,   b   ,   c   )    (a,b,c)   (a,b,c)，且满足     a   +   b   ,   b   +   c   ,   a   +   c    a+b,b+c,a+c   a+b,b+c,a+c都是     k    k   k的倍数。 思路：显然，若要满足条件，三元组必须满足： 1.每个数都是k的倍数 或者 2.在模k意义下，三元组至少有两个相同。 那么就好做了 。 先预处理出每种模k意义下数字的数量，然后直接统计即可。 细节见...

题目链接 思路：考虑递推     f   [   i   ]   [   j   ]   [   a   ]   [   b   ]    f[i][j][a][b]   f[i][j][a][b]表示，表示第     i   ,   j    i,j   i,j个宝藏选了     a    a   a个，其中最大是     b    b   b的方案数。 每个宝藏都有两种，选或者不选。 初始条件为：     f   [   1   ]   [   1   ]   [   0   ]   [   0   ]   =   f   [   1   ]   [   1   ]   [   1   ]...

题目链接 题意：给你一个数组，让你求出满足删除     (   l   ,   r   )    (l,r)   (l,r)内所有值后，剩下的数组单调不减的     (   l   ,   r   )   ,   l   ≤   r    (l,r),l \leq r   (l,r),l≤r的对数。 思路：首先，对每个数进行预处理最先出现和最后出现的位置，若数组没这个数，则最后出现的位置设置成一个极大数，最先出现为0. 然后从大到小进行讨论，看不删这个数是否合法。意为：假设最大数为     q    q   q，那么如果当前数为     t    t   t,是否满足     t   −   ...

题目链接 大意：给你一系列的障碍物的信息（出现位置和时间），然后给你一系列的人的出发时间（从零坐标开始），问你每个人最多能走多远。 思路：我们可以换个方式思考，不考虑人，考虑每个障碍物可以挡住哪些人，先将障碍物按坐标从小到大排序，然后将所有的人存进set中，遍历所有的障碍物，每次二分查找位置     [    l   i    ,    r   i    )    [l_i,r_i)   [li​,ri​)，左闭右开的障碍物区间，（事先将障碍物的存在时间减去坐标，即等价于0坐标出障碍物的时间），然后更新答案即可了，然后删除更新过的人，每个人只会被删一次。 细节见代码。 #include<...

题目链接 大意：给你三个数     n   ,   m   ,   k    n,m,k   n,m,k，让你在     n   ∗   m    n*m   n∗m的矩阵中选择     k    k   k个单元，计算      ∑   i    K   −   1      ∑    j   =   i   +   1    K    (   ∣    x   i    −    x   j    ∣   +   ∣    y   i    −    y   j    ∣   )    \sum_i^{K-1}\sum_{j=i+1}^K(|x_i-x_j|+|y_i-y_j|)   ∑i...

比赛链接 A.Nearest Interesting Number 题目大意：给你一个数     n    n   n,让你找一个最小的     x    x   x,满足     n   ≤   x    n\leq x   n≤x,且     x    x   x的数位和是4的倍数。直接暴力跑一下就行了。 #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mp make_pair #define pb push_back using namespace ...

题目链接 思路：考虑     d   p   [   i   ]   [   j   ]    dp[i][j]   dp[i][j]表示两个不下降子序列一个末尾在     i    i   i，一个末尾在     j    j   j，(     i   <   j    i<j   i<j)。 然后每次新加一个数     a   [   k   ]    a[k]   a[k]，枚举     i   ,   j    i,j   i,j的位置进行转移。 1.     a   [   k   ]   ≥   a   [   i   ]   ,   d   p...

题目链接 大意：给你一颗树，第一次选一个点染黑，之后从与黑点连接的白点中选点涂黑，问最大价值是多少？ 价值定义：每次选择涂的点可获得这个点的联通块大小的价值，简而言之就是，将黑点看为根的话，那么当前点的子树的节点数即为价值。 思路：考虑换根     d   p    dp   dp，先以     1    1   1为根，预处理每个点的子节点数目和染某个点的价值和。很显然，答案只与第一个点有关，与染的顺序无关，所以我们要考虑的就是每个点为第一次染的点的最大值。那么显然我们可以换根来解决。 在     d   f   s    dfs   dfs过程中，假设当前点为     n   o   w ...

题目链接 大意：给你两个数组     a   ,   b    a,b   a,b，第一个数组可以将任意子数组按非递减顺序排序，问你是否能变成第二个数组 思路：先将     a    a   a数组建一个最小值线段树，然后我们遍历     b    b   b数组，显然对于每个      b   i     b_i   bi​，我们需要一个下标最小的等于当前元素的      a   k     a_k   ak​来移动到     i    i   i这个位置，那么我们先考虑      b   1     b_1   b1​，显然，要想     a    a   a数组与      b   1 ...

题目链接 题意：本题就是很显然的题意，让你求出共有多少个最长上升子序列，每个数在多少个最长上升子序列中。 这题的难点在于如何求出每个数在多少最长上升子序列中，显然可以用dp，直接dp时间复杂度不允许，由于我们只在前缀上转移，于是我们可以用树状数组优化dp，考虑一个结构体数组，有两个值，一个为以当前数结尾的最长上升子序列长度，一个是数量，我们每次遍历a数组（即输入的数组），查询在以     [   1   ,    a    t   h     −   1   ]    [1,a_{th}-1]   [1,ath​−1]这个范围结尾的LIS最长长度和数量。即可以推出以这个数结尾的LIS长度和数量...

xyq0220

题目链接 大意：给你两个不连通的树，让你加一条边，使得两个树联通，并且使得      ∑   i   n     ∑    i   +   1    n    d   i   s   (   i   ,   j   )    \sum_i^n\sum_{i+1}^ndis(i,j)   ∑in​∑i+1n​dis(i,j)最小。 思路：首先我们需要一个dfs将两个联通块的点求出来，然后再用一个dfs求出以每个点的子节点个数，和每个点的子节点的dis之和，用两个数组，cnt数组记录子节点个数，dp数组记录子节点的dis之和，设f为父节点，点集s为f的子节点集合，那么      d   p   [...

题目链接 大意：给你一个字符串，让你找出长度为k的子序列满足每个字符出现次数的区间满足所有限制。 思路：先倒着处理一遍字符串，然后贪心选k次，每次从     a   −   z    a-z   a−z判断是否能选即可。 细节处理一下即可： #include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mp make_pair #define pb push_back using namespace std; LL gcd(LL a,LL b){return b?gcd...

题目链接 大意：给你一个长度为n的数组，然后每个元素都是     [   1   ,   c   ]    [1,c]   [1,c]之间的整数，然后让你求一个最大的子数组使得这个子数组中每种数出现的次数大于k次，问你满足条件的最长子数组。 思路：先假设右端点为n，对所有的数预处一遍，枚举每种数，如果没出现的话显然     [   1   ,   n   ]    [1,n]   [1,n]的每个数当左端点都可以，若出现超过k次，那么显然有两端封闭的区间可以满足条件，一个是没出现过这个数的所有位置，一个是出现多于k次的，我们假设集合      S   i     S_i   Si​是i这个数字...