银当taki

分类

题解(21)

/ 注册

全部文章（共19篇）

题解 | #柠檬可乐#

寒假营4 D 数论，特判！！每次可以把一个数减一，零一个数加一，问最终整个序列有多少种可能的gcd。一个数是整个数组的gcd，他首先一定是每个元素的约数，也就是说所有元素的和是这个数的倍数。我们现在得到了一个判断的必要条件，但它实际上也是一个充分条件，可以通过构造证明：我们可以把一个数减一，零一...

2024-02-24

1 268

题解 | #mutsumi的质数合数#

寒假营第五场 B 思维可以删任意个数的字符串，但是不能删连续两个，每种删除方案的得分是"mygo"出现的次数，问全部方案的总分。首先一个重要的观察是，由于不能删连续字符，删除后能出现"mygo"的字符串实际上只有八种，具体来说就是"mygo"中间的三个空都可以插入一个其他字符。对于这八种字符串，...

2024-02-24

5 292

题解 | #智乃与瞩目狸猫、幸运水母、月宫龙虾#

周赛round32 D 树形dp 每个节点有0或1的权值，设f(i)为从i节点出发，向叶子节点走，可以中途停下，所形成的数字中奇数的个数，求所有f(i)。奇数显然就是最后一位为1，所以这实际上就是要求每个节点所在子树权值为1叶结点个数。但又特殊规定：单独的叶节点不能形成一个数，因此叶节点虽然对祖先的...

2024-02-12

17 238

题解 | #Tokitsukaze and Bracelet#

寒假训练营2 C 字典树求升序子序列个数，其中最大值和最小值的异或小于等于d。如果确定了最小值最大值分别为a[i]，a[j]，，那么中间的数都可选可不选，这组maxmin对总方案数的贡献就是2^(j-i-1)。直接二重循环枚举minmax显然是不行的，只能枚举一个，然后logn查询另一个。但这个...

2024-02-10

1 191

题解 | #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 188

题解 | #小红大战小紫#

小白月赛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 287

题解 | #小红小紫替换#

周赛Round31 D.map模拟静态数组给一个数列，要完成两种操作：在一个指定元素的右侧插入，删除指定元素。维护序列首先考虑一下最经典的两种结构：数组和链表，数组插入和删除都需要O(n)，而本题操作次数有1e5，舍去。链表插入是只需要O(1)，但是寻找插入位置需要O(n)，也不行。看起来都不...

2024-02-05

3 255

题解 | #小红大战小紫#

周赛Round29 D.小红的中位数开始想用堆顶堆，但很快就发现每次都只是自在初始序列上删一个之后的查询，中位数只会跟中间几个数有关，只要根据初始序列长度的奇偶和删去元素的位置讨论一下就能以O(1)算出每次查询如果是偶数，删去元素位于左半边，会让右半边第一个成为中位数，位于右半边，会让左半边最后...

2024-01-30

0 339

题解 | #小红的删字符#

周赛Round30 D.小红整数操作首先一个很显然的思路是算出满足大于等于l的最小的x需要乘几，再算出满足小于等于r的最大的y需要乘几，然后这两个数之差就能得到有几组可行的x,y。开始就是这样写的，但是挂了因为问题是这个思路默认了x,y开始都小于l,r，但这是不一定的。在赛场上意识到这个问题后我...

2024-01-29

0 240