牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

省选模拟6 题解

A. Yist 首先考虑怎样的情况答案是不收敛的。操作中涉及到对一个权值非$0$，并且不作除法的点的加法贡献。因为只要最终的答案，可以想到对每个点作为出边的贡献分别处理。部分分提示求出第一次迭代的贡献，发现对于每个点，贡献都是一个等比数列，所以只要代入求和公式就好了。然而暴力做的复...

分块图论后缀自动机 dp 树状数组

2020-01-13

0 393

省选模拟5 题解

A. 青蛙因为每个青蛙都可以一步跳到终点。所以二分几个青蛙可以无消耗跳到终点，只要让最贵的几个青蛙跳过去。之后特判一下一个青蛙都跳不过去的情况就好了。 B. 一起自习的日子伯努利数练习题。不断的把自然数幂和用伯努利数展开，顺便二项式展开一下就好了。另外分析可知原式可以...

贪心主席树 lct 二分答案伯努利数后缀自动机

2020-01-12

0 418

省选模拟4 题解

A. 点点的圈圈因为题中保证的特殊性质，容易发现圆之间的关系形成树形结构。对于每棵子树，选择树的根或者累计所有子树的答案。问题在于建图，容易发现这个可以用KDTree优化。考虑将所有的点建在KDTree上。用每个点的圆覆盖KDTree，当完全覆盖时直接塞入对应点的vector中。...

结论题 set 扫描线 lct 主席树线段树 tarjan KD-Tree 计算几何

2020-01-12

0 875

数学专题测试3 题解

A. young 大概的意思是说，由低到高考虑不同的二进制位。形成一个最小生成树，那么最高二进制位不同的情况一定只出现一次。所以除掉最高位之后的情况形成两个集合，递归下去$dp$就好了。一个技巧是，将每个方案的最小值的总和，即$\sum \limits_{i}min(i)$转化为$\s...

莫比乌斯函数组合计数多项式数学杜教筛

2020-01-12

0 414

数学专题测试2 题解

A. B $[n=1]=\sum \limits_{d|n} \mu(d)$ 于是考虑用莫比乌斯函数容斥出题意中的$[gcd=1]$。设$f_n$表示$gcd$为$n$的倍数的答案。 $g_n$表示$gcd$为$n$的答案。 $g_1=\sum \limits_{i=1}^n\mu(i)...

矩阵线性代数莫比乌斯函数多项式数列

2020-01-05

0 441

数学专题测试1 题解

A. 解方程考虑没有任何限制的东西， m个元素分为n个连续的区间，直接用组合数插板法就好了。考虑如何去掉元素大于$a_i$的限制，只要给最终的元素个数减掉$a_i$就好了。考虑如何搞元素个数小于$a_i$的限制，不妨使用子集反演，要求的是恰好$0$个元素大于$a_i$。只要...

容斥 lucas定理组合计数数学多项式倍增 fwt dp 区间dp

2020-01-02

0 493

字符串专题测试1 题解

A. 阿尔法显然只要对位合并，最后查询不同的集合数就好了。似乎听过一个叫倍增并查集的东西，然而考场上没有$yy$出来。 $f_{k,i}$表示点$i$以及$i$往后数$2^k$个元素共同被合并的祖先。对于合并操作，直接用ST表的思路合并即可。考虑最终的下传操作：枚举倍增的次幂数...

并查集斯特林数生成函数多项式倍增

2020-01-02

0 427

数据结构+插头dp+多项式题解乱写

可持久化数据结构 A.森林树上的数据结构常可以启发式合并，用启发式合并的思路合并树上主席树就可以了。 B.影魔一个常见的这种数据结构题的套路是：离线询问，按右端点排序。在右指针扫过去的同时在数据结构（常为线段树）中更新该右端点能产生的答案。同时在数据结构中查询统计右端点对应的区间就好...

单调栈线段树状压 dp 多项式

2019-12-29

0 450

省选模拟3 题解

A. 好题很神仙的做法。考虑颜色数较小的情况，可以直接通过状压$dp$实现。对于颜色数较大，不妨通过随机数将每种颜色都映射到$k$的范围内。显然这个玩意不会使答案更优，但是这样不一定能找出正确的答案。然而算一下就可以发现，这个玩意的正确性高达$\frac{k!}{k^k}$，所以...

容斥 AC自动机

2019-12-24

0 325

省选模拟2 题解

A. 铁轨建设暴力插头dp+网络流判断可行性，可以拿到85分。然而这个题看起来就很像无限之环，只要稍微改一下建图就好了。然而这个建图还蛮难想到的。 B. 圈地游戏因为不会做+看不懂题解+std太长，所以咕掉了。 C. 组合数学 70分部分分：考虑到状态数很少，直接暴...

dp 网络流二项式反演容斥组合计数

2019-12-24

0 408