牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共18篇）

模拟105 题解

A. 小W的魔术考虑问题的逆问题，怎样的字符串是好的字符串。即长度为$n$，前缀与给定字符串的前缀匹配，后缀与给定字符串的后缀匹配的字符串个数。不妨枚举给定字符串的断开点，那么答案即$(len+1)*26^{n-len}$ 然而这里面有重复计算的方案，把它画出来就可以发现，相邻两次...

结论题 dp 倍增组合计数数位dp

2019-11-08

0 357

模拟108 题解

A. 打表正确的题意是：求出最优决策下取得的值与答案的差绝对值的期望。考虑到本题中二者选择的概率各占一半。二者都选择各自的最优策略，在按位划分的情况下，只有$0$,$1$两种取值，如果前者选择$0$，那么后者可以选择$1$ 最终每个下标都会被等概率的选择，所以最终的答案就是对绝...

dp Hash 结论题

2019-11-11

0 473

模拟113 题解

A. ZYB建围墙手玩发现这个东西好像有一点规律。考虑在最优的方案下，每增加一个点对答案的贡献$0/1$，然后随便写写就好了。 B. ZYB和售货机把$x$向$x$能偷的节点建边。发现这个东西一定会形成森林，其中一些树为基环树，其余为普通形态的树。对于普通...

dp 基环树结论题

2019-11-13

0 322

省选模拟4 题解

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

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

2020-01-12

0 875

省选模拟9 题解

A. Surprise me 直接将$\varphi(i*j)$展开为$\varphi(i)*\varphi(j)*\frac{gcd(i,j)}{\varphi(gcd(i,j))}$。于是可以套用莫比乌斯反演。最终的式子大概是$\sum \limits_{T=1}^{n}f(T)\su...

二分图虚树图论结论题莫比乌斯函数点分治提交答案

2020-01-17

0 654

省选模拟61 题解

A. GTM 考虑一个点 $(x,v)$ ，能够碰到的点 $(x',v')$。有 $(x',v')$ 满足 $x'<x,v'>v$ 或者 $x'>x,v'<v$。然后有这样一个结论，我们将所有的点按照 $v$ 排序，然后在每个点能影响到的是一个连续区间。区间的左...

结论题树状数组容斥线段树

2020-04-03

0 800

省选模拟62 题解

A. Fable 虽然没打 noi online，但是大概看了一眼题。其中 T2 就用到了一个结论是：设 $p_{i,k}$ 表示 $i$ 次冒泡排序之后，第 $k$ 个点与之前的点形成的逆序对个数。则有每次冒泡排序之后，$p_{i+1,k}=\max{p_{i,k+1},0}$。 ...

结论题高斯消元多项式 set 矩阵平衡树启发式合并树状数组线性代数

2020-04-04

0 415

省选模拟69 题解

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

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

2020-04-13

0 381