2013吉林大学信息学竞赛冬令营课程资料

2013吉林大学信息学竞赛冬令营课程资料

#include 
#include 

int n k l r mid Min i j;
int list[100005];
int left[300005] right[300005] min[300005] tag[100005];

int check（int Ans）;
void Make（int l int r int i）;
void Modi（int a int b）;
void Ask（int l int r int i）;

int main（）
{
	freopen（“btp.in“ “r“ stdin）; freopen（“btp.out“ “w“ stdout）;
	scanf（“%d %d“ &n &k）;
	l = 1 r = n;
	while （l < r）
	{
		mid = （（l + r + 1） >> 1）;
		if （check（mid） == 1）
			l = mid;
		else
			r = mid - 1;
	}
	
	check（l）;
	printf（“%d\n“ l）;
	for （i = （n >> 1）; i > 0; （i >>= 1））
	{
		for （j = i; j >= 1; j--）
			printf（“%d %d “ list[j] list[j + i]）;
		printf（“\n“）;
	}
	
	return 0;
}

int check（int Ans）
{
	int tot tot2 i Now;
	Make（1 n 1）;
	list[1] = Ans Modi（Ans n + 1）;
	for （tot = tot2 = 1; tot < n; tot = tot2）
	{
		for （i = 1; i <= tot; i++）
		{
			Now = list[i];
			Min = n + 1;
			if （Now - k > 0）
				Ask（Now - k n 1）;
			else
				Ask（1 n 1）;
			if （Min == n + 1）
				return 0;
			Modi（Min n + 1）;
			list[++tot2] = Min;
		}
	}
	
	return 1;
}

void Make（int l int r int i）
{
	int mid = （（l + r） >> 1）;
	left[i] = l right[i] = r min[i] = l;
	if （l == r）
	{
		tag[l] = i;
		return;
	}
	
	Make（l mid （i << 1））;
	Make（mid + 1 r （（i << 1） | 1））;
	return;
}

void Ask（int l int r int i）
{
	if （l > right[i] || r < left[i]）
		return;
	if （l <= left[i] && r >= right[i]）
	{
		if （min[i] < Min）
			Min = min[i];
		return;
	}
	
	Ask（l r （i << 1））;
	Ask（l r （（i << 1） | 1））;
	return;
}

void Modi（int a int b）
{
	int now = tag[a] lc rc;
	min[now] = b;
	now >>= 1;
	while （now > 0）
	{
		lc = （now << 1） rc = （lc | 1）;
		if （min[lc] < min[rc]）
			min[now] = min[lc];
		else
			min[now] = min[rc];
		now >>= 1;
	}
	
	return;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     891392  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治.ppt

     文件       1841  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\btp.cpp

     文件      11307  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\BTP职业网球赛.docx

     文件          5  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.1.in

     文件         74  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.1.out

     文件         11  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.10.in

     文件     752608  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.10.out

     文件          4  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.2.in

     文件          2  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.2.out

     文件          4  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.3.in

     文件          6  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.3.out

     文件          5  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.4.in

     文件         79  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.4.out

     文件          6  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.5.in

     文件        368  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.5.out

     文件          6  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.6.in

     文件        779  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.6.out

     文件          9  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.7.in

     文件       8039  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.7.out

     文件          8  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.8.in

     文件      36611  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.8.out

     文件         10  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.9.in

     文件     168518  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\data\btp.9.out

     文件      29696  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\BTP职业网球赛\solution.doc

     文件        244  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\地毯填补问题\blank.bat

     文件       1180  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\地毯填补问题\blank.cpp

     文件       2826  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\地毯填补问题\BLANK.PAS

     文件          6  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\地毯填补问题\BLANK0.IN

     文件        147  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\地毯填补问题\BLANK0.OUT

     文件          8  2013-03-13 13:59  2013冬令营_6341\2013冬令营\吉林冬令营2月2日-2月7日\分治2月2日\地毯填补问题\BLANK1.IN

............此处省略1840个文件信息