A 两个正整数 ，。对于任意整数 ，都有 ，不管怎么操作，两个数的 都不会变小。所以只需要判断初始给出的数组是否为孤独的数组，如果是，输出 ，否则输出 。 复杂度为 。 #include <bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+10,mod=1e9+7; ll A[N]; int main() { int n; cin>>n; for (int i=1; i<=n; i++) cin>>A[i]; for (int i=...

A 一个数有 个因子，第 个因子必然是它本身，所以不管哪个因子，都必然能整除它本身，所以直接输出 即可。 时间复杂度 ：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=50310925 B 第一步： 或者 等于 ，输出 。第二步： 是奇数 由于不管怎么操作，都必然会翻倍，所以 需要是偶数才能实现，输出 。第三步：，这种情况必然可以通过 次操作，让其中一个瓶子的饮料变成 毫升，然后结束操作的时候翻倍达到了 ，输出 。第四步：，不管怎么倒饮料，设 为两个瓶子的饮料总毫升，每次操作后 都会...

我们先根据题意一步一步分析，由于只是给出树的节点个数，树可以由我们任意构造，我们假设n个节点取得答案最大的时候树长这样根节点root，连接着k个子树，k个子树大小分别为sum1,sum2.....sumk，有我们令ans[n]为n个节点的树所得的最优解root的“心腹”其实就是root的重儿子，我们root的重儿子是所在子树是X，重儿子中全部节点到root的费用，是不是就是ans[sumX]，因为经过重儿子的边到父节点不会有任何影响。如果不是重儿子的所在子树Y（Y不等于X），这个子树的全部节点到root的贡献，是否都需要+1（题意转换，不理解的话仔细读题），因此这个子树的全部点到root的费用...

根据题意，一个点延伸的所有边，一定是颜色不一样的，求最小颜色数和方案。由于是二分图，最小颜色很显然是全部点的最大度数，关键就在于如何求解方案？我们这样思考，由于存在最小颜色数是最大度数这一结论，所以，我们每次使用一个颜色后，所有度数最大的点的度数肯定会减一，不然就会得出一个错误的构造方案（与结论相反），对于每个颜色，由于同色的边肯定没有交点，所以可以看成二分图上的匹配，我们对于每个颜色，使得度数最大的所有点，全部匹配成功即可，枚举颜色，多次匹配。但是这又会出现一个新的问题：如何保证度数最大的点全部匹配成功？因为二分图最大匹配算法（匈牙利算法）的匹配过程是-----如果不能新增一个成功匹配，就不...

题意简洁明了， 数据级别，直接排除了多源最短路的算法，值得一提的是， 十分奇特，一棵树的边是 ，我们可以将这个图看成一棵树加上100条以内的边的图。先考虑一棵树，如何求两点距离？我们需要前置知识点：LCA（最近公共祖先）红色框框的两个节点u,v，求他们的距离，看他们的深度:depth[u]=4，depth[v]=3，depth[lca]=2细心观察，可以发现他们的树上的距离公式：对于求LCA，方法也多种多样，倍增，树剖都是常用的主流方法，因个人喜好，影响不大。我们解决了这个问题，那么对于多出来的100条边怎么办？（不一定是100条，其实是多出来的边数为m-n+1条，下文为了方便，一律写100条...

根据题意，找出左右子树最大差值，这个最大值一定是通过这颗树的根节点的左右子树的差值得到的，对于左子树，我们可以令他为满二叉树，这样的节点数最多，假设深度为n，那么左子树为满二叉树的节点数 ,对于右子树，如果差值要越大，那么节点数尽可能小，我们只要求出高度差为不超过d且深度为n-d-1的平衡树的最少节点数即可，接下来上图：假设n=8 d=2；如何构造最小的二叉树，一步一步递推，以下全部是左右子树差值不超过d=2的平衡二叉树的最少节点画法 深度为1 深度为2 深度为3 深度为4 深度为5 深度为6 深度为7 深度为8 上面全部图都是差值为d=2的限制我们可以发现...

