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

CF510D:Fox And Jumping 题解

主要思路

欲覆盖整个直线,那么只需要让这些步数能合成一个\(1\)即可。那么根据 Bézout 定理,有\(ax + by = \gcd(a, b)\),那么我们可以用这个做 DP:不停地合成新的\(\gcd\)来找最小代价。

代码

// CF510D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 330;

int li[MAX_N], ci[MAX_N], n;
map<int, int> ump;
map<int, int>::iterator it;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &li[i]);
    for (int i = 1; i <= n; i++)
        scanf("%d", &ci[i]);
    for (int i = 1; i <= n; i++)
    {
        int tmp = ump[li[i]];
        if (tmp == 0)
            ump[li[i]] = ci[i];
        else
            ump[li[i]] = min(tmp, ci[i]);
        for (it = ump.begin(); it != ump.end(); it++)
        {
            int di = gcd(it->first, li[i]);
            tmp = ump[di];
            if (tmp == 0)
                ump[di] = it->second + ci[i];
            else
                ump[di] = min(tmp, ci[i] + it->second);
        }
    }
    printf("%d", ump[1] ? ump[1] : -1);
    return 0;
}

二项式反演

对称的反演

二项式反演的主要内容就是:

\[ f_n = \sum_{i = 0}^n (-1)^i {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^i {n \choose i} f_i \]

这个反演的式子非常的优美:在这种形式下,它们是对称的。当然,亦可以写作:

\[ f_n = \sum_{i = 0}^n {n \choose i} g_i \longleftrightarrow g_n = \sum_{i = 0}^n (-1)^{n – i} {n \choose i} f_i \]

继续阅读二项式反演

[Fortuna OJ]Aug 1st – Group A 解题报告

A – 水叮当的舞步

真的是玄妙重重。

我们先思考正常的暴力搜索:枚举每一次按下的颜色,然后检查继续更新。考虑用 IDA* 优化这个过程,首先估值函数就是剩下的颜色个数,因为至少需要更新这些颜色才有可能到达最终状态。然后注意控制 BFS 求连通块的个数的优化就行了。很好的一道题。

继续阅读[Fortuna OJ]Aug 1st – Group A 解题报告