牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共15篇）

模拟14 题解

A. 旋转子段对于位置i上的数$a_i$，易知有且仅有一个旋转点使它旋转到$a_i$，这个旋转点是$\frac{i+a_i}{2}$ 因为旋转点分落在点上的旋转点和两点之间的旋转点，除2不易处理。不妨将位置i上的数存放在$i+a_i$处。设1~i的原本固定点为$pre_i$个，后缀同理...

模拟退火搜索图论树状数组

2019-08-08

0 474

模拟40 题解

A. 队长快跑非常显然的数据结构优化dp，线段树下标为a的最小值，要求支持区间最值，区间加，单点取max。随便写下转移方程就好了。 B. 影魔树上数颜色？但是要求了一个深度。我的做法是将询问离线，显然在一个询问中我们只关注每种颜色在该子树中出现的最...

dp 树状数组线段树离线

2019-09-08

0 358

模拟56 题解

A. Merchant 看到一次函数，马上想到维护一个凸包，或许可以维护一下前m大一次函数的总和？然而想了想并不会维护，于是转换了下思路。似乎答案具有单调性：除去答案为0的情况，其它一定具有单调性。结论是显然的。不妨考虑任何一个组合。一些一次函数的和仍为一次函数。如果总一次...

二分答案高斯消元树状数组单调指针

2019-10-03

0 322

模拟60 题解

A. 嘟嘟噜约瑟夫问题，然而线性过不去。观察本题的特殊性质：m远小于n。再看递推公式，发现当m很小的时候取模次数并不多，所以在这种情况下可以直接用一次乘法代替多次加法。 B. 天才绅士少女助手克里斯蒂娜拆一拆式子就可以将i和j分离出来。然后用分治的思想在线...

分治线段树树状数组 dp

2019-10-06

0 341

模拟67 题解

A. 神炎皇尝试枚举$a$,$b$的$gcd$，设为$d$。那么有$$ans=\sum \limits_{d=1}^{n} \sum \limits_{i=1}^{n} \sum \limits_{j=1}^{n} [gcd(i,j)==d][i+j<=n][i+j|i=j]$$ ...

dp 数学树状数组

2019-10-10

0 385

模拟74 题解

A. 梦境已经做过很多类似的套路题。都是排序后贪心就完了。将所有的区间以右端点排序，因为每个区间对答案贡献相同为1，区间右端点不断增加，那么显然可以直接取尽量靠左的点。用$multiset$维护一下点，支持后继操作就可以了。因为题中有相同的点，用$set$必死。 ...

dp 贪心组合计数 set 图论树状数组

2019-10-15

0 374

模拟93 题解

A. 序列一眼二分，然后发现二分有点不对？一测大样例果然不对，因为有两个限制，问题并不具有单调性。作前缀和后问题其实是个三维偏序问题，似乎还得一个$log$复杂度。先打个$cdq$分治套树状数组，结果极限数据$0.3s$，所以就$AC$了。正解确实是一个$log$。最后一维偏...

dp 树状数组分治高斯消元

2019-10-30

0 400

模拟103 题解

A. Game $yxs$大神教你转化题意：将B哥的牌视作左括号，小A的牌视作右括号。那么问题转化为最多匹配多少个括号，并求出最大字典序的一组解。如果不需要最大字典序，问题是简单的贪心，每次取出最小的右括号尝试匹配。考虑一个暴力做法：对于B哥的每一张牌，做$nlogn$的...

启发式合并分治线段树贪心差分树状数组

2019-11-07

0 394

模拟115 题解

A. Tiny Counting 考虑枚举$a$，可以直接用树状数组查找合法的$b$，接着直接乘逆序对个数就好了。然而这个时候就存在一些非法的状态，$b$作为逆序对出现了。所以只要再枚举一遍$b$，减掉对应的贡献就好了。 B. Medium Counting 因为...

数位dp 树状数组组合计数

2019-11-14

0 379

省选模拟6 题解

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

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

2020-01-13

0 393