今天是  吉林大学信息学奥赛2017冬令营  开营第一天 好赛艇啊

Day 1 知识点：模拟、排序、贪心、递推、分治、二分答案

D1T1 净月潭探险

问题描述

学习信息学奥赛的OIER都热爱探险,小明就是其中的一个，有一天小明在净月潭公园中一条充满许多有趣路标的路上探险。这条路就像数轴一样被标记了，小明开始的时候站在原点(x = 0)处。共有n个路标中，每个路标坐落于点 x1, x2, …, xn。小明想在日落之前访问尽可能多的路标，现在距离日落还有T分钟，她每走一个单位长度，需要1分钟。
小明route照一个特殊的规则访问路标。即距离原点越近的路标，对 小明越重要，他每次总是跑到未访问过的距离原点越近的路标。没有两个路标距离原点的距离相等。
请你帮助计算一下，小明在日落之前能够访问多少个路标。

思路：

因为小明访问路标有一个特殊的规则 所以我们要将路标按照坐标绝对值从大到小排序 然后再枚举路标看是否能够走到，累加就是答案

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,t;
int a[51000];
int Absnumber(int x)
{
	return x>=0?x:-x; 
}
int cmp(int x,int y)
{
	return Absnumber(x)<Absnumber(y);
}
int ans;
int main()
{
	scanf("%d%d",&t,&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		int tmp=Absnumber(a[i]-a[i-1]);
		if(t>tmp) t-=tmp,ans++;
		else break;
	}
	printf("%d",ans);
}

 

D1T2 净月潭航线

问题描述

圆上有N个点，在这些点之间连一些不相交的弦（共同端点也算相交，即一个顶点只能连接0或1条弦，可以一条弦也不连），问共有多少种连法。

思路：

我们可以建立一个圆的内接正i边型；
当第i个顶点参与连线，任选一点a，枚举另一不同的点b，则余下的点被分为两部分，这部分方案数则为两组新的顶点方案数之积；
当其不参与连线，其他顶点间关系保持不变，这部分方案数即为F[i-1]；
将两部分方案数加和即为F[i]。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int f[2000];
int n;
int main()
{
	scanf("%d",&n);
	f[0]=1;f[1]=1;f[2]=2;
	for(int i=3;i<=n;i++)
	{
		f[i]=f[i-1];
		for(int j=0;j<=i-2;j++)
			f[i]=(f[i]+(f[i-j-2]*f[j])%12345)%12345;
	}
	printf("%d",f[n]%12345);
}

 

D1T3 排干净月潭水塘

问题描述

净月潭公园里有n个水塘，因为要做吉林省OIER们的宿营地，需要把这n个水塘中的水排干，水塘中的水在自然条件下1个单位的时间可以蒸发A升水。现在买了1台抽水机，使用抽水机可以让你用1个单位的时间使每个水塘除开自然蒸发的A升水外，还可抽B升水，但在1个单位的时间内只能对1个水塘使用。
要你求出排干所有水塘的最少时间（水塘中的水为0时为排干）。

思路：

二分答案,二分时间:对于每件衣服a[i],设需要抽水机工作x时，自然蒸干mid小时
所以我们能推出：mid*t1+t2*x=a[i]
整理得：x=(a[i]-mid*t1)/t2 (a[i]>mid*t1),向上取整
累加得出sum,如果sum>mid说明不合法 反之，则合法
然而考试时候公式推错了，-40分 QAQ

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,t1,t2;
int a[510000];
int calc(int x,int y)
{
	if(x%y==0)return x/y;
	return (x/y)+1;
}
int check(int x)
{
	int sum=x;
	for(int i=1;i<=n;i++)
	{
		if(a[i]<=x*t1) continue;
		sum-=calc((a[i]-t1*x),t2);
		if(sum<0)return 0;
	}
	return 1;
}
void find(int l,int r)
{
	int ans=0;
	int mid=(l+r)>>1;
	while(l<r)
	{
		if(check(mid))
			r=mid,ans=mid;
		else l=mid+1;
		mid=(l+r)>>1;
	}	
	printf("%d",ans);
}
int main()
{
	scanf("%d%d%d",&n,&t1,&t2);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
 	find(1,10000000);
}

Day 1总结：做T3时思路还是不够清晰，竟然漏掉了题中的关键信息，  真是太可怕了 一定要 吸取教训，之后再接再厉QAQ