首页 > ACM题库 > HDU-杭电 > HDU 4506-小明系列故事――师兄帮帮忙-背包问题-[解题报告]HOJ
2015
07-17

HDU 4506-小明系列故事――师兄帮帮忙-背包问题-[解题报告]HOJ

小明系列故事――师兄帮帮忙

问题描述 :

  小明自从告别了ACM/ICPC之后,就开始潜心研究数学问题了,一则可以为接下来的考研做准备,再者可以借此机会帮助一些同学,尤其是漂亮的师妹。这不,班里唯一的女生又拿一道数学题来请教小明,小明当然很高兴的就接受了。不过等他仔细读题以后,发现自己也不会做,这下小明�辶耍喝绻�回复说自己不懂,岂不是很没面子?
  所以,他现在私下求你帮忙解决这道题目,题目是这样的:
  给你n个数字,分别是a1,a2,a3,a4,a5……an,这些数字每过一个单位时间就会改变,假设上一个单位时间的数字为a1’,a2’,a3’……an’,那么这个单位时间的数字a[i] = a[i - 1]’ * K(i == 1的时候a[1] = a[n]’ * K),其中K为给定的系数。
  现在的问题就是求第t单位时间的时候这n个数字变成了什么了?由于数字可能会很大,所以只要你输出数字对10^9 + 7取余以后的结果。

输入:

  输入数据第一行是一个正整数T,表示有T组测试数据;
  每组数据有两行,第一行包含输入三个整数n, t, k,其中n代表数字个数,t代表第t个单位时间,k代表系数;第二行输入n个数字ai,代表每个数字开始的时候是多少。

  [Technical Specification]
  T <= 100
  1 <= n <= 10 ^ 4
  0 <= t <= 10 ^ 9  其中 t = 0 表示初始状态
  1 <= k <= 10 ^ 9
  1 <= ai<= 10 ^ 9

输出:

  输入数据第一行是一个正整数T,表示有T组测试数据;
  每组数据有两行,第一行包含输入三个整数n, t, k,其中n代表数字个数,t代表第t个单位时间,k代表系数;第二行输入n个数字ai,代表每个数字开始的时候是多少。

  [Technical Specification]
  T <= 100
  1 <= n <= 10 ^ 4
  0 <= t <= 10 ^ 9  其中 t = 0 表示初始状态
  1 <= k <= 10 ^ 9
  1 <= ai<= 10 ^ 9

样例输入:

2
3 2 5
1 2 3
3 0 5
1 2 3

样例输出:

50 75 25
1 2 3

hdu4505

/*

分析:
    水题。
    人是刚开始全部上到电梯上的。
                                                                                 2013-03-21
*/

#include"iostream"
#include"cstdlib"
using namespace std;

int n;
int aim[111];
int cmp(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}
int main()
{
	int T;
	int i;
	int now,ans;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(i=0;i<n;i++)cin>>aim[i];
		qsort(aim,n,sizeof(int),cmp);

		now=ans=0;
		for(i=0;i<n;i++)
		{
			if(aim[i]==now)	{if(i==0)ans+=5;ans++;continue;}
			ans+=(aim[i]-now)*6;
			now=aim[i];
			ans+=5;
			ans++;
		}
		ans+=now*4;
		cout<<ans<<endl;
	}
	return 0;
}

hdu4506:

/*
分析:
    快速幂取余的果题。
    囧~~么有看数论的队友、也么有看计算几何的队友,数学方面弱到
爆的我、这个快速幂取余是比赛的时候临时学的- -III。

                                            2013-03-21
*/

#include"iostream"
using namespace std;
const int N=10011;

int n;
__int64 t,k;
__int64 node[N],ans[N];
int pre[N];

