HDU 4791 Alice's Print Service

从后往前预处理打印纸的最小花费。然后在询问时通过upper_bound找到位置p，比较当前打印纸张花费与相邻临界点最小花费即可。

 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

int T;

const int maxn = 100010;
const int INF = 0x3f3f3f3f;
typedef long long LL;

LL x[maxn], y[maxn];
LL cost[maxn];

int main()
{
	int T;
	for(scanf("%d", &T); T > 0; T--)
	{
		int n, m;
		scanf("%d%d", &n, &m);
		
		for(int i = 0; i < n; i++)
		{
			scanf("%I64d%I64d", &x[i], &y[i]);
			cost[i] = x[i]*y[i];
		}
		
		LL pre = cost[n-1];
		for(int i = n-1; i >= 0; i--)
		{
			if(pre < cost[i])
			{
				cost[i] = pre;
				pre = cost[i];
			}
		}
		
		while(m--)
		{
			LL q; scanf("%I64d", &q);
			if(q >= x[n-1]) { printf("%I64d\n", q*y[n-1]); continue ; }
			
			LL p = upper_bound(x, x+n, q)-x;
			
			LL ans = q*y[p-1];
			ans = min(ans, cost[p]);
			printf("%I64d\n", ans);
		}
	}
	return 0;
}

acm 模拟 Comments(27) 2014年9月28日 16:51

HDU 4950 Monster & HDU 4952 Number Transformation

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

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;
}

acm 模拟 Comments(5) 2014年8月15日 14:58

HDU 4961 Magical Forest

大意：虚拟出一个2*10^9 * 2*10^9的数组内存空间，现在这个内存空间初始化为0，并且对其中的某些元素进行赋初值。后接着一系列的操作使得这个数组的行和列得以交换，中间还对某一行或者是某一列元素的值进行询问。

前段时间写过一个类似的题，二哥的内存。没想到在多校遇到了这道题，只不过数据范围改一下，但是有一个限制条件，即交换的两行（列）必须都有水果或者都没水果，注意这一点，用map映射一下值就可以了。

 

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

map<long long int, int> mp;
map<int, int> r, c;

int n, m, k;

void swap(int &a, int &b)
{
    int t = a;
    a = b;
    b = t;    
}

int main()
{
	int T, kase = 0;
	for(scanf("%d", &T); T > 0; T--)
	{
		scanf("%d%d%d", &n, &m, &k);
		
		mp.clear();
		r.clear();
		c.clear();
		
		for(int i = 0; i < k; i++)
		{
			int x, y, z;
			scanf("%d%d%d", &x, &y, &z);
			mp[1LL*x*2000000005+y] = z;
			r[x] = x, c[y] = y;
		}
		
		int q; scanf("%d", &q);
		printf("Case #%d:\n", ++kase);
		
		while(q--)
		{
			int cmd, x, y;
			scanf("%d%d%d", &cmd, &x, &y);
			if(cmd == 1)
			{
				if(r.count(x) && r.count(y))
				{
					swap(r[x], r[y]);
				}
				if(!r.count(x) && !r.count(y))
				{
					r[x] = x, r[y] = y;
					swap(r[x], r[y]);
				}
			}
			else if(cmd == 2)
			{
				if(c.count(x) && c.count(y))
				{
					swap(c[x], c[y]);
				}
				if((!c.count(x) && !c.count(y)))
				{
					c[x] = x, c[y] = y;
					swap(c[x], c[y]);
				}
			}
			else
			{
				if(mp[1LL*r[x]*2000000005+c[y]] != 0)
				{
					printf("%d\n", mp[1LL*r[x]*2000000005+c[y]]);
				}
				else printf("0\n");
			}
		}
	}
	return 0;
}

acm 模拟 Comments(2) 2014年8月12日 21:16

HDU 4930 Fighting the Landlords

给定斗地主的规则以及两幅手牌，然后判断是否在这一轮内你不会输给对手或者出完了全部手牌。

在比赛中我判断所有的情况，这样比较麻烦。其实可以把Bomb、Tri、Pair拆开分别去判断，有很多细节需要注意。

 

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

int x[20], y[20];

