CDOJ 29 飞镖(dart) 解题报告

题目链接:http://acm.uestc.edu.cn/#/problem/show/29

比较坑爹的一道题,我是先打表找了规律,然后证明这个规律的……

稍微说一下,随便的X次指的是其中不必要包括一次双倍,如果包括一次最后一次会说的。

首先,如果不考虑红心,如果只剩一次,随便的一次,那么显然只有1~K K~2K的偶数 2K~3K的三的倍数可以投中。

如果只剩两次,包括一次最后一次,那么显然是2~3K全部可以被充满。
对于3K~5K的分数:
3K+t = 2K + K+t 或 2K-2 + K+t+2
可以证明对于t是奇偶均可以成立
以上式子的边界:
5K-3 = 2K + 3K-3
5K-2 = 2K-2 + 3K
5K = 2K + 3K
这里可以知道5K-1是取不到的(如果5K-1恰好是3的倍数是可以取到的)

如果只剩两次,随便的两次,则在只剩最后一次的基础上加上2K~3K的部分,也就是在5K-1~6K里面3的倍数均可以达到。

如果只剩三次,必然包括一次最后一次
已知,2~5K除了5K-1都可以达成;
可知,2~8K除了8K-1是肯定可以达到的。
只要对于两次里面的每一个都+3K即可。
又因为最大只能达到8K=(3+3+2)K,不用考虑更上。
所以任何在2~8K-2或者8K的值均可以取到。

接下来考虑红心:
如果只能有一个小红心,参考只剩两次,包括一次最后一次。
如果可以有一个大红心,参考只剩两次,随便的两次。
如果可以有一个大红心+一个小红心,参考只剩一次,随便的一次。
如果可以有两个大红心,参考只剩一次,随便的一次。
如果可以有两个大红心+一个小红心,参考个P。

有一个小要求就是C必须要大于等于2,想必能理解吧。不过,疑似,数据没有这个坑。

原谅我压代码压得我自己都不认得了。

#include <cstdio>
using namespace std;

int K, M, C;
bool able;

int main() {
	while (~scanf("%d%d%d", &K, &M, &C) && (K || M || C)) {
		able = false;
		able |= C == M * 2 || C == M * 3 || C == M * 4 || C == M * 5 || C == M * 6;
		able |= C >= 2 && (C < K * 8 - 1 || C == K * 8);
		able |= (C -= M) >= 2 && (C < K * 5 - 1 || C == K * 5);
		able |= (C -= M) >= 0 && (C < K * 5 - 1 || C == K * 5 || C <= K * 6 && !(C % 3));
		able |= (C -= M) >= 0 && (C <= K || C <= K * 2 && !(C % 2) || C <= K * 3 && !(C % 3));
		able |= (C -= M) >= 0 && (C <= K || C <= K * 2 && !(C % 2) || C <= K * 3 && !(C % 3));
		puts(able ? "Yes" : "No");
	}
	return 0;
}
原文地址:https://www.cnblogs.com/johnsonyip/p/5668700.html