Solution_CF2195 A~D

A. Sieve of Erato67henes

1. 题意梗概

给定一个数列 $a$，问能否选出任意数量的元素，使它们的乘积为 $67$。

• $n \leq 5$
• $1 \leq a_{i} \leq 67$

2. 逻辑推导

鉴于 $n \leq 5$，这个数量级可以直接用搜索搜，秒了。

等等，Div3T1 就搜索不太对吧，注意到 $67$ 是一个质数。

根据唯一分解定理 $67 = 67^1$，那就只需要判断有没有 67 就行了。

3. 代码实现

void solve( )
{
    cin >> n;
    bool ok67 = 0;
    for( int i = 1; i <= n; ++ i )
    {
        int x; cin >> x;
        if( x == 67 ) ok67 = 1;
    } 
    if( ok67 ) cout << "YES" << '\n';
    else cout << "NO" << '\n';
}

---

B. Heapify 1

1. 题面梗概

中译中：给定一个排列，你只能交换下标为 $i$ 和 $2i$ 的元素。问能否通过任意次交换将其排好序？

• $1 \leq n \leq 2 \cdot 10^5$
• $1 \leq a_{i} \leq n$

2. 逻辑推导

注意到 任意次 和 交换 这两个条件，那么本质上就是在讨论 连通性。

我的写法是 并查集，把所有 $i,2i$ 都合并，然后查询 $a[i]$ 能不能交换到 $i$ 即可。

排列的性质：由 $n$ 个从 $1$ 到 $n$ 的不同整数按任意顺序组成。

当然这里还有别的实现方式，比如：

• $a_{1}, a_{2}, a_{4}, a_{8}, \dots$ 能重排；
• $a_{3}, a_{6}, a_{9}, \dots$ 能重排；
• $a_{5}, a_{10}, a_{15}, \dots$ 能重排；
• $a_{7}, a_{14}, a_{21}, \dots$ 能重排；

那么只要处理 各个子数列 能否满足 $a[i] == i$ 即可。

吐槽：这个子数列的划分有点素数筛的感觉了。

3. 代码实现

int find( int x )
{
    if( fa[x] == x ) return fa[x];
    else return fa[x] = find( fa[x] );
}

void merge( int x, int y )
{
    int rx = find( x ), ry = find( y );
    if( rx != ry ) fa[rx] = ry;
}

void solve( )
{
    cin >> n;

    for( int i = 1; i <= n; ++ i ) fa[i] = i;

    for( int i = 1; i <= n / 2; ++ i ) merge( i, 2 * i );
    
    bool ok = 1;
    for( int i = 1; i <= n; ++ i )
    {
        cin >> a[i];
        if( find( i ) != find( a[i] ) ) ok = 0;
    }
    
    if( ok ) cout << "YES" << '\n';
    else cout << "NO" << '\n';
}

---

C. Dice Roll Sequence

1. 题意梗概

中译中：修改最少的骰子序列，使得相邻的骰子面在立方体上也是相邻的（即不相对且不相同）。

• $1 \leq n \leq 3 \cdot 10^5$
• $1 \leq a_i \leq 6$

2. 逻辑推导

骰子只有 6 个面，而且当前状态受到前一个状态的约束。那么这题就可以用一个 DP 来解决。

定义：设 $dp[i][j]$ 表示前 $i$ 个骰子合法，且第 $i$ 个骰子面为 $j$ 的最小修改数。

转移：$dp[i][j] =\min(dp[i-1][k]) + cost(a_{i}, j)$，条件 $j \neq k$ 且 $j + k \neq 7$，即不是 相同 且 不是 相对。

官方题解还有一种贪心的方法？感兴趣可以研究研究，我感觉不如 DP 直观，偷懒了。
下面简要介绍一下，想了想还是写一下吧。

对于任意两个面 $S, T$，总是存在一个面 $U$ 与这两个面相邻。

• 若 $S$ 和 $T$ 相邻，则 $U$ 是与 $S$ 和 $T$ 共角的任意一面。
• 若 $S$ 和 $T$ 相同，则 $U$ 是和 $S$ 相邻的面。
• 若 $S$ 和 $T$ 相对，则 $U$ 是剩下任意四个面。

然后我们把序列 $a$，按照相对和相同面拆分成 $m$ 个子段。(按照冲突的子段拆分)

比如说 $[6, 1, 4, 3, 1, 3, 2, 5, 4, 4]$ 就可以拆成 $[6, 1], [4, 3], [1], [3], [2, 5], [4, 4]$。

总次数为：$4 \times \lfloor \frac{2}{2} \rfloor + 2 \times \lfloor \frac{1}{2} \rfloor = 4$

每个由 $k$ 个元素组成的子段，至少需要修改 $\lfloor \frac{k}{2} \rfloor$ 才能解决，那也可以在 $O(n)$ 的时间拆分数列解决。

