0314考试总结

总体来说今天的题目其实还是蛮良心的。

T1昨天刚刚学习的预处理组合数,今天正好就用上了,挺好的不过如何A呢?手玩了1个小时,发现的确不是很好搞,于是暴力50弃疗。

T2什么玩意啊...问了学长题意以后刚了一会,发现的确没什么思路,略过。

T3想了想贪心,自己手玩了一些小数据,发现贪心的思想是错误的。然后想着如何正解的时候,用了个假的贪心,发现四组大数据全部过了,稳!

--------------------------------------中午打球-------------------------------------------

下午来的时候评测,发现自己只有0+0+70

whatfa?T1怎么回事,一看程序,忘了取模,加上...瞬间多了50分。

听了一波题解,发现T1和昨天的思路很像,都是组合数和走的方案数的模型转换,这个操作不错,以后遇到这种题目可以尝试往这方面想一下。

改了以后AC的code:

#include<bits/stdc++.h>
using namespace std;
long long ans=0,maxn=0,v[10010],f[4010][4010],n,fv[10010],mod=1000000007,a[210000],b[210000],ff[10010];
long long f2[4010][4010];
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i],&b[i]);
	v[1]=1;
	for(int i=2;i<=10000;i++)v[i]=(mod-mod/i)*v[mod%i]%mod;
	ff[0]=1;fv[0]=1;
	for(int i=1;i<=10000;i++){ff[i]=ff[i-1]*i%mod;fv[i]=fv[i-1]*v[i]%mod;}
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;i++){scanf("%d%d",&a[i],&b[i]);maxn=max(maxn,a[i]);maxn=max(maxn,b[i]);}
	maxn++;
	for(int i=1;i<=n;i++){f[maxn-a[i]][maxn-b[i]]++;f2[maxn+a[i]][maxn+b[i]]++;}
	for(int i=1;i<=maxn*2;i++)
		for(int j=1;j<=maxn*2;j++)
		{
			f[i][j]+=f[i-1][j]+f[i][j-1];
			f[i][j]%=mod;
			if(f2[i][j]){ans+=f[i][j]*f2[i][j];ans%=mod;}
		}
	for(int i=1;i<=n;i++)
	{
		ans-=((ff[a[i]*2+b[i]*2]*fv[b[i]*2]%mod)*fv[a[i]*2]%mod);
		ans=((ans%mod)+mod)%mod;
	}
	printf("%lld
",ans/2);
	return 0;
}

  T2好像是个什么构造的题,感觉考场上敲这种题目是很不知得的。

  T3树形DP或者乱搞的题目,澜神好强大啊...

原文地址:https://www.cnblogs.com/mybing/p/8570217.html