__int64 cal(__int64 a,__int64 b,__int64 c)
{
	__int64 zz=1;
	a%=c;
	while(b>0)
	{
		if(b%2)	zz=(zz*a)%c;
		b/=2;
		a=(a*a)%c;
	}
	return zz;
}
int main()
{
	int T;
	int i;
	__int64 z,temp;
	cin>>T;
	while(T--)
	{
		cin>>n;
		scanf("%I64d%I64d",&t,&k);
		for(i=0;i<n;i++)	scanf("%I64d",&node[i]);

		if(!t)
		{
			printf("%I64d",node[0]);
			for(i=1;i<n;i++)	printf(" %I64d",node[i]);
			printf("\n");
			continue;
		}

		z=t%n;
		temp=cal(k,t,1000000007);
		if(!temp)		temp=1;
		for(i=0;i<n;i++)
		{
			pre[i]=i-z;
			if(pre[i]<0)	pre[i]+=n;
			ans[i]=(node[pre[i]]*temp)%1000000007;
		}
		printf("%I64d",ans[0]);
		for(i=1;i<n;i++)	printf(" %I64d",ans[i]);
		printf("\n");
	}
	return 0;
}

hdu4507

/*
分析:
    完全背包果题。
    小心会爆int。

                            2013-03-21
*/

#include"iostream"
using namespace std;
const int N=111;
const int M=100111;

int n,m;
int w[N],val[N];
__int64 dp[M];
__int64 max(__int64 a,__int64 b)
{
	return a>b?a:b;
}
int main()
{
	int i,l;
	while(scanf("%d",&n)!=-1)
	{
		for(i=0;i<n;i++)	cin>>val[i]>>w[i];
		cin>>m;

		memset(dp,0,sizeof(dp));
		for(i=0;i<n;i++)
		for(l=w[i];l<=m;l++)
			dp[l]=max(dp[l],dp[l-w[i]]+val[i]);

		printf("%I64d\n",dp[m]);
	}
	return 0;
}

hdu4509

/*
分析:
    线段树。
    也算是一道果题吧,只是简单的对区间的覆盖,范围也只有24*60。

                                                         2013-03-21
*/

#include"iostream"
#include"cstdlib"
using namespace std;
const int N=500111;

int n;
struct Seg
{
	int l,mid,r;
	int flag;				//有么有被覆盖
}T[4*N];
int hash[N];
void ko(int l,int r)
{
	int i;
	for(i=l;i<=r;i++)	hash[i]=1;
}
void build(int l,int r,int k)
{
	T[k].l=l;
	T[k].r=r;
	T[k].mid=(l+r)>>1;
	T[k].flag=0;
	if(l==r)	return ;
	build(l,T[k].mid,2*k);
	build(T[k].mid+1,r,2*k+1);
}
void cover(int l,int r,int k)
{
	if(T[k].l==l && T[k].r==r)
	{
		T[k].flag=1;
		return ;
	}
	if(r<=T[k].mid)		cover(l,r,2*k);
	else if(l>T[k].mid)	cover(l,r,2*k+1);
	else
	{
		cover(l,T[k].mid,2*k);
		cover(T[k].mid+1,r,2*k+1);
	}
	if(T[2*k].flag && T[2*k+1].flag)	T[k].flag=1;
}
void find(int k)
{
	int ans=0;
	if(T[k].flag)
	{
		ko(T[k].l,T[k].r);
		return ;
	}
	if(T[k].l==T[k].r)	return ;
	find(2*k);
	find(2*k+1);
}
int main()
{
	int i,l;
	char str[111];
	int a,b,s,e;
	while(scanf("%d",&n)!=-1)
	{
		build(0,24*60-1,1);
		//
		for(i=0;i<n;i++)
		{
			cin>>str;
			a=b=0;
			for(l=0;str[l]!=':';l++)	a=a*10+str[l]-'0';
			for(l++;str[l];l++)			b=b*10+str[l]-'0';
			s=a*60+b;

			cin>>str;
			a=b=0;
			for(l=0;str[l]!=':';l++)	a=a*10+str[l]-'0';
			for(l++;str[l];l++)			b=b*10+str[l]-'0';
			e=a*60+b-1;

			if(e<s)	continue;
			cover(s,e,1);
		}
		//
		memset(hash,0,sizeof(hash));
		find(1);
		//
		int ans=24*60;
		int limit=24*60;
		for(i=0;i<limit;i++)	if(hash[i])	ans--;
		cout<<ans<<endl;
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/8705661