Codeforces 362 Div2

Posted on Edited on In

很早的一轮了，一直没写，主要是因为笨，然后还有懒。。。

仔细想想一个div2的题目，充其量够写的也就3道题，然后自己还一直补不完，我的天。。。

代码在这里

C:Lorenzo Von Matterhorn

题意是对于一个图来说，该图每一个节点i会连接到 2 * i 与2 * i + 1。然后现在有两种操作，第一种操作是给出v、u、w，表示v到u的路径上所有边的权值都加上w，第二种操作是询问v和u路径上所有边的权值之和。

这个问题就是map+暴力，不用考虑边，只考虑对于其父节点的权值相加。每次查询也是直接暴力查询。所以就是考虑如何标记点，找父节点就好了。

D:Puzzles

题意是给定一个树，根节点是1，然后从根节点开始dfs，对于每一个子节点来说，每次访问的先后概率是相等的，问最终每一个节点访问步数的期望。

其实不是很理解这个做法，看答案的那个意思是说u和v都作为子节点的话，那么u排在v前面的概率和排在v后面的概率都是0.5，所以根据这个的话就有
$$
dp[i]=\frac{num[fa[i]]-num[i]-1}{2}+dp[fa[i]]
$$

num[x]表示包括节点x在内的x所有子节点的数量。

E:PLEASE

题意是有三个杯子，一开始把东西放到了中间的杯子下面。每一轮Barney随机选两边的某个杯子，与中间的杯子交换。在第n轮之后，问这个东西还在中间的概率。

问题先到这里的话，可以假设dp[i]表示第i轮东西在中间的概率，然后有dp[1]=0,对于i>0有
$$
dp[i]=\frac{1-dp[i-1]}{2}
$$
但是不幸的是，n不会这么轻易的告诉你，n用k个ai的乘积表示的，即
$$
n=\prod_{i=1}^{k}{a_i}
$$
然后最后的结果要输出分数的形式,p/q，p和q互质，p和q本身对1e9+7取模。

接下来就是变形了，对下面的式子
$$
dp[i]=\frac{1-dp[i-1]}{2}
$$
这个式子是可以构造等比数列的，该法适用于递推式形如a(n+1)=b*a(n)+c 或者a(n+1)=b*a(n)+f(n)其中b、c为不相等的常数，f(n)为一次式

所以假设

$$
dp[i]+p=-\frac{1}{2}*(dp[i-1]+p)
$$

求解这个p，解得p=-1/3，即

$$
dp[i]-\frac{1}{3}=-\frac{1}{2}*(dp[i-1]-\frac{1}{3})
$$

剩下来就好办了，dp[n]可以求通项公式了，有

$$
dp[i]=-\frac{1}{3}*(-\frac{1}{2})^{i-1}+\frac{1}{3}
$$

考虑p和q互质，能够得到：

当n是偶数时，

$$
p=\frac{2^{n-1}+1}{3} 然后q=2^{n-1}
$$

当n是奇数时，

$$
p=\frac{2^{n-1}-1}{3} 然后q=2^{n-1}
$$

易证p和q互质，p是奇数，q是2的幂，所以一定没有大于1的公约数。

剩下的就是快速幂和费马小定理的东西了。

F:Legen…

这个题个人觉得很SXBK。。。

有n个单词，每个单词有相应的权值，然后你要组成一个长度为l的字符串，在这里面匹配到一个单词就加上相应的权值，可重叠匹配。问最终能够得到的最大值是多少。

挺裸的AC自动机+矩阵快速幂。但还是很难写。。。

多字符串模式的匹配根据我目前的水平，肯定是要往AC自动机上想。之后就把各个字符串插入到自动机中，然后构造转移矩阵。

构造矩阵之后还是不够，l特别大(1e14)，考虑如何进行dp推倒，转移方程是dp[n]=max(dp[i])+val[i][n]。

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
void mul(ma &a, ma &b)
{
	res.sz = a.sz;
	for (int i = 1; i <= res.sz; i++)
	{
		for (int j = 1; j <= res.sz; j++)
		{
			if (i == j)
			{
				res.val[i][j] = 0;
			}
			else
			{
				res.val[i][j] = -1;
			}
		}
	}

	for (int i = 1; i <= a.sz; i++)
	{
		for (int j = 1; j <= a.sz; j++)
		{
			for (int k = 1; k <= a.sz; k++)
			{
				if (a.val[i][k] == -1)continue;
				if (b.val[k][j] == -1)continue;

				res.val[i][j] = max(res.val[i][j], a.val[i][k] + b.val[k][j]);
			}
		}
	}
	for (int i = 1; i <= a.sz; i++)
	{
		for (int j = 1; j <= a.sz; j++)
		{
			a.val[i][j] = res.val[i][j];
		}
	}
}

相乘的时候是这样乘的，因为函数的空间还不足，所以数组只能在外面开。

好难啊。。。。还是觉得好难，好多地方还需要慢慢理解。。。。