最近文章

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 模拟赛 – 算式树

牛客CSP-S提高组赛前集训营 2 – 解题报告

这次比赛必须要仔细反省,不能再出现暑假的精神状态。

A – 服务器需求

假设我们有很多服务器了,我们现在按天考虑,进行服务器的分配:假设有一个服务器编号集合\(\{id_i\}\),考虑一天天分配若干台,这样就可以保证每一台服务器的分配中不会出现同样的日期。

这样就可以分配完了,直接就有\(\sum a_i \leq |id_i| m\)。然后就是傻逼代码了。

继续阅读牛客CSP-S提高组赛前集训营 2 – 解题报告

[CEOI2011]Traffic 题解

主要思路

我们发现这其实就是一个多源覆盖问题。注意到「保证边在交点以外的任何地方不相交」,大概画个图就可以知道这样我们所覆盖的是一个区间(这有点像某年的一道跟种田有关的题目)。

如果没有这个性质,那么我们只能用 bitset 来维护所能到的点集,在缩完点上的 DAG 做需要\(\Theta(\frac{n^2}{32})\)的时间。然而,有了这个性质之后我们可以直接记录上下端点,相减得到答案。

继续阅读[CEOI2011]Traffic 题解

P4320:道路相遇题解

做法

我们发现,其实这道题就是要求询问无向图上点对之间的割点数量:可以确定割点的数量是唯一的,因为如果有更多的割点,那么不存在更少的割点使点双连通分量连通。

既然我们知道了大概的题意和要求,那么我们可以发现:如果把这些割点所在域内的非割点全部缩成一个点,然后让割点分别连接,那么根据「不存在更少的割点使点双连通分量连通」的「唯一性」,可以知道这样建出来的东西一定是一棵树。

这样就很好做了!直接树上差分+LCA即可。我们需要用 Tarjan 把这些点缩起来,通过割点进行连接,然后做一遍 DFS 之类的获取前缀和,再处理 LCA 倍增数组,我们就可以在线回答询问了。算法的复杂度为\(\Theta(n \log n + m \log n)\)。

继续阅读P4320:道路相遇题解