游记 - 广州纪中游学 Day0 & Day1 | Lucky_Glass's Blog

以心为名，名为爱惜

0%

游记 - 广州纪中游学 Day0 & Day1

发表于 更新于 分类于 Valine：

本来这七天是给我们放假的，结果教练过来，“推荐”我们去参加广州纪中的培训。

一开始大家说好不去，然后 （咕咕咕），就剩了一个同学很懵逼地（“你们怎么都去了”）……

现在是在纪中了，还不能及时地更新blog，只能回家再同时发布了 TAT

<题面链接> 提取码：7puf

· Day0 - 奔波 & 休憩

乘坐飞机前往广州（似乎因为天气恶劣飞机还晚点了）。下了飞机过后就看到外面狂风大作，雨点也随着风的飘摇不定而从四面八方刮来……反正打了伞跟没打只是头发湿不湿的区别。

纪中离机场好远啊！从机场坐车竟然还要花两个多小时……

到了纪中，雨只是小了一点。第一感觉就是纪中比HF（我的初中）大多了（Tab. 这个就叫没法比），但是看到地上到处散落着树枝，还有很多地方正围起栅栏施工，很荒僻的景象。

更加荒凉的是宿舍……外观像四合院一样，看起来挺棒，但是进到宿舍，徒有四壁，连洗手台都长了青苔。也是做了好久的清洁，后来清洁没来得及做完就被同行的家长催去吃晚饭了。晚饭吃到接近九点才回宿舍，主要是因为雨开始下大了（然后另外一个原因是同学们的确饿了 QwQ）。

虽然全身淋湿了，床还特别不舒服，但是还是没怎么影响同学们的心情，当晚熄灯过后全寝室八个人开展K歌大会(HHH)，还是比较开心的一天。

· Day1 - 初试(出事)

料事如神，说第一天可能会来一个所谓的“开营考试”，然后就真的来了……一点准备都没有，基本上就是才找到教室就开始考试了。然后发现似乎每天都是 考试-讲题-补题-写blog，这样弄得我都不是特别想写游记了……

这场考试的题都是原题，在网上找得到的

(所以说好好的一篇游记就变成题解了？？？你也可以这么理解……)

- Day1T1 水叮当的舞步

= 题目

水叮当得到了一块五颜六色的格子形地毯作为生日礼物，更加特别的是，地毯上格子的颜色还能随着踩踏而改变。为了讨好她的偶像虹猫，水叮当决定在地毯上跳一支轻盈的舞来卖萌~~~

地毯上的格子有N行N列，每个格子用一个0~5之间的数字代表它的颜色。

水叮当可以随意选择一个0~5之间的颜色，然后轻轻地跳动一步，地毯左上角的格子所在的联通块里的所有格子就会变成她选择的那种颜色。这里连通定义为：两个格子有公共边，并且颜色相同。

由于水叮当是施展轻功来跳舞的，为了不消耗过多的真气，她想知道最少要多少步才能把所有格子的颜色变成一样的。

（T组询问）

数据规模：
$N\leq 8$,$T\leq 20$

= 纪 · 录

考试的时候特别懵逼，一开始想的是贪心，刚想到就构造了一组数据把自己啪啪打脸，于是放弃贪心……

接下来就看到 $N$ 很小（=_=），就想到了搜索，方向是正确的，但是我对搜索的思维太局限了，实际上搜索不只是暴力，还可以有灵活的IDA*（启发式迭代加深搜索）！

没写出正解，预估 $70$ 分，结果只得到了 $30$ 分（惨兮兮）。

= 解 · 析

刚才也提到了这是一道 IDA* 的题 —— 不过首先我们要知道怎么搜索。对于每一个格子，定义一个 tag ，若：

  • tag=1 ，表示 该格子与左上角那个格子属于一个联通块；
  • tag=2，表示该格子不属于左上角的格子的联通块，但与左上角格子的联通块相邻；
  • tag=0，即除去上述两种的情况；

