我我我我更完了 QAQ

链上二次求和

有一条长度为 $n$的链($1\leq i<n$,点 $i$与点 $i+1$之间有一条边的无向图),每个点有一个整数权值,第 $i$个点的权值是 $a_i$。现在有 $m$个操作,每个操作如下:
操作 $1$(修改):给定链上两个节点 $u,v$和一个整数 $d$,表示将链上 $u$到 $v$唯一的简单路径上每个点权值都加上 $d$。
操作 $2$(询问):给定两个正整数 $L,r$,表示求链上所有节点个数大于等于 $L$且小于等于 $r$的简单路径节点权值和之和。
由于答案很大,只用输出对质数 $1000000007$取模的结果即可。
一条节点个数为 $k$的简单路径节点权值和为这条上所有 $k$个节点(包括端点)的权值之和,而本题中要求是对所有满足要求的简单路径,求这一权值和的和。
由于是无向图,路径也是无向的,即点 $1$到点 $2$的路径与点 $2$到点 $1$的路径是同一条,不要重复计算。


题目不是把题解告诉你了吗……
$S_k$表示 $k$阶前缀和,则:

\begin{eqnarray}
Ans &= &\sum_{i=L}^R \sum_{j = i} ^ N S_1[j] – S_1[j – i]\\
&= &\sum_{i=L}^R (\sum_{j=i}^N S_1[j] – \sum_{j=0}^{N-i} S_1[j])\\
&= &\sum_{i=L}^R (S_2[N] – S_2[i-1] – S_2[N – i])\\
&= &(R + L – 1) * S_2[N] – \sum_{i=L-1}^{R-1}S_2[i] – \sum_{i=N-R}^{N-L} S_2[N-i]
\end{eqnarray}

考虑修改:
对于 $L \leq i \leq R$,$add = \frac{(i-L+1)*(i-L+2)}{2} * v$;
对于 $R < i \leq N$,$add = \frac{(R-L+1) * (R-L+2)}{2} * v + (i-R)*(R-L+1) * v$
明明就不卡常~\(≧▽≦)/~成功 rank7


治疗之雨

你现在有 $m+1$个数:第一个为 $p$,最小值为 $0$,最大值为 $n$;剩下 $m$个都是无穷,没有最小值或最大值。
你可以进行任意多轮操作,每轮操作如下:
在不为最大值的数中等概率随机选择一个(如果没有则不操作),把它加一;
进行 $k$次这个步骤:在不为最小值的数中等概率随机选择一个(如果没有则不操作),把它减一。
现在问期望进行多少轮操作以后第一个数会变为最小值 $0$。


首先要看仔细题目。
用 $f[i]$表示 $k$次攻击中恰好 $i$次击中英雄的概率,$f[i] = C_k^i * (\frac{1}{m+1})^i * (\frac{m}{m+1})^{k-i}$。
$a[i][j]$表示一次从 $i$滴血掉到 $j$滴血的概率,则

\begin{eqnarray}
a[i][j] =
\begin{cases}
\frac{m}{m+1} * f[i – j] + \frac{1}{m+1} * f[i + 1 – j] &\mbox{j <= i}\\
\\
\frac{1}{m+1} * f[0] &\mbox{j == i + 1}
\end{cases}
\end{eqnarray}

然后 $x[i]$表示 $i$滴血时的期望,则:

\begin{eqnarray}
x[0] &= &0\\
x[1] &= &a[1][1] * x[1] + a[1][2] * x[2] + 1\\
x[2] &= &a[2][1] * x[1] + a[2][2] * x[2] + a[2][3] * x[3] + 1\\
x[3] &= &a[3][1] * x[1] + a[3][2] * x[2] + a[3][3] * x[3] + a[3][4] * x[4] + 1\\
&\vdots \\
x[n] &= &a[n][1] * x[1] + a[n][2] * x[2] + a[n][3] * x[3] + \cdots + a[n][n] * x[n] + 1\\
\end{eqnarray}

可以看出这是一个 $n$元的方程,并且 $a$自动构成了一个下三角,所以可以 $n^2$解出来。注意由于 $n$不能变成 $n+1$,所以 $a[n]$要特别计算。即 $a[n][i] = f[n – i]$。
为什么又是 rank7(╯‵□′)╯︵┻━┻


求和

$master$对树上的求和非常感兴趣。他生成了一棵有根树,并且希望多次询问这棵树上一段路径上所有节点深度的 $k$次方和,而且每次的 $k$可能是不同的。此处节点深度的定义是这个节点到根的路径上的边数。他把这个问题交给了 $pupil$,但 $pupil$并不会这么复杂的操作,你能帮他解决吗?


大概是只有 $HNOI2018D2T3$能与之相提并论。
路径是 $1\sim 2$条链构成的,一条链上的深度是单调的,而且 $1\leq K \leq 50$,所以我们维护一下 $1\sim 50$次方的前缀和就好了。
成功 Rank21 而且 register 居然还慢了 (MMP.jpg)


二进制

$pupil$发现对于一个十进制数,无论怎么将其的数字重新排列,均不影响其是不是 $3$的倍数。他想研究对于二进制,是否也有类似的性质。于是他生成了一个长为 $n$的二进制串,希望你对于这个二进制串的一个子区间,能求出其有多少位置不同的连续子串,满足在重新排列后(可包含前导 $0$) 是一个 $3$的倍数。两个位置不同的子区间指开始位置不同或结束位置不同。由于他想尝试尽量多的情况,他有时会修改串中的一个位置,并且会进行多次询问。


经历了看错题 $\rightarrow Naive \rightarrow$看对题 $\rightarrow Naive \rightarrow$终于不 $Naive$但还是很 $Simple$的曲折过程。
首先需要自己推出一个傻逼的结论。然后维护非法的子区间个数,用总数减去它。一共只有两种是违法的:
1. 只出现了一次 $1$。
2, 出现了奇数个 $1$并且 $0$的出现数量少于 $2$。
然后就是冗长的 $update$了。


染色

$pupil$喜欢给图的顶点染颜色。有一天,$master$想刁难他,于是给了他一个无重边和自环的无向图,并且对每个点分别给了一个大小为 2 的颜色集合,$pupil$只能从这个集合中选一种颜色给这个点染色。$master$希望 $pupil$的染色方案使得没有两个有边相连的点被染了相同的颜色。现在 $pupil$想知道,是否无论 $master$的颜色集合是什么,他均有办法按照要求染色。


结论细节题。
首先奇环不行;度数为 $1$的节点可以直接忽略;偶环只有一个交点不行;偶环中出现了度数 $> 3$的不行;偶环的交中度数为 $3$的两个点的三条路径需要为 $2-2-$偶数。
详细的看代码….

分类: 文章

发表评论

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