house_cat
house_cat
全部文章
分类
ACM(110)
JAVA(5)
其他(3)
文(1)
算法导论(2)
计算机图形学(4)
面试(2)
题解(2)
归档
标签
去牛客网
登录
/
注册
house_cat
不要忘记努力
全部文章
(共129篇)
[贪心]邻项交换
引言 训练赛遇到一个小学生的题,然后完全没思路.赛后才发现就是简单的邻项交换. 初学的时候一直对一种题很迷茫,就是排序一下就可以做的贪心,感觉这个简直就是瞎搞. 其实也是可以简单证明的. 题目:得分 题目描述 现在zql手上有 N 道题,他总共有 T 的时间来完成他们中的...
贪心
2020-02-06
0
616
KMP算法复杂度证明
引言 KMP算法应该是看了一次又一次,比赛的时候字符串不是我负责,所以学到的东西又还给网上的博客了…… 退役后再翻开看,看到模板,心想这不是\(O(n^2)\)的复杂度吗? 有两个循环也不能看做是\(O(n^2)\)的,这要用到摊还分析. 模板 这里用到的模板是算竞上的 calc...
字符串
KMP
2020-02-03
0
699
[算法导论]#1 摊还分析
引言 一个哈希表多大合适? 数据量为\(n\),如果哈希表无限大(>=\(n\)),那么时间复杂度是\(O(1)\)的,不过很显然,虽然节省了时间,但是浪费了空间. 实际上在我们不知道数据量的情况下,我们无法确定哈希表的大小,这时我们有个很美丽的数据结构->动态表 ...
2020-02-02
1
750
[转载]markown语法
C***rkdown 公式指导手册 标签: Tutorial 2018-03-20 补档: 收到很多小伙伴对本文的源文档转载需求,故传了一份 md 文件,请按需 下载 。 本文固定链接: https://www.zybuluo.com/codeep/note/163962 ...
2020-02-01
0
756
[AC自动机]玄武密码
题目描述 一个长度为\(N\)的母串,有四个元素分别是:N,S,W,N. 有M个长度为100的模式串. 现在要求每个模式串的前缀与母串匹配最长长度. 输入样例 7 3 SNNSSNS NNSS NNN WSEE 输出样例 4 2 0 题解 这是AC自动机的模板题...
字符串
AC自动机
2020-01-29
1
459
[学习笔记]AC自动机
目录 概述 回顾KMP 字典树insert() 失配指针fail[] 构建函数build() 多模式匹配query() 模板 Aho-Corasick automaton 本文基本上是oiwiki的复制粘贴:https://...
学习笔记
AC自动机
字符串
2020-01-27
0
662
分火腿
假设把所有香肠接在一起想象成一根大香肠 总长度为 \(A\) 那不难想到,需要切\(m-1\)刀,则每隔\(\frac{A}{m}\)要切一刀,设\(y=\frac{A}{m}\) 设原来一根香肠长度为\(x\),\(x=\frac{A}{n}\),\(x\)的倍数不用切,不能算在答案里 所以...
数学
2020-01-15
0
482
[学习笔记]二分与分治
二分 二分法常用来查找单调序列或单调函数上的答案. 当问题的答案具有单调性时,可以考虑通过二分求解. 先思考一个简单问题 A心里想一个1-1000之间的数,B来猜,B可以问问题,A只能回答是或者不是,怎么猜才能问的问题次数最小? 是1吗?是2吗?……平均要问500次 大...
2019-11-22
0
439
house_cat 's blog
ACM退役选手 欢迎指正:QQ:1468580561 不要忘记努力,不要辜负自己
2019-11-04
0
466
[学习笔记]二项式反演
例题:[King's Colors][https://vjudge.net/problem/Kattis-kingscolors] 题意:n个点的树,用恰好k种颜色染色,并且要求相邻两个点不同。 这题可以发现就是组合数学题,跟树的形状一点关系都没有。求最多用k种颜色染色...
学习笔记
数学
组合数学
2019-09-25
0
728
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页