2017 FDU-ICPC 程序设计校赛网络赛解题报告

作者:root     创建时间:2017年11月12日 21:12     最后更新:2017年11月15日 15:31

A - 数字游戏

一个很显然的做法就是枚举每一项,并统计是3的倍数的项个数即可。时间复杂度:O(Tn)。

但是这样会超时,所以我们考虑时间复杂度更优的做法。首先列举一下前几项的答案。

当n=1时答案为0,当n=2时答案为1,当n=3时答案为2,当n=4时答案为2,当n=5时答案为3,当n=6时答案为4。

可以发现:ans=(n*2)/3(向下取整)


B - Sqrt

由于数字过大导致无法用任何整型变量来存储,所以我们考虑用字符串来读入。

首先我们可以推导出:

所以当数字串的长度大于10的时候,可以直接输出 KILL la KILL,否则就把字符串转成数字,然后一个一个判断即可。或者是也可以写一个递归函数来求解。

注意用字符串转出来的数字应该用 long long 类型,然后 4294967295 是 unsigned 类型,可以用 -1u 来等价表示这个数字。


C - 大逃亡

这个题需要用到搜索的算法知识,比较考验选手的代码能力。

搜索的思路大概如下

  1. 以(0,0)为起点,并记(0,0)的到达时间为0s,然后把该点加入队列。
  2. 取出队列中的队首head,并考虑其相邻的四个点,如果其中某个相邻的点没有出界,目前还未坍塌,且还从来没有被访问过,则我们认为该点的到达时间为head点的到达时间+1s,并把该点加入队列的末尾。
  3. 将head弹出队列。
  4. 如果队列中还剩有元素,则返回步骤2,否则继续进行步骤5。
  5. 在所有的未坍塌点中找到到达时间最小的点,并输出该到达时间。如果不存在这样的点,输出-1。

注意不要想当然以为HS只能在300以内的坐标点行走,有可能得从外面绕一下路才能继续前行。


D - BubbleSort

对于每个元素x,我们记以下三个值

  1. x的初始位置,记为 pos
  2. x的最终位置,实际上也就是x本身,就记为 x
  3. 在x右边的比x小的数的个数,记为 cnt

那么对于x而言,因为会有cnt个比x小的数先从x的右边移到x的左边,所以x会先往右边移动cnt个位置。然后x最终会移动到位置x。此后x就再也不会动了。

我们来看一下x的运动轨迹:pos -> (pos + cnt) -> x,所以x的答案就是这三者的最大值减去最小值。

于是现在问题在于求在x右边的比x小的数的个数,这个我们可以用归并排序或者树状数组来求解。

标程给出的是用树状数组求解的代码,用归并排序的求解代码请等待公告更新。

Update:归并排序求解的代码已贴出


Gromah's codes

以下是这场比赛4个题目的参考程序。

// A - 数字游戏
#include <cstdio>

int Case;
unsigned int n;

int main()
{
	for (scanf("%d", &Case); Case; Case --)
	{
		scanf("%u", &n);
		printf("%u\n", n * 2 / 3);
	}
	return 0;
}
// B - Sqrt
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;

const int N = 105;
int Case, len;
char s[N];

int Solve(LL x)
{
	if (x == 1) return 0;
	else return Solve((LL) sqrt(x + 0.5)) + 1;
}

int main()
{
	while (~scanf("%s", s))
	{
		len = strlen(s);
		if (len > 10) puts("KILL la KILL");
		else
		{
			LL x = 0;
			for (int i = 0; i < len; i ++)
				x = x * 10 + s[i] - '0';
			if (x == 0)
			{
				puts("KILL la KILL");
				continue ;
			}
			int res = Solve(x);
			if (res > 5) puts("KILL la KILL");
			else printf("%d\n", res);
		}
	}
	return 0;
}
// C - 大逃亡
#include <cstdio>
#include <algorithm>
using namespace std;
#define INF 593119681

