题目链接 大意：给你一个数组，询问一个区间仅出现一次的数。 思路：我们记录每个位置x左边的第一个相同数的位置y，记为这个x的值为y，如果左边没数的话就是0，然后询问的区间必然是满足存在一个     t   ,   t   ∈   [   l   ,   r   ]    t,t\in[l,r]   t,t∈[l,r]，且     f   (   t   )   <   l    f(t)<l   f(t)<l，     f   (   t   )    f(t)   f(t)就是左边第一个数的位置，如果找到的这个t，那么答案就存在。 我们将询问离线，按r升序排...

题目链接 大意：给你一棵树，问你树上距离等于x的无序点对个数 点分治模板题，直接做 #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 b) {r...

题目链接 大意：给你一个目标点，让你从(0,0)出发走k步到(n,m)，（8个方向），问你最多能走几次斜着的，或者不能到 思路：我们思考一下我们该怎么走，显然我们上来先斜着走到一个坐标为0，（从(n,m)到(0,0) ），然后我们看剩余的步数last和剩下的k，的奇偶关系。（首先要满足能走到的条件） 如果两个都是偶数的话，我们显然可以直接走完k步 如果last是偶数但是k是奇数的话，我们显然要把之前斜着走的一次给换成直着走的，然后奇数k走一次直的就成偶数了，然后剩下的再斜着走就行。 last是奇数的情况直接输出K-1就行了。。因为我们可以走到目标点的相邻点然后直着走一次就到了 #include...

题目链接 大意：给你n个数，支持修改和查询操作 查询一个和最小的集合，使得该集合不平衡(就是不满足：集合的和的所有位上的数字等于集合中的至少一个数的同位) 思路：显然我们要找到某一位上存在两个不为0的最小数，这两个数加起来就是答案。 显然我们要拆分每一位建10颗线段树。具体做法：把每个数拆开，看每一位是多少，如果是0，那么贡献就是无穷大，否则就是原本的数。 修改就算重新拆一下数往上但点更新即可。。。 然后我们查询就是查10颗线段树上的前2小数的和。 细节见代码： #include<bits/stdc++.h> #define fi first #define se second #...

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

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

题目链接 预处理：     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(...

本文原地址 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 = ...

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

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

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...

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

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

题目链接 大意：让你      ∑    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维护...