牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

杂题

1.容易发现题意中的子序列没啥用，其实要求的是集合个数。然后考虑并不是所有的点对都是需要关注的，处理的方法是把所有的数按照大小排序。其实按照大小排序就是 $0/1 tire$ 树的样子，所以这样做的话，一个集合中的两两最小异或值实际上就是按照顺序的两两异或值的最小值。然后只要考虑每个...

dp 期望容斥字符串组合计数

2020-04-07

0 457

省选模拟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

省选模拟61 题解

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

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

2020-04-03

0 800

省选模拟60 题解

A. 摧毁图状树考虑一个暴力做法。维护一个堆，每次取出深度最大的点，如果他还没有覆盖，那么就给答案增加 $1$。否则直接跳过，然后直接跳到他的 $k$ 级祖先加入堆中，复杂度是 $O(n^2log)$ 的。然后发现这样一个事情，这个复杂度肯定是不满的。比如说对于单次操作，复杂度大...

树状数组期望 dp

2020-04-03

0 746

省选模拟59 题解

A. 杨柳考虑实际上有这样一个结论，棋子之间是互不干扰的。可以使得最优方案上不存在两个棋子中途碰上的情况。然后问题就是一个二分图最小匹配，一个简单的想法就是 bfs 然后跑一个费用流，点数不多，边数很多。另外一个做法是直接在原图上建图跑个费用流，点数很多，边数不多。经过实验，只有...

区间dp 二分图 tarjan dp 网络流

2020-04-01

0 336

省选模拟57 题解

A. Max 看到这个数据范围就想一下是不是可以状压。然后发现只有 $m$ 压的下。容易发现题目中的顺序并不关键，其实可以无视掉原有的操作顺序。然后现在给 $1... n$ 每个元素分配一些操作就好了。这样在给第 $i+1$ 个元素分配操作之前，我们只关注已经分配的操作集合、最大的...

树剖扫描线动态dp dp 线段树状压

2020-03-29

0 353

省选模拟56 题解

A. 取石子游戏容易发现这个问题的 $sg$ 值就是每堆的石子个数的异或和。问题是后手能赢，也就是求删除 $d$ 的倍数个石子，使得剩余石子的异或和恰好为 $0$ 的方案数。然后发现直接 $dp$ 复杂度就是 $O(n*d*\max(a_i))$ 的。发现题面中给出了一个很特殊的限制...

模拟博弈论 SG函数 dp 容斥扫描线线段树

2020-03-28

0 399

博弈论题解乱写

1.对于一个转移方程 $dp_{i,j}= not (dp_{i-1,j} \ and \ dp_{i,j-1})$。可以发现除了前两行两列，其他每个对角线的取值是相同的。所以只要做前三行三列的 dp 即可得到整个 dp 数组。然后这个东西的初始值不一定要整齐，只要拓展过来两三行都可以解...

线段树博弈论 SG函数

2020-03-27

0 853

省选模拟55 题解

A. 调兵遣将对于一个确定的右端点，只有 $log$ 种 $\gcd$ 不同的左端点。可以把这个东西写成 $(a,b,R)$ 的形式。在集合中不便于计算，可以考虑转化为总方案数减不在集合中的方案数。可以考虑设 $f_x$ 表示最后一个区间的右端点 $\leq x$ 的方案数，然后对上...

线段树扫描线博弈论 dp SG函数

2020-03-27

0 442

省选模拟54 题解

A. space 首先考虑建个图，发现每个点的入度出度均为 $1$，其实就是形成了若干个环排列。起点为 $(1,1,1,1)$ ，但是最终还要经过一次起点。所以在 $n \neq 1$ 时，考虑直接无视这个起点，转化为自选起点，但是要花钱来，然后要求经过每个点一次的最小代价。发现代价显...

折半搜索莫比乌斯反演 dp

2020-03-25

0 314