题目链接 题目大意：  思路：用单调栈维护最优决策的集合。 我们倒着遍历数组，每次遍历到的相当于     i    i   i, 每次新建一个决策     {    a   i    ,    l   i    ,    r   i    ,   x   }    \left\{ a_i,l_i,r_i,x\right\}   {ai​,li​,ri​,x}，意为：当前最优     x    x   x位置的时候包含的右端点区间为      l   i    ,    r   i     l_i,r_i   li​,ri​，然后更新是在top的两个决策之间，设两个决策分别为     n   e...

官方题解：  代码如下： #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define LL long long #define pii pair<int,int> #define SZ(x) (int)x.size() #define all(x) x.begin(),x.end() using namespace std; LL gcd(LL a, LL b) {return b ? gcd(b, a % b) ...

题目链接 大意：输出每个i为开头情况下的满足字典序最大的长度。 思路：每个i的答案显然是在[pos-k,pos+k]中取一个最大的且不超过i的答案+1，那么，我们可以用树状数组预处理出每个i在区间内小于他的个数，然后用主席树直接差区间第x小即可。 树状数组的操作细节为，把区间拆成左右两部分，然后求前缀小于i的值，两个剪一下就是区间了。 细节见代码 #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define LL long lo...

题目链接 大意：给你一个数组，每次询问一个区间，问你区间     l   ,   r    l,r   l,r内合法的     (   i   ,   j   )    (i,j)   (i,j)有多少对。 若     m   i   n   (    a   i    ,    a   j    )   =   g   c   d   (    a   i    ,    a   j    )    min(a_i,a_j)=gcd(a_i,a_j)   min(ai​,aj​)=gcd(ai​,aj​)则合法。 思路：离线处理。 先预处理出和每个i构成合法区间的所有j，我们用两个     ...

题目链接 大意：让你      ∑    i   =   1     n   −   1      ∑    j   =   i   +   1    n    v   a   l   u   e   (   i   ,   j   )    \sum_{i=1}^{n-1}\sum_{j=i+1}^nvalue(i,j)   ∑i=1n−1​∑j=i+1n​value(i,j)，其中     v   a   l   u   e   (   i   ,   j   )    value(i,j)   value(i,j)为区间第二大的数 思路：考虑每个值的贡献，从大到小扫，我们用两个set维护...

题目链接 大意：给你长度n的数组和k，让你输出n个数，表示每个位置向右最远的位置pos，使得a[pos]-a[i]>=k，输出两个位置中间隔的数量。 思路：直接建一个维护区间最大值的线段树，每次查询直接查[i+1,n]范围内>=a[i]+k的最远位置即可。 我们查询的时候先查右儿子，没查到就查左儿子，否则答案必然在右儿子中，右儿子中没答案的话，那么答案必然在左儿子中（查询的区间要合法）  #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mp m...

题目链接 大意：给你一个长度n的数组，和两个数l,r，问你有多少区间满足     l   ≤    ∑    i   =   l    r     a   i    ≤   r    l \leq \sum_{i=l}^ra_i\leq r   l≤∑i=lr​ai​≤r，输出即可。 思路：枚举区间右端点j，即我们要找的就是有多少个i，使得     i   <   j   且   l   ≤   s   u   m   [   j   ]   −   s   u   m   [   i   ]   ≤   r    i<j 且 l\leq sum[j]-sum[i]...

J - Weird Sanchola （贪心) 我们思考一下最终的素数取什么最优，假设素数     P    P   P，有     L    L   L个元素小于等于     P    P   P,有     R    R   R个元素大于     P    P   P, 那么我们需要移动的次数就显然是     P   ∗   (   L   −   R   )   −   s   u    m    ≤   p     +   s   u    m    >   p      P*(L-R)-sum_{\leq p}+sum_{>p}   P∗(L−R)−sum...

题目链接 大意：让你求树上%3后分别为0，1，2的所有路径之和。 思路：树上路径分为两种，过根节点的，和 在子树的，所以直接点分治，在计算每个根节点的贡献的时候，统计一下%3分别为0 1 2 的路径数，和 路径和，然后每次直接算一下贡献就好了。 细节见代码： #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mp make_pair #define LL long long #define SZ(X) X.size() #define pii pair&lt...

题目链接 大意：有个无向图，你从1出发，可以到任意联通的非怪物点，你至多可以选择一个可达的怪物房间使用魔法，传送到随机一个与怪物点相邻的点上，问你取得糖果的期望值（操作者足够聪明）。 思路：我们先dfs记录一下，不到怪物房间就能取到的糖果数量，这一部分肯定是可以直接拿的，剩下就是从那些相邻（意为不用经过怪物房间就能到的怪物房间）的怪物房间取一个最优的。 这个最优也是dfs记录从当前怪物点出发，随机下一个儿子，dfs计算能取到的糖果数量（同上面的dfs一样，不遇到怪物）加起来，除以儿子数量。 注意中间要记录访问过的点，不然会段错误哦。 细节见代码： #include<bits/stdc++...

本文原地址 const int MAXN=150; struct bign { int len, s[MAXN]; bign () { memset(s, 0, sizeof(s)); len = 1; } bign (int num) { *this = num; } bign (const char *num) { *this = num; } bign operator = (const int num) { char s[MAXN]; sprintf(s, "%d", num); *this = s; return *this; } bign operator = ...

题目链接 预处理：     d   p   [   i   ]   [   j   ]   [   k   ]    dp[i][j][k]   dp[i][j][k]表示i行诗，第j层，最大字母是k有多少个。 然后直接dfs找就行了。 #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define LL bign #define pii pair<int,int> #define SZ(x) (int)x.size(...

题目链接 每次找重心，然后处理每个子树。 // luogu-judger-enable-o2 #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mp make_pair #define LL long long #define SZ(X) X.size() #define pii pair<int,int> #define ALL(X) X.begin(),X.end() using namespace std; LL gcd(LL a, LL ...

题目链接 大意：初始n天都是工作日，给你q个操作，分别是把l,r变成工作日或者非工作日。让你求出工作日的天数。 思路：n很大，但操作数不大，所以我们要动态开点线段数来解决这个问题，算是裸题了。 记录每个点和左右儿子节点的编号，如果是新的点就新开一个节点。其他的操作都是根普通线段树一样拉 细节见代码： #include<bits/stdc++.h> #define fi first #define se second #define pb push_back #define mp make_pair #define LL long long #define SZ(X) X.size(...