枚举上界和下界用判断连通,复杂度 枚举下界,上界可以二分,理论复杂度似乎能冲...但是T了 枚举下界,然后使用并查集动态加入边判断连通,复杂度,可以通过 枚举下界,使用取每个点最优(小)的上界。但是不知道可不可以,没试过 #include <bits/stdc++.h> using namespace std; const int maxn = 2e5+10; struct edge { int l,r,w; }d[maxn]; int mu,zi,n,m,s,t,pre[maxn]; double ans = 1e9; int gcd(int a,int b){ retu...

传送门 先说结论的做法 差分数组的和原数组相同 因为设原数组的啊为 那么每个数都是的倍数,每个数减去一个的倍数仍然不会改变整体的 那么数组的每个数加上,差分数组只有第一个数会加上去 也就是差分数组的的就是最大的,这样就非常简单 但是我太傻了,开始没想到这个结论^_^ 加上一个使得所有数字的最大,设最大的为 那么首先所有数模的意义下都是相同的,否则加上也不会改变余数 设最小数是,次小数是(已经去除了重复数字) 那么答案不可能比大,这样的话最小的两个数是不同余的 所以如果答案落在之间,要求,此时取是同余的 拿去检验一下即可 否则,考虑答案落在之中 由于要求模的意义下相等,必然有是的倍数 这样枚举...

传送门 一定存在的边放一起跑一边弗洛伊德 然后再加上可能存在的边跑弗洛伊德 这样是的 但是由于这里只需要判断是否连通,所以可以使用或运算、 也就是把每个点能到的点看成一个二进制数,这样可以使用优化复杂度 一定存在的边放一起跑一边弗洛伊德 然后再加上可能存在的边跑弗洛伊德 这样是的 但是由于这里只需要判断是否连通,所以可以使用或运算、 也就是把每个点能到的点看成一个二进制数,这样可以使用优化复杂度 一定存在的边放一起跑一边弗洛伊德 然后再加上可能存在的边跑弗洛伊德 这样是的 但是由于这里只需要判断是否连通,所以可以使用或运算、 也就是把每个点能到的点看成一个二进制数,这样可以使用优化复杂度 #i...

传送门 因为是,所以选出来的数一定都是答案的倍数 那么有一个很直观的方法 由于枚举每个数的约数复杂度是根号的 那就直接枚举约数,让 最后如果就代表有个数含有因子 那么选出这些数来一定是 然后从后往前更新答案 因为可以作为个数的,那么去掉任何一个属,也还可以作为选出个数的 #include <bits/stdc++.h> using namespace std; const int maxn = 2e5+10; int n,ok[maxn],ans[maxn]; int main() { cin >> n; for(int i=1;i<=n;i++)...

物品可以放左边也可以放在右边 其实可以看成一个物品可以作为重量也可以作为 那么看成个物品来一次$背包即可 但是这里稍微有点变化,物品的价值可能是负数 那么如果负数也按照我们倒序枚举会有问题,负数应该正序枚举 负数正序枚举能保证状态没有重复使用一个物品 当然如果你用的是二维数组来就不需要分两次了 #include <bits/stdc++.h> using namespace std; const int N = 1e4 + 10; int dp[N], a[N], n, m, sum; int main() { while (scanf("%d", &n) != EOF...

传送门 首先确定肯定使用字典树 然后因为异或的性质有 那么只需要把所有的前缀插入字典树 然后枚举端点去字典树上找有多少个即可 也就是对每一个都去字典树上找有多少个前缀满足条件 那么最后答案需要除以,因为每个一可以作为字典树上的前缀,也可以作为 值得一提的是需要把0插入进去 因为允许存在 那么我们也对前缀去字典树上查询,因为最后的答案是除以二的 如何查询??? 因为是二进制数比较大小,所以当的这一位是时 异或值必须是,否则无解,继续往下查询 当的这一位不是时 异或值是,那么直接累加符合条件的前缀个数 然后异或值是,继续查询 最后返回符合条件的个数即可 时间复杂度 #include <bi...

传送门 由于不能包括的因子 所以得到的数字分解质因子后必定都是大于等于的质因子 那么一个数的质因子不会个...好像没什么用 搜索的复杂度是上天的。 那就套路的容斥,求符合条件的就是求符合条件的 那么如何求的方案数.... 首先是倍数的数有个,在这基础上需要进行容斥,因为有数拥有比小的因子的同时也拥有 也就是减去是的倍数的数 这里使用递归计算 然后目测复杂度很低,因为一直除以 #include <bits/stdc++.h> using namespace std; #define int long long int a,b,k; bool isprime(int x) { ...

