issue是云哥的小迷×呀

分类

未归档(1) 题解(74)

/ 注册

全部文章（共75篇）

牛客挑战赛53 C.奇奇怪怪的魔法阵(状压)

Link 我们要求fT=∑S∈T[S为独立集]f_T=\sum\limits_{S\in T}[S为独立集]fT=S∈T∑[S为独立集] 考虑集合TTT的最低位二进制位代表的集合是yyy(这个点设为uuu),其他二进制位代表的是xxx 那么T=x+yT=x+yT=x+y 显然,若SSS集合中不包...

C++

2021-10-18

4 660

J.溪染的优惠券(贪心01背包)

LINK 有点像背包,但是又不完全是原因在于使用的物品有限制,使得物品的使用次序是未知的这样显然无法扫一遍做背包如果按照排序也是不对的,限制大的不一定先使用若使用变为,这样中间错过了许多小型优惠劵,可能先使用中间的才更优于是想到按照排序,直接做背包即可. 这样选择物品的顺序满足如果只选择...

2021-06-19

5 811

牛客练习赛84 D.牛客推荐系统开发之动态特征获取

LINK 作为题的受害者忍不住来写一发题解... 其实就是个简单的模拟,但是数组用混了就非常脑瘫对n个询问按时间戳排序,并设置一个存机器缓存的特征是结构体,包含这个缓存的特征类型和优先级,重载<为优先级更小的优先级使用变量维护,每次加入新的特征类型把即可(后来的优先级一定更大) 那么...

2021-06-13

1 611

牛客练习赛84 E.牛客推荐系统开发之标签重复度

LINK 比较明显的点分治问题,考虑如何计算通过点的路径贡献获得从出发的所有路径,显然经过的所有路径都是由出发的两条路径拼接而来每条路径存成一个,第一关键字为最大值,第二关键词为最小值现在就是一个简单的二维偏序问题一下那么每个位置的最大值一定比前面大然后使用动态开点权值线段树，最小值为下标...

2021-06-13

2 695

CF633C Spy Syndrome 2(ACAM简单应用)

LINK 随机数据下,时间复杂度应该是碾压哈希的hhh 大小写是不重要的,因为第一步总是会把大写改成小写所以我们可以暂时把字符集的大小都变成小写去匹配然后拿样例来说 iherehtolleh 我们匹配这个,其实可以把这个串反过来 hellotherehi 然后匹配这个玩意,最后把答案倒过来就好了...

2021-02-25

0 657

CF803F Coprime Subsequences(容斥)

考虑先求出最大公约数大于的子序列个数显然,我们可以枚举这个最大公约数我们预处理一个表示有个数字含有约数然后我们去枚举子序列的最大公约数来计算答案我们定义表示最大公约数是倍数的方案数怎么求最大公约数是的方案数呢?? 我们定义表示最大公约数是的方案数那么预处理数组的复杂度,直接质因子分解...

2021-02-25

2 814

366 C.Dima and Salad

不会写...看的题解,wsfw 物品的两个属性不太好弄假如暴力设计状态,就是定义表示在中且的状态是否存在暴力枚举的话复杂度上天换种思路考虑到最后的合法方案是也就是不妨给所有扩大到,这样一来我们只需要关注当前选择两种属性的偏移量如果偏移量为零,那么达到目的因为所以偏移量不会超过这么多...

2021-02-05

1 798

1043 E. Train Hard, Win Easy(贪心.)

传送门每个人做第一题需要事件,做第二题需要的事件每个人都要和其他个人组成一组队伍做一次题,你能选择的就是谁做第一题谁做第二题。但是现在有对关系起了冲突,不能组队求能组队的最小花费时间总和. 考虑和花费是两种选择方式的费用差是也就是当说明的方式比较好(因为差是正数) 当说明的方式比...

2021-02-04

2 861

1183 H. Subsequences (hard version)(dp)

传送门如果想到了的话,这题就不难了。首先解决一个简单的问题,如何求出串有多少不同的子序列定义为以的长度为的子序列个数 ,意思是选或者不选都是一种选择但是有重复,考虑且时形成的子序列后面接上或者接上是等价的所以真正的转移方程是也就是找到最近的一个满足条件的,然后去掉的方案数那么这题就简...

2021-02-04

3 743

牛客每日一题和与或(数位DP)

传送门也就是每一位二进制只能放在这个数中的某一个上面每位数字不能超过,我们发现这非常像数位的过程现在简化一下问题求的对数满足且很明显这就是一个数位,表示枚举到二进制第位,卡不卡上界,卡不卡上界然后只需要暴力考虑当前位二进制填还是填填的话填在还是填在,然后更新上下界范围即可。回到这...

2021-01-28

7 1024