house_cat

ACM

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

/ 注册

全部文章 / ACM （共110篇）

[学习笔记]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

[学习笔记]二项式反演

例题：[King's Colors][https://vjudge.net/problem/Kattis-kingscolors] 题意：n个点的树，用恰好k种颜色染色，并且要求相邻两个点不同。这题可以发现就是组合数学题，跟树的形状一点关系都没有。求最多用k种颜色染色...

学习笔记数学组合数学

2019-09-25

0 728

Travelling Businessmen Problem

Travelling Businessmen Problem 先求出图的两个部分，可能只有一个部分然后用set模拟，得到不同部分差最小的 #include <bits/stdc++.h> using namespace std; typedef long long ll; ...

STL-set

2019-09-14

0 380

Random Access Iterator

Random Access Iterator 树型概率DP dp[u]代表以当前点作为根得到正确结果的概率将深度最深的几个点dp[u]很明显是1 然后很简单的转移有k次，但我们要先看一次的情况，然后再推到k次，k次中只要有一次就可以正确，所以求出k次全失败的概率，用1去减即可 #in...

概率树动态规划

2019-09-14

0 424

Complier

Complier [2019福建省赛] 模拟题应该有信心写，多出一些样例当/* 与// 在一起的时候总会出错，一旦出现了这些有效的应该把它删掉不对后面产生影响 #include<bits/stdc++.h> using namespace std; char s[1000...

模拟

2019-09-14

0 430

Review For Exam

Review For Exam [2019 福建省赛] 一个很简单的状态压缩DP，结果集体走偏如何解决连续几日的限制问题？这种东西普通的DP很难写 #include <bits/stdc++.h> #define ll long long using namespace std...

动态规划状态压缩

2019-09-14

0 365

Pipe Fitter and the Fierce Dogs

Pipe Fitter and the Fierce Dogs [JAG Asia 2016] 理解题意之后，就是一个非常傻的DP 然后难在理解题意，理解非法状态 #include <bits/stdc++.h> using namespace std; const int ...

动态规划

2019-09-14

0 456

Escape from the Hell

Escape from the Hell [JAG Asia 2016] 容易证明优先选择差值大的更优对于最后一瓶我们可以枚举枚举最后一瓶，然后在树状数组上消去它的影响，然后线段树check是否出现被追上的情况，即查询区间最小值。需要用到两个线段树，因为当二分找到的位置在最后一瓶后面...

树树状数组线段树

2019-09-14

0 431