house_cat

ACM

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

/ 注册

全部文章 / ACM （共110篇）

We don't wanna work!

We don't wanna work! [JAG Asia 2016] 两个set，一个代表工作的，一个代表不工作的其实是一个很简单的模拟，但是我竟然排序之前标号。。。。检查代码的时候要从头开始检查。。 #include <bits/stdc++.h> using n...

STL-set

2019-09-14

0 351

[徐州网络赛]Longest subsequence

[徐州网络赛]Longest subsequence 可以分成两个部分，前面相同，然后下一个字符比对应位置上的大。枚举这个位置用序列自动机进行s字符串的下标转移注意最后一个字符 #include <bits/stdc++.h> const int maxn = 1e6 ...

序列自动机思维字符串

2019-09-13

0 420

[单调队列]XKC's basketball team

XKC's basketball team 题意：给定一个序列，从每一个数后面比它大至少 \(ｍ\) 的数中求出与它之间最大的距离。如果没有则为 \(-1\)。题解：从后向前维护一个递增的队列，从后往前遍历，若当前的数大于队尾就进队，否则从该队列中二分找最小的比自己大至少 \(ｍ...

单调栈

2019-09-13

0 377

XEN 3166

XEN 3166 这题原题是spj，校oj上只用判断yes no，不过也差不多题意分析之后就是求两个东西：字典序最小的长度为m的子序列同时这个字典序严格大于某个字符串用序列自动机先尽量相同，然后再考虑严格大于 #include <bits/stdc++.h&g...

序列自动机字符串

2019-09-13

0 437

[学习笔记]启发式分治

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

学习笔记启发式分治

2019-08-29

0 599

[一般图最大匹配]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