Codeforces Round 899 (Div. 2)

Card Game

算法本质

思维

题目大意

给定长度n序列，玩家初始金额0元，可以进行若干次以下操作之一：

• 删除奇下标元素，并加+对应元素的金额
• 删除偶下标元素
• 结束游戏

输出最大化最终金额。

思路推演

先贪心的想，所有>0的元素我们都希望得到，能否实现。

奇下标元素当然容易实现，只需要从后往前拿即可。
偶下标稍微困难一些，其核心在于，若前面有被拿掉的元素，则一定可以实现。

考虑首个>0的元素下标是偶下标，我们也可以尝试删除下标2的元素，来实现前面拿到元素这个条件。
所以可以知道，下标>2的元素，可以任取。

然后再考虑下标1和下标2的元素情况即可。

Tree XOR

算法本质

思维

题目大意

给定一棵树，每个点有初始值a[i]，希望最终使得所有点的值相等。
玩家可以进行以下操作：

• 选择某个节点u和正整数x，其含自己的所有子节点都异或x，成本是子树（含自己）节点数 * x

对于这棵树的根是[1 ~ n]的情况，分别计算其最小成本。

思路推演

首先拆位是肯定的，拆位之后可以把图看成黑白双色的图。
因为题目的要求对所有点都当根节点的情况，这十分贴合换根dp的特性，所以优先考虑换根dp。

然后其实这就是一个相对基础的换根dp做法，推一下递推公式即可。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
vector<int> g[maxn];
int c[maxn], a[maxn];
int wast[maxn], num[maxn], wast2[maxn];
// 有方向情况：num[x]表示包括其本身的子节点数目，wast[x]表示将其子树都变成和自己同一颜色的操作节点数
// 无方向情况（或者所有方向情况）：wast2[x]其作为根节点，需要操作的节点数
void dfs(int u, int fr=0)
{
    wast[u] = 0;    
    num[u] = 1;
    for (int v:g[u])
    {
        if (v==fr)    continue;
        dfs(v, u);
        num[u] += num[v];
        wast[u] += wast[v];
        if (c[v] != c[u])
            wast[u] += num[v];
    }
}
void dfs2(int u, int fr=0)
{
    wast2[u] = wast[u];
    if (fr!=0)
    {
        int wfu = wast2[fr] - wast[u];
        if (c[u]!=c[fr])    wfu -= num[u];
        wast2[u] += wfu;
        if (c[u]!=c[fr])    wast2[u] += n-num[u];
    }
    for (int v:g[u])
    {
        if (v==fr)    continue;
        dfs2(v, u);
    }
}
inline void solve()
{
    cin>>n;
    for (int i=1; i<=n; i++)
        cin>>a[i];
    m = n-1;
    while (m--)
    {
        int u, v;
        cin>>u>>v;
        g[u].push_back({v});
        g[v].push_back({u});
    }
    vector<int> ans(n+5);
    for (int val=1, t=0; t<20; val*=2, t++)
    {
        for (int i=1; i<=n; i++)
        {
            if (a[i] & val)
                c[i] = 1;
            else    
                c[i] = 0;
        }
        dfs(1);
        dfs2(1);
        for (int i=1; i<=n; i++)
            ans[i] += wast2[i]*val;
    }
    for (int i=1; i<=n; i++)
    {
        cout<<ans[i]<<" \n"[i==n];
        g[i].clear();
    }
    return;
}

Two Permutations (Hard Version)

算法本质

思维

题目大意

给定长度分别是n和m的排列a[] b[]，现在玩家可以进行若干次操作：

• 选择i j
• a[i]左右两侧的元素交换，同时其内部顺序不变
• b[j]左右两侧的元素交换，同时其内部顺序不变

目的是最终使得a[]和b[]同时有序。（不可行输出-1）

• 简单版本
  1e4次操作内完成
• 困难版本
  最少操作次数完成

n m <= 2500

思路推演 - 简单版本

首先思考简单版本，显然是需要一个必胜法。
朴素的想法是，维护有序区间，然后依次增长，说白了就是先找1，然后找1 2，然后找1 2 3。

模拟的时候就可以发现，因为中间仅有一个元素位置不变，例如已经有了1 2 3，现在希望加入4，则4要成为这个被操作的元素。
我们希望当时的情况类似于：x x x 4 x x x 1 2 3，这样通过一次操作就可以凑成1 2 3 4了。
想要使得1 2 3出现在末尾，其实也比较简单，x x 1 2 3 p x x，操作p元素即可。

至此我们就得到了一个简单的必胜法，每次至多2次操作即可使得维护的有序区间+1。
接下来要解决的问题是同时有序。

稍加模拟可以发现，对同一元素重复操作2次数组不变，意味如果其操作数之差是偶数，则两者可行。

模拟过程中可以发现，对于长度n的序列，一定存在操作n次后不变的情况。
所以考虑一下奇偶同步的情况即可。

这个结论可以说是模拟后猜的，结合简单版本的限制，困难版本会证明

思路推演 - 困难版本

到这一步，需要抽象成一个全新的模型才能求解最小操作——每次操作的核心。
每次操作会移动n-1个元素，这太复杂了，能否看作移动操作元素。

至此需要引入循环数组。
对于1 2 3 4 5，如果对3操作，理论上应该是4 5 3 1 2，如果我们只考虑移动3，则可以视作移动至开头的循环数组3 1 2 4 5。
但是显然，下次移动就并非移动至开头，而是移动至上次3存在的地方。

我们引入一个虚拟的0，每次操作可以视作选择某个非0元素与0的位置交换。
最后保证有序的循环数组即可。

（未完）

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。