由于每条裙子被选中的概率相同,这点可以认为条裙子没有差异 那么定义为已经穿过条裙子,为了达到终止条件,期望还需要穿几次 意思是,选中穿过的裙子概率,选中没穿过的,然后本次也需要穿次裙子 那么化简得到 那么 上面提到每条裙子无差异,可以认为被穿过的次数相等,所以除以一个 每条裙子期望被穿过 不难发现这个时候只需要预处理这个调和级数的前缀和就可以知道每条裙子被穿过的期望次数 然后输出答案即可... 其实这是个经典的"邮票收集问题"，知道就很好写啦 #include<bits/stdc++.h> using namespace std; const int maxn = 1e7 + 5...

传送门 这里只说的把,也就是暴力枚举删除区间 似乎有更快的算法,以后再补 当删除某段区间后,最终剩下一段前缀和一段后缀作括号匹配 会自动消除 对于一段序列来说消除的顺序是不影响最终的结果的 不妨先对前缀做括号匹配,变成的形式 对后缀也做括号匹配,变成的形式 不难发现,此时能消除的只剩下前缀后面的连续零和后缀前面的连续一 所以直接预处理这两部分,还要预处理前缀自己匹配剩下的长度和后缀剩下的长度 用栈模拟括号匹配即可 #include <bits/stdc++.h> using namespace std; const int maxn=1e5+10; int n,top,pre[...

传送门 加入一直乘以二加上去的话只能构造到的时候就超过了 所以需要考虑为奇数的情况的操作 发现每一次递归下去都会让函数值 也就是说,奇数和偶数的函数变换只是让函数值而已,那么显然是选择奇数的变换更优 也就是说我们倒推回去,一直执行和就能得到最小的 这么构造最优,预处理即可 发现最大能构造到 然而我这个***,一开始把奇数的 这么转换之后,就再也没看出什么规律。 #include <bits/stdc++.h> using namespace std; #define int long long int a[209]; signed main() { memset( a,-1...

人都傻了 倒是模板,被的操作搞晕了... 返回一个大于等于查找元素的指针 是的末尾位置,但是最后一个元素在末尾位置的前面 当返回说明没找到这个元素 至于这里用也是有原因的,因为编号不重复,否则需要使用 回到这道题,维护每个点的结实度 显然想知道一个点的结实度必须要把所有子节点的编号排成一个序列计算 但是直接计算是的 考虑到这个序列是可以合并的,答案也是小幅度修改,可以使用 使用来储存当前子树内的编号序列 加入一个编号时,直接找到插入的前驱后继,累加权值 删除时同理 这样就变成模板了 插入时分四种情况来写 内元素个数只有个 无前驱 无后继 有前驱和后继 删除同理 然后就直接套用的模板 #inc...

非常巧妙的题(然而有什么用嘛!!!!我又不会) 如果只选一个数,一定选最大的数 Ⅱ 如果选两个数和,一定选掉最大的那个数 证明如下 ① 若只有一个数是的约数,那么拿去替换他 ② 若两个数都不是的约数,替换任何一个数都会时答案更优 ③ 若两个数都是的约数,那么最大就是 综上所诉,选择最大的才是最优的. Ⅲ. 选择三个数最大,有了上面的铺垫就不难推了.此时要不要选最大的数呢?? 若三个数都不是的约数,替换任何一个都会更优 若三个数只有一个是的约数,替换掉会更优 若三个数有两个是的约数,那么最大可以是 而我只要选和就可以否定掉这个答案。 若三个数都是的约数,最大的情况 ,确实此时需要特判一下 但...

水过(写这么详细是不是50nb呀!!!) 状态似乎无法压缩,假如压缩需要是一个长位的三进制数,不可取 难道就没法了吗 考虑到问题的特殊性,在确定了前行后,每列只需要放一个或者两个 设目前有列需要填充一个,有列需要填充两个 那么有行可以去填充数字,我们来枚举这行转移 是截至到第行填充后,还剩下列需要放一个,列需要放两个 那么枚举和,对当前行做出决策来转移 若本行选择的列都是需要放一个的,那么需要从列选出两列来 若本行选择的列都是需要放一个的,同理 若本行选择的两列,一个在需要放一个的列上,一个在需要放两个的列上 滚动数组来优化空间,然后时间复杂度仍然是 观察到由于每行只需要填充两个 而填充...

这题其实并不难啊,有个结论比较显然 下面推个狮子 #include <bits/stdc++.h> using namespace std; typedef long long LLL; const int N = 1e6 + 10, mod = 1e9 + 7, Mod = mod - 1; LLL prime[N], mu[N], Fib[N], phi[N], inv_Fib[N], f[N], cnt; bool st[N]; LLL quick_pow(LLL a, int n) { LLL res = 1; while(n) { if(n &...