[国庆集训]Day5解题报告

发表于 | 阅读次数：

题目链接

戳我n(≧▽≦)n

T1

这题其实不难。。。（日常开头）

我考试时就想出正解了（嗯考试结束前半小时想出来的），然后卧槽扫雷高级过了！！！再来一把！！！

emmm。。。

我们考虑一个对一个联通块进行操作，它实际就就是联通块的扩张，一个联通块变得更Big了

然后呢，我们可以考虑缩点，一个联通块缩成一个点

然后不同的相邻联通块连一条权值为1的边

代表可以花费1的代价使得两个联通块颜色一样

枚举第一个操作的点，则在新图中以它为起点的最长路径就是当前答案

然后对每个点进行操作，对每次的答案取最小值就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#define ID(x,y) ((x-1)*M+(y))
#define Re register int
using namespace std;

struct Edge{
	int to,next;
}e[100000];
const int dx[3]={0,1},dy[3]={1,0};
queue<int> q;
char str[75];
int cnt,head[10000],u[10000],v[10000],tot;
int N,M,map[75][75],fa[10000],c[10000],vis[10000],dis[10000],ans=0x7FFFFFFF;

inline bool Check(int x,int y) {return 1<=x&&x<=N&&1<=y&&y<=M;}
int GetF(int x) {return x==fa[x]?x:fa[x]=GetF(fa[x]);}
inline void Union(int x,int y) {fa[GetF(x)]=GetF(y);}
inline void AddEdge(int u,int v)
{
	e[++cnt]=(Edge){v,head[u]}; head[u]=cnt;
	e[++cnt]=(Edge){u,head[v]}; head[v]=cnt;
}
inline void Preprocess()
{
	for (Re i=N*M; i; --i) fa[i]=i;
	for (Re i=1; i<=N; ++i)
		for (Re j=1; j<=M; ++j)
			for (Re p=0; p<2; ++p)
			{
				int nx=i+dx[p],ny=j+dy[p];
				if (Check(nx,ny))
					if (map[i][j]==map[nx][ny]) Union(ID(i,j),ID(nx,ny));
					else u[++tot]=ID(i,j),v[tot]=ID(nx,ny);
			}
}
inline void BFS(int S)
{
	memset(dis,0x3F,sizeof(dis));
	int len=0; dis[S]=0; q.push(S);
	while (!q.empty())
	{
		int now=q.front(); q.pop(); vis[now]=1;
		for (Re i=head[now];i;i=e[i].next)
			if (dis[e[i].to]==0x3F3F3F3F)
			{
				dis[e[i].to]=dis[now]+1;
				q.push(e[i].to);
				len=max(len,dis[e[i].to]);
			}
	}
	if ((c[S])^(len%2)) ++len;
	ans=min(ans,len); return;
}
int main(int argc, char const *argv[])
{
	scanf("%d%d",&N,&M);
	for (Re i=1; i<=N; ++i)
	{
		scanf("%s",str+1);
		for (Re j=1; j<=M; ++j)
			map[i][j]=(str[j]=='B'),c[ID(i,j)]=map[i][j];
	}
	Preprocess();
	for (Re i=1; i<=tot; ++i) AddEdge(GetF(u[i]),GetF(v[i]));
	for (Re i=N*M; i; --i)
		if (fa[i]==i) BFS(i);
	printf("%d\n",ans);
	return 0;
}

T2

一个神奇的做法（我们机房一个大佬的神奇想法）自己看程序吧（意会）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <iostream>
#define Re register int

int N,K,Q,map[3005][3005],S[3005][3005],l[3005][3005],r[3005][3005],ans;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
inline int abs(int x) {return x<0?-x:x;}
inline int max(int a,int b) {return a>b?a:b;}
int main(int argc, char const *argv[])
{
	read(N),read(K),read(Q);
	for (Re i=1,x,y; i<=K; ++i)
		read(x),read(y),++map[x+N][y+N];
	for (Re i=1; i<=3*N; ++i)
		for (Re j=1; j<=3*N; ++j)
		{
			S[i][j]=S[i-1][j]+l[i-1][j-1]+r[i-1][j+1]+map[i][j];
			l[i][j]=l[i-1][j-1]+map[i][j]; r[i][j]=r[i-1][j+1]+map[i][j];
		}
	while (Q--)
	{
		int s,ans=0; read(s);
		for (Re i=1+N; i<=N+N; ++i)
			for (Re j=1+N; j<=N+N; ++j)
				ans=max(ans,S[i+s][j]-S[i-1][j-s]-S[i-1][j+s]-
					l[i-1][j-s-1]-r[i-1][j+s+1]+S[i-s-1][j]);
		printf("%d\n",ans);
	}
	return 0;
}

如果这个不懂的，看看官方题解吧。。。

对于每个询问，暴力枚举老蛤的位置， 统计答案
那么对原图斜着维护前缀和就行了
或者将曼哈顿距离转化成切比雪夫距离
统计正方形区域前缀和
注意方案二中枚举的老蛤的位置要在原图内

今天实在太困了。。。不写了

T3

我们设$f[S][T]$表示点的集合为$S$，叶子节点的集合为$T$时的数量。

然后转移方程显然。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <iostream>
#define Re register int

int N,M,K,e2[11],u[50],v[50],f[1024][1024],cnt[1024],ans;

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	var=w?-x:x;
}
inline int lowbit(int x) {return x&-x;}
int main(int argc, char const *argv[])
{
	read(N),read(M),read(K); e2[0]=1;
	for (Re i=1; i<=10; ++i) e2[i]=e2[i-1]<<1;
	for (Re i=1; i<=M; ++i)
	{
		read(u[i]),--u[i],read(v[i]),--v[i];
		f[e2[u[i]]|e2[v[i]]][e2[u[i]]|e2[v[i]]]+=2;
	}
	for (Re i=1; i<e2[N]; ++i)
	{
		int tot=0;
		for (Re x=i; x; x-=lowbit(x)) ++tot;
		cnt[i]=tot;
	}
	for (Re i=1; i<e2[N]; ++i)
		for (Re j=1; j<e2[N]; ++j)
			if (f[i][j])
			{
				f[i][j]/=cnt[j];
				for (Re p=1; p<=M; ++p)
				{ 
					int _u=u[p],_v=v[p];
					if ((i&e2[_u])&&(i&e2[_v])) continue;
					if (!(i&e2[_u])&&!(i&e2[_v])) continue;
					int New=i|e2[_u]|e2[_v],Leaf=j;
					if (!(i&e2[_u])) Leaf|=e2[_u];
					else if (j&e2[_u]) Leaf-=e2[_u];
					if (!(i&e2[_v])) Leaf|=e2[_v];
					else if (j&e2[_v]) Leaf-=e2[_v];
					f[New][Leaf]+=f[i][j];
				}
			}
	for (Re i=1; i<e2[N]; ++i) if (cnt[i]==K) ans+=f[e2[N]-1][i];
	printf("%d\n",ans); return 0;
}