对于一个区间[L,R],对于X二进制下的每一位，如果第i位1，那么对总和的贡献就是[L,R]中的元素第i位是0的元素个数，反之，所以对于X的每一位i的取值依赖于[L,R]中所有元素该位中0，1的数量，如果1居多，那我们就设置0，得到的总和就会大一点，否则就设置1，前缀和预处理一下即可。 #include <cctype> #include <cfloat> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include &l...

以时间为下标，1~n，每个位置的值初始化为当天可以出租的教室数量，按顺序处理订单，对于每个订单d s t，在区间[s,t]减去d，如果出现了区间最小值出现了小于零的情况，说明不符合，直接输出然后return 0，否则处理完全部订单之后输出0即可。 #include <cctype> #include <cfloat> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include...

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44026704 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44026604 两份代码除了遍历顺序不一样，其他完全一样，为什么就一份wa了呢？感觉和遍历顺序没关系啊，求帮助！！！

假设节点颜色为 ,对于求颜色 在树上距离最大的两点，我们需要先找出树上颜色为 的距离最大的两点，找出树上颜色为 的距离最大的两点，然后枚举求不同颜色的两点距离，得到的最大值就是 的最远距离。 所以，我们只需要预处理出所有颜色的最远两点，然后计算的时候用LCA求距离即可。 当然，颜色可能很多，多达 种，并且树的节点也是 ，如果直接一一枚举颜色，然后在原树上dp求最远距离，复杂度将会是 ,肯定不行，我们想，原树上是不是有很多节点，我们可能并不需要，我们不用耗费时间去遍历，所以，我们需要在寻找一个新颜色的时候，重构一棵虚树，把不需要的节点全部给抛弃（不是说颜色不是所求的颜色就不需要，有可能有一些连接...

相信珂学emmm，一眼板子题，直接珂朵莉树，set针对区间覆值进行启发式合并，使用内置二分函数lower_bound分裂区间左右端点，然后暴力模拟，十分简单粗暴，操作1和操作2都是暴力，直接for，为何不会超时，就因为有操作3，每次区间赋值，我们可以将区间合并为一个，直接用结构体表示struce node={l,r,val}，这就是珂朵莉树的精髓了，至于操作4的添加节点，因为一般来说set里面都会插入一个末尾节点，下标比数组大1，为了方便分裂区间右端点为数组末尾的操作,所以用一个变量记录数组末尾下标，然后每次操作4，先删除set的末尾节点，然后扩展一个新节点，然后标记末尾变量+1，再插入末尾标...

， 如果k是奇数，那么sum也是奇数，如果k是偶数，那么sum也是偶数，第一步先判断n和k的奇偶性是否一致，第二步，因为正偶数2开始，正奇数1开始，所以最小总和为 ，判断n是否小于这个最小值，如果小于就 ，否则 #include <bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while (t--) { long long n,k; cin>>n>>k; if (3*k>n) cout&l...

由于要求全部子区间都存在唯一元素，所以最初可以判断 是否符合，直接暴力for，然后记录只出现一次的元素的下标，存进一个vector里面，我们可以发现，只要包含唯一元素的区间，肯定符合条件，因为在区间 唯一，所以其他区间该元素肯定也唯一，就像分治一样，以这些唯一元素为分界点，递归其剩余区间。例如区间 ，出现3个唯一元素下标为 ，那么我们需要递归4个区间， 判断是否符合，因为这样做复杂度很迷，所以需要加上一个判断，读入的时候只要出现相邻元素一样，直接输出 #include <cctype> #include <cfloat> #include <cmath>...

繁琐的模拟题，本来不打算做的，正当退缩的时候突然发现，好像实现起来代码量挺少的，就那么几个情况，于是写了一会就过了，也不算太复杂，找到了刚学算法的时候做题的那种感觉（雾），模拟大法好啊 ~~ 主要是分类讨论，用vector G[maxn]存起来每一类，括号()的全部放到一个vector，不然就下一个vector，读{digit} 的时候用个数组pos储存该vector的元素出现几次即可。 #include <cctype> #include <cfloat> #include <cmath> #include <cstdio> #include ...