#Div.1
##Level 1.WaterTank
###Task
给一个水箱，入口以一定的速度进水，第\(i\)段以\(x_i\)的流量进水\(t_i\)时间
水箱还有一个出口，以一定的速度放水，求放水的最小速度，使得水箱不满
###Solution
二分答案，模拟
###Code
struct WaterTank{
bool check(vector<int> &t, vector<int> &x, int C, double v) {
double current = 0;
int n = t.size();
for (int i = 0; i < n; i++) {
double rate = x[i] - v;
current += rate * t[i];
if (current < 0) current = 0;
if (current > C) return false;
}
return true;
}
double minOutputRate(vector<int> t, vector<int> x, int C) {
double maxVal = 1e10, minVal = 0;
while (maxVal - minVal > 1e-8) {
double mid = (maxVal + minVal) / 2;
if (check(t, x, C, mid)) maxVal = mid;
else minVal = mid;
}
return maxVal;
}
};
##Level2 BoardEscape
###Task
棋盘上有若干Token与若干Escape，以及若干不能走的区域，Token的耐久度均为K
Alice与Bob轮流移动棋子，每次往任意一个四联通块移动任意一个Token一格，同时Token的耐久减1
不能走的人输
###Solution
由SG定理知道这是一个Nim游戏，因此我们知道
\[f_{\textrm{ThisStatus}} = \textrm{mex}(f_{\textrm{NextStatus}})\]考虑在\((x,y)\)，耐久为k的Token，有如下方程
\[f_{x,y,k} = \textrm{mex}(f_{x-1,y,k-1},f_{x+1,y,k-1},f_{x,y-1,k-1},f_{x,y+1,k-1})\]若该位置为Escape，则\(f_{x,y,k} = 0\)
之后能发现这个存在长度为4的循环节，因而我们可以大大减小枚举的范围
最后答案显然就是所有的xor和，非零就是Alice赢，否则是Bob赢
###Code
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0,-1, 0};
typedef pair<int, int> pii;
#define x first
#define y second
#define able( _x , _y ) ( ( ( _x ) >= 0 ) && ( ( _x ) < ( _y )) )
int gr[55][55][6];
struct BoardEscape {
string findWinner(vector <string> s, int k) {
int r = s.size();
int c = s[0].size();
for (int i = 1; i < 6; i++) {
for (int x = 0; x < r; x++) {
for (int y = 0; y < c; y++) {
if (s[x][y] == 'E') {gr[x][y][i] = 0;continue;}
if (s[x][y] == '#') continue;
bool mex[3] = {0, 0, 0};
for (int d = 0; d < 4; d++)
if (able(x + dx[d], r) && able(y + dy[d], c))
if (s[x + dx[d]][y + dy[d]] != '#')
mex[gr[x + dx[d]][y + dy[d]][i - 1]] = true;
while (mex[gr[x][y][i]]) {
gr[x][y][i]++;
}
}
}
}
int ans = 0;
if (k > 4) k = 4 + k % 2;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
if (s[i][j] == 'T')
ans ^= gr[i][j][k];
return ans ? "Alice" : "Bob";
}
};
##Level3
###Task
有N种植物，植物之间有依赖性，即种某个植物之前必须已经收获过另一些植物
种植植物\(i\)需要\(T_i\)的时间，播种和收获时间不计
同时植物\(i\)可以花费\(C_i\)将种植时间减1，至多减为0
求播种到收获所有植物所需的最少时间，多种植物可以同时种植
###Solution
网络流（待补全）
###Code
（待补全）