issue是云哥的小迷×呀

题解

未归档(1)

/ 注册

全部文章 / 题解（共74篇）

P3723 [AH2017/HNOI2017]礼物(构造FFT)

传送门最小化同时增大亮度是没有意义的,可以转化为增大一个数组的亮度,设增大了数组亮度假设增加的亮度一定,变化的就只有最后一项,也就是最大化但是每一种对齐方式都需要计算形如的式子这部分已经是的了但是如果把数组复制一份在最后面是一个长度的序列把数组反转,做卷积得到的项中有模拟一下的...

2021-01-19

1 640

D. Mike and distribution

传送门找到个互不相等的使得且注意你构造的我是废物^ _ ^ 既然不限制,那么令要大于原数组的一半不妨先满足数组,挑选最大的个下标那么如何调整让数组也满足条件? 是不是选择最大的的下标会比较好呢?但是如果相应的非常小呢?无法抉择,抛弃这种想法... 至此,废物的思想停止了正文,上面都...

2021-01-14

1 683

New Year Tree

关于子树的修改和查询很容易想到树链剖分用序建立线段树线段树中保存每个节点的颜色信息由于颜色最多种所以可以压缩为二进制数然后维护一个懒标记,就是裸题了 (另外,我是真不喜欢写树的题啊!!!!!) #include <bits/stdc++.h> using namespace s...

2021-01-14

1 753

[HAOI2006]旅行COMF

枚举上界和下界用判断连通,复杂度枚举下界,上界可以二分,理论复杂度似乎能冲...但是T了枚举下界,然后使用并查集动态加入边判断连通,复杂度,可以通过枚举下界,使用取每个点最优(小)的上界。但是不知道可不可以,没试过 #include <bits/stdc++.h> using na...

2021-01-14

2 654

牛客挑战赛47. A一道GCD问题(同余)

传送门先说结论的做法差分数组的和原数组相同因为设原数组的啊为那么每个数都是的倍数,每个数减去一个的倍数仍然不会改变整体的那么数组的每个数加上,差分数组只有第一个数会加上去也就是差分数组的的就是最大的,这样就非常简单但是我太傻了,开始没想到这个结论^_^ 加上一个使得所有数字的最大,设...

2021-01-10

0 821

牛客挑战赛47 C.条件

传送门一定存在的边放一起跑一边弗洛伊德然后再加上可能存在的边跑弗洛伊德这样是的但是由于这里只需要判断是否连通,所以可以使用或运算、也就是把每个点能到的点看成一个二进制数,这样可以使用优化复杂度一定存在的边放一起跑一边弗洛伊德然后再加上可能存在的边跑弗洛伊德这样是的但是由于这里只需要...

2021-01-10

1 706

牛客挑战赛47 B.又一道gcd题

传送门因为是,所以选出来的数一定都是答案的倍数那么有一个很直观的方法由于枚举每个数的约数复杂度是根号的那就直接枚举约数,让最后如果就代表有个数含有因子那么选出这些数来一定是然后从后往前更新答案因为可以作为个数的,那么去掉任何一个属,也还可以作为选出个数的 #include <b...

2021-01-10

0 671

小M的天平

物品可以放左边也可以放在右边其实可以看成一个物品可以作为重量也可以作为那么看成个物品来一次$背包即可但是这里稍微有点变化,物品的价值可能是负数那么如果负数也按照我们倒序枚举会有问题,负数应该正序枚举负数正序枚举能保证状态没有重复使用一个物品当然如果你用的是二维数组来就不需要分两次了 #i...

2021-01-08

12 848

665 E. Beautiful Subarrays(字典树与异或性质)

传送门首先确定肯定使用字典树然后因为异或的性质有那么只需要把所有的前缀插入字典树然后枚举端点去字典树上找有多少个即可也就是对每一个都去字典树上找有多少个前缀满足条件那么最后答案需要除以,因为每个一可以作为字典树上的前缀,也可以作为值得一提的是需要把0插入进去因为允许存在那么我们也...

2021-01-07

1 738

83D. Numbers(容斥+暴力)

传送门由于不能包括的因子所以得到的数字分解质因子后必定都是大于等于的质因子那么一个数的质因子不会个...好像没什么用搜索的复杂度是上天的。那就套路的容斥,求符合条件的就是求符合条件的那么如何求的方案数.... 首先是倍数的数有个,在这基础上需要进行容斥,因为有数拥有比小的因子的同时也拥有...

2021-01-06

2 668