HDU 4950 Monster & HDU 4952 Number Transformation

Doubi Gao3 posted @ 2014年8月15日 14:58 in acm with tags 模拟 , 974 阅读

多校第八场,做比赛还是不够稳呐!(=@__@=)!

4950:给定一个怪物,初始HP为h,战士攻击力为a,每次回合结束后怪物能回复b的血量,如果怪物的血量<1时,判负。战士经过K轮战斗必须休息一轮,问是否能杀死怪物。

贪心即可,首先判断一次杀死的情况,在判断a<=b,永远杀不死的情况,然后再在a>b的情况里分类判断,注意int越界。

 

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <cmath>
#include <stack>
using namespace std;

typedef long long LL;
LL h, a, b, k;

int main()
{
	int kase = 0;
	while(~scanf("%I64d%I64d%I64d%I64d", &h, &a, &b, &k))
	{
		if(h == 0 && a == 0 && b == 0 && k == 0) break;
		printf("Case #%d: ", ++kase);
		if(a >= h)
		{
			printf("YES\n");
			continue ;
		}
		
		if(a <= b) printf("NO\n");
		else
		{
			LL T = h-a*k+b*(k-1);
			if(T <= 0) printf("YES\n");
			else
			{
				LL M = h-a*k+b*(k+1);
				if(M >= h) printf("NO\n");
				else printf("YES\n");
			}
		}
	}
	return 0;
}

4952:打表找规律,我找到的规律大约是在sqrt(n)左右后面的项与前面的项是等差数列,而且差值=等差数列的首项x/i(i-th operation),时间复杂度大约在O(sqrt(n)),对10^10次方左右的数据足够了。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <cmath>
#include <stack>
using namespace std;

typedef long long LL;

LL work(LL x, LL i)
{
    if(x%i == 0) return x;
    LL q = x/i*i+i;
    return q;
}

LL n, k;

int main()
{
	int kase = 0;
	while(~scanf("%I64d%I64d", &n, &k) && (n+k))
	{
		LL x, y;
		
		x = n;
		
		LL i, a;
		LL b;
		for(i = 2; i <= k; i++)
		{
			y = x;
			x = work(x, i);
			a = x-y;
			b = x/i;
			if(x%i == 0 && a == b) break;
		}
		
		if(i <= k) x += (k-i)*b;
		
		printf("Case #%d: %I64d\n", ++kase, x);
	}
	return 0;
}
jackjohnny 说:
2021年6月26日 21:53

I think this is an informative post and it is very useful and knowledgeable. therefore, I would like to thank you for the efforts you have made in writing this article. 안전놀이터

jackjohnny 说:
2021年6月29日 18:36

I like your post. It is good to see you verbalize from the heart and clarity on this important subject can be easily observed... indian visa for british citizens

jackjohnny 说:
2021年7月05日 19:08

I definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work. สล็อต

jackjohnny 说:
2021年7月11日 18:49

This is my first time i visit here. I found so many interesting stuff in your blog especially its discussion. From the tons of comments on your articles, I guess I am not the only one having all the enjoyment here keep up the good work 토토사이트

AP SSC Maths Model P 说:
2022年9月11日 18:10

Mathematics is one of the tough subjects and also an easy subject for class 10th standard students of TM, EM, AP SSC Maths Model Paper UM and HM studying at government and private schools of the state. Department of School Education and teaching staff of various institutions have designed and suggested the Mathematics question paper with solutions for all chapters topic wide for each lesson of the course, and the AP SSC Maths Model Paper 2023 Pdf designed based on the new revised syllabus and curriculum.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter