2021/1/17 *2200 Codeforces Round #689 (Div. 2, based on Zed Code Competition) E.Water Level

  • (x > y) 的时候,每次都在降低,直接看能不能撑住t次
  • (x <= y) 的时候,情况比较复杂一些,可以这样考虑,只有在当前的水量已经没办法再减少,又无法加 (y) 的情况下,才会出现超出范围,所以如果 (l-r) 的范围是超过或者等于 (x+y) 的,是不会出现这种情况的,所以我们讨论的范围就在 (r-l<x+y) 的情况下,在这种情况下,每次喝到水量尽可能的最低,只能加一次 (y),再重复这个循环,由于 (x) 的范围是 (x <= 10^6) ,所以我们每次找到最低的位置,它离 (l) 肯定是 (x) 以内,所以可以用当前水量 (%x) 表示这个位置,之后看能不能构成循环,如果之前访问过,说明可以形成循环,直接输出 (Yes) ,否则最多就是 (x)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ll k, l, r, t, x, y;
	scanf("%lld %lld %lld %lld %lld %lld", &k, &l, &r, &t, &x, &y);
	if (k < l || k > r)	return puts("No"), 0;
	if (x > y) {
		if (k + y > r)	k -= x, t--;
		ll cnt = (k - l) / (x - y);
		if (cnt < t)	return puts("No"), 0;
		else	return puts("Yes"), 0;
	}
	else {
		vector < bool > flag(x, false);
		while (t > 0) {
			if (flag[k % x])	return puts("Yes"), 0;
			flag[k % x] = true;
			ll cnt = (k - l) / x;
			t -= cnt; k -= cnt * x;
			if (t <= 0)	return puts("Yes"), 0;
			if (k + y > r)	return puts("No"), 0;
			k += y; k -= x; t--;	
		}
		puts("Yes");
	}
	return 0;
}
原文地址:https://www.cnblogs.com/cminus/p/14290460.html