每次枚举将左上角格子的联通块变成颜色 ccol；然后找到与当前左上角格子的联通块相邻（即 tag=2 ）、且颜色是 ccol 的格子，然后把该格子所在联通块与左上角格子所在联通块合并，暴力搜索一遍即可。

显然当所有格子颜色一样（注意并不是所有格子的 tag 都是 1）时，找到答案。

这就是一个不加任何优化的暴力做法，如果加了剪枝，还可以再得到一些部分分。

接下来就是 IDA 的重点，预估函数 Expect() 。对于当前状态，我们要尽可能乐观地估计还需要多少步能够得到答案（也就是至少需要多少步），虽然这是乐观估计，但是学过 IDA 的都知道预估函数的值与真实需要步数越接近越好。

但是这里我也没有什么好办法，只能非常乐观地估计——当前不在左上角格子的联通块内的颜色个数。正确性是非常显然的，但是的确很不优秀……能够跑过AC可能也是因为数据规模很小。

= 源代码

纪中的老师告诉我们，看了别人的源代码，这道题对你就没什么价值了。所以说不要直接看源代码（我的题解真的这么烂吗？）

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
73
74
75
76
77
78
79
80
81
82
83
/*Lucky_Glass*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=10;
const int DIR[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int n,expdep;
int num[N+3][N+3],tag[N+3][N+3];
/*
tag=1: 属于左上角的联通块
tag=2: 与左上角联通块相邻
tag=0: none 
*/
int Expect(){
	bool g[10]={};
	int ret=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(tag[i][j]!=1 && !g[num[i][j]])
				g[num[i][j]]=true,
				ret++;
	return ret;
}
void GetTag(int sx,int sy){
	queue< pair<int,int> > que;
	que.push(make_pair(sx,sy));
	tag[sx][sy]=1;
	while(!que.empty()){
		pair<int,int> pre=que.front();que.pop();
		for(int i=0;i<4;i++){
			int x=pre.first+DIR[i][0],y=pre.second+DIR[i][1];
			if(x<1 || x>n || y<1 || y>n || tag[x][y]) continue;
			if(num[x][y]==num[sx][sy])
				tag[x][y]=1,
				que.push(make_pair(x,y));
			else
				tag[x][y]=2;
		}
	}
}
bool ChangeTag(int ccol){
	bool okey=false;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(tag[i][j]==2 && num[i][j]==ccol){
				GetTag(i,j);
				okey=true;
			}
	return okey;
}
bool IDA(int dep){
	int expres=Expect();
	if(!expres) return true;
	if(expres+dep>expdep) return false;
	int cpytag[N+3][N+3]={};
	for(int ccol=0;ccol<6;ccol++){
		memcpy(cpytag,tag,sizeof tag);
		bool res=false;
		if(ChangeTag(ccol)) res=IDA(dep+1);
		if(res) return true;
		memcpy(tag,cpytag,sizeof cpytag);
	}
	return false;
}
int main(){
	while(~scanf("%d",&n) && n){
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				scanf("%d",&num[i][j]),
				tag[i][j]=0;
		GetTag(1,1);
		expdep=0;
		while(!IDA(0))
			expdep++;
		printf("%d\n",expdep);
	}
	return 0;
}

- Day1T2 Vani和Cl2捉迷藏

= 题目

vani和cl2在一片树林里捉迷藏……

这片树林里有 $N$ 座房子，$M$ 条有向道路，组成了一张有向无环图。
树林里的树非常茂密，足以遮挡视线，但是沿着道路望去，却是视野开阔。如果从房子A沿着路走下去能够到达B，那么在A和B里的人是能够相互望见的。

现在Cl2要在这 $N$ 座房子里选择 $K$ 座作为藏身点，同时vani也专挑Cl2作为藏身点的房子进去寻找，为了避免被vani看见，Cl2要求这 $K$ 个藏身点的任意两个之间都没有路径相连。

为了让vani更难找到自己，cl2想知道最多能选出多少个藏身点？即 $K$ 最大为多少？

数据规模：
$N\leq 200,M\leq30000$，保证输入的图是一个 DAG

