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

Tenzing and Balls

算法本质

思维、dp

题目大意

存在n个小球排成一列，给定数组a[]表示每个小球颜色，玩家可以执行任意次操作：

• 选择2个相同颜色的小球，删除两球中间包括其在内所有小球

输出最大化删除的小球个数。

思路推演

稍加模拟可以发现，核心在于不同颜色小球的交错。相同颜色小球可以用连续区间来表示，问题在于如何处理不同颜色区间的交。

再次模拟思考，发现没有特定规律，于是考虑dp：dp[x]=y表示在区间1~x中最多可以删除y个小球。
转移的方式有二：

• 不删除当前小球
  dp[i] = dp[i-1]
• 当前小球作为区间右端点删除
  dp[i] = max(dp[x] + i-x)其中a[x+1] = a[i]

复杂度在于第二个转移方程，朴素去做的话复杂度达到O(n^2^)，既然是向前寻找，能否维护一个极值：dp[x]-x即可。
当然也可以转换dp定义，这样看起来更直观：

dp[x]=y表示区间1~x中最少剩余y个小球：

• 不删除当前小球
  dp[i] = dp[i-1] + 1
• 删除当前小球
  dp[i] = min(dp[x])其中a[x+1] = a[i]，这里开个数组记录一下即可

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
    cin>>n;
    vector<int> dp(n+5, 1e9), cod(n+5, 1e9);        // dp[x]表示下标1~x中，保留的最少球数
    dp[0] = 0;            // cod[x]表示，当前小球颜色为x，之前状态的最少小球数
    for (int i=1; i<=n; i++)
    {
        int x=in();
        dp[i] = min(dp[i-1]+1, cod[x]);        // 直接继承和跳跃继承
        cod[x] = min(cod[x], dp[i-1]);        // 维护
    }
    int ans = n-dp[n];
    cout<<ans<<endl;
    return;
}

Tenzing and His Animal Friend

算法本质

思维

题目大意（抽象）

给定无向有权图，玩家可以进行任意次操作：

• 将点设置为白点或黑点（1必须是白点、n必须是黑点），任意边两侧点颜色不一致，则边权-1

在保证边权不出现负数情况下，输出玩家至多可以进行的操作次数，并且输出每次操作的信息（用01表示点的黑白）。
若可以无限次输出inf。

n <= 1e2

思路推演

稍加模拟可以发现，若1 n两点不连通，则可以进行无限次操作。

题目核心在于固定1是白点、n是黑点，那一定有中间点受伤。
若画出1 n的任意一条路径，可以发现，每次操作至少路径上某边的边权会-1。

这不难推出，理论上最多操作次数即其最短路，带着这个思路去模拟发现：

• 若某点与n的最短路径是0，则其必须是黑点。

随后以最短路的思维，从n出发，除开必须黑点的点，其余点每次操作都取白点。
随着操作数的增加，可以视作黑点的面积不断扩大——正是最短路的模型。

随后代码模拟即可。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
// 省略DSU板子
inline void solve()
{
    cin>>n>>m;
    vector<vector<int>> g(n+5, vector<int>(n+5, 1e18));        // 两点的初始距离
    DSU dsu(n);
    while (m--)
    {
        int u, v, w;
        cin>>u>>v>>w;
        dsu.merge(u, v);
        g[u][v] = g[v][u] = w;
    }
    if (dsu.same(1, n)==0)        // 检查是否联通
    {
        cout<<"inf"<<endl;
        return;
    }
    string now(n+1, '1');        // 初始情况：除了n点全选白点
    now[n] = '0';
    vector<int> cod(n+5);
    for (int i=1; i<=n-1; i++)
        cod[i] = g[i][n];
    int tim=0, ci=0;
    vector<pair<string, int>> ans;
    while (1)
    {
        int minw=1e18, id=-1;
        for (int i=1; i<=n; i++)
            if (now[i]=='1' && cod[i]<minw)
                minw=cod[i], id=i;
        if (minw > 0)        // 需要记录
        {
            ans.push_back({now.substr(1, n), minw});        
            tim += minw;
            ci++;
        }
        for (int i=1; i<=n; i++)
            if (now[i]=='1')
                cod[i]-=minw;
        now[id] = '0';
        for (int i=1; i<=n; i++)
            if (now[i]=='1')
                cod[i] = min(cod[i], g[id][i]);
        if (id==1)        // 当1必须是黑点时，就无法继续操作了
            break;
    }
    cout<<tim<<" "<<ci<<endl;
    for (auto [s, t] : ans)
        cout<<s<<" "<<t<<endl;
    return;
}

Tenzing and Triangle

算法本质

思维、线段树

题目大意

存在一个区间由3条直线围成：

• y=0
• x=0
• x+y=k

思路推演

一个重要的特性是，三角形之间不存在交集。
观察x+y=k线，我们需要在这选择若干不相交区间。

在一维坐标上，我们需要选择若干区间（不同选择有不同成本），最后完全覆盖整个区间。
这是一个经典的dp[]做法：dp[x]=y表示覆盖区间[1~x]的最小成本是y。

先假设所有点都是单独消除，整体成本目前是sum，设f(l,r)表示x轴l~r三角形覆盖点的成本和 - A*(r-l)。
这样就可以把题目转为sum减去若干个不相交的f(l,r)——求若干个不相交的f(l,r)的最大值。

dp[x]=y表示处理完所有1~x

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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