Codeforces 362 Div2

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

仔细想想一个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];
}
}
}

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

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