Yali 模拟赛 #1 – 解题报告

A – 神奇的位运算

想了半天,最后一看是离线来维护,直接吐血。

首先大概能想到用本质不同的异或和与区间异或和进行异或得到答案。因为这样可以把出现次数为奇数次的给过滤掉并得到最终的答案。考虑如何得到本质不同的区间异或和,一种方式是使用主席树进行维护,另一种方式是进行离线维护。我们可以在树状数组中维护本质不同的前缀异或:我们把每个数往尽可能近的地方塞,这个时候就需要用 map 来判断要不要移动。

继续阅读Yali 模拟赛 #1 – 解题报告

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;
}