Google Code Jam Round 1A 2008

Posted on Edited on In

题目链接与代码链接

一开始只是特别想记一下C题，后来发现B题也不错。。。

A Minimum Scalar Product

题意是给出了两个$n$维的向量，你可以对这$n$个向量的坐标任意排序，使得他们之间的scalar product(点积$x_1y_1+x_2y_2+…+x_ny_n$)最小。问这个最小点积。

一个正向排序，一个逆向排序。

B Milkshakes

题意是给出了$n$种物品，每种物品可0可1。$m$种顾客，每一个顾客有$T$个要求，每个要求”$X Y$”代表第$X$个物品是$Y$($Y$是0或者1)，其中$Y=1$每个顾客至多一种。要求对每一个顾客至少满足他的一个要求，满足所有顾客的情况下，0的数量最少。如果不可能，输出”IMPOSSIBLE”。

对每一个为0的物品和顾客一个一个检查，如果对一个顾客有一个满足条件的即跳出循环。有为1要求的记录下来，下一次将其改为1。如果都是1，而顾客要求为0导致的都不满足要求的情况，那就直接输出”IMPOSSIBLE”。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
void solve()
{
	memset(state, 0, sizeof(state));
	memset(num, 0, sizeof(num));
	memset(chan, 0, sizeof(chan));

	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		scanf("%d", &num[i]);
		for (int j = 1; j <= num[i]; j++)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			chan[i][j][0] = u;
			chan[i][j][1] = v;
		}
	}
	int fini = 0;
	int imp = 0;
	while (!fini)
	{
		fini = 1;
		for (int i = 1; i <= m; i++)
		{
			int k = -1;
			int j = 1;
			for (j = 1; j <= num[i]; j++)
			{
				if (state[chan[i][j][0]] == chan[i][j][1])
				{
					break;
				}
				if (chan[i][j][1] == 1)
				{
					k = j;
				}
			}
			if (j > num[i])
			{
				if (k == -1)
				{
					fini = 1;
					imp = 1;
					break;
				}
				fini = 0;
				state[chan[i][k][0]] = 1;
			}
		}
	}
	if (imp)
	{
		puts("IMPOSSIBLE");
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (i > 1)
		{
			printf(" ");
		}
		printf("%d", state[i]);
	}
	printf("\n");
}

C Numbers

题意很简单，求$(3+\sqrt{5})^n$的最后三个整数部分的值。

这个是一个很经典的问题了，特意来记录一下。

设$a=3+\sqrt{5}$，$b=3-\sqrt{5}$，$x_n=a^n+b^n$。

会发现得到的$x_n$是一个整数，另外由于$b_n<1$，所以得到的$x_n$是大于结果的第一个整数。所以现在考虑求这个$x_n$。

然后对于$x^{n+1}$来说，有$(3+\sqrt{5})(a_n+b_n*\sqrt{5})=(3a_n+5b_n)+(3b_n+a_n)*\sqrt{5}$，那么可以得到$a_{n+1}=3a_n+5b_n$，$b_{n+1}=3b_n+a_n$。

这样可以化成矩阵的形式：
$$
\begin{pmatrix}
a_{n} \
b_{n+1}
\end{pmatrix}=A\begin{pmatrix}
a_{n-1} \
b_{n-1}
\end{pmatrix}=A_{n}\begin{pmatrix}
a_{0} \
b_{0}
\end{pmatrix}
$$
其中
$$
A=\begin{pmatrix}
3&5 \
1&3
\end{pmatrix}
$$
因为$a_0=1$,可以得到$(a_0,b_0)=(1,0)$

太困了。。。明天接着填。。。。

这样就可以矩阵快速幂啦~