非常抱歉G题本来是换一道题目的，本来想把题目出的更有好一些，结果同学说是找了一道内部校赛题目，结果撞了原题，抱歉给大家打来不好的体验，其实是不是可以删掉G题？但是声明一下D题不是原题，这题的数据范围和原题有一定的出入，导致可能算法有60%的不同 这题非常签到我们可以直接用的或者就可以了，然后您就签到成功代码： #include<bits/stdc++.h> using namespace std; int a[1000005],n; map<int,int> mp; long long ans; int main(){ cin>>n; fo...

起因是提高组周赛，首先我同学“撞了快艇下大雨”昨天发了一些...言论，其实是事实，但是他确实有些冲动了，不过也是希望牛客能够改善吧 这里我劝他删掉了帖子，我在这里做下说明，下面我就说一些具体建议吧 本人在练习赛77的题面里出了点锅（确实是本人不长写博客，不怎么用latex，给大家赔个不是），后来也想了很多有关于出题的事吧，这里列举一些建议 1 出题人的水平要注意 但是这个水平要多方面评估 好像改进方案里写了要公开出题人的信息，我个人觉得不是特别合理，因为有些dalao可能并不愿意公开自己的个人信息或者cf账号等等 首先我觉得要依每个人的风格，可以是nowco...

牛客练习赛77是本人命题，由于latex的缘故导致前三道题的描述出了些问题 首先非常抱歉给大家带来了不好的体验，其次如果要喷请不要喷牛客，全是本人的责任。 出题人再此，甘愿接受指责，欢迎提出建议。 还有牛客练习赛79是本人和一位dalao共同出的题目，排版方面主要有他负责，有三道题目是本人提供的，希望能当给大家一次补偿的机会吧，欢迎大家来玩。 这次比赛确实出了点问题（本人不太会用nowcoder的latex），还请大家见谅。

T1 签到题，等差数列求和O(1)输出即可 T2 类似的思路，我们发现约数的条件我们也是可以转化成倍数的 这样就是考虑x的倍数在n之内的数的求和，我们同样可以用等差数列求和来求出来 T3 容易发现我们的这个函数G(n)=sum i=1..n i*n/i 这个很好想我们只需要知道每个i出现在约数有多少个倍数满足这个条件，因此还是转化成倍数问题 于是这个我们其实可以用整除分块来优化 推荐一个博客：https://www.cnblogs.com/peng-ym/p/8661118.html T4 本题我们用一种折半思想类似折半的思想来做 相当于我们枚举一位，然后另外一位用meeting in ...

T1签到题，等差数列求和O(1)输出即可 T2类似的思路，我们发现约数的条件我们也是可以转化成倍数的这样就是考虑x的倍数在n之内的数的求和，我们同样可以用等差数列求和来求出来 T3容易发现我们的这个函数G(n)=sum i=1..n i*n/i这个很好想我们只需要知道每个i出现在约数有多少个倍数满足这个条件，因此还是转化成倍数问题于是这个我们其实可以用整除分块来优化推荐一个博客：https://www.cnblogs.com/peng-ym/p/8661118.html T4本题我们用一种折半思想类似折半的思想来做相当于我们枚举一位，然后另外一位用meeting in the middle做但...

会写就行了，我们先求出在root情况下的lca，发现实际上是所有lca中深度最大的那个，于是我们可以分情况大力讨论一下lca和root的关系，同理我们query的时候也是讨论一下当前x和root的关系剩下就只需要一个求k级祖先的过程，这个我们可以长链剖分，但是作者直接写了个倍增的log求法剩下树剖就完了！代码： #include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> #include<queue> ...

首先我们把树上的子树问题转化成一维序列上的问题之后我们发现颜色数的处理暴力合并比较慢，但是由于颜色数较小，我们可以直接压位一下，然后直接取个or就可以了实际上不需要什么bitset，builtinpopcountll也是O(1)复杂度的！具体实现线段树上打tag常规操作做一下。代码： #include<bits/stdc++.h> using namespace std; #define debug(x) cerr<<#x<<" = "<<x #define sp <<" " #define ...

这道题之前可以用4e8左右的复杂度通过，现在加强了一发好像有很多质数，我们只需要套用millerRobin就可以通过现在的数据了，但是其实还有办法卡，因为标算应该是还要加上pollardrho，我们只需要对于所有的质因数见一个树，实际上不用建出来，然后根据这个质因数在树上DFS，还是按照平常找直径的方法来搞，就可以了。代码： #include<bits/stdc++.h> using namespace std; #define debug(x) cerr<<#x<<" = "<<x #define sp <<&q...

与其说这题是贪心题这题更像一个构造题，非常开阔思维首先我们随便以一个A或B为关键字排序，然后发现N/2+1这个加1很重要，根据经验暗示我们选第一个然后接下来我们钦定假设以A为第一关键字排序于是我们剩下的每两个选一个B那位max的，可以发现B显然是满足条件的，那么A满足条件吗？a[1].A>=max(a[2].A,a[3].A),min(a[2].A,a[3].A)>=max(a[4].A,a[5].A)以此类推肯定满足条件于是我们构造出来了方案，偶数最后一个数也选特别判断一下就好了代码： #include<bits/stdc++.h> using namespace s...

提供一种新做法，理论复杂度更快，我们用bitset加速维护发现一共只有三种可能，放左边放右边和不放我们初始设定一个sum以防负数，然后左右移位就可以了代码： #include<bits/stdc++.h> using namespace std; #define LL long long #define DB double #define M 20200 int n,a[M],Q; bitset<M>B,tmp; int main(){ while(scanf("%d",&n)!=EOF){ int all=0; ...

这题还是有点新意的，套路部分就不讲了，我们套路前缀和，然后就知道要用一个trie树这样的东西来维护一下，如果有人这里不是很熟可以看一下我之前写的https://blog.nowcoder.net/n/744869ac01154d47b1240cfaebc3839e接着我们来看一下如何处理，我们有点像是在trie上统计若干的子树的sz和，这样的一个二分的过程我们来看具体维护，我们考虑当前是在第k位，然后当前val的第k位是x，K的第k为是y那么如果y是0那么我们相当于对于xor val的这一位就有两种选择其中如果异或出来是1的那种选法我们无论底下怎么选都是满足条件的反之我们就必须只有一种选法。具...

简单题，我们发现边数和点数都很小允许我们可以用平方做法来做，然后我们直接枚举最小的边权，依次往上最小做生成树，然后把所有得出的答案取个最优就可以了，在这里我们可以把并查集的复杂度看成是O(1)的，因为边数只有500。具体细节需要我们判断分数的大小和一些无解的情况，看一下代码就ok了代码： #include<bits/stdc++.h> #define LL long long using namespace std; const int N=505,M=5e3+5; struct Graph{int u,v,w;}gra[M]; int n,m,s,t,fa[N],fz=-1,f...