辛几何旋律

分类

dp(1) 哈希(1) 数学(2) 数据结构(1)

/ 注册

全部文章（共5篇）

牛客练习赛 74 F

题目链接 CCA的树关于树的组合计数考虑容斥，容易知道总方案数为\(n^{n-2}*m^n\) 考虑在什么情况下不存在好链，容易知道当且仅当不同的颜色组成不同的连通块时，该种方案下不存在好链对于每一种固定的方案，我们枚举\(i\)条要断的边这样会形成\(i+1\)个连通块，有...

2020-12-21

0 482

牛客练习赛 73 D

题目链接离别离线算法+线段树容易发现当我们枚举右端点r时，符合条件的左端点是一段连续的区间我们可以用队列来维护这个连续区间的左右端点当枚举到端点\(i\)时，将下标\(i\)插入到队列\(q[a_i]\)中如果元素大于k，队首+1即为左端点（注意要与之前的取max) 如果元...

2020-12-16

0 380

牛客挑战赛46 D

题目链接：数列查询有多少\([l,r]\)区间满足每个数出现\(k\)的倍数次即为\(1\)到\(r\)与\(1\)到\(l-1\)每个数相减的次数为\(k\)的倍数次可以使用哈希维护记录每个数出现的次数为\(cnt[x]\)，哈希值为\(hash[x]\) 那么前缀哈希和即为...

2020-12-15

0 396

牛客挑战赛46 C

题目链接：排列考虑\(dp\)，我们思考如何设计状态将第i个数插入i-1个数中，我们考虑会新增多少个超级逆序对假设将\(i\)插入后\(i\)的位置为\(l\)，\(i-1\)的原来的位置为\(l2\) 如果\(l2>=l\) 我们会新产生\(i-l-1\)个逆序对否则\...

2020-12-15

0 461

牛客挑战赛46 B

题目链接：最小的指数乍一看还以为是Pollard_rho算法，其实大可不必。发现\(1<= n <= 1e18\),我们可以将n分为两部分（分块思想降低时间复杂度）。剔除小于等于\(4000\)的所有质因子，剩余的设为x，设此时得到的答案为\(minnum\) 如果x为...

2020-12-14

0 532