HDU/HDOJ 4038 2011成都赛区网络赛H题

Stone

Time Limit: 3000/2000 MS (Java/Others)Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 130Accepted Submission(s): 26

Problem Description

Given an array of integers {xi}. Each time you can apply one of the following operations to the array:
1. Choose an integer x from the array, replace it with x+1.
2. Add a new integer 1 to the array.

Define p as the product of all integers in the set. i.e. p=x1*x2*x3*...
What's the maximum possible value of p after exactly M operations?

Input

First line is a integer T (T ≤ 100), the number of test cases.
The first line of each test case contains two integers N and M, the number of integers in the initial set, and the number of operations.
The second line is N integers xi initially in the set.
1 ≤ N ≤ 100000
0 ≤ M ≤ 10^18
-10000 ≤ xi ≤ 10000

Output

For each case, you should output “Case k: ” first, where k indicates the case number and counts from one. Then the maximum product mod 1000000007.

Sample Input

4
1 1
5
3 2
1 2 3
3 2
-1 2 3
3 1
-3 -3 -3

Sample Output

Case 1: 6
Case 2: 18
Case 3: 6
Case 4: -18

Source

The 36th ACM/ICPC Asia Regional Chengdu Site —— Online Contest

这个题的思路很简单，就是尽量多的凑够3

然后在这个大的思路前提下，进行各种讨论

非常考察选手的模拟能力。

这个题的情况非常多。我是把数据分为了正数和负数来处理的。

中间要考虑负数的个数是奇数还是偶数

然后分开处理

细节就不多说啦，看代码吧

我的代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<stdlib.h>

using namespace std;

typedef __int64 ll;

const ll mod=1000000007;

ll x[100005];
ll po[100005];
ll ne[100005];
ll num1,num2;

bool cmp(ll a,ll b)
{
	return a>b;
}

ll power(ll p,ll n,ll mod)
{
	ll sq=1;
	while(n>0)
	{
		if(n%2==1)
			sq=(sq%mod)*(p%mod)%mod;
		p=(p%mod)*(p%mod)%mod;
		n=n/2;
	}
	return sq%mod;
}

