牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共16篇）

图论杂题

矩阵游戏 https://www.lydsy.com/JudgeOnline/problem.php?id=1059 刚开始以为只要每行每列都存在一个1，就是可行的解，然后发现可以被yxm简单的数据hack掉： 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 正解是...

图论二分图树上差分桶线段树 wqs二分

2019-07-16

0 296

[NOIP2013]华容道题解

[NOIP2013]华容道首先是一种比较显然的做法。整个棋盘，除了起点，终点和空格，其他的方块是等价的。对于终点，它始终不会变化，如果搜到终点结束搜索即可，所以我们不需要考虑终点。所以需要考虑的是空格的位置和起点方块的位置。定义$f(i1,j1,i2,j2)$为空格所在坐标$...

图论搜索

2019-07-17

0 378

远古杂题 2

Base基站选址(线段树优化dp) 首先写dp转移式， $dp(i，j)$表示在第i位修建第j个基站。定义$l(i)$为能覆盖i的最靠左的基站，$r(i)$为能覆盖i的最靠右的基站， l和r数组均可以用二分求出， $dp(i，j)=min( dp(u，j-1)+cost(u，i)...

dp 数学高斯消元期望图论状压

2019-07-17

0 671

模拟5 题解

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

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

2019-07-18

0 274

模拟8 题解

A. 匹配 $Hash$直接搞。如果使用$KMP$，注意B字符串与A完全匹配，这是原本的$KMP$无法处理的问题。 B. 回家刚开始以为是割点，打完后仔细一想发现不对。于是打了圆方树，没有什么技巧。另一种简单的做法：只判断割点，但修改判断割点的方法。 ...

Hash KMP 字符串 tarjan 图论三分

2019-07-25

0 214

模拟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 370

模拟15 题解

A. 建设城市（city）相较于那一天我们许下约定，数据范围有所改变。如果不考虑k的限制，是显然的插板法。枚举至少超过限制的个数，大力容斥就完了。 B. 轰炸行动（bomb）论如何看懂题。如果能够理解题意，缩了scc，拓扑排序求个点带权最长链就完...

容斥组合计数数学 tarjan 图论 dp 期望

2019-08-10

0 252

模拟19 题解

A. count 结论题一棵树可以被分为d块，当且仅当子树节点个数和为d的倍数的节点有$\frac{n}{d}$个。对于任何一个树，size为d的倍数的节点个数不会超过$\frac{n}{d}$个。在以上情况下，在每个符合的节点与父亲的路上截断，是一种合法方案。故得证。 ...

图论最短路计数倍增二分答案结论题

2019-08-14

0 259

模拟74 题解

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

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

2019-10-15

0 287

模拟79 题解

A. 树发现问题是树上对祖先链维护单调栈，然后分别二分权值和深度。因为已经做过一个类似的题，直接维护一个基于倍增进行二分的链栈（或者叫可持久化单调栈？）就完了。 B. 环 circle 一个结论是：在竞赛图中，要么不存在环，要么存在的最小环为三元环。虽然想不到，...

单调栈图论桶结论题

2019-10-20

0 294