int Win(int n)
{
	if(n == 4 || n == 6) //炸弹带 
	{
		for(int i = 17; i >= 3; i--)
		{
			if(x[i] == 4) return 1;
		}
	}
	if(n == 5) //3带2 
	{
		int Tri = 0, Dou = 0;
		for(int i = 17; i >= 3; i--)
		{
			if(x[i] == 3) Tri = 1;
			if(x[i] == 2) Dou = 1;
		}
		if(Tri && Dou) return 1;
	}
	if(n == 4) //3带1 
	{
		for(int i = 17; i >= 3; i--)
		{
			if(x[i] == 3) return 1;
		}
	}
	if(n == 3) //三个 
	{
		for(int i = 17; i >= 3; i--)
		{
			if(x[i] == 3) return 1;
		}
	}
	if(n == 2) //Double 
	{
		for(int i = 17; i >= 3; i--)
		{
			if(x[i] == 2) return 1;
		}
	}
	if(n == 1) return 1; //一个 
	
	return 0;
}

int main()
{
	int T;
	for(scanf("%d", &T); T > 0; T--)
	{
		char s[20];
		scanf("%s", s);
		
		memset(x, 0, sizeof(x));
		memset(y, 0, sizeof(y));
		
		for(int i = 0; s[i]; i++)
		{
			int t;
			if(s[i] == 'T') t = 10;
			else if(s[i] == 'J') t = 11;
			else if(s[i] == 'Q') t = 12;
			else if(s[i] == 'K') t = 13;
			else if(s[i] == 'A') t = 14;
			else if(s[i] == '2') t = 15;
			else if(s[i] == 'X') t = 16;
			else if(s[i] == 'Y') t = 17;
			else t = s[i]-'0';
			x[t]++;
		}
		
		int len = strlen(s);
		scanf("%s", s);
		for(int i = 0; s[i]; i++)
		{
			int t;
			if(s[i] == 'T') t = 10;
			else if(s[i] == 'J') t = 11;
			else if(s[i] == 'Q') t = 12;
			else if(s[i] == 'K') t = 13;
			else if(s[i] == 'A') t = 14;
			else if(s[i] == '2') t = 15;
			else if(s[i] == 'X') t = 16;
			else if(s[i] == 'Y') t = 17;
			else t = s[i]-'0';
			y[t]++;
		}
		
		if(x[16] == 1 && x[17] == 1) //有大小王 
		{
			printf("Yes\n");
			continue;
		}
		
		if(Win(len)) { printf("Yes\n"); continue ; } //出完的情况 
		
		if(y[16] == 1 && y[17] == 1) //有大小王 
		{
			printf("No\n");
			continue;
		}
		
		
		int bomb = -1, p;
		for(int i = 17; i >= 3; i--) //炸弹 
		{
			if(x[i] == 4)
			{
				bomb = 1;
				p = i;
				break;
			}
		}
		
		int win = 1;
		if(bomb == 1)
		{
			for(int i = 17; i > p; i--)
			{
				if(y[i] == 4)
				{
				 	win = 0; break;
				}
			}
		}
		
		if(bomb == 1 && win) { printf("Yes\n"); continue; } //有炸弹且最大 
		else if(!win) { printf("No\n"); continue ;} //有炸弹，但输了。 
		
		for(int i = 3; i <= 17; i++) if(y[i] == 4) { bomb = 2; break; }
		if(bomb == 2) { printf("No\n"); continue ; } //对手有炸弹，我没有。
		
		
		win = 1;
		int Tri = -1;
		for(int i = 17; i >= 3; i--) //三个 
		{
			if(x[i] == 3)
			{
				Tri = 1;
				p = i;
				break;
			}
		}
		
		if(Tri == 1)
		{
			for(int i = 17; i > p; i--)
			{
				if(y[i] == 3)
				{
					Tri = 0;
					break;
				}
			}
		}
		
		if(Tri == 1) { printf("Yes\n"); continue ;}
		else if(Tri == 0) win = 0;
		
		
		int Dou = -1;
		for(int i = 17; i >= 3; i--) //两个 
		{
			if(x[i] == 2)
			{
				Dou = 1;
				p = i;
				break;
			}
		}
		
		if(Dou == 1)
		{
			for(int i = 17; i > p; i--)
			{
				if(y[i] == 2 || y[i] == 3)
				{
					Dou = 0;
					break;
				}
			}
		}
		
		if(Dou == 1) { printf("Yes\n"); continue ; }
		else if(Dou == 0) win = 0;
		
		int solo = -1;
		for(int i = 17; i >= 3; i--) //一个 
		{
			if(x[i] == 1)
			{
				solo = 1;
				p = i; 
				break;
			}
		}
		
		if(solo == 1)
		{
			if(win == 0) win = 1;
			for(int i = 17; i > p; i--)
			{
				if(y[i] == 1 || y[i] == 2 || y[i] == 3) { win = 0; break; }
			}
		}
		
		if(win == 1) printf("Yes\n");
		else if(win == 0) printf("No\n");
	}
	return 0;
}

acm 模拟 Comments(5) 2014年8月08日 12:30