= 纪 · 录

一开始的思路就和正解错开了，令人惊奇的是竟然骗了 $75$ 分（预估 $60$）。

我自己的思路是如果 $u,v$ 两点之间不存在路径（既不存在 $u$ 到 $v$ 的路径，也不存在 $v$ 到 $u$ 的路径），那么在另一张图中，我在 $u,v$ 之间连边。那么另一张图的边就表示两端点可以同时被选为藏身点。

不难想到，如果另一张图中存在一个子图是完全图，该子图里的所有点都可以同时选为藏身点。反之，如果一个子图不是完全图，则该子图中的所有点不能同时被选。

于是我构造出图后，就开始求一个最大的、是完全图的子图（之后从 tly 神犇那里才知道我的做法就是求最大团，如果图没有特殊性质，就只存在 $O(2^n)$ 的做法……QwQ）。我就是暴力搜索求的最大团，最后当然 TLE 了……

= 解 · 析

令原图为 $G_0$；新建一个图 $G$ —— 若 $G_0$ 中存在从 $u$ 到 $v$ 的一条路径，则在 $G$ 中连一条从 $u$ 到 $v$ 的有向边。我也没仔细证明，听讲题人说 $G$ 也是一个 DAG。

于是，我们就是要在 $G$ 中求最小路径覆盖（这里的转化留给 reader 们想了），记最小路径覆盖的答案为 $t$，答案即 $(n-t)$。

？？？DAG的最小路径覆盖？？？听说可以转成二分图求最大匹配（我也是才知道）。具体方法把DAG转成二分图的方法如下：

将DAG中的每一个点 $x$ 在二分图中拆成两个点，记为 $x_0,x_1$；

如果DAG中存在 $u$ 到 $v$ 的有向边，则在二分图中连 $u_0$ 到 $v_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
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200;

int n,m;
int mat[2*N+3];
bool vis[2*N+3];
bool dis[N+3][N+3];
vector<int> lnk[2*N+3];

