全国信息学奥林匹克联赛(NOIP2011)复赛提高组day2

一、计算系数

首先对题目多项式进行简化分析

(x+y)²=x²+2xy+y²

(x+y)³=x³+3x²y+3xy²+y²

(x+y)⁴=x⁴+4x³y+6x²y²+4xy³+y⁴

不难发现它们的系数组成了一个杨辉三角

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

……

进一步带入则可得

(ax+by)²=a²x²+2abxy+b²y²

(ax+by)³=a³x³+3a²bx²y+3ab²xy²+b³y³

(ax+by)⁴=a⁴x⁴+4a³bx³y+6a²b²x²y²+4ab³xy³+b⁴y⁴

……

于是得(ax+by)^k中xⁿy^m项的系数为(杨辉三角的第(k+1)行第(m+1)或(k-n+1)个的值*(aⁿb^m))的值

下面为代码:

#include<bits/stdc++.h>
#define mod 10007
using namespace std;
long long a,b,k,n,m;
long long yh[5010][5010];
int Pow(int x,int y){//计算幂
	long long r=1;
	for(long long i=1;i<=y;i++){
		r*=x;
		if(r>=mod)r%=mod;
	}
	return r;
}
void dfs(int x,int y){//杨辉三角
	if(y>x)dfs(x+1,1);
	else{
		yh[x][y]=yh[x-1][y]+yh[x-1][y-1];
		if(yh[x][y]>=mod)yh[x][y]%=mod;
		if(x==k+1&&y==m+1){
			cout<<(yh[x][y]*Pow(a,n)*Pow(b,m))%mod;
			return;
		}
		dfs(x,y+1);
	}
}
int main(){
	cin>>a>>b>>k>>n>>m;
	yh[1][1]=1;
	dfs(2,1);
}

二、聪明的质检员

三、观光公交

这道题本人主要就是贪心思想

首先记录每个景点最后一个乘客来到出发地的时间与这个景点(从前一个景点来)最迟到达时的时间。然后分析在哪个时刻使用氮气加速才是省时最多的(贪心):当这个景点的乘客开始等待时,公交还在来的路上,即这个景点的到达时间晚于最后一个乘客来到出发地的时候，使用氮气加速器可以减少乘客等待的时间。但也许会有很多个这种时候，所以要将它们记录下来，每次加速取省时最多的，再更新再继续进行此操作直到此时氮气加速器使用完(途中注意D[i]>0)

代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int d[1010];
int t,a,b;
int num[1010],times[1010],wait[1010],rest[1010];
int ans=0;
int main(){
	cin>>n>>m>>k;
	for(int i=2;i<=n;i++)
	    scanf("%d",&d[i]);
	for(int i=1;i<=m;i++){
	    scanf("%d%d%d",&t,&a,&b);
	    wait[a]=max(wait[a],t);
	    ans-=t;
	    num[b]++;
	}
	for(int i=2;i<=n;i++)
	    times[i]=max(wait[i-1],times[i-1])+d[i];
	for(int i=1;i<=k;i++){
		for(int j=n;j>=2;j--){
		    rest[j]=num[j];
			if(wait[j]<times[j])rest[j]+=rest[j+1];
		}
		int maxn=-1,u=0;
		for(int j=2;j<=n;j++)
			if(rest[j]>maxn&&d[j]>0){
				maxn=rest[j];
				u=j;
			}
		d[u]--;
		for(int j=u;j<=n;j++)
		    times[j]=max(wait[j-1],times[j-1])+d[j];
	}
	for(int i=2;i<=n;i++)ans+=num[i]*times[i];
	printf("%d",ans);
}

其中有点难理解的地方：

ans:如果在后面减去t也没有问题,只是分开更简洁些

rest[]:如果在第i路段加速造福的乘客(能被减少等待时间的乘客数)

times[]:到达第i景点的时间

num[]:在第i个景点下车的乘客数

wait[]:第i个景点最后一个来到的乘客的时间