CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)

Prefix Purchase

算法本质

思维

题目大意

给定长度n的数组c[]，初始拥有长度n的全0数组a[]和k元。
可以进行任意次操作：

• 花费c[i]元，使得a[1~i]元素都+1

输出操作后最大化的a[]（字典序）。

思路推演

稍加模拟可知：

• 价格相同，下标大的优
• 下标相同，价格低的优
• 可以选择不同价格的，但是要保证次数不减少

这说明了，可以用贪心的思路去遍历可能的点，其符合：

• 下标递增
• 价格递增
• 首个点是价格最低中，最靠右的点

根据此模拟即可。（详细看代码）

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
void solve()
{
    cin>>n;
    map<int, int> mp;
    for (int i=1; i<=n; i++)
        mp[in()]=i;
    cin>>k;
    vector<int> ans(n+5);
    int max_ci=1e9, lastid=0, bo=0;        // max_ci表示选择次数上限、lastid记录上次访问id（排序保证价格递增，lastid维护id递增）、bo表示价格底部
    for (auto [w, id]:mp)
    {
        if (id < lastid)    continue;    // 维护id递增
        int ci=k/(w-bo);
        ci = max(ci, 0ll);      // 范围在[0~max_ci]之前
        ci = min(ci, max_ci);
        k -= ci*(w-bo);        // 计算“剩余的钱”
        ans[id] = ci;       // 记录选择
        max_ci = ci;        // 更大最大值限制
        bo = w;
        lastid = id;
    }
    for (int i=n; i>=1; i--)        // 因为是选取了一部分点，没有覆盖全部，手动覆盖
        ans[i] = max(ans[i], ans[i+1]);
    for (int i=1; i<=n; i++)  
        cout<<ans[i]<<" \n"[i==n];
    return ;
}

Another MEX Problem

算法本质

思维、dp

题目大意

给定长度n数组a[]，元素值为[0~n]。

玩家可以选择若干个互不相交的子数组，输出最大化的每个子数组的mex值的异或和。

n <= 5e3

思路推演

显然需要用到dp，在不考虑复杂度的情况下，构建dp解决（这个过程很可能领悟题目的特性）。

首先来说表示一个范围的精确值十分好计算，但是这显然不合适题意来dp——因为可以空许多地方，意味分割线的数目会很多。
所以自然而然的，使用dp[l][r][x] = 0/1来表示区间a[l~r]是否可以制造出x值。

同时考虑转移方程，发现并不需要精确的左右端点范围，所以修改为：dp[r][x] = 0/1表示区间a[1~r]是否可以制造出x值。
转移方程也相对简单：

• 1~r可以视作由完全自己构成
  dp[r][ mex(a[1~r]) ] = 1
• 看作由2个区间异或而成
  dp[r][ dp[mid][x] ^ mex(a[mid+1~r]) ] = 1

通过设计dp状态，目前空间复杂度n^2^、时间复杂度n^3^，寻找特征继续优化。

考虑mex的特征，当一个区间向外延申时，其mex值可能不变。
定义不可替代区间：

• 当区间长度为1 或者 不存在真子区间也可以获得相等的mex值

通过继承方式，我们可以只用在不可替代区间上更新。

证明：不可替代区间的数目是O(n)量级

区间长度为1的都是不可替代：有n个
考虑区间长度>1的情况：
对于任意长度>1的不可替代区间，其左右端点元素一定不相同，则先假定左端点值>右端点值

反证法：
对于每个左端点l，若存在多个r端点可以组成不可替代区间，先取2个为r1 r2，其r1<r2
首先可以知道mex(l, r1)>l（不可替代区间特点），r2<l<mex(l,r1)，所以r2显然无贡献，删除r2不会对mex值产生影响。

所以可得，对于每个左端点l，至多有1个r端点可以组成不可替代区间（长度>1）
然后反过来，不可替代区间的数目是3n
（也可以修改定义使其求为2n，但是这种方式不改变数量级，无所谓）

所以，对于每个左端点，转移复杂度降低至O(n)。

另外有担心异或导致值超出n，实际上没有这种数据，手动模拟，应该是存在什么数学式子约束。
但是没有题解做出回答，所以目前无法解答。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
void solve()
{
    cin>>n;
    vector<int> a(n+5);
    vector<vector<int>> dp(n+5, vector<int>(n+5)), mex(n+5, vector<int>(n+5)), cod(n+5);
    for (int i=1; i<=n; i++)
        cin>>a[i];
    // 初始化mex[][]
    for (int i=1; i<=n; i++)
    {
        vector<bool> zhi(n+5);
        int val=0;
        for (int j=i; j<=n; j++)
        {
            zhi[ a[j] ] = 1;
            while (zhi[val])
                val++;
            mex[i][j] = val;
        }
    }
    // 维护cod，cod[l]记录了所有以l为左端点的**不可替代区间**
    for (int l=1; l<=n; l++)
    {
        cod[l].push_back(l);
        for (int r=l+1; r<=n; r++)
        {
            if (mex[l][r]!=mex[l+1][r] && mex[l][r]!=mex[l][r-1])
                cod[l].push_back(r);
        }
    }
    dp[0][0] = 1;
    for (int l=0; l<=n; l++)
    {
        if (l>0)        // 继承，表示中间有部分没有选择
        {
            for (int x=0; x<=n+1; x++)
                if (dp[l-1][x])
                    dp[l][x] = 1;
        }
        for (int r:cod[l+1])
        {
            for (int x=0; x<=n; x++)
            {
                if (dp[l][x]==0)    continue;
                dp[r][ x^mex[l+1][r] ] = 1;
            }
        }
    }
    int ans=0;
    for (int i=0; i<=n; i++)
        if (dp[n][i])
            ans = i;
    cout<<ans<<endl;

    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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