题目链接 题目大意： 思路：用单调栈维护最优决策的集合。 我们倒着遍历数组，每次遍历到的相当于 i i i, 每次新建一个决策 { a i , ...

官方题解： 代码如下： #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 %...

题目链接 大意：输出每个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 lo...

题目链接 大意：给你一个数组，每次询问一个区间，问你区间 l , r l,r l,r内合法的 ( i , j ...

题目链接 大意：让你 ∑ i = 1 n − 1 ...

题目链接 大意：给你长度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 ...

题目链接 大意：给你一个长度n的数组，和两个数l,r，问你有多少区间满足 l ≤ ∑ i = l r ...

J - Weird Sanchola （贪心) 我们思考一下最终的素数取什么最优，假设素数 P P P，有 L L L个元素小于等于 P P ...

题目链接 大意：让你求树上%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 pai...

题目链接 大意：有个无向图，你从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 p [ i ] [ j ] [ k ...

题目链接 每次找重心，然后处理每个子树。 // 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...

题目链接 大意：初始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...