const int N = 305;
const int M = 100005;
const int Fx[5][2] = {{0, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int Case, n, m, k, Time[N][N], Dist[N][N], q[M][2];

void BFS(int sx, int sy)
{
	Dist[sx][sy] = 0;
	int l = 1, r = 1;
	for (q[1][0] = sx, q[1][1] = sy; l <= r; l ++)
	{
		int x = q[l][0], y = q[l][1];
		for (int t = 0; t < 5; t ++)
		{
			int tx = x + Fx[t][0], ty = y + Fx[t][1];
			if (tx >= 0 && tx < N && ty >= 0 && ty < N && Time[tx][ty] > Dist[x][y] + 1 && Dist[tx][ty] > Dist[x][y] + 1)
			{
				Dist[tx][ty] = Dist[x][y] + 1;
				r ++;
				q[r][0] = tx, q[r][1] = ty;
			}
		}
	}
}

int main()
{
	for (scanf("%d", &Case); Case; Case --) 
	{
		scanf("%d", &k);
		for (int i = 0; i < N; i ++)
			for (int j = 0; j < N; j ++)
				Time[i][j] = Dist[i][j] = INF;
		for (int i = 1, x, y, t; i <= k; i ++)
		{
			scanf("%d%d%d", &x, &y, &t);
			for (int j = 0; j < 5; j ++)
			{
				int tx = x + Fx[j][0], ty = y + Fx[j][1];
				if (tx >= 0 && tx < N && ty >= 0 && ty < N)
					Time[tx][ty] = min(Time[tx][ty], t);
			}
		}
		BFS(0, 0);
		int Min = INF;
		for (int i = 0; i < N; i ++)
			for (int j = 0; j < N; j ++)
				if (Time[i][j] == INF && (i || j))
					Min = min(Min, Dist[i][j]);
		if (Min == INF) puts("-1");
		else printf("%d\n", Min);
	}
	
	return 0;
}
// D - BubbleSort(树状数组版本)
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100005;
int Case, Test, n, A[N], T[N], Ans[N];

int Calc(int x)
{
	int res = 0;
	for (; x; x -= (x & -x))
		res += T[x];
	return res;
}

void Modify(int x)
{
	for (; x <= n; x += (x & -x))
		T[x] ++;
}

int main()
{
	for (scanf("%d", &Case); Case; Case --)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n; i ++)
		{
			scanf("%d", A + i);
			T[i] = 0;
		}
		for (int i = n; i; i --)
		{
			int st = i, tmp = i + Calc(A[i] - 1), dest = A[i];
			Ans[A[i]] = max(tmp, dest) - min(st, dest);
			Modify(A[i]);
		}
		printf("Case #%d: ", ++ Test);
		for (int i = 1; i <= n; i ++)
			printf("%d%c", Ans[i], i == n ? '\n' : ' ');
	}
	return 0;
}
// D - BubbleSort(归并排序版本)
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100005;
int Case, Test, n, Pos[N], Cnt[N], A[N], T[N];

void Solve(int l, int r)
{
	if (l == r) return ;
	int mid = l + r >> 1;
	Solve(l, mid);
	Solve(mid + 1, r);
	int t_a = l, t_b = mid + 1, t = l;
	while (t_a <= mid || t_b <= r)
	{
		if (t_a <= mid && (t_b > r || A[t_a] < A[t_b]))
		{
			Cnt[A[t_a]] += t_b - (mid + 1);
			T[t ++] = A[t_a ++];
		}
		else T[t ++] = A[t_b ++];
	}
	for (int i = l; i <= r; i ++)
		A[i] = T[i];
}

int main()
{
	for (scanf("%d", &Case); Case; Case --)
	{
		scanf("%d", &n);
		for (int i = 1; i <= n; i ++)
		{
			scanf("%d", A + i);
			Pos[A[i]] = i;
			Cnt[i] = 0;
		}
		Solve(1, n);
		printf("Case #%d: ", ++ Test);
		for (int i = 1; i <= n; i ++)
		{
			int ans = max(Pos[i] + Cnt[i], i) - min(Pos[i], i);
			printf("%d%c", ans, i == n ? '\n' : ' ');
		}
	}
	return 0;
}