Sol: A:小y的考试 我们按照字符串的长度排序然后分类讨论判断长度的关系，按照题目的要求输出就可以了。 注意字符串的读入方式。 B:小y的序列 题目要求的本质上是a[i]与i的关系，因此我们发现如果两个数i,j,a[i+1]-sum(1,i)和a[j+1]-sum(1,j)的定值如果相同，这两个彼此的关系就不需要修改，所以我们直接开一个map统计一下哪个值出现的次数最大。 对于n<=1000这个出现次数最大我们可以把它存下来求一个暴力n方求出和这个数相同的数个个数。 C:小y的旅行 对于40%的数据我们朴素维护连通性dfs就可以。 对于100%的数据我们考虑如果一条边...

A:牛牛和牛可乐的赌约简单题，我们还是正难则反，概率减一下全赢的概率就可以了。代码： #include<bits/stdc++.h> #define LL long long using namespace std; const int P=1e9+7; LL qpow(LL x,LL y){LL res=1;for(;y;y>>=1,x=x*x%P)if(y&1)res=res*x%P;return res;} int main(){ int T;scanf("%d",&T); while(T--){ ...

A:排列简单题，我们发现m不大，我们暴力模拟m次翻转过程。然后我们针对一次的变换求出倍增数组，倍增即可。复杂度：O(nm+nlogk)代码： #include<bits/stdc++.h> #define LL long long using namespace std; const int N=1e5+5; struct Range{int l,r;}a[15]; int n,m,k,id[N],ans[N],f[N][31]; int main(){ scanf("%d%d%d",&n,&m,&k); for(int ...

A:牛牛的mex题目要求一个区间的mex，可以离线，我们可以莫队维护。需要注意的是，因为我们要的是根号算法，不能带log，因此我们搞两个分块，一个是莫队的，一个是值域的。可以做到插入是O(1)的，单次查询是O(sqrt(n))的，就可以通过，总时间复杂度O(nsqrt(n))代码： #include<bits/stdc++.h> #define LL long long using namespace std; const int N=1e5+5,B=355; struct node{int l,r,id;}b[N]; int n,q,cntB,a[N],s[N],cnt[N],b...

悬线法是一类用于解决最大子矩阵的问题的算法，其大概的代码实现和dp递推差不多？大致算法是我们用一条线(横竖貌似都行)左右移动直到不满足约束条件或者到达边界，统计最大扩展的距离。然后我们注意的是红色的面积更大，这样的情况也可以在红色的边界被算上，所以这大概是悬线法算法的正确性。接下来举一些悬线法的例题，或者是思想类似于悬线法的例题来分析一下。 洛谷P1387 最大正方形https://www.luogu.com.cn/problem/P1387悬线法模板，只需要求三个数组l和r和up就可以。代码： #include<bits/stdc++.h> #define LL long lon...

题目链接：https://ac.nowcoder.com/acm/problem/205370题目难度：提高+/省选-推荐理由：思路非常妙，巧妙的运用了随机生成数据的特点，一道非常好的思维题题目知识点：位运算技巧，阈值思想题意描述：我们用一种随机生成数据的方式生成一个长度为n的序列，然后有m个询问，每次询问序列中是否存在和当前这个数xor以后二进制中1的个数小于等于3 这题如果不是随机的，可能不太可做。但是然后运用了随机的这个思想，我们考虑随机分布基本上是平均的，可以根据生日悖论推导一下。于是我们还有一种阈值的考虑方法，如果把他拆掉，拆成4个部分，每个部分是一个1<<16的范围是不...

A:数字计数简单题，基础模拟，我们sort一遍就可以了但是我们要用一个unique去重，不太熟悉unique的同学可以用一个桶，或者和上一次的值比较一下手动去重！然后直接输出，这个没什么好说的吧？代码： #include<bits/stdc++.h> #define LL long long using namespace std; int n,a[105]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); s...

