前面的碎碎念：这次比赛的题目感觉还是挺有趣的，可惜晚上要和朋友玩游戏，所以鸽了比赛... 正文部分： A-牛牛爱学习很显然，只要天数越长，所能获得的最大知识力也就越多，其具有单调递增性，因此我们可以二分这个天数，接下来的问题就变成了如何求取给定天数所能获得的最大知识力。这里我们利用贪心的思想，先把数组从大到小排序，然后从前往后遍历。假设当前二分的天数为day，我们每day个分为一组，第1到第day个是原始值，第day+1到第2day个是原始值-1，第2day+1到第3day个是原始值-2，以此类推。注意若某本书的知识力降为0就可以停止遍历了，不然后面可能取到负的知识力，使得总知识力之和反而变小...

前面的碎碎念：这次比赛事故有点大啊，D和E题都是在最后关头才进行了rejugde。牛客的题目老实说还是挺不错的，就是题面或者数据老出问题，给人的体验就不太好... 题解部分： A-最值序列很显然，我们把数字从小到大排序后，取前n/2个数字相加，再不断乘以后n/2个数字，通过这样的贪心策略即可最大化答案。时间复杂度：O(nlog(n))。代码部分： #include<bits/stdc++.h> using namespace std; int i,j,n,ans=0,a[500005]; const int mod=998244353; int main() { scan...

前面的碎碎念：状态好差，罚时上天，我裂开了QAQ。 题解部分： A-古老的牛市，遗迹的天梯典型的BFS搜索题，关键在于设好状态。设标记数组为V[i][j]，表示以连续后退了j步的状态访问第i层阶梯，那么开始BFS搜索，对于某个状态，按照题目给定的要求，其可以退一步，或者跳跃到与其高度差不超过2^k的阶梯上，每次都按照这两点转移，最后输出到第n阶阶梯的最小步数即可。时间复杂度：O(nlog(max(ai)))。代码部分： #include<bits/stdc++.h> using namespace std; struct node { int x,h,s; }Q[6005...

代码思想：每秒对小B进行两次BFS，对小A进行一次BFS，当他们碰见对方走过的路就跳出循环输出此时时间即可，具体可见代码。时间复杂度：O(nm)代码部分： #include<bits/stdc++.h> using namespace std; //定义队列节点 struct node { int x,y; }rear,front; //Q[0]为小B进行BFS的队列，Q[1]为小A进行BFS的队列 queue<node>Q[2]; //ans表示双方碰面时间 int ans=0,N,M,dx[]={0,0,1,-1,1,1,-1,-1},dy[]={1,-1...

前面的碎碎念：因为比赛那天晚上朋友喊我去剧本杀，所以直接把比赛鸽了，直到今天才想起来把题解补上... 题解部分： A-怪盗-1412按照111...111444...444111...111222...222这样来分配数字个数能最大化1412子序列个数，其中两部分1的个数应该尽可能相近，所以答案就是n/2(n-n/2)mk。时间复杂度：O(1)。代码部分： #include<bits/stdc++.h> using namespace std; int main() { long long T,a,b,c; scanf("%lld",&T); wh...

代码思想：设答案为ans，很显然想要遍历完整个图，这个图必须联通，所以要添加(联通分量数-1)条边，先令ans=连通分量数-1。再考虑走两步这个性质，若一个图存在奇数环，那么这个图自然就能全部走到，因此DFS判断图内是否存在奇数环，若不存在再令ans++，最后输出ans即可。时间复杂度：O(n+m)。代码部分： #include<bits/stdc++.h> using namespace std; vector<int>R[100005]; bool F=0,V[100005]={0},S[100005]; void DFS(int x) { int i,j...

前面的碎碎念：啊啊啊，差点就AK了好可惜啊，数学题忘了小球放盒子怎么快速求方法数了，对不起高中数学老师... 题解部分： A-AOE还是单体？比较简单的贪心题目。若怪兽数目大于x，那么释放一个AOE技能对所有怪物造成1伤害，肯定比一个一个放个单体技能对所有怪物造成1伤害赚；若怪兽数目等于x，两者等价；若怪兽数目小于x，单体技能比AOE技能更赚。所以我们先用AOE技能把怪杀到只剩x-1个，再用单体技能把剩下的怪物全部杀死即可。时间复杂度：O(nlog(n))。代码部分： #include<bits/stdc++.h> using namespace std; int a[20000...

