牛客237787563号
牛客237787563号
全部文章
分类
未归档(241)
归档
标签
去牛客网
登录
/
注册
牛客237787563号的博客
全部文章
(共11篇)
模拟18 题解
A. 引子 模拟 完了 B. 可爱精灵宝贝 注意到特殊性质: 1.对于每个位置,只关注第一次到达的时间。 2.人走的区间是连续的。 问题转化为区间dp。 设$dp(i,j,k,0/1)$表示在$k$时间走完区间$(i,j)$,当前在区间的左/右端点的最优答...
数位dp
dp
模拟
2019-08-12
0
368
模拟21 题解
A. 折纸 考虑$O(nm)$暴力, 对于每次操作,暴力修改n个点的下标, 同时维护左右端点下标,最后相减就是答案。 对于后40分,n的范围很大。 恰好我们并不关注每个点的下标。 对于每次翻折, $O(m)$查询并记录下翻折操作时的下标即可。 注意每次操作不能单纯向一个方向翻折。 ...
数学
exgcd
模拟
数位dp
2019-08-14
0
410
模拟22 题解
A. 数论 一条性质: 对于一个不良好的数$x$,$x*p^c$一定不是良好的。 因为那些小于x,并且因数比x多的数,乘上$p^c$仍然更优。 这个性质告诉我们:一个目前认为不优的数,不会贡献出良好的数。 显然最大的质因子不会很大,良好的数也不会很多。 ...
dp
数位dp
位运算
2019-08-15
0
372
模拟29 题解
A. 壕游戏 不会做,以为是贪心。 结果发现贪心是错的。 正解是网络流中的费用流。 将每条边$i$拆为$c_i$条边, 将所有边建出来,每条边的费用为$a_i*j+b_i$,$1<=j<=c_i$。 然后可以直接跑费用流。然而复杂度$O(mk^2)=O(跑不过)$,死了...
数位dp
网络流
AC自动机
dp
主席树
2019-08-22
0
357
模拟42 题解
A. 世界线 毒瘤出题人,bitset题卡空间。 于是将所有的点分成两份,做两次拓扑排序,bitset只用开一半,空间就能够了。 B. 时间机器 似乎是很显然的贪心,然而没想到。 只会打更加显然的网络流暴力。 按左端点排序,set维护一下不断取后继就行了,当没有后继即为无解。...
bitset
拓扑排序
set
贪心
数位dp
2019-09-13
0
384
模拟66 题解
A. 棋盘 打表发现$ans_i=ans_{i-1}*i+[i$&$1]?-1:1$ 然后写高精度就完了。 所以这个式子的原型其实是: $ans_i=ans_{i-1}*(i-1)+ans_{i-2}*(i-1)$, 其含义可以直接画图理解。 对于前一个ans的每一种方案, 可...
组合计数
bitset
拓扑排序
数位dp
2019-10-09
0
376
模拟86 题解
A. 异或 位运算所以按位考虑。 数位$dp$统计每一位$0/1$的取值个数,随便乘一乘就出结果了。 B. 取石子 $O(n^4)$的$dp$是显然的。 可以发现$dp$中必败的状态是很少的。 所以直接打表 所以可以用必败的状态刷表进行$dp$,复杂度是对的。 ...
数位dp
博弈论
dp
位运算
2019-10-25
0
431
模拟105 题解
A. 小W的魔术 考虑问题的逆问题,怎样的字符串是好的字符串。 即长度为$n$,前缀与给定字符串的前缀匹配,后缀与给定字符串的后缀匹配的字符串个数。 不妨枚举给定字符串的断开点,那么答案即$(len+1)*26^{n-len}$ 然而这里面有重复计算的方案,把它画出来就可以发现, 相邻两次...
结论题
dp
倍增
组合计数
数位dp
2019-11-08
0
357
模拟115 题解
A. Tiny Counting 考虑枚举$a$,可以直接用树状数组查找合法的$b$, 接着直接乘逆序对个数就好了。 然而这个时候就存在一些非法的状态,$b$作为逆序对出现了。 所以只要再枚举一遍$b$,减掉对应的贡献就好了。 B. Medium Counting 因为...
数位dp
树状数组
组合计数
2019-11-14
0
379
dp 题解乱写
AGC034E 枚举根节点表示最终汇聚的点。 发现有祖先关系的点对是没必要进行操作的。 关注的是深度的和,不妨把深度为 $x$ ,转化为有 $x$ 个点需要匹配。 只有不同子树的点可以匹配。 如果对于一个点,最大的儿子的大小 $maxsz*2 \leq sumsz$,那么显然可以全部匹配。...
dp
轮廓线
数位dp
dp套dp
2020-03-19
0
404
首页
上一页
1
2
下一页
末页