P6145:

d[i] i 最早开始的时间

while(true)
{
bool change = false;
for (枚举每条记忆)
if (d[b] < d[a] + x) // 一个点a只能被枚举1次
{
d[b] = d[a] + x;
change = true;
}
if (!change)
{
break;
}
}
超时，内部循环O(m)外部循环O(n)，一共O(nm)

希望变成O(n + m)

(a, b, x)看做一条a到b长度为x的边，a影响b

没有被别人影响 等价于入度为0

queue
BFS / 拓扑排序 / 边长为1的最短路

单调队列 （不是严格意义上的队列）
处理区间不互相包含的区间最值问题

stack:

1. 表达式求值
2. 括号匹配 （1种括号，只需要计数，多种需要栈）
3. 单调栈 （求凸包，求最大矩形）

中缀表达式
需要括号

后缀表达式
8 3 2 6*+5/-4+
遇到数值入栈
遇到符号，拿出需要的操作数（一般是2），进行运算，放回去
最后应该剩下恰好一个数字。

维护一个数值栈
8 3 2 6
8 3 12
8 15
8 15 5
8 3
5
5 4
9

2类做法

1. O(n^2) 直接递归
   找到最后一个执行的运算是什么
   然后两边递归处理

按运算符优先级枚举，先枚举低优先级的（先枚举加减，再乘除，再乘方）
根据运算符结合性，如果加法这种的，从右向左扫
如果是乘方，从左向右
括号内的不算
特殊情况整体被一个括号包住了
(a + b + c)

a + b + c = (a + b) + c
a ** b ** c = a ** (b ** c)

2. 栈
   需要一个数值栈
   需要一个符号栈

优先级小的可以让优先级大的运算
优先级相等（取决于结合性）
如果没有括号，这样做就可以了

a + b * c *

数值栈:a b c
符号栈:+ *

括号的处理
任何运算都不能让左括号(出栈，括号优先级最低
只有右括号遇到左括号会消掉
(a + b)

USACO没出过

scanf("%d%d")
scanf(" %d %d")
scanf("%d %d")
都是一样的

scanf("&%lld",a[cnt]);

scanf("%c", &c) 读入一个字符
scanf(" %c", &c) 读入一个非空字符 cin >> c;
不一样

P1175,P1241,P1449,P1739,P1981

P1054 等价表达式
判断多项式是否等价？
带入几个a的值，看mod 10007之后是否相等

如果需要，可以再解出系数
f是k次函数
已知f(0) f(1) .. f(k)可以解出所有系数

P1310 表达式的值
每个表达式可以表示为
(x, y)
x表示有多少种填的方法使得这个表达式的值为0
y表示有多少种填的方法使得这个表达式的值为1

x + y = 2 ** 表达式中 _ 的个数

表达式1 (x1, y1)
和
表达式2 (x2, y2)

(+++)*(++++++_)

(x1, y1) * (x2, y2) = (x1 * x2 + x1 * y2 + y1 * x2, y1 * y2)
(x1, y1) + (x2, y2) = (x1 * x2, y1 * y2 + x1 * y2 + y1 * x2)

_ = (1, 1)

P5788 【模板】单调栈
最简单的单调栈

P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包
凸包

其实也不是真正的栈，因为需要访问最后2个元素

所有凸包算法效率一样，一般用水平序的
好写，没有精度问题
有一些题目，只有半个凸包

P5155 [USACO18DEC]Balance Beam P
0 到 n
f[i] 初始值为 i 到 n的概率是多少
f[i] = (f[i - 1] + f[i + 1]) / 2
所以f[i]是等差数列
f[0] = 0
f[n] = 1
f[i] = i / n

P4147 玉蟾宫
枚举矩形 的下边界
预处理每个位置，向上最多可以找到多少个F

用栈存矩形
矩形需要x轴方向上的大小，和y轴方向上的大小
栈是单调栈，矩形的高度单调上升
需要注意所有矩形都要更新到答案

为了化简代码。最后加入一个宽度为1，高度为0的矩形。

http://poj.org/problem?id=2559
相当于找个区间，使得区间的 最小值*区间的长度 最大

priority_queue
堆

set/map
用平衡树实现：set / map （有序的）
用Hash实现：unorder_set / unordered_map

Hash实现更快一些，但是不支持一些功能

Java
TreeSet / TreeMap
HashSet / HashMap

P1503
set 去重，有序的
需要查询集合中

= x最小的数字是什么
<= x最大的数字是什么

if (s.find(x) != s.end()) {
{
// s 中存在 x
}
else
{
// 没找到
}

lower_bound返回 >= x 最小的数字（的iterator）是什么
upper_bound返回 > x 最小的数字（的iterator）是什么

set中是有序的，
iterator-- 访问小于当前值的最大的是什么 O(log n)
iterator++ 访问大于当前值的最小的是什么 O(log n)

for (set::iterator it = s.begin(); it != s.end(); it++)
{
}
// O(n)

set/map 的 iterator 不能 += ..
不能相减 iter1 - iter2

P2073
map访问不存在的位置等于新建

删除最大值
g.erase(--g.end());

区间是左闭右开
g.end() 是没有东西

不能erase一个不存在的指针
可以erase一个不存在的值
不能对空集合 *s.begin();

P2061 [USACO07OPEN]City Horizon S
multiset erase 一个值，会删掉所有相同的值

P2141 珠心算测验
其中有多少个数，恰好等于集合中另外两个（不同的）数之和？

6 = 1 + 5 = 2 + 4 只算一次
6 = 3 + 3不算

P2161 [SHOI2009]会场预约

s.erase(it++); 是可以的

s.erase(it);it++; 是错误的

删去集合中的偶数

错误写法
for (set it=s.begin(); it!=s.end(); it++)
{
if (*it % 2 == 0)
{
s.erase(it);
}
}

错误写法
for (int i: s)
{
if (i % 2 == 0)
{
s.erase(i);
}
}

正确写法
for (set it=s.begin(); it!=s.end()😉
{
if (*it % 2 == 0)
{
s.erase(it++);
}
else
{
it++;
}
}

erase的都有类似的问题。

x不在map中
map如果不存在的话，那么会加入新的
不能这么写的 g[x] = g.size()
g[x] = n++;

以下写法很不好
if (g.find(x) != g.end())
if (g[x] != 0)
{
找到了
}
else
{
没找到
}

P1059,P2141,P2234,P4404,P1125,P2814