前面的碎碎念：每次练习赛都能让我清楚认识到自己有多么菜，有多少知识缺乏，菜不成声.jpg。 题解部分： A-牛牛的三角形众所周知，能形成三角形要求任意两边之和大于第三边。我们对数组从小到大排序一下，排序后，a[i+2]+a[i]>a[i+1]和a[i+1]+a[i+2]>a[i]是一定满足的，所以满足a[i]+a[i+1]>a[i+2]的三条边一定能形成三角形。故我们遍历一遍数组，判断是否有满足此要求的三条边即可。时间复杂度：O(nlog(n))。代码部分： #include<bits/stdc++.h> using namespace std; int mai...

前面的碎碎念：本次小白月赛做的心急了一点，因为大部分题目都会，但是需要码量，所以写完没怎么仔细检查就交了。导致出现了各种神奇的错误：忘记取模/数组开小/数据范围看错/多组样例忘记初始化。不过整体做题速度还是挺快的，可惜最后一小时战略错误选择开A题，做了一小时各种解方程人都做没了，开E题的话应该能再多A一道。 题解部分： A-最短路太菜了，做了一小时人给做没了，以后还是自动放弃计算几何算了... B-组队我们对数组排序一下，使用尺取法：若右端点的值-左端点的值小于等于k，那么在这两段点间的所有元素都可以被选，因此更新ans=max(ans,R-L+1)，之后再移动右端点。若右端点的值-左端点的值...

前面的碎碎念：本次比赛题目比较对胃口，一个半小时就A了前五题，尤其是第二题，我正好做过它的加强版(笑)。现在比赛rating还在计算，希望能借此上个绿名吧。 题解部分： A-打怪签到题。当我们的攻击力大于等于怪物的总血量，每次我们都可以不耗血秒杀怪物，从而可以杀死无数只怪物，对此输出-1。当我们的攻击力小于怪物的总血量时，我们设打死一只怪物需要round个回合，而每打死一只怪物，我们将会减少(round-1)A的血量(因为最后一回合我们杀死了怪物，因而少受一回合怪物的攻击)。设答案为ans，那么我们就是要寻找满足ans(round-1)A<h最大的那个ans，对此我们二分查找这个ans即...

题目分析：序列自动机板子题。注意字符串字符均为小写字母，因此我们设一个T数组，T[i][j]表示在i位置右边，离i最近的j+‘a’字母的下标，我们可以从后到前求出T数组。在询问时，需要对每个字符串判断，我们可以利用T数组在主串上进行跳跃匹配。若该字符串利用T数组能匹配到尾部，输出YES，否则输出NO。时间复杂度：O(26|A|+∑|Bi|)代码部分： #include<bits/stdc++.h> using namespace std; int T[1000005][26]={0}; char A[1000005]; int main() { int i,j,N,L; ...

前面的碎碎念：报名前看到比赛难度宣称DIV2 A-C，总担心出题人会不会虚晃一枪，把菜逼的我锤懵了。做完后感觉难度确实算是牛客比赛里偏简单的，挺适合我这种新手练习。 题解部分： A-Maximize The Beautiful Value首先我们算出原序列的F(n)值，然后题目要求我们把序列中某个元素前移k格，假设这个元素移动前的位置为i，那么移动后这个元素的位置就变成了i-k，很显然这个值前移导致原序列的F(n)值减少了kai。除此之外，原序列i-k到i-1位置的元素全部后移一格，那么这些元素后移导致原序列的F(n)值增加了a[i-k]+a[i-k+1]+...+a[i-1]，这个和可以利用...

链接：https://blog.nowcoder.net/n/2f48c40d6a874091953834d928b0ea90。 应该算是写的比较详尽+用心了，如果有疏漏之处，还望大佬们轻喷QAQ。

前面的碎碎念：本次比赛A了A/D两题，B题拿优先队列BFS瞎搞了半天，发现状态数太多无法开出标记数组，遂扑街。C题思考了一会，发现有点差分数组那味，但是没有想出啥解法，遂扑街。赛后补完题，感觉B题没有做出来有点不应该，优先队列做法其实很像BFS搜索的过程，DP做法也很妙，思维上还是差一点。C题有点接近了，但是最关键的部分并没有想出来，不过比赛中A了这题的人并不多，情有可原。 题解部分： A-咪咪游戏签到题。字符串若全是由mq链接而成，这个字符串长度肯定是偶数，所以长度为奇数的字符串肯定非法。若字符串长度为偶数，我们就遍历一遍，看其是否均由mq连接而成即可。时间复杂度：O(Q|s|) 代码部分：...