看心情填坑

就写了四题

前面两题没啥好讲的。

F The Pool for Lucky Ones

定义unlucky pool指没有pool中人比它更多的pool，在unlucky pool中的人会不开心，现在给你初始每个pool中的人数，你有一次机会（可以不用）把一个pool中的一个人转移到它相邻的一个pool里（首尾不相邻），求最小不开心人数

大特判题，判的要死了。显然假如我们不操作的话最终答案就是max*s,我们有两种办法使得答案变优，第一种是把一组max中的人往旁边挪一个，答案为max*(s-1)，假如s=1，而且不存在a_i=max-1那么显然我们这么操作假如有效的话答案是max-1，第二种是当s>1时，我们可以通过让一个max变大，使得答案从max*s变成max+1。反正特判多的我要吐了。

#include<cstdio>
using namespace std;
int max,s,n;
int a[100005];
long long sum;
inline long long min(long long x,long long y){return x<y?x:y;}
int main(){
	scanf("%d",&n);
	max=-1;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(max==a[i])s++;
		if(max<a[i]){
			max=a[i];
			s=1;
		}
	}
	bool b=false,B=false;
	for(int i=2;i<=n;i++)if(((a[i]==max)&&(a[i-1]<max-1))||((a[i-1]==max)&&(a[i]<max-1)))b=true;
	for(int i=1;i<=n;i++)if(a[i]==max-1)B=true;
	if(s==1){
		bool f=false;
		for(int i=1;i<=n;i++)if(a[i]==max){
			if(i>1)if(a[i-1]<max-2)f=true;
			if(i<n)if(a[i+1]<max-2)f=true;
		}
		if(B)printf("%d",max);
		else if(f)printf("%d",max-1);
		else printf("%d",max);
	}else{
		bool f=false;
		for(int i=2;i<=n;i++)if(((a[i]==max)&&(a[i-1]>0))||((a[i-1]==max)&&(a[i]>0)))f=true;
		if(f){
			f=false;
			for(int i=2;i<=n;i++)if(((a[i]==max)&&(a[i-1]>0))||((a[i-1]==max)&&(a[i]>0)))f=true;
		}
		if(f)if(b){
			if(s==2)printf("%I64d",1LL*(s-1)*max);
			else printf("%d",max+1);
		}else printf("%d",max+1);
		else if(b)printf("%I64d",1LL*(s-1)*max);
		else printf("%I64d",1LL*max*s);
	}
}

K Microcircuits

现在在圆上有依次n个互不相同的点，我们要在它们之间连若干条线，使得线与线不相交而且没有公共顶点，求方案数。

一开始往polya定理想的我还是太年轻，摆渡了一下然后发现是卡特兰数裸题。。。。

#include<cstdio>
using namespace std;
long long ca[45];
int n,m;
long long c(int x,int y){
	if(x-y>y)y=x-y;
	long double ans=1;
	for(int i=y+1;i<=x;i++)ans*=i,ans/=i-y;
	return (long long)ans;
}
int main(){
	scanf("%d%d",&n,&m);
	if(m*2>n){
		printf("0");
		return 0;
	}
	ca[0]=1;
	for(int i=1;i<=m;i++)ca[i]=ca[i-1]*(4*i-2)/(i+1);
	printf("%I64d",c(n,m*2)*ca[m]);
}

B lunch

现在你是一只蛤，有两种移动方式：1、跳1格2、跳2格。从左到右有N片荷叶，现在你要从S点出发，到达T点结束，每片都要经过且只经过1次，求最少要使用移动方式1几次。

显然起始点和终点可以交换所以我们可以强制S≤T，然后最优方案显然是从S开始一直2格2格向左跳，然后跳回来一直跳到N为止，然后再跳回来直到跳到T。

手撸了几个发现细节好多，然后就想看代码。

然后就深深的意识到了自己的TOO YOUNG TOO SIMPLE

然后我就生气地不打了来表达我的生气MGJ人NAIVE有什么办法

填坑去了