牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共12篇）

模拟70 题解

A. 木板相似三角形，简单推出结论。发现要求的是$\sum \limits_{i=1}^{n-1}[n|i*i]$。那么只要把$n$质因数分解，设为$\prod_{j}^{} p_j^{c_j}$，那么设$k$为最小的合法的$i$，有$k=\prod_{j}^{} p_j^{\l...

数学 dp 构造题搜索

2019-10-13

0 301

模拟76 题解

A. 序列观察部分分，可以得到一些奇怪的构造方法。比如当$N=A*B$，直接将数按$A$的大小或$B$的大小分块就可以了接着打表，发现似乎全部的情况都可以通过类似的方法构造出来。只要对后面的部分分块，前面不足的部分不用分块。 B. 购物奇妙的数的范围很宽泛，达...

构造题 dp 组合计数

2019-10-17

0 297

模拟98 题解

A. 线性代数 (algebra) B. 装饰 (decoration) 暴力记录每个点的当前状态和上传状态，可以做到$O(4^n)$ 注意到答案并不大，不妨设最终答案为$k$，考虑在时间点$i$，选择点$j$对最终态的贡献，即对每一层祖先的状态取反。所以可以直...

状压模拟构造题最短路 dp

2019-11-04

0 356

模拟99 题解

A. 陶陶摘苹果一眼线段树维护单调栈，所以写就完了。当然本题中修改不继承，所以有更好的一个$log$的做法。 B. 开心的金明贪心地选择当前最优的策略。用一个$set$维护备选的集合。当跨月的时候，如果集合中元素个数大于限制数，可以不断去除最劣的选择。 ...

set 贪心线段树单调栈构造题

2019-11-04

0 359

省选模拟25 题解

A. 环是一道很巧妙的构造题。考虑写出满足条件的 $s_i,s_{i+1}$ 一定满足的式子。设 $x_{i,j}$ 表示 $s_i$ 中第 $j$ 个 $1$ 的位置。由操作A有 $k*t+\sum \limits_{j=1}^k x_{i,j}\equiv \sum \limi...

构造题贪心字符串并查集

2020-02-18

0 344

省选模拟30 题解

A. 任凭风浪起，稳坐钓鱼台其实就是一个优化过的暴力。首先答案 $x^3$ 显然可以转化为 $3$ 个位同时出现的方案数*权值求和。当 $k<=20$ ，直接异或 fwt ，然后做一个超集求和运算，$C(k,3)$ 枚举就行了。这个算法不优秀的原因是只关注三个位同时出现，并不需...

数学构造题分治 fwt

2020-02-26

0 498

省选模拟51 题解

A. 数学利用本题的特殊性质，可以得到如果 $n$ 为奇数，那么答案为 $(ab)^{\frac{n+1}{2}}$ ，对这个玩意平方一下即可发现是对的。对于 $n$ 为偶数，可以把 $2$ 全都提取出来，然后对剩余的部分取得一个解。然后不断缩小 $2$ 的次数以迭代，当缩小为 $2^0...

数学构造题 dp bitset 网络流

2020-03-22

0 410

省选模拟52 题解

A. 图两个二分图，可以直接对应出一个四分图来。第二个操作要求连通性，所以可以考虑先生成一棵树，这棵树显然是二分图。对于剩下的边，考虑是否形成二分图。如果能够形成，那么可以对应出合法的四分图。如果不能，那么说明剩下的边中存在奇环。因为树边已经连通了，所以这个奇环是合法解。 ...

交互构造题 dp

2020-03-22

0 334

省选模拟69 题解

A. 最小生成树因为最小生成树上一条非树边的权值必须大于两点的路径上的最大值，所以最优的策略肯定是将这棵树弄成一个菊花图。然后考虑把所有的边权按顺序列出来。如果当前还没有超出 $m$ 条边的限制，那么第 $i$ 条边的贡献就是 $(i-1)*w_i$。那考虑一个特殊的情况，如果说...

二项式反演多项式动态dp dp 分治构造题结论题容斥贪心

2020-04-13

0 381

省选模拟87 题解

A. a 直接构造一个简单的生成函数，就转化为求 $A^n(x)$ 的前 $x$ 项系数。一个很神奇的解决多项式 $A^n(x)$ 前 $n$ 项系数的做法。复杂度为 $O(nk)$，其中 $k$ 为 $A(x)$ 的项数。做法是这样的，对 $A^{n+1}(x)$ 分别用乘法 $A(...

网络流构造题二分图多项式

2020-05-04

0 402