TopCoder SRM676(Div.1)

Posted on By 二价氢

#Div.1

##Level 1.WaterTank

###Task

给一个水箱,入口以一定的速度进水,第段以的流量进水时间

水箱还有一个出口,以一定的速度放水,求放水的最小速度,使得水箱不满

###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游戏,因此我们知道

考虑在,耐久为k的Token,有如下方程

若该位置为Escape,则

之后能发现这个存在长度为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种植物,植物之间有依赖性,即种某个植物之前必须已经收获过另一些植物

种植植物需要的时间,播种和收获时间不计

同时植物可以花费将种植时间减1,至多减为0

求播种到收获所有植物所需的最少时间,多种植物可以同时种植

###Solution

网络流(待补全)

###Code

(待补全)