题意 给你一个初始值为的序列。你现在有两种操作，一是给的区间加；二是再执行一遍第次到第次的操作。 思路 两次差分。第一次为处理第二种操作，我们定义为第次操作要执行的次数，用差分实现。第二次是处理区间加，也可以用差分。 所以，差分就对啦！ 代码 #include<bits/stdc++.h> #define ll long long const int N=1e5+5,INF=0x3f3f3f3f,mod=1e9+7; using namespace std; int n,m; int opt[N],l[N],r[N],ans[N],sum[N]; inline int read...

题意 有个稻草在不同的位置，还有头奶牛，每头奶牛炸的范围为，求的最小值； 分析 显然的二分答案，对于进行二分，取，取的最大值。至于函数，用来维护已经使用的奶牛个数，再用来记录以爆破的位置。如果当前已爆破的范围小于下一个能触及的范围，则需要一头新的奶牛，如果大于，则可直接返回。否则直到最后都没有大于则满足，更新答案。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e5+5,INF=0x3f3f3f3f,mod=998244353; using namespace std; int n,k; int x[N]...

写在前面的话 蒟蒻流下了不学无术的眼泪，英语不好是真的硬伤，蒟蒻在巨佬的提示下才勉强明白了题意 题意 你有条按顺序（很重要！）给出的线段，要求你使用最少的线段覆盖。另外在你选择一条线段时你必须保证你的前置线段已全部被覆盖。 思路 我们可以定义为前个排序器将第个数提到所需要的最少的排序器的数量，那么当的时候 当的时候 ,我们状态数有个，显然是会飞的结果啊。所以考虑使用线段树来优化一下就好。 代码 #include <algorithm> #include <bitset> #include <cctype> #include <cmath> #i...

题意 有台电脑,每台电脑，他的初始电量为，每分钟消耗电量为 你有一个功率为的充电器，每分钟可以使一台电脑电量增加。问，至少为多大才能保证在的时间内任意一台电脑电量都不为负 思路 直接二分充电器的功率。那么接下来就考虑如何这个功率值。 考虑使用优先队列，按照还能使用的时间排序，每次贪心的选取可以撑的时间最少的加上的电，然后每当有可以超过的，就直接移出队列，当队列为空时，便为成功，然后继续二分即可. 代码 #include<bits/stdc++.h> #define ll long long const ll N=1e6+5,INF=2e12; using namespace std...

题意 给你一的网格图，表示通路，为障碍。你有次机会使得障碍变为道路（变为）。求这张图上的最大欧几里得距离。 思路 先预处理表示一个点到任意点之间的障碍个数，如果小于则视为通路。再求这一点和全图的最大欧几里得距离。最后枚举全图每一个点作为起点的情况，再用记录最大值就可以了。 代码 #include<bits/stdc++.h> #define ll long long const int N=1e3+5,INF=0x3f3f3f3f; using namespace std; int n,m,t; int map_[N][N],dis[N][N],ans; int mx[5]={...

一眼看去，就是个多重背包嘛~~ 但是看一下数据范围，emm，好的，换思路。 首先考虑，如果没有次数限制的话，那么直接完全背包预处理，然后询问就好了。 然后考虑容斥，从中减去不合法的方案。首先肯定会有一种硬币超额使用，对于第种硬币等于说强制选了个，剩下的依然随便选，那么对于第种硬币不合法的方案数等于，于是从里减去就可以了。 另外，第一、二种，第一、三种，第一、四种，第二、三种，第二、四种，第三、四种都非法的方案在上一步中都被减了两次，所以额外都加一次回来。 #include<bits/stdc++.h> #define int long long const int N=1e5+5,...

一眼看上去就是一个经典题啊 直接考虑不是很容易那就容斥 全部方案为：一对相邻：,此情况有种两对相邻：,此情况有种……所以： 最后预处理一下就可以了。 #include<bits/stdc++.h> #define ll long long const ll N=30000010,INF=0x3f3f3f3f,P=1e9+7; using namespace std; inline ll read() { register ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1;...

这道题最主要的就是问题的转化，转化完就是一道**题了。 仔细的分析一下，题目中要求“再次出现1,2,3...N的排列”，或者也就是问要进行多少次“置换操作”得到原排列，而我们知道任何置换都是可以写成循环乘积的形式的。 也就是比如对于 1->3 2->4 3->1 4->5 5->2我们可以化简为 (1 3)(2 4 5)而对于一个给定置换，问它要多少次才能再次得到原排列，显然只有这个置换分解出的的各个循环的长度是我们关心的。比如对于上例中的置换，我们只需要直到它分解出两个循环，长度为2与3即可断定其只需6次即可得到原排列。也就是所有循环的长度的最小公倍数次。但这不...

题目大意: 你有一棵树,问你距离为二的节点的最大联合权值与联合权值和 分析 在巨佬的提示下得到了思路，这不就是枚举每个点作为中间点，再枚举儿子们。求一下最大值和权值和就好了啊。 #include<bits/stdc++.h> #define ll long long const int N=2e6+5,INF=0x3f3f3f3f,mod=10007; using namespace std; int n,cnt,ans,maxx; int w[N],head[N]; struct node { int to,next_; }e[N<<1]; inline ...

首先说一下题意。 这题就是给你一棵树，求树上所有路径中异或和最大的。 一个前置小芝士：01trie树不会的童鞋自行百度一下（雾） 好了，分析一下本题 我们对于每一个数到根节点的异或和进行建01trie树。我们知道一个数，如果它两次异或同一个数，那么它是不会变的。所以i-j的路径上的异或和，就可以表示成根到i的异或和异或上根到j的异或和。我们就以一个点为根，预处理出根到其他所有节点的路径异或和。那我们就可以贪心的选取，因为当前位的权值是大于后面所有位的权值之和的。如（1000）=（8）>（0111）=（7）。所以我们每一位贪心的选取异或后为1的点，否则沿原路向下走。 #include&lt...

首先可以初步判断这个题肯定要计算LCA，我们、就写个简单的倍增只会这个吧，使用链式前向星存储边。 选择1号结点开始dfs dfs过程中计算up[ ][ ]数组（up[x][i]表示 x 结点的 2^i代祖先是谁）和deep[ ]数组（deep[x]表示结点 x 在树中的深度） 然后我们不从运动员入手，而是枚举观察员。看看哪些结点会为这个观察员i做贡献（刚好在wi秒跑到他这儿）。 大头戏来了 AC代码 #include<algorithm> #include<bitset> #include<cctype> #include<cmath> #inc...