题目链接 大意：给你两个字符串a,b，问你第一个字符串有多少子序列的十进制表示大于第二个字符串的十进制表示 思路：考虑     d   p    dp   dp      d   p   [   i   ]   [   [   0   ]   表   示   a   字   符   串   中   长   度   为   i   的   子   序   列   等   于   b   的   个   数    dp[i][[0]表示a字符串中长度为i的子序列等于b的个数   dp[i][[0]表示a字符串中长度为i的子序列等于b的个数      d   p   [   i   ]   [   ...

题目链接 大意：给你一个长度为n的数组，m个询问，每次询问给你一个区间     [   l   ,   r   ]    [l,r]   [l,r]，给你一个p 设长度为     r   −   l   +   1    r-l+1   r−l+1的数组S，其中      S   i    =   ∣   p   −    a    l   +   i   −   1     ∣   ,   i   ∈   [   1   ,   r   −   l   +   1   ]    S_i=|p-a_{l+i-1}|,i\in[1,r-l+1]   Si​=∣p−al+i−1​∣,i∈[1,r−...

Lianjie 化简一下公式：      p   =   1    0   9    +   7    p=10^9+7   p=109+7       ∑    i   =   1    n     ∑    j   =   1    m     (   i   j    (   n   %   i   )     (   m   %   j   )    )    %   p    \sum ^{n}_{i=1}\sum ^{m}_{j=1}\left( ij\left( n\% i\right) \left( m\% j\right) \right) \% p   ∑i=1n​∑j=1m...

题目链接 题意：给你一个长度为n的数组和一个k，让你对每个i，你可以改变     1   ∼   i   −   1    1\sim i-1   1∼i−1的任何一个数为0，使得      ∑    j   =   1    i     a   j    ≤   k    \sum_{j=1}^ia_j\leq k   ∑j=1i​aj​≤k，问你对每个i至少需要改变多少个元素的值，每个i独立，互不影响。 思路：我们先对a种的元素进行离散化，然后用两个树状数组分别维护前缀和和每个数出现的次数，然后对于每个i显然我们先得 二分一个极大值的值pos,使得pos是满足条件的最大值，那么对于pos+...

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

题目链接 大意：给你一个字符串，让你找出长度为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...

题目链接 大意：给你两个不连通的树，让你加一条边，使得两个树联通，并且使得      ∑   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   [...

题目链接 大意：给你两个不连通的树，让你加一条边，使得两个树联通，并且使得      ∑   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   [...

#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(b,a%b):a;} LL lcm(LL a,LL b){return a/gcd(a,b)*b;} LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=...

xyq0220

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

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

题目链接 大意：给你两个数组     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 ...

题目链接 大意：给你两个数组     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 ...