我我我我更完了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-$偶数。
详细的看代码….

分类: 所有

发表评论

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

你是机器人吗? =。= *