int main()
{
	ll i;
	ll n,m,t,T,ans;
	scanf("%I64d",&T);
	for(t=1;t<=T;t++)
	{
		num1=0,num2=0;
		ans=1;
		scanf("%I64d%I64d",&n,&m);
		for(i=1;i<=n;i++)
		{
			scanf("%I64d",&x[i]);
			if(x[i]>=0)
			{
				num1++;
				po[num1]=x[i];
			}
			else
			{
				num2++;
				ne[num2]=x[i];
			}
		}
		sort(po+1,po+1+num1,cmp);
		sort(ne+1,ne+1+num2,cmp);
		if(num2&1)
		{
			if(m<abs(ne[1]))
			{
				ne[1]=ne[1]+m;
				for(i=1;i<=num1;i++)
					ans=(ans*po[i])%mod;
				for(i=2;i<=num2;i++)
					ans=(ans*abs(ne[i]))%mod;
				ans=(ans*ne[1])%mod;
				printf("Case %I64d: %I64d\n",t,ans);
			}
			else if(m==abs(ne[1]))
			{
				printf("Case %I64d: 0\n",t);
			}
			else
			{
				m=m-abs(ne[1])-1;
				ne[1]=1;
				num1++;
				po[num1]=ne[1];
				sort(po+1,po+1+num1,cmp);
				for(i=1;i<=num1;i++)
				{
					if(po[i]==0)
					{
						m=m-1;
						po[i]=1;
					}
					if(m==0)
						break;
				}
				if(m==0)
				{
					for(i=1;i<=num1;i++)
						ans=(ans*po[i])%mod;
					for(i=2;i<=num2;i++)
						ans=(ans*abs(ne[i]))%mod;
			//		ans=(ans*ne[1])%mod;
					printf("Case %I64d: %I64d\n",t,ans);
				}
				sort(po+1,po+1+num1,cmp);
				if(m>0)
				{
					bool flag=true;
					while(1)
					{
						flag=true;
						for(i=num1;i>=1;i--)
						{
							if(po[i]<3)
							{
								flag=false;
								po[i]=po[i]+1;
								m=m-1;
							}
							if(m==0)
								break;
						}
						if(flag)
							break;
						if(m==0)
							break;
					}
					if(m==0)
					{
						for(i=1;i<=num1;i++)
							ans=(ans*po[i])%mod;
						for(i=2;i<=num2;i++)
							ans=(ans*abs(ne[i]))%mod;
					//	ans=(ans*ne[1])%mod;
						printf("Case %I64d: %I64d\n",t,ans);
					}
					if(m>0)
					{
						ll tmp=m%3,uk;
						if(m==1)
						{
			//				ne[1]=ne[1]+1;
							po[num1]=po[num1]+1;
							for(i=1;i<=num1;i++)
								ans=(ans*po[i])%mod;
							for(i=2;i<=num2;i++)
								ans=(ans*abs(ne[i]))%mod;
					//		ans=(ans*ne[1])%mod;
							printf("Case %I64d: %I64d\n",t,ans);
						}
						else
						{
							if(tmp==1)
							{
								for(i=1;i<=num1;i++)
									ans=(ans*po[i])%mod;
								for(i=2;i<=num2;i++)
									ans=(ans*abs(ne[i]))%mod;
				//				ans=(ans*ne[1])%mod;
								m=m-4;
								uk=power(3,m/3,mod);
								uk=(uk*4)%mod;
								ans=(ans*uk)%mod;
								printf("Case %I64d: %I64d\n",t,ans);
							}
							else if(tmp==2)
							{
								for(i=1;i<=num1;i++)
									ans=(ans*po[i])%mod;
								for(i=2;i<=num2;i++)
									ans=(ans*abs(ne[i]))%mod;
				//				ans=(ans*ne[1])%mod;
								m=m-2;
								uk=power(3,m/3,mod);
								uk=(uk*2)%mod;
								ans=(ans*uk)%mod;
								printf("Case %I64d: %I64d\n",t,ans);
							}
							else
							{
								for(i=1;i<=num1;i++)
									ans=(ans*po[i])%mod;
								for(i=2;i<=num2;i++)
									ans=(ans*abs(ne[i]))%mod;
				//				ans=(ans*ne[1])%mod;
								uk=power(3,m/3,mod);
								ans=(ans*uk)%mod;
								printf("Case %I64d: %I64d\n",t,ans);
							}
						}
					}
				}
			}
		}
		else
		{
			for(i=1;i<=num1;i++)
			{
				if(po[i]==0)
				{
					m=m-1;
					po[i]=1;
				}
				if(m==0)
					break;
			}
			if(m==0)
			{
				for(i=1;i<=num1;i++)
					ans=(ans*po[i])%mod;
				for(i=1;i<=num2;i++)
					ans=(ans*abs(ne[i]))%mod;
		//		if(num2>=1)
		//			ans=(ans*ne[1])%mod;
				printf("Case %I64d: %I64d\n",t,ans);
			}
			sort(po+1,po+1+num1,cmp);
			if(m>0)
			{
				bool flag=true;
				while(1)
				{
					flag=true;
					for(i=num1;i>=1;i--)
					{
						if(po[i]<3)
						{
							flag=false;
							po[i]=po[i]+1;
							m=m-1;
						}
						if(m==0)
							break;
					}
					if(flag)
						break;
					if(m==0)
						break;
				}
				if(m==0)
				{
					for(i=1;i<=num1;i++)
						ans=(ans*po[i])%mod;
					for(i=1;i<=num2;i++)
						ans=(ans*abs(ne[i]))%mod;
			//		if(num2>=1)
			//			ans=(ans*abs(ne[1])%mod;
					printf("Case %I64d: %I64d\n",t,ans);
				}
				if(m>0)
				{
					ll tmp=m%3,uk;
					if(m==1)
					{
						po[num1]=po[num1]+1;
						for(i=1;i<=num1;i++)
							ans=(ans*po[i])%mod;
						for(i=1;i<=num2;i++)
							ans=(ans*abs(ne[i]))%mod;
				//		if(num2>=1)
				//			ans=(ans*ne[1])%mod;
						printf("Case %I64d: %I64d\n",t,ans);
					}
					else
					{
						if(tmp==1)
						{
							for(i=1;i<=num1;i++)
								ans=(ans*po[i])%mod;
							for(i=1;i<=num2;i++)
								ans=(ans*abs(ne[i]))%mod;
					//		if(num2>=1)
					//			ans=(ans*ne[1])%mod;
							m=m-4;
							uk=power(3,m/3,mod);
							uk=(uk*4)%mod;
							ans=(ans*uk)%mod;
							printf("Case %I64d: %I64d\n",t,ans);
						}
						else if(tmp==2)
						{
							for(i=1;i<=num1;i++)
								ans=(ans*po[i])%mod;
							for(i=1;i<=num2;i++)
								ans=(ans*abs(ne[i]))%mod;
					//		if(num2>=1)
					//			ans=(ans*ne[1])%mod;
							m=m-2;
							uk=power(3,m/3,mod);
							uk=(uk*2)%mod;
							ans=(ans*uk)%mod;
							printf("Case %I64d: %I64d\n",t,ans);
						}
						else
						{
							for(i=1;i<=num1;i++)
								ans=(ans*po[i])%mod;
							for(i=1;i<=num2;i++)
								ans=(ans*abs(ne[i]))%mod;
					//		if(num2>=1)
					//			ans=(ans*ne[1])%mod;
							uk=power(3,m/3,mod);
							ans=(ans*uk)%mod;
							printf("Case %I64d: %I64d\n",t,ans);
						}
					}
				}
			}
		}
	}
	return 0;
}