传送门 假设只有操作一和操作三 操作一普通线段树可以完成,操作三普通线段树也能完成 做法是维护一个数组表示节点表示区间的 由于具有传递性,所以很容易维护。 假如只有操作一和操作三 操作一普通线段树可以轻松完成,操作二的话....势必要维护一个差分数组 也就是令 在线段树上维护这个数组的关系 比如在区间内加,只需要在加以及在位置减 那么求最大的绝对值的数组,只需要维护一个表示的绝对值即可 有了和,思路就出来了 建立两颗线段树,一颗维护原数组,一颗维护差分数组 第一棵树解决区间问题,第二棵树解决区间最大差值问题 但是我没有写代码因为还有T_4 其实只需要维护差分数组的线段树就能解决区间问题...

本来不算裸题,但是这个数据范围提示的太明显了 先对边按照编号排序 先保证最大 那么我们的边从一直并查集合并,一旦连通就停下来 那么这个一定是最大的 现在我们要求最小 那我们把并查集数组再次初始化,按顺序加边 一旦连通就停下来,此时是最小的 正确性显然....(不显然可以留言) #include <bits/stdc++.h> using namespace std; const int maxn = 1e6+10; struct edge{ int l,r,w; bool operator < (const edge&tmp ) const{ ...

传送门 求期望的套路题 转化为每个点染成黑色期望的累加和 那么如果本来就是黑色,期望直接加上 如果是白色,概率是多少呢??实际上可以考虑这个点在多少的最短路径上 选点有种方式 再计算有条最短路径经过这个点,那么一次操作覆盖这个点概率为 那么至少覆盖一次期望就是 累加即可 至于一个点在多少最短路径上,弗洛伊德即可 然后这样判断 #include <bits/stdc++.h> using namespace std; #define int long long int dis[509][509],n,m,k,color[509],vis[509]; const int mod = 1...

请各位来这里给菜鸡点个赞,评个论,收个藏呜呜呜 最近在学一点组合数学....但是自己太笨了害,一点很简单的东西要看好久 于是做一点笔记,方便自己以后复习....

非常考验技巧的一题...emm这个我最不会了... 首先断环为链,也就是把士兵和站台复制一份放在后面,这样只需要考虑覆盖一个区间而已 因为区间两两不包含,所以当选择了第个士兵后 现在覆盖了 那么从左端点不大于里选,一定是选右端点最大的最优秀了 那么这样选择的士兵就固定了... 关键就找下一个士兵的过程,可以二分预处理 但是倍增更快!!! 说起来 简单,但还是不会写,实现能力太差了... #include <bits/stdc++.h> using namespace std; int n,m; const int maxn = 4e5+10; struct soldier { ...

这题的思维难度并不很大 但是细节有一点点需要注意 首先两点间的距离如果是奇数必定无解 如果是偶数,那么可以找到中间的那个点,必定满足条件 而且从延伸出去的各种分支,只要不是包含的分枝都是满足条件的 因为两点都是从拐过去的 这个规律在任意时刻都是适用的 但是当deep[l]==deep[r]注意一下计算方式 #include <bits/stdc++.h> using namespace std; const int maxn = 4e5+10; int n; struct edge{ int to,nxt; }d[maxn]; int head[maxn],cnt=1; ...

不会证明,只会观察..... 两点肯定到最好 三点求出两两的,然后....观察!! 发现三点的最短路就是用两条链把三点穿起来 所以距离是两两距离和除以二 然后三个最多有一个和其他的不同 那么就选那个相同的点作为集合点,这样只会有一个点需要多走 #include <iostream> using namespace std; const int maxn= 6e5+10; struct edge{ int to,nxt; }d[maxn]; int head[maxn],cnt=1; void add(int u,int v) { d[++cnt] = (edge)...

传送门 观察发现一定是从连出来的边最划算 而且连到一个点之后,这个点周围的所有点都是满足要求的. 定义为和有连边 为通过父亲到 为通过儿子到 那么 那么 但是如果的儿子没有一个和有边,还需要选一个儿子和相连... #include <bits/stdc++.h> using namespace std; const int maxn = 4e5+10; struct edge{ int to,nxt; }d[maxn]; int head[maxn],cnt=1; void add(int u,int v) { d[++cnt]=(edge){v,head[u]}...

定义为前个书分成组的最大价值 这么转移是有后效性的 价值不是越大越好 观察到价值计算是与运算,可以一位一位单独考虑 比如,如果每组都能凑齐,那这一位上必然是 然后考虑能否凑齐,但是同时也要凑齐... 就这样一位一位去判断 还是比较显然的.... #include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 59; int f[maxn][maxn],a[maxn],k,n,pre[maxn]; bool ok(int x,int y){ return ((x&...

好难写....完全想不到,也不会证明 抄的https://ac.nowcoder.com/acm/problem/blogs/200179 好厉害呜呜 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5+7; int n,a[maxn],ans[maxn]; vector<int>g[maxn]; set<int>s[maxn]; int deep[maxn],fa[maxn][20],dfn[maxn],tag,in[maxn];...

传送门 使用数组表示当前子树内,深度字母为的有多少个 那么可以开始,这样与有关的所有询问都可以快速得出解 差不多就是板子了 储存询问用或链式前向星 #include <bits/stdc++.h> using namespace std; const int maxn = 5e5+19; struct edge{ int to,nxt; }d[maxn]; int head[maxn],ccnt=1; struct asking{ int to,nxt; bool ans; }ask[maxn]; int qhead[maxn],num=1; void add(in...

传送门 注意一下这两句话 如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大； 如果在左子树选了一个点，在右子树中选的其他点要比它小。 根节点比子节点都要小 右子树比左子树都要大 所以可以跑序维护最长上升子序列来写 #include <bits/stdc++.h> using namespace std; const int maxn = 2e5+10; int n,l[maxn],r[maxn],a[maxn],id,top,w[maxn],ans[maxn]; void dfs(int u) { if( u==0 ) return; a[++i...

不知道为什么这么裸... vec存图排个序 然后按照dfs的顺序给节点小到大编号 顺被维护一个表示节点编号是的是哪个节点... #include <bits/stdc++.h> using namespace std; const int maxn = 8e5+10; struct edge{ int to,nxt; }d[maxn]; int head[maxn],cnt=1; void add(int u,int v){ d[++cnt] = (edge){v,head[u]},head[u]=cnt; } int id[maxn],num,n,q,siz[ma...

在纸上画一棵树,发现如果是回路,每条边走两次就够了 那么不是回路,有些边就不需要走两次了 发现,任意选择两点,从端点出发,路上一旦出现分支就出去走两遍回来 这样走到两一个端点的时候,两点间的距离其实只被走了一次 这样的话就求树的直径就好了 有点像规律题呢 #include <bits/stdc++.h> using namespace std; #define int long long const int maxn = 5e5+10; int n,ans,temp; struct edge{ int to,nxt,w; }d[maxn]; int head[maxn],c...