bool DFS(int u){
	if(vis[u]) return false;
	vis[u]=true;
	for(int i=0;i<lnk[u].size();i++){
		int v=lnk[u][i];
		if(mat[v]==u) continue;
		if(!mat[v] || DFS(mat[v])){
			mat[u]=v;mat[v]=u;
			return true;
		}
	}
	return false;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		dis[u][v]=true;
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dis[i][j]|=(dis[i][k] && dis[k][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(dis[i][j])
				lnk[i].push_back(n+j);
	int maxmat=0;
	for(int i=1;i<=n;i++)
		if(!mat[i]){
			for(int j=1;j<=n;j++) vis[j]=false;
			maxmat+=DFS(i);
		}
	printf("%d\n",n-maxmat);
	return

- Day1T3 粉刷匠

= 题目

赫克托是一个魁梧的粉刷匠，而且非常喜欢思考= =

现在，神庙里有 $N$ 根排列成一直线的石柱，从 $1$ 到 $N$ 标号，长老要求用油漆将这些石柱重新粉刷一遍。赫克托有 $K$ 桶颜色各不相同的油漆，第 $i$ 桶油漆恰好可以粉刷 $T_i$ 根石柱，并且，$T_1+T_2+T_3+…+T_K=N$（即粉刷N根石柱正好用完所有的油漆）。长老为了刁难赫克托，要求相邻的石柱颜色不能相同。

喜欢思考的赫克托不仅没有立刻开始粉刷，反而开始琢磨一些奇怪的问题，比如，一共有多少种粉刷的方案？

为了让赫克托尽快开始粉刷，请你尽快告诉他答案。

= 纪 · 录

考试的时候完全没想到正解，只是隐隐约约感觉跟组合数有点关系，反正还是大暴力写完了……（awsl）

= 解 · 析

讲道理这就是一道组合数的题……外加DP（应该很容易想到会用DP吧？？）

DP状态定义比较奇特：$f[i][j]$ 表示前 $i$ 种油漆涂 $s[i]$ 根柱子，有 $j$ 对相邻的柱子颜色相同的方案数（$s[i]$ 表示前 $i$ 种油漆总共可以刷的柱子的数量，即 $s[i]=T[1]+T[2]+…+T[i]$）。

因为这个状态的定义很有意思，所以它的转移也很奇怪——考虑从 $f[i][j]$ 转移到 $f[i+1][j’]$ ：

我们换一种思路来看转移：“在原来已经涂好颜色的 $s[i]$ 根柱子之间插入 $T[i+1]$ 根颜色为 $i+1$ 的柱子”，容易证明这样的思路和题目中的意思是等价的。

考虑把 $T[i+1]$ 根柱子分成恰好 $k$ 段连续的柱子，即在原来涂了色的 $s[i]$ 根柱子之间插入 $k$ 段柱子。根据隔板法，可以知道分段的方案数为 $C_{T_{i+1}-1}^{k-1}$ ；

然后考虑把 $k$ 段柱子中的 $t$ 段放在原本颜色相同的 $j$ 对柱子之间 ，剩下的 $(k-t)$ 段柱子放在原本颜色不同的 $(s[i]+1-j)$ 对柱子之间。
从 $j$ 对颜色相同的柱子中挑出 $t$ 对的方案数为 $C_j^t$ ，从 $(s[i]+1-j)$ 对颜色不同的柱子中挑出 $(k-t)$ 对的方案数为 $C_{s[i]+1-j}^{k-t}$，则总方案数为 $C_j^tC_{s[i]+1-j}^{k-t}$ 。

根据上面的转移，我们可以发现——原来 $j$ 对颜色相同的柱子中有 $t$ 对之间插入了颜色为 $i+1$ 的柱子，所以颜色相同 的柱子会减少 $t$ 对；但是插入 $k$ 段柱子后，一定会产生 $(T[i+1]-k)$ 对新的颜色相同的柱子，所以颜色相同的柱子又会增加 $(T[i+1]-k)$ 对；
则新的颜色相同的柱子的数量 $j’$ 为 $(j-T[i+1]-k-t)$ 对。

综上，状态转移方程式为：

注意上面的 $k,t$ 都是枚举出来的。

最后答案就是 $n$ 桶油漆用完，颜色相同的柱子有 $0$ 对 —— $f[n][0]$~

预处理的话就是阶乘以及阶乘的逆元，或者直接预处理组合数也可以。

= 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=15;
const ll MOD=(ll)1e9+7;

int cas,n;
int num[N+3],sum[N+3];
ll f[N+3][6*N+3];
ll fra[100],invfra[100];

ll QPow(ll cura,ll curb){
	ll ret=1;
	while(curb){
		if(curb&1) ret=ret*cura%MOD;
		cura=cura*cura%MOD;
		curb>>=1;
	}
	return ret;
}
ll fucC(int cura,int curb){
	return fra[curb]*invfra[cura]%MOD*invfra[curb-cura]%MOD;
}
int main(){
	fra[0]=invfra[0]=1;
	for(int i=1;i<100;i++)
		fra[i]=fra[i-1]*i%MOD,
		invfra[i]=QPow(fra[i],MOD-2);
	scanf("%d",&cas);
	while(cas--){
		memset(f,0,sizeof f);
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&num[i]),
			sum[i]=sum[i-1]+num[i];
		f[1][sum[1]-1]=1;
		for(int i=1;i<n;i++)
			for(int j=0;j<sum[i];j++)
				for(int k=1;k<=num[i+1];k++)
					for(int t=0;t<=k && t<=j;t++){
						if(k-t>sum[i]+1-j) continue;
						f[i+1][j+num[i+1]-k-t]+=f[i][j]*fucC(k-1,num[i+1]-1)%MOD*fucC(t,j)%MOD*fucC(k-t,sum[i]+1-j)%MOD;
						f[i+1][j+num[i+1]-k-t]%=MOD;
					}
		printf("%lld\n",f[n][0]);
	}
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ，欢迎提问~