house_cat

分类

ACM(110) JAVA(5) 其他(3) 文(1) 算法导论(2) 计算机图形学(4) 面试(2) 题解(2)

/ 注册

全部文章（共129篇）

[学习笔记]启发式分治

启发式分治给定n个数，求满足某种条件的点对数目或最大权值，而这个最大权值与点对(a,b)的区间[a,b]的区间最大/最小值有关。那么这时就可以考虑分治，对于区间[L,R]，找到最小/大值所在位置，然后处理横跨最小/大值所在位置的点对，然后递归处理子区间。 HUD-Make Roun...

学习笔记启发式分治

2019-08-29

0 600

[一般图最大匹配]Bimatching

10566 Bimatching 题意：一个男生必须跟两个女生匹配，求最大匹配思路：一般的二分图匹配做不了，网络流也不会建图，这题采用的是一般图匹配首先在原来二分图的基础上，将一个男生拆成两个点两个点之间有一条边，这样图至少会有n个匹配如果想要答案...

图论学习笔记一般图匹配

2019-08-25

0 360

[HDU多校]Ridiculous Netizens

[HDU多校]Ridiculous Netizens 点分治分成两个部分：对某一点P，连通块经过P或不经过P．经过P采用树形依赖背包不经过P的部分递归计算树型依赖背包 v点必须由其父亲u点转移过来即必须经过P...

点分治树

2019-08-14

0 424

杭电多校第二场

杭电多校第二场 1005-Everything Is Generated In Equal Probability[期望递推] 如果猜的话就是：\((n^2-1)/9\) 暴力跑一下得到样例是怎么出来的然后猜测一下……. #include <bits/stdc++.h> #de...

训练记录

2019-07-29

0 454

杭电多校第一场

[模板]杭电多校第一场据说标题加模板浏览量++ 1002 Operation[贪心+线性基] 题目强制在线一来我就写了一个线段树MLE,仔细一想1.2e8必然MLE 这题求的是\((l,r)\)上的任意数的最大异或和我们来回忆一下线性基求最大异或和的操作：将线性基从高...

训练记录

2019-07-22

0 490

[学习笔记]点分治

点分治解决问题对于某些限定条件的路径静态地进行统计的算法．基本思路分治思想对于某一点P，树上路径可以分为两类，经过点P，包含与点P的某一棵子树上第二种可以递归处理第一种通过求P的所有子节点的深度就可以处理树的重心如果是一条链的话，那复杂度很大，需要递归N层，...

学习笔记点分治

2019-07-21

0 682

2019牛客多校第二场

2019牛客多校第二场 D.Kth Minimum Clique（dijkstra+bitset+二进制）题意：从图中随机选几个点，如果这些点连通，那么就称为团．团的价值是所有点的和．求第\(k\)小的团．一开始想到\(2^n\)的算法如果从合法状态然后增广，就可以避免走到很...

训练记录

2019-07-21

0 382

2019牛客多校第二场

2019牛客多校第二场 D.Kth Minimum Clique（dijkstra+bitset+二进制）题意：从图中随机选几个点，如果这些点连通，那么就称为团．团的价值是所有点的和．求第小的团．一开始想到的算法如果从合法状态然后增广，就可以避免走到很多非法状态，然后用一个last避免重复 ...

2019-07-21

2 889

2019牛客多校第一场

2019牛客多校第一场 A:Equivalent Prefixes（单调栈）题意：注意是每个子区间都要满足可以发现必须要有单调性，想到要同增同减然后找到一个满足同增同减，但是不符合题意的反例： 1 3 2 1 3 0 然后发现必须要维护一个以当前点结尾的最长上升子序列长度相同如果不同就...

2019-07-19

0 757

[概率DP]相逢是温厚

题意有\(n\)场比赛，他每次等概率地选择一场，选择的比赛可能有没ac过的题，他一定会ac这次比赛中的某一道，并说我好菜啊。如果全ac过了，也会说我好菜啊。求期望说多少次我好菜啊。注意题目中每场题的范围是1到3 我们可以把相同题数的场看成同一种，那就有三种把题意抽象成取球游戏，就是\(...

动态规划概率

2019-07-19

0 476