# HDU 4702. Group

http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=46279

### Brief description:

给定长度为 N 的置换集合 S，|S| = M，求满足一下条件的集合 G 的最小的阶。

- $$S\subset G$$
- $$\forall \sigma, \tau \in G, \sigma \tau^{-1} \in G$$

# HDU 4742. Pinball Game 3D

# BZOJ 1493. [NOI2007]项链工厂

# BZOJ 1503. 郁闷的出纳员

# ACM-ICPC World Finals Ekaterinburg 2014

挖坑。

https://gist.github.com/lychees/6b77182120f681429f8f

http://blog.brucemerry.org.za/

## Problem B. Buffed Buffet

### Brief description:

多重背包、凸背包。

有两类物品可供选择，离散和连续。

对于连续的物品，初始单位容量的价值为 `t`

、单位容量价值损失的速率为 dt。

对于离散的物品，每份物品的容量是 `w`

、初始每份物品的价值为 `t`

、每选择一个物品，下一个件物品价值损失的速率为 `dt`

。

问恰好装满 `m`

容量时的最大价值。

### Analysis:

$$! \begin{aligned}g'(i) &= \max_{0 \le j \le i}\big\{ g(j) + \sum_{n=1}^{i-j}(t – (n-1)d\big\}\\&= \max_{0 \le j \le i}\big\{ g(j) + (i-j)t – \frac{(i-j-1)(i-j)}{2}\cdot d\big\}\\&= \max_{0 \le j \le i}\big\{ g(j) + (i-j)t – \frac{i(i-1)+j(j+1)-2ij}{2}\cdot d\big\}\\&= it – \frac{i(i-1)d}{2} + \max_{0 \le j \le i}\big\{ g(j)-\frac{j(j+1)d}{2} – jt + ijd\big\}\\&= it – \frac{i(i-1)d}{2} + \max_{0 \le j \le i}\big\{ h(j) + ijd \big\}\end{aligned}$$

## Problem D. Game Strategy

## Problem K. Surveillance

# 2014 ACM/ICPC Asia Regional Beijing Online

## Problem 1001. Always Cook Mushroom

### Brief description:

给定一个 `[1, 1000] x [1, 1000]`

的点阵，每个点阵中的点有一个权值。

`n`

组询问，每次询问一个由 (0,0)、(x,0) 点一以及从原点出发的方向向量 (a,b) 构成的直角三角形包围的点的权值和。

ゆっくり読んでください …