A:小睿睿的数列我们注意到一个区间内的数字全部相同这种贡献是可以单独算的那么我们可以把它们都缩在一起然后我们发现我们每个点的gcd要使找得到，一定是下一次是这一次的约数，然后我们不断向两边扩展，由于是约数而且我们规定了它们不同，所以每次至少是上次的两倍，这样最多是log次的我们找一个起点作为gcd然后向两边枚举即可，不断更新取max然后计数就可以了因此总复杂度是一个log的，代码里只有些去重的技巧，还是比较好写的代码： #include<bits/stdc++.h> #define LL long long #define pii pair<int,int> using...

A:巨木之森首先这题的路径我们发现除了最后到达的点以外，其他每条边都要遍历两次（因为最后不回来了）然后我们会尽量贪心的走最远的点，然后有一个关于直径的性质，距离一个点最远的点一定是直径的两个端点，因此我们求出直径，然后在树上倍增lca选下距离，选出最优的最后我们sort一遍能选就选，取最多的就可以了！代码： #include<bits/stdc++.h> #define LL long long using namespace std; const int N=1e5+5; struct Edge{int to,w,nxt;}e[N<<1]; int n,fst[N],...

部分题题解，剩余部分待补A：Ancient Distance这道题写了个根号的复杂度的，没有被卡我们只需要做到O(1)判断就好了！然后我们可以写一个有关于单调性的解法，然后我们可以类似于整除分块可能更好理解！nlogn的代码和思路以后会补，先放上根号的代码： #include<bits/stdc++.h> #define LL long long using namespace std; const int N=2e5+5; struct Edge{int to,nxt;}e[N]; int fst[N],tote,n,dep[N],a[N],ma,fa[N],ans[N],id[...

写一下一些作者掌握的题的题解，其他会慢慢补A: Clam and Fish这题是一道贪心，我们发现我们要最优策略就是有鱼我们就钓鱼，反之如果最后有多余的蛤蜊，我们可以花一半的时间用来更优的策略，注意要下取整算是一道基础题吧！B: Classical String Problem一道不易让我们思维定向的题，我们容易往平衡树treap上想然后发现倍长一下当前的字符串然后用一个指针维护当前所在，然后我们的移动字符可以转化为指针的移动其实这题的妙处在于字符的相对位置就是那个带绝对值的位置其实不会彼此发生变化，因此我们可以这么理解！C: Operation Love这个idea有点类似于AI智能我们首先...

A: 牛牛爱字符串一道简单的模拟题稍微有点细节注意不要输出多余的空格并且不能有多余的0000这样的问题，但是要注意如果是0必须输出0，这是个易错的细节这里读入用string和getline更方便，并且细节部分可以用个deque维护代码： #include<bits/stdc++.h> #define LL long long #define pb push_back using namespace std; string str; int main(){ while(getline(cin,str)){ int n=str.size();str='#'+st...

首先由于这场比赛的代码写得有点过于仓促，主要都是考试写得代码，和大部分根据框架改的代码，所以可读性一般，因此这篇题解就不给代码了，见谅！A: All with Pairs首先这道题要求我们求一个最长前缀和后缀的关系，我们可以把所有的前缀和后缀都存在一个hash表里面，然后我们发现有些前缀和后缀会算重复，当且仅当我们可以把最长的后缀和前缀合在一起再算一遍，然后我们可以发现这个就是KMP的next数组，然后我们只需要把字符串做一遍KMP和hash表就可以求出这题需要的答案，最后我们统计一个长度出现了几次然后我们可以用一个数组记录一下，最后累加即可，不要忘记取模！B: Boundary这题我们可以通...

首先由于作者水平有限，可能只有部分的题解，且有些做法不一定标准，但是均可过题，大家见谅... A: B-Suffix Array这是一道结论题：首先题目是要求求一个B数组，但是这个B数组的求***有一定的问题，也就是整个字符串的B数组的一个后缀，但是它不一定满足是这个后缀的B数组，感觉可能有点绕...然后B数组是求的和这个数最接近的pre，那么我们可以同理搞一个C数组，然后求一个与这个数最接近的suf，然后根据这个C数组做一下后缀排序，然后逆序的就是这个ans数组！上面没有证明，这个证明可以感性理解下，感觉有一篇博客写的比较好，大概是你考虑比较Cx比Cy大，和Cx比Cy小的2种情况，然后分别发...