再比如说 $[1,6,1,1,2,5,2,5,2,3,4,1,1]$ 变成了 $[1,6,1,1],[2,5,2,5,2],[3,4],[1,1]$。

总次数为：$\lfloor \frac{5}{2} \rfloor + \lfloor \frac{4}{2} \rfloor + 2 \times \lfloor \frac{2}{2} \rfloor = 6$

3. 代码实现

void solve( )
{
    cin >> n;
    for( int i = 1; i <= n; ++ i ) cin >> a[i];

    for( int j = 1; j <= 6; ++ j )
    {
        if( a[1] == j ) dp[1][j] = 0;
        else dp[1][j] = inf;
    }

    for( int i = 2; i <= n; ++ i )
    {
        for( int j = 1; j <= 6; ++ j )
        {
            dp[i][j] = inf;
            int cost = 1;
            if( a[i] == j ) cost = 0;

            for( int k = 1; k <= 6; ++ k )
            {
                if( j == k || j + k == 7 ) continue;
                dp[i][j] = min( dp[i][j], dp[i - 1][k] + cost );
            }
        }
    }

    int ans = inf;
    for( int j = 1; j <= 6; ++ j ) ans = min( ans, dp[n][j] );
    cout << ans << '\n';
}

---

D. Absolute Cinema

1. 题面梗概

中译中：给定 $n$ 个位置的函数值，其中 $a_i$ 是隐藏的整数序列。已知所有的 $f(1 \dots n)$，求原序列 $a$。

$$f(x) = \sum_{i=1}^n a_i |i - x|$$

• $2 \leq n \leq 3 \cdot 10^5$
• $-10^{14} \leq f(i) \leq 10^{14}$

2. 逻辑推导

这个题看起来就不是很友善，但绝对值的核心在于 分段线性。我们可以先把柿子展开看看：

$$f(x) = \sum_{i=1}^{x}(a_{i}(x - i)) + \sum_{i=x + 1}^{n}(a_{i}(i - x))$$

既然是 线性 的，我们可以先差分看看性质。

$$df(x) = f(x + 1) - f(x) = \sum_{i=1}^{x}(a_{i}(x + 1 - i)) + \sum_{i=x+1}^{n}(a_{i}(i - x - 1)) - \sum_{i=1}^{x}(a_{i}(x - i)) + \sum_{i=x+1}^{n}(a_{i}(i - x))$$

化简后得到柿子如下：记 $S_{x} = \sum_{i=1}^{x}a_{i}$。

$$df(x) = \sum_{i=1}^{x}a_{i} - \sum_{i=x+1}^{n}a_{i} = S_{x} - (S_{n} - S_{x}) = 2S_{x} - S_{n}$$

这里我们再差分一次（因为我们得到了 $2S_{x} - S_{n}$ 这个前缀和关系，差分可以还原回正常序列）

$$ddf(x) = df(x) - df(x - 1) = (2S_{x} - S_{n}) - (2S_{x-1} - S_{n}) = 2(S_{x} - S_{x-1}) = 2a_{x}$$

然后我们就得到了$a_{x}$ 和 $ddf$ 函数的关系了，至于两端的 $a_{1}$ 和 $a_{n}$ 怎么求呢？我们可以从 $df$ 函数的端点出发。

$$df(1) = 2S_{1} - S_{n} = 2a_{1} - S_{n}$$

$$df(n - 1) = 2S_{n - 1} - S_{n} = 2(S_{n} - a_{n}) - S_{n} = S_{n} - 2a_{n}$$

至于这个 $S_{n}$ 怎么求？我们可以从 $f$ 函数的端点出发。

$$f(1) = \sum_{i=1}^n a_i (i - 1) \quad f(n) = \sum_{i=1}^n a_i (n - i) \quad$$

那么就可以得到这个柿子了：

$$f(1) + f(n) = \sum_{i=1}^{n}( a_{i} \cdot ( n - 1 ) ) = S_{n} \cdot ( n - 1 )$$

3. 代码实现

void solve( )
{
    cin >> n;
    for( int i = 1; i <= n; ++ i ) cin >> f[i];

    ll Sn = ( f[1] + f[n] ) / ( n - 1 );

    for( int i = 1; i <= n; ++ i ) df[i] = f[i + 1] - f[i];

    for( int i = 1; i <= n; ++ i ) ddf[i] = df[i] - df[i - 1];

    a[1] = ( Sn + df[1] ) / 2;

    for( int i = 2; i <= n - 1; ++ i ) a[i] = ddf[i] / 2;

    a[n] = ( Sn - df[n - 1] ) / 2;
    
    for( int i = 1; i <= n; ++ i ) cout << a[i] << " ";
    cout << '\n';
}