Yali CSP-S 2019 模拟赛 – 算式树

思路

这道题思路很妙。

发现算子只有\(+, -, \times\),所以路径上的解可以表示成线性组合:\(ax + b\)。我们记录从根到下、从下到根的线性组合前缀,然后我们考虑来利用前缀进行分割:就是树上差分的那种套路。

我们先考虑父亲边为:

  • 加法/减法:从根向下直接加上即可,从下到根也直接加上就好,但是需要乘上之前的\(a\)。
  • 乘法:从根到下需要把\(a\)乘上,\(b\)加上乘积;但是如果是向上合并的话,就可以直接把\(a\)乘上就行:因为反向而言只对乘项有关。

大概这样合并:

void dfs(int u)
{
	dep[u] = dep[fa[0][u]] + 1;
	for (int i = head[u]; i != -1; i = edges[i].nxt)
		if (edges[i].to != fa[0][u])
		{
			fa[0][edges[i].to] = u, upweight[edges[i].to] = edges[i].weight;
			trs_up[edges[i].to] = trs_up[u], trs_down[edges[i].to] = trs_down[u];
			if (edges[i].weight == 1)
			{
				trs_down[edges[i].to].b = (trs_down[edges[i].to].b + vi[edges[i].to]) % mod;
				trs_up[edges[i].to].b = (1LL * trs_up[u].a * vi[u] + trs_up[u].b) % mod;
			}
			else if (edges[i].weight == 2)
			{
				trs_down[edges[i].to].b = (trs_down[edges[i].to].b - vi[edges[i].to] + mod) % mod;
				trs_up[edges[i].to].b = (1LL * trs_up[edges[i].to].b - 1LL * trs_up[u].a * vi[u] % mod + mod) % mod;
			}
			else
			{
				trs_down[edges[i].to].a = 1LL * trs_down[u].a * vi[edges[i].to] % mod;
				trs_down[edges[i].to].b = 1LL * trs_down[u].b * vi[edges[i].to] % mod;
				trs_up[edges[i].to].a = 1LL * trs_up[edges[i].to].a * vi[u] % mod;
			}
			dfs(edges[i].to);
		}
}

如何分裂边呢?我们只需要抵消掉\(a\)和\(b\)的效果即可,直接用逆元和减法就行了:考虑设置\(ax + b\)为从\(x\)到根的效果,设置\(cx + d\)为\(lca\)到根的效果,那么\(x\)到根的效果为\(ex + f\),可以列式为:

\[ e(cx + d) + f = ax + b \]

解出来就行了,然后再对\(y\)做差不多的处理就可以解决这道题了。(挺麻烦的,细节还挺多,不如打暴力

继续阅读Yali CSP-S 2019 模拟赛 – 算式树

「杂题集」- 2019年9月19日

方格取数

看一眼复杂度,\(O(nm)\)级别的,考虑两个循环的 DP。分析整个题面之后发现,我们穿过边界时,当且仅当另一个连通块的权值比当前的大,否则便不会为了穿过边界而损失当前金块。所以,我们做一个 DP 一样的东西:因为发现每个格子只能走一遍,那么在每一列你只能选择一直向上走和一直向下走,所以这个 DP 便没了后效性,然后再处理连通块之间的连接判断就做完了。

继续阅读「杂题集」- 2019年9月19日

P3317:[SDOI2014]重建题解

矩阵树定理的运用

正常来讲,在矩阵树中,我们其实要算的东西就是这个:

\[ \sum_T  \prod_{e \in T} p_e, \forall p_e = 1 \]

我们算的其实就是概率都为\(0/1\)的情况。现在我们要算:

\[ \sum_T \prod_{e \in T} p_e \prod_{e \notin T} (1-p_e) \]

我们可以考虑写成和式内仅与矩阵有关的式子:

\[ \sum_T \prod_{e \in T} p_e \frac{ \prod_e (1 – p_e) }{\prod_{e \in T} (1-p_e) } \]

合并积和式:

\[ \prod_e p_e \sum_T \prod_{e \in T} \frac{p_e}{1 – p_e} \]

然后我们把矩阵的内容改成\( \frac{p_e}{1 – p_e} \)就行了。

继续阅读P3317:[SDOI2014]重建题解

P1600:天天爱跑步题解

解法

翻译一下:

给你一棵带点权的树和一堆路径,问对于每一个点\(i\)有多少条路经满足\(w(s,i) = weight(i)\)。

听起来就挺毒瘤的,是吧。根据这一类树上问题的套路,考虑把所有路径拆成\((s \to LCA(s,t))\)和\((t \to LCA(s,t))\),分开处理。我们先来处理\((s \to LCA(s, t))\)这一类问题:假设我们现在要知道路径\((s \to LCA(s, t))\)对点\(i\)的贡献,必须满足:

继续阅读P1600:天天爱跑步题解

Codeforces Round #551 (Div. 2) 解题报告 (CF1153)

C – Serval and Parenthesis Sequence

这道题主要是运用贪心。首先我们可以确定以下几种情况是肯定无解的:

  • 第一个字符是 ‘)’,最后一个字符是 ‘(‘。
  • 字符串长度为奇数。

我们发现整个字符串\(s[1 \dots n]\)中,第一个和最后一个字符一定要是 ‘(‘ 和 ‘)’。所以我们只用关心\(s[2 \dots n-1]\)就好。统计需要补充的括号个数:也就是\((n-2)\)减去现已确定的括号个数,分\(remL\)为左括号需要补充的个数、\(remR\)为右括号需要补充的个数。

继续阅读Codeforces Round #551 (Div. 2) 解题报告 (CF1153)