其实……这篇是真咕了。

反思：

××我$T1$两个小时构造$xiebi$了（虽然我觉得如果干仨小时可能行？）

……如果$T1$用时过长的话那考试多半不行……

结果：

Miemeng

03:08:09

03:08:10

T1显然交的暴力……

题解:

T1

好题

构造一下，分分块就可以辣。

#include <iostream>

#include <cstring>

#include <cstdio>

#define N 111111

using namespace std;

int nn,un,dn;

int arr[N];

int epl[N];

void revset(int l,int r){

	for(int i=l,j=r;i<=r;i++,j--)

		arr[i]=j;

}

int main(){

	int T;

	cin>>T;

	while(T--){

		scanf("%d%d%d",&nn,&un,&dn);

		if(un*dn>=nn && un+dn<=nn+1){

			puts("Yes");

			revset(nn-dn+1,nn);

			if(un-1!=0){

				int pl=(nn-dn)/(un-1),

					pn=un-1,

					prn=nn-dn-pl*pn;

				for(int i=1;i<=pn;i++)

					epl[i]=pl;

				for(int i=1;i<=prn;i++)

					epl[i]++;

	//			for(int i=1;i<=pn;i++)\

					cout<<epl[i]<<" ";\

				cout<<endl;

				for(int i=1;i<=pn;i++)

					epl[i]=epl[i]+epl[i-1];

				for(int i=1;i<=pn;i++){

	//				cout<<epl[i-1]+1<<" "<<epl[i]<<endl;

					revset(epl[i-1]+1,epl[i]);

				}

			}

			for(int i=1;i<=nn;i++)

				printf("%d ",arr[i]);

			puts("");

		}

		else puts("No");

	}

}

T2

性质题，通过找规律证明了有一段不连续的区间并求解。

至于证明请去模大佬的博客（右方翻友链）

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdio>

#define N 111111

#define LL long long

using namespace std;

int nn;

LL arr[N],

   pre[N],

   ans;

int main(){

	scanf("%d",&nn);

	for(int i=1;i<=nn;i++)

		scanf("%lld",arr+i);

	sort(arr+1,arr+nn+1);

	for(int i=1;i<=nn;i++)

		pre[i]=pre[i-1]+arr[i];

	ans=pre[nn]-(arr[1]-1)/2;

	for(int i=2;i<=nn;i++){

		if((arr[i]-1)/2>pre[i-1])

			ans-=(arr[i]-1)/2-pre[i-1];

	}

	printf("%lld\n",ans);

}

T3

二叉树计数可得$20$

正解$dp$

将树上的位置关系转化成子树的大小关系。

（显然我是水果的……）

#include <iostream>

#include <cstring>

#include <cstdio>

#define LL long long

#define N 888

using namespace std;

const int Mod=1e9+7;

LL dp[N][N];

int pn,lin,minn[N],maxn[N];

int main(){

	int T,a,b;

	cin>>T;

	while(T--){

		memset(dp,0,sizeof dp);

		scanf("%d%d",&pn,&lin);

		for(int i=1;i<=pn;i++)

			minn[i]=0,maxn[i]=pn;

		for(int i=1;i<=lin;i++){

			scanf("%d%d",&a,&b);

			if(a<b){

//				for (int i=1; i<x; ++i) mn[i]=max(mn[i],i-x);

			    maxn[a]=min(maxn[a],b-a-1);

			}//minn[a]=max(minn[a],b-a-1);

			else   minn[b]=max(minn[b],a-b);

		}

		for(int i=1;i<=2*pn+1;i++)

			dp[i][0]=1;

		for(int i=pn;i>=1;i--){

			for(int j=1;j<=pn;j++){

				for(int k=minn[i];k<=min(maxn[i],j);k++){

					if(j-1-k<0)break;

					dp[i][j]=(dp[i][j]+dp[i+1][k]*dp[i+1+k][j-1-k]%Mod)%Mod;

				}

			}

		}

		printf("%lld\n",dp[1][pn]);

	}

}

巴特西

19-10-16-R

反思：

结果：

题解:

T1

T2

T3

最新文章

热门文章