2017吉大冬令营Day1


十分赛艇的2017吉大冬令营就这样开营了QwQ

吉大日新楼(食堂)的吃的真多真好(逃


D1 模拟、动归、二分

D1讲的都是一些十分基础(简单)的算法……于是今天的比赛题也十分简单QwQ

JLU WinterCamp 2017 D1

全局信息

 

题目名 文件名 时间限制 内存限制
净月潭探险 explore.cpp/in/out 1s 256M
净月潭航线 route.cpp/in/out 1s 256M
排干净月潭水塘 dry.cpp/in/out 1s 256M

总得分:300’/300’

AK!


T1 模拟

T1真心没难度……

题目大意:主人公在数轴的原点0处,给你n个坐标,让你按照各个点坐标距原点的距离的绝对值进行排序,你一共可以走t个长度,问你最多能经过几个点。

样例

Input Output
10 -3 8 -7 1 4

D1T1就是大水题……直接模拟就好了经典的结构体排序QwQ然后就直接开始模拟就好了

AC.

附代码:

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

#include <cstdio>
#include <algorithm>

int t,n,x[51000],ans,dis;

int absolute(int target)
{
	return target>0?target:-target;
}

bool cmp(int x,int y)
{
	return absolute(x)<absolute(y);
}

int main()
{
	freopen("explore.in","r",stdin);
	freopen("explore.out","w",stdout);
	scanf("%d%d",&t,&n);
	for(int i=1;i<=n;++i) scanf("%d",&x[i]);
	std::sort(x+1,x+n+1,cmp);
	for(ans=1;ans<=n;++ans)
	{
		dis+=absolute(x[ans]-x[ans-1]);
		if(dis>=t)
		{
			dis-=absolute(x[ans]-x[ans-1]);
			break;
		}
	}
	ans--;
	printf("%d",ans);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T2 递推

题目大意:在一个环上有x个点,现构建一些边将这些点连接在一起,要求这些边不能重叠不能交叉(两条边的端点是同一个也判断为有交叉),问共有多少种构造方案。

这道题难度比较大……可能是这三道题里面最大的……但是这道题实际上老师上午是讲过的……(帅帅的学长#滑稽)

直接使用递推,f[i]表示前i个点所能构成图形的个数。

求f[i]我们可以用这样的方法:第i个点有两种选择:第一种就是这个点不与任何点相连,此时可能出现的总方案个数为f[i-1]。第二种就是这个点i与前i-1个点有连线。这条连线将会将整个图形分成两部分:设i与j相连,一部分是前j-1个点,另一部分是j+1~i-1构成的图形。

这两个图形不能交叉,所以它们是独立的,所以它们的个数和是f[j-1]+f[i-j-1]

于是我们可以得到f[i]=f[i-1]+(Σ(j∈ [1,i) ) f[j-1]+f[i-j-1])

进行递推,f[x]即为所求。

AC.

附代码:

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

#include <cstdio>

int n,f[1010];

int main()
{
	freopen("route.in","r",stdin);
	freopen("route.out","w",stdout);
	scanf("%d",&n);
	f[0]=1;
	f[1]=1;
	for(int i=2;i<=n;++i)
	{
		for(int j=1;j<i;++j) f[i]=(f[i]+(f[j-1]*f[i-j-1]))%12345;
		f[i]=(f[i]+f[i-1])%12345;
	}
	printf("%d",f[n]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

T3:二分答案

题目大意:共有n个湖,每个湖中有a[i]单位的水,你有一个每单位时间可以抽出b单位水的抽水泵,每分钟每个湖可以自然蒸发a单位水,在抽水时仍然会自然蒸发。求最少需要多少单位时间才能使所有湖中的所有水完全蒸发。

这道题一看就知道是二分答案……这道题就是POJ Drying的只是变换题目描述的题……

那么就开始写呗:使用二分答案,每次二分出来的答案都进行check()看看符不符合要求(即能否在此时间内抽干所有湖里的所有水),之后根据返回值维护答案,最终结果即为所求。

本题需要注意的是关于check()里面求所需时间的时候一不能出现负数(出现负数不能直接计算),二必须要使用ceil()函数进行向上取整,这同时又需要我们强制转换int 为double……需要经过一段调试才能确保正常哇QwQ

AC.

附代码:

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

#include <cstdio>
#include <cmath>

int n,a,b,w[500100];

bool check(int target)
{
	int res=0;
	for(int i=1;i<=n;++i)
	{
		int tmp=w[i]-a*target;
		if(tmp>0) res+=ceil(tmp*1.0/b);
		if(res>target) return false;
	}
	return true;
}

int bifind()
{
	int l=0,r=500000,mid;
	while(l<r)
	{
		mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	return l;
}

int main()
{
	freopen("dry.in","r",stdin);
	freopen("dry.out","w",stdout);
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;++i) scanf("%d",&w[i]);
	printf("%d",bifind());
	fclose(stdin);
	fclose(stdout);
	return 0;
}

写在最后

D1就这样AK了……我很开心#滑稽

不过D2D3似乎就没有好运气了?#翻白眼

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

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


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