2017吉大冬令营Day3


(博客补更到)第三天了……开心~


D3 搜索与剪枝、记忆化搜索

Day 3讲的是搜索......搜索整体上我还是比较擅长的……可是没想到下午考的却是暴力与骗分……真是尴尬#滑稽

JLU WinterCamp 2017 D3

全局信息

 

题目名 文件名 时间限制 内存限制
矩阵乘法 matrix.cpp/in/out 1s 256M
交朋友 friend.cpp/in/out 1s 256M
物以类聚 kind.cpp/in/out 1s 256M

总得分:160’/300’


T1 骗分::离散化

maya这句话看起来比较诡异……但是T1的的确确是骗分骗满的……

后来也和博学多才的可爱学姐确认了一下,这道题使用骗分技巧中的离散化技巧即可得到AC分数。


T2 DFS

题目大意:求n个人两两配对的所有方案。(为了防止输出超时仅输出最大权值)

啊呀看到这道题顿时感觉十分亲切……T2是师大学长讲过的原题,而且还是喜闻乐见的DFS~于是就十分开心的码~

考试开始第一个写的就是这道题~欢快地码完了一个生成全排列的优化Version(每一对必须是序号小的在前面,序号大的在后面)但是发现了一个问题:

序列

1 2 3 4 5 6 7 8
1 2 3 4 7 8 5 6
1 2 5 6 7 8 3 4
1 2 5 6 3 4 7 8
1 2 7 8 3 4 5 6
1 2 7 8 5 6 3 4
3 4 5 6 7 8 1 2
5 6 7 8 1 2 3 4
7 8 1 2 3 4 5 6
......
......

这是<1 2><3 4><5 6><7 8>  所产生的可能序列。

这样就会导致一点:虽然我们进行了先小后大的特殊优化处理,但是仍然会出现很多的重复组合,于是便会出现各种TLE的情况……

所以我们可以换一种方法进行DFS。我们取代直接生成全排列(或者类似全排列)的做法,转而直接“找朋友”:我们直接在DFS函数里面对Target位置的数“找朋友”——从Target+1向后搜,只要搜到了一个没有被标记的位置就开始从头向后走(不然的话那前面的就搞定不了了,无法出解),找到第一个没有被标记的(只要交朋友了就要标记上)然后就开始递归DFS,在递归之后不能继续循环找了!!!这一点十分重要也正是通过这种方式防止TLE。

于是AC。

看来我果然是DFS小王子啊哇哈哈哈哈哈#捂脸

//JLU WinterCamp 2017
//D3T2 by Tony Zhao.

#include <cstdio>
#include <algorithm>

int n,t[20][20],ans=0x7fffffff,tmp[20];
bool use[20];

void calc()
{
	int res=0;
	for(int i=1;i<=n;i++) res+=t[i][tmp[i]];
	res=res>>1;
	ans=std::min(ans,res);
	return;
}

void dfs(int target,int finish)
{
	if(finish==n-2)
	{
		for(int i=target+1;i<=n;++i)
		{
			if(!use[i])
			{
				tmp[i]=target;
				tmp[target]=i;
				break;
			}
		}
		calc();
		return;
	}
	for(int i=target+1;i<=n;++i)
	{
		if(!use[i])
		{
			use[i]=true;
			tmp[i]=target;
			tmp[target]=i;
			for(int j=target+1;j<=n;++j)
				if(!use[j])
				{
					use[j]=true;
					dfs(j,finish+2);
					use[j]=false;
					break;
				}
			use[i]=false;
		}
	}
	return;
}

int main()
{
	freopen("friend.in","r",stdin);
	freopen("friend.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j) scanf("%d",&t[i][j]);
	use[1]=true;
	dfs(1,0);
	use[1]=false;
	printf("%d",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T3 喵喵喵???

声明:TonyZhao's Home|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 2017吉大冬令营Day3


不骗了,不骗了。
A Simple OIer fighting tooth and nail.