topcoder srm 450 div1

problem1 link

用$f[i][0],f[i][1]$表示从$i$位置开始Alice是先手是否可以胜利，是后手是否可以胜利。

problem2link

每次钱数够$price$时可以选择使得$n$或者$k$中较小的一个增加1。最多也就增加$2*10^{6}$次。钱数不够$price$时可以直接算出还要多少次可以够$price$。每一次也可以直接计算出不再变化$n,k$而直接挣够$target$时的次数。

problem3 link

如果$k$足够大，最后一定是在某一个区间$[L,R]$循环。当从左到右到达$R$之后，其要选择的循环的$L$一定是满足使得$sum(i,R)$最大的$i$。

那么现在就是应该尽快第一次到达$R$。

设$minTime[i],maxScore[i]$表示从0到达$i$并且下一次应该朝左时最小次数，以及在次数最小情况下最大的分数。

那么每次到达$i$时，一定是在$i$进行了若干次循环$[x,i]$后，从$i$到达了后面的某个$j$。在$i$循环的次数就是满足到达$j$不为负值的最小值。

code for problem1

import java.util.*;

import java.math.*;

import static java.lang.Math.*;

public class OrderedNim {

	public String winner(int[] layout) {

		final int n = layout.length;

		boolean s0 = true;

		boolean s1 = false;

		for (int i = n - 2; i >= 0; --i) {

			boolean t0, t1;

			if (layout[i] == 1) {

				t0 = s1;

				t1 = s0;

			}

			else {

				if (s0 || s1) {

					t0 = true;

					t1 = false;

				}

				else {

					t0 = false;

					t1 = true;

				}

			}

			s0 = t0;

			s1 = t1;

		}

		if (s0) {

			return "Alice";

		}

		return "Bob";

	}

}

code for problem2

import java.util.*;

import java.math.*;

import static java.lang.Math.*;

public class StrongEconomy {

	public long earn(long n, long k, long price, long target) {

		if (n >= (target + k - 1) / k) {

			return 1;

		}

		long result = Long.MAX_VALUE;

		long usedDays = 0;

		long sum = 0;

		while (n * k < target) {

			long speed = n * k;

			result = Math.min(result, usedDays + (target - sum + speed - 1) / speed);

			if (sum < price) {

				long d = (price - sum + speed - 1) / speed;

				sum += speed * d;

				usedDays += d;

			}

			sum -= price;

			if (n < k) {

				++n;

			}

			else {

				++k;

			}

		}

		result = Math.min(result, usedDays + 1);

		return result;

	}

}

code for problem3

import sun.rmi.runtime.Log;

import java.util.*;

import java.math.*;

import static java.lang.Math.*;

public class RowGame {

	public long score(int[] board, int k) {

		final int n = board.length;

		long[] lmax = new long[n];

		for (int i = 0; i < n; ++ i) {

			lmax[i] = Long.MIN_VALUE;

			long s = 0;

			for (int j = i; j >= 0; --j) {

				s += board[j];

				lmax[i] = Math.max(lmax[i], s);

			}

		}

		long[] minTimes = new long[n];

		long[] maxScore = new long[n];

		long tmp = 0;

		for (int i = 0; i < n; ++i) {

			minTimes[i] = Long.MAX_VALUE;

			tmp += board[i];

			if (tmp >= 0) {

				minTimes[i] = 1;

				maxScore[i] = tmp;

			}

		}

		long result = 0;

		for (int i = 0; i < n; ++i) {

			if (minTimes[i] > k) {

				continue;

			}

			result = Math.max(result, maxScore[i] + lmax[i] * (k - minTimes[i]));

			if (lmax[i] <= 0) {

				continue;

			}

			tmp = maxScore[i];

			for (int j = i + 1; j < n; ++j) {

				tmp += board[j];

				long t = (- tmp + 2 * lmax[i] - 1)/(2 * lmax[i]);

				if ( t <= 0) {

					t = 1;

				}

				long newTimes = minTimes[i] + t * 2;

				long newScore = tmp + lmax[i] * t * 2;

				if (minTimes[j] > newTimes || minTimes[j] == newTimes && maxScore[j] < newScore) {

					minTimes[j] = newTimes;

					maxScore[j] = newScore;

				}

			}

		}

		return result;

	}

}

巴特西

topcoder srm 450 div1

最新文章

热门文章