题面

题解:

T1:

先对图进行染色，重新对联通快重新建图

根据四色定理，珂以得出这实际是一颗树

因为树的中心肯定是最佳的决策，所以答案就是树的直径/2（上取整）

#include <bits/stdc++.h>

#define N 1005

using namespace std;

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

inline int Min(register int a,register int b)

{

	return a<b?a:b;

}

inline int Max(register int a,register int b)

{

	return a>b?a:b;

}

int n,m,ma[N][N],cnt=0;

int a[]={-1,-1,-1,0,0,1,1,1},b[]={-1,0,1,-1,1,-1,0,1};

int c[N][N];

bool vis[N][N];

inline void dfs(register int x,register int y,register int col)

{

	if(x<1||y<1||x>n||y>m)

		return;

	c[x][y]=col;

	for(register int i=0;i<8;++i)

		if(ma[x][y]==ma[x+a[i]][y+b[i]]&&!c[x+a[i]][y+b[i]])

			dfs(x+a[i],y+b[i],col);

}

struct edgee{

	int to,next;

}e[(N*N)<<1];

int head[N*N],tot=0;

inline void add(register int u,register int v)

{

	e[++tot]=(edgee){v,head[u]};

	head[u]=tot;

}

struct node{

	int X,Y;

	node(int x,int y){

		X=Min(x,y);

		Y=Max(x,y);

	}

	friend bool operator<(node x,node y){

		if(x.X!=y.X){

			return x.X<y.X;

		}

		return x.Y<y.Y;

	}

};

set<node> ed;

inline void dfs2(register int x,register int y)

{

	if(x<1||y<1||x>n||y>m)

		return;

	vis[x][y]=true;

	for(register int i=0;i<8;++i)

		if(c[x][y]==c[x+a[i]][y+b[i]]&&!vis[x+a[i]][y+b[i]])

			dfs2(x+a[i],y+b[i]);

		else if(c[x][y]!=c[x+a[i]][y+b[i]]&&c[x+a[i]][y+b[i]]!=0)

			ed.insert(node(c[x][y],c[x+a[i]][y+b[i]]));

}

int maxv,maxi,dis[N*N];

inline void dfs3(register int x,register int fa){

	dis[x]=dis[fa]+1;

	for(register int i=head[x];i;i=e[i].next)

		if(e[i].to!=fa)

			dfs3(e[i].to,x);

}

int main()

{

	freopen("paint.in","r",stdin);

	freopen("paint.out","w",stdout);

	int T=read();

	while(T--)

	{

		ed.clear();

		cnt=0,tot=0;

		memset(head,0,sizeof(head));

		n=read(),m=read();

		for(register int i=1;i<=n;++i)

			for(register int j=1;j<=m;++j)

			{

				char ch=getchar();

				while(ch!='0'&&ch!='1')

					ch=getchar();

				ma[i][j]=ch=='0'?0:1;

			}

		memset(c,0,sizeof(c));

		for(register int i=1;i<=n;++i)

			for(register int j=1;j<=m;++j)

				if(!c[i][j])

					dfs(i,j,++cnt);

		memset(vis,false,sizeof(vis));

		for(register int i=1;i<=n;++i)

			for(register int j=1;j<=m;++j)

				if(!vis[i][j])

					dfs2(i,j);

		set<node>::iterator iter;

		for(iter=ed.begin();iter!=ed.end();++iter)

		{

			node ii=*iter;

			int jj=ii.X,kk=ii.Y;

			add(jj,kk),add(kk,jj);

		}

		dis[0]=-1;

		dfs3(1,0);

		maxv=maxi=0;

		for(register int i=2;i<=cnt;++i)

			if(dis[i]>maxv)

			{

				maxi=i;

				maxv=dis[i];

			}

		dfs3(maxi,0);

		maxv=0;

		for(register int i=1;i<=cnt;++i)

			if(dis[i]>maxv)

				maxv=dis[i];

		write((maxv+1)>>1),puts("");

	}

	return 0;

}

T2:

神仙题目qaq，学不会啊

官方题解：

首先，如果在某一个时刻，排在左边的人和右边的人之间还有鸽子的话，左边的人一定会先取完两人之间的鸽子。设f[i]为当最后一只鸽子上的数是i时，小X的得分，那么当n=1时，显然f[i]=i。我们从后往前考虑后k只鸽子，每次我们在最左端加入一只鸽子k时，先手的第一步决策只会有两种：

1. 走到新加入的鸽子上。那么原来的先手就变成了后手，先手的得分就是a[k]-f[i];

2. 不走到新加入的鸽子上。那么先手的决策应该和原来相同，先手的得分就是f[i]-a[k]。

因此，每当我们在最左端加入一只鸽子k时，f[i]会变为max(a[k]-f[i],f[i]-a[k])，即减去a[k]后取绝对值。因此，原问题就变成了这样一个问题：

最初你有一个一次函数f[i]=i，你会进行若干次操作，每次将函数向下平移若干单位后取绝对值，然后询问这个函数在某个点的值。

考虑第一次操作，你会将一个一次函数向下平移x格，然后取绝对值，可以发现f[i]=f[2*k-i]，也就是之后的函数关于x对称，且对称轴右边依然是一个一次函数f[i]=i-x。因此只要继续计算x及以后的位置上的函数值，x以前的函数值可以根据后面的直接算出。求出f[0]-f[∑a[i]]，大于∑a[i]的询问直接回答即可。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=200005,M=2000005;

int read(){

	int f=1,g=0;

	char ch=getchar();

	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;

	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';

	return f*g;

}

int n,m,a[N],sum,f[M*2];

void build(int l,int r,int x){

	if (!x){

		for (int i=l;i<=r;i++)

		f[i]=i-l;

		return;

	}

	int mid=l+a[x];

	build(mid,r,x-1);

	for (int i=l;i<mid;i++)

	f[i]=f[mid+mid-i];

}

int main(){

	freopen("pigeon.in","r",stdin);

	freopen("pigeon.out","w",stdout);

	n=read();

	for (int i=1;i<n;i++) {a[i]=read();sum+=a[i];}

	build(0,2*sum,n-1);

	m=read();

	while (m--){

		int x=read();

		if (x>sum) printf("%d ",x-sum);

		else printf("%d ",f[x]);

	}

	printf("\n");

	return 0;

}

T3:

考的是卡特兰数，可惜我不会通项公式

首先，设f[i]为拥有i个节点的不同形态二叉树数量，g[i]为拥有i个节点的所有不同形态二叉树的叶子节点数量和，那么答案就是要求\(\frac{g[n]}{f[n]}\) 。通过打表可以发现一个结论，g[n]=f[n-1]*n，证明如下：

1、对于每棵n个点的二叉树，如果里面有k个叶节点，那么我们分别把这k个叶子删去会得到k棵n-1个点的二叉树，也就是所有n个节点的二叉树中的每个叶子都唯一对应一棵n-1个节点的二叉树；

2、对于每棵n-1个点的二叉树，有n个位置可以接上一个新的叶子节点，所以每棵n-1个节点的二叉树都对应（所有n个节点的二叉树中的所有叶子中的）n个叶子。

因此，答案就是 \(\frac{f[n-1]*n}{f[n]}\)。其中f[n]表示的是n个节点的不同形态二叉树数量，也就是卡特兰数，其通项公式为\(\frac{C_n^{2n}}{n+1}\) ，化简得答案为\(\frac{n^2+n}{4n-2}\) 。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll p=2148473647;

ll qpow(ll x,ll k){

	ll t=1;

	for (;k;k>>=1){

		if (k&1) t=t*x%p;

		x=x*x%p;

	}

	return t;

}

ll n;

int main(){

	freopen("game.in","r",stdin);

	freopen("game.out","w",stdout);

	scanf("%lld",&n);

	printf("%lld\n",n*(n+1)/2%p*qpow((n*2-1)%p,p-2)%p);

	return 0;

}

还是太菜了啊~

T1xjb写了个以为是暴力的正解，t2博弈搜索写挂，t3卡特兰数也写挂了qaq

真是菜啊

深深地感受到自己的弱小~

最新文章

1. expense KK [ɪkˋspɛns] DJ [iksˋpens]
2. python自我输出源程序
3. perl push an array to hash
4. 讨论一下js获取响应中后台传回来的BigInteger类型的数字时，后几位会自动变为0的问题
5. libev 宏展开
6. mysql实用教程的数据构造
7. Flash Activex NPAPI PPAPI 各种网页插件完整安装包下载地址
8. C++编写Config类读取配置文件
9. windows各种程序中文显示乱码又找不到原因时
10. UITableView-FDTemplateLayoutCell自动计算UITableView高度的使用
11. EF 请求数据是缓存 求大神解释
12. html+css底部自动固定底部
13. 自动化之路 python psutil模块 收集硬件信息
14. angularjs上传图片和文件
15. VUE项目快速构建
16. wsl 子系统 用户目录位置
17. Go 环境配置
18. SAP PA Document List
19. leveldb 学习记录(二) Slice
20. 基于akka-http搭建restfull框架

热门文章

1. vue.config.js
2. JavaScript 运行机制详解
3. vim 命令补充(1)
4. Java 8 Stream API说明
5. idea实用插件
6. caffe编译报错 cudnn.hpp:127:41: error: too few arguments to function ‘cudnnStatus_t cudnnSetPooling2dDescriptor
7. Mysql数据库配置参数详解大全
8. mysql插入数据会变中文
9. java框架之MyBatis(2)-进阶&整合Spring&逆向工程
10. vs添加github代码库