[Fortuna OJ]Jul 5th – Group B 解题报告

A – 铁轨

sb 题,不讲。(为什么 B 组会有这么水的题?)

B – 独立集

这道题翻译过来就是独立集计数,也是一道 sb 题。

首先,这种计数题肯定都是基于树形 DP 的,所以我们来设状态。起初,我设的状态是:该节点所在的子树的独立集个数为 \(dp[u]\)。后面发现不太对劲:状态转移时,大体可以分为两种进行计数,一种是儿子子树内的乘积(包括空集在内,这样就可以算所有的并集个数),还有一种是孙子子树和本节点的独立集。所以,这些信息要分开储存:设\(dp[u][1]\)为独立集个数,\(dp[u][0]\)孙子节点的独立集个数。所以,可以得到下列方程:

\[ dp[u][0] = 1, dp[u][1] = 2, deg[u] = 1 \text{且} u \text{不是根节点} \\ \begin{cases} dp[u][0] = \prod_{v \in son(u)} dp[v][1] – dp[v][0] \\ dp[u][1] = dp[u][0] + \prod_{v \in son(u)} dp[v][1] \end{cases} \]

记得判定根节点的度数时要特殊处理(考场上因此丢掉 70 分)。

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100100, mod = 10081;

int head[MAX_N], current, dp[MAX_N][2], deg[MAX_N], n;

struct edge
{
	int to, nxt;
} edges[MAX_N<<1];

void addpath(int src, int dst)
{
	edges[current].to = dst, edges[current].nxt = head[src];
	head[src] = current++;
}

void dfs(int u, int fa)
{
	if(deg[u] == 1)
	{
		dp[u][0] = 1, dp[u][1] = 2;
		return;
	}
	int tmp_A = 1, tmp_B = 1;
	for(int i = head[u];i!=-1;i=edges[i].nxt)
		if(edges[i].to != fa)
		{
			dfs(edges[i].to, u);
			tmp_A = tmp_A * dp[edges[i].to][1] % mod, tmp_B = tmp_B * (dp[edges[i].to][1] - dp[edges[i].to][0] + mod) % mod;
		}
	dp[u][0] = tmp_B % mod;
	dp[u][1] = (tmp_A + tmp_B) % mod;
}

int main()
{
	memset(head, -1, sizeof(head));
	scanf("%d", &n);
	for(int i = 1, tmpx, tmpy; i <= n - 1; i++)
		scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx), deg[tmpx]++, deg[tmpy]++;
	int rt = 1;
	deg[rt]++;
	dfs(rt, 0);
	printf("%d", dp[rt][1]);
	return 0;
}

C – 石子游戏

真 tm 毒瘤。

这道题很明显是博弈论。首先将目光瞄准\(k=1\)的情况,打表可知形如\(n = 2^x\)的是先手必败局势,下面是解释:

在\(k=1\)的情况下,我们把\(n\)拆解成二进制的数。在游戏一开始,先手就要决定整个游戏的上界,且之后的操作序列肯定是不升的。考虑从二进制数中拿走一些 1 ,然后会发现,在 2 的幂的情况下,每次拿走一部分,都会留下至少一个 1 给对手,这样的话对手就可以在最后一轮赢下整场游戏。

考虑\(k = 2\)的情况,根据某个定理,任意一个正整数都可以被分解成几个 Fibonacci 数,然后发现任意两个不相邻的 Fibonacci 数之间的比例总是大于\(k = 2\),所以依照这个思路,如果\(n\)为 Fibonacci 数的话,那么就是必败的(由连续的 Fibonacci 数组成),解释如下:

对于\(n\)不为 Fibonacci 数的情况,\(n\)总是可以分解成不连续的 Fibonacci 数列之子序列的和,这样的话,在不连续的地方,倍数总是大于\(k=2\),所以我们就可以在这里制造最后一次的取石子的动作,这样就可以完成必胜序列;而对于\(n\)为 Fibonacci 数的情况,每一个 Fibonacci 数都可以被重新分解,所以连续的情况下,对手取走两倍之内的石子数简直就是易如反掌!这样就是必败局势。

考虑泛情况,我们也可以构造一个数列,类似于 Fibonacci 数列。要构造一个这样的\( \{ a_i \} \),我们可以开一个辅助序列\( \{ b_i \} \),表示前\(i\)个中,合法(求和顺序要符合取石子的顺序)加起来的最大数字。这样的话,考虑下一个\(a_{i+1}\)时就可以直接从\(b_i\)处转移即可,然后合法取数多加一个指针指向上一个满足\(ka_{cursor} < a_i\)的就行了。

// C.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 2000000;

int ai[MAX_N], bi[MAX_N], T, n, k;

int main()
{
	scanf("%d", &T);
	for (int cas = 1; cas <= T; cas++)
	{
		scanf("%d%d", &n, &k);
		int i = 0, j = 0;
		ai[0] = bi[0] = 1;
		while (ai[i] < n)
		{
			i++;
			ai[i] = bi[i-1]+1;
			while(ai[j + 1] * k < ai[i])
				j++;
			if(ai[j]* k < ai[i])
				bi[i] = bi[j] + ai[i];
			else
				bi[i] = ai[i];
		}
		printf("Case %d: ", cas);
		if (ai[i] == n)
			printf("lose\n");
		else
		{
			int ans = 0;
			while (n != 0)
			{
				if(n >= ai[i])
					n -= ai[i], ans = ai[i];
				i--;
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

 

发布者

Kal0rona

江西师大附中全机房最弱

《[Fortuna OJ]Jul 5th – Group B 解题报告》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注