2022“杭电杯” 中国大学生算法设计超级联赛（8）5 7题解

1005-Ironforge

题目大意：
一条直线上有若干个点，每个点都有一个数字，经过一个点后，背包里就会获得这个点上数字的所有质因子。两个相邻的点之间有一条路线，路线有一个质数，只有背包里有路线上的质数时才能通过。每个点可以经过无数次，有若干次询问，每次给定一个起点和终点，问能否到达。（数字的范围是[1,200000]）

思路：
如果能预处理每个点所能到达的最大边界，即可O(1)处理每个询问。
那么从左往右进行预处理每个点。
每次判断向左或向右能否进行扩展。
如果能到达左侧的那个点，就将左侧范围更新为左侧那个点的范围，右侧范围取二者的最大值。
对于右侧的点同样处理。
如果一轮中向左和向右都无法扩展，说明已经到达最大边界了，停止扩展，进行下一个点的预处理。
理论上这种扩展的方法的均摊复杂度是O(1)的。
但是会遇到一种特殊的情况使得复杂度退化成O(n)：
一种点的范围是[i, n]，一种点的范围是只有i。这两种点如果交替出现的话，那么第一种点每次都只能向右扩展，要O(n)的时间来预处理范围。
改进的方法是：既然特殊情况只能向右扩展，那么不妨先预处理每个点只向右走能到达的最大边界，然后再进行上面的预处理过程。

然后是判断能否扩展：
假设当前的范围是[l, r]，如果要走到点r+1或l-1的话，就要判断对应路线上的那个质数是否出现在[l, r]区间内的质因子中。
因为数字范围不大，直接预处理每个质数在哪些位置上出现过即可。然后二分查找当前区间内是否有出现的位置。就可以O(logn)来判断了。

另一种思路（但实现有困难）：
既然背包中只有质数，那么可以将背包视为一个数字。如果背包中有对应的质数，说明背包能被该质数整除。（相当于背包维护了所包含质数的最小公倍数）
预处理的时候，如果能走到某个点，就将背包乘上这个点上的数字。
如果不考虑数字过大的影响，可以将判断从O(logn)优化成O(1)，但是数字过大，没法存储，因此这种做法实现起来有困难。

AC代码：

#include 
const int N = 2e5 + 5;
using namespace std;
int prime[N], low[N]; // low[i]记录i的最小质因子
bool isprime[N];
void get_prime()
{
    int cnt = 0;
    for (int i = 1; i <= 200000; i++)
        isprime[i] = 1;
    isprime[1] = 0;
    for (int i = 2; i <= 200000; i++)
    {
        if (isprime[i])
        {
            prime[++cnt] = i;
            low[i] = i;
        }
        for (int j = 1; j <= cnt && i * prime[j] <= 200000; j++)
        {
            isprime[i * prime[j]] = 0;
            low[i * prime[j]] = prime[j];
            if (i % prime[j] == 0) break;
        }
    }
}

int a[N], b[N], L[N], R[N];
vector<int> pos[N]; //存储每个质数出现的位置

bool check(int l, int r, int p) //检查在[l,r]区间内是否出现了质因子p
{
    if (pos[p].size() == 0 || pos[p].back() < l) return 0;
    int x = *lower_bound(pos[p].begin(), pos[p].end(), l);
    return (x <= r);
}

void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        L[i] = R[i] = i;
    }
    for (int i = 1; i < n; i++)
        cin >> b[i];
    for (int i = 2; i < N; i++)
        pos[i].clear();
    for (int i = 1; i <= n; i++) //预处理每个质数出现的位置
    {
        int x = a[i], cur;
        while (x > 1)
        {
            cur = low[x];
            pos[cur].push_back(i);
            while (cur == low[x])
                x /= cur;
        }
    }
    for (int i = n; i >= 1; i--) //预处理每个点只向右能走到的最远位置
    {
        int r = i;
        while (r < n && check(i, r, b[r]))
            r = R[r + 1];
        R[i] = r;
    }
    for (int i = 1; i <= n; i++) //预处理每个点的左右最远位置
    {
        bool flag = 1;
        int l = i, r = R[i];
        while (flag) //向左向右都无法更新边界时退出
        {
            flag = 0;
            while (l > 1 && check(l, r, b[l - 1]))
            {
                l = L[l - 1];
                flag = 1;
            }
            while (r < n && check(l, r, b[r]))
            {
                r = R[r + 1];
                flag = 1;
            }
        }
        L[i] = l, R[i] = r;
    }
    int x, y;
    while (m--)
    {
        cin >> x >> y;
        if (y >= L[x] && y <= R[x])
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    get_prime();
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

1007-Darnassus

题目大意：
一共有n个点，每个点有一个点权p_i且各不相同，p_i<=n。
每个点都和其他的点之间都有一条边，边权为|i-j|*|p_i-p_j|。
求最小生成树的权值。

思路：
因为这个图的边非常多，无法将每条边都找出来跑最小生成树，所以要想办法进行边的筛选，缩小范围。
如果把每个点i和i+1之间的边作为最小生成树里的边，那么每条边都是小于等于n-1的，因此可以保证最小生成树的每条边都不会大于n-1，有了这个结论后，就可以去掉很多无用的边了。
既然每条边都是不大于n-1的，那么 |i-j| 和 |p_i-p_j| 之间至少有一个是小于等于$\sqrt{n-1}$的。
那么对于每个点i，先限定 |i-j| 的范围，可以直接确定j的范围，然后在这个范围内将符合的边找出。
然后限定 |p_i-p_j|，对每个点按p进行排序，那么也可以确定一个范围，记录原始下标，然后在这个范围内找出符合的边。
找边的时间复杂度为O(n$\sqrt{n}$)

然而直接跑Kruskal的话，复杂度为O(n$\sqrt{n}$logn)，还是会超时。

既然边的权值最大只有n-1，完全可以用桶排序来代替快排，记录每种边权有哪些边，就可以把这个logn给优化掉了。

另外，该题会卡常，使用vector来存储边会超时，改用链式前向星就能通过了。

AC代码：

#include 
const int N = 5e4 + 5;
using namespace std;

struct edge
{
    int u, v, next;
} e[N * 460];
int head[N], ecnt;
void add(int w, int u, int v) { e[++ecnt].next = head[w], e[ecnt].u = u, e[ecnt].v = v, head[w] = ecnt; }
int n, m, p[N], pos[N], fa[N];
int Find(int x)
{
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
        pos[p[i]] = i;
        fa[i] = i;
        head[i] = 0;
    }
    ecnt = 0;
    m = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = min(n, i + m); j >= i + 1; j--)
        {
            int tmp = (j - i) * abs(p[i] - p[j]);
            if (tmp <= n - 1) add(tmp, i, j);
            tmp = (j - i) * abs(pos[i] - pos[j]);
            if (tmp <= n - 1) add(tmp, pos[i], pos[j]);
        }
    }
    long long ans = 0, cnt = 0;
    for (int i = 1; i <= n - 1 && cnt < n - 1; i++)
    {
        for (int j = head[i]; j; j = e[j].next)
        {
            int fu = Find(e[j].u);
            int fv = Find(e[j].v);
            if (fu != fv)
            {
                fa[fu] = fv;
                ans += i;
                cnt++;
            }
        }
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    long long T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64