牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共4篇）

模拟5 题解

星际旅行题中很特殊的给出，恰好2条边1次经过，m-2条边2次经过，让我有一点想到了欧拉路。然而考试中还是没有想到拆边这个巧妙的方法，只打了一个dfs。正解是将每条边拆为两条，问题转化为删去两条不同的边，使图中存在欧拉路。判断每个点的度即可。在每个边拆为两条之后，每个点的度一定是偶...

dp 组合计数图论欧拉路数论分块数学

2019-07-18

0 378

模拟25A 题解

A. Lighthouse m的范围极小，显然的容斥。总的方案数，减去受任意一个限制的方案数，加回受两个限制的方案数。就能得到受所有限制的的方案数。将选择的一些边所指向的点放在同一个联通块里。方案数其实就是这些联通块的圆排列，再乘上$2^{不为1的联通块个数}$，因为每个联通块...

容斥欧拉路点分治线段树

2019-08-19

0 436

模拟100 题解

A. 组合将两个字符之间建边，问题转化为一笔画，也就是欧拉路问题。所以直接用dfs压栈的方法解决，注意正确使用当前弧优化。 void dfs1(int x){ for(int i=head[x];i;){ if(vis[i>>1]){ head[x]...

dp 线段树图论欧拉路状压

2019-11-05

0 369

省选模拟14 题解

A. 开车关系似乎和欧拉回路很大。所以考虑首先通过构造欧拉回路的方式干掉所有的偶度点。然后发现问题转化为所有奇度点的最小带权匹配。刚开始的思路一直局限于靠原有的边匹配。后来发现只要是一条路径连接即可。考虑利用题中的特殊性质，二进制下所有小边的加和不大于大边。所以直接使用最小生成树...

最小生成树欧拉路杨氏矩阵

2020-02-01

0 335