讲原则的柠檬精不要香菜
讲原则的柠檬精不要香菜
全部文章
分类
题解(13)
归档
标签
去牛客网
登录
/
注册
讲原则的柠檬精不要香菜的博客
全部文章
(共11篇)
题解 | #小红的数位删除#
周赛round36 E 构造一张图,让左上角到右下角的最短路不是把所有点都走一遍,也不是长度为n+m-2(一直向下或向右),并且不存在绝对众数(某个字母出现次数大于总数一半) 由于是构造题,不止一种思路。我开始想的是一种比较麻烦的,不过最后也过了。就是类似样例里的那种走法,先一直往下,再一直往右,直...
2024-03-11
0
100
题解 | #智乃与瞩目狸猫、幸运水母、月宫龙虾#
B 博弈 虽然不难但是很有教育意义。很大一类博弈问题的思路都是:某一个量每轮都可以变化某一固定值,当这个量达到某一阈值时游戏结束。那么不管怎么操作,游戏的胜负在开始时都已经注定了,唯一的影响就是先后手,只要判断下奇偶就行了。 对这题来说,每轮都变化的固定值是每轮数字个数都会减一,阈值是结束时数字一定...
2024-02-25
0
82
题解 | #柠檬可乐#
寒假营4 D 数论,特判!! 每次可以把一个数减一,零一个数加一,问最终整个序列有多少种可能的gcd。一个数是整个数组的gcd,他首先一定是每个元素的约数,也就是说所有元素的和是这个数的倍数。 我们现在得到了一个判断的必要条件,但它实际上也是一个充分条件,可以通过构造证明:我们可以把一个数减一,零一...
2024-02-24
1
99
题解 | #mutsumi的质数合数#
寒假营第五场 B 思维 可以删任意个数的字符串,但是不能删连续两个,每种删除方案的得分是"mygo"出现的次数,问全部方案的总分。 首先一个重要的观察是,由于不能删连续字符,删除后能出现"mygo"的字符串实际上只有八种,具体来说就是"mygo"中间的三个空都可以插入一个其他字符。对于这八种字符串,...
2024-02-24
4
116
题解 | #智乃与瞩目狸猫、幸运水母、月宫龙虾#
周赛round32 D 树形dp 每个节点有0或1的权值,设f(i)为从i节点出发,向叶子节点走,可以中途停下,所形成的数字中奇数的个数,求所有f(i)。奇数显然就是最后一位为1,所以这实际上就是要求每个节点所在子树权值为1叶结点个数。但又特殊规定:单独的叶节点不能形成一个数,因此叶节点虽然对祖先的...
2024-02-12
17
125
题解 | #Tokitsukaze and Bracelet#
寒假训练营2 C 字典树 求升序子序列个数,其中最大值和最小值的异或小于等于d。如果确定了最小值最大值分别为a[i],a[j],,那么中间的数都可选可不选,这组maxmin对总方案数的贡献就是2^(j-i-1)。 直接二重循环枚举minmax显然是不行的,只能枚举一个,然后logn查询另一个。但这个...
2024-02-10
1
61
题解 | #DFS搜索#
寒假训练营1 E dfs 被骗了,名字叫贪心,实际上是dfs。 注意到比赛场数只有10场,每场只有3种结果,爆搜复杂度也只有3^10,果断dfs。教训是数据小到能爆搜,就直接爆搜。 if(x==m+1){//比完了 int p0=p[0]; sort(p.be...
2024-02-08
1
77
题解 | #小红大战小紫#
小白月赛86 D.dfs 问图中有多少个长方形,正方形也算长方形,并且每个长方形都是当前区域最大的。 判断长方形可以计算连通块面积s,以及横坐标之差最大值mx,纵坐标之差最大值my,如果mx*my=s则是长方形。 int xm[4]={1,0,-1,0}; int ym[4]={0,-1,0,1};...
2024-02-05
1
89
题解 | #小红小紫替换#
周赛Round31 D.map模拟静态数组 给一个数列,要完成两种操作:在一个指定元素的右侧插入,删除指定元素。 维护序列首先考虑一下最经典的两种结构:数组和链表,数组插入和删除都需要O(n),而本题操作次数有1e5,舍去。链表插入是只需要O(1),但是寻找插入位置需要O(n),也不行。 看起来都不...
2024-02-05
3
99
题解 | #小红大战小紫#
周赛Round29 D.小红的中位数 开始想用堆顶堆,但很快就发现每次都只是自在初始序列上删一个之后的查询,中位数只会跟中间几个数有关,只要根据初始序列长度的奇偶和删去元素的位置讨论一下就能以O(1)算出每次查询 如果是偶数,删去元素位于左半边,会让右半边第一个成为中位数,位于右半边,会让左半边最后...
2024-01-30
0
123
首页
上一页
1
2
下一页
末页