Codeforces Round 804 (Div. 2)

Almost Triple Deletions

算法本质

思维

题目大意

给定数组a[]，Alice希望不断执行以下操作使得a[]的元素种类唯一或者无元素：

• 删除两个相邻且不相等的元素

幸运的是，玩家可以指定Alice所选的元素。
输出最大化剩余a[]的长度。

n <= 5e3
a[] <= n

思路推演

很显然的dp题目。

既然最后会留下某种元素，则朴素的想法就是，遍历选择元素种类，然后O(n)判断其最后剩余的最大数目。
比如枚举x，接下来需要面对的就是，如何计算x之间元素的剩余。

对于n个元素，我们希望其剩余最少个数：

• n%2==1
res = max(1, 最多元素个数*2-n)
• n%2==0
res = max(0, 最多元素个数*2-n)

稍加思考，我们可以用O(n^2^)的时间来预处理所有区间，使其之后可以O(1)查询区间的最小剩余元素个数。
接着来验证这样朴素的贪心是否可行，有一组样例表示不可行：

14
3 3 3 3 2 2 1 1 2 2 2 2 2 2

上面这组样例的最优解，应该是将1~8的区间优化至最少个数，然后用右侧的2减去即可。
以2分割来看区间的做法是不正确的。

如果对于每个值都如此操作，其复杂度是O(n^2^)，一共n个值就是O(n^3^)，我们需要优化。
朴素的想法也相对简单——能否n个值同时处理。

于是构建出dp[x]=y表示1~x元素最后剩余a[x]的数目为y。

之后的转移方程和答案相对细微繁琐，但是比较简单，可以看代码思考一下。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
    cin>>n;
    vector<int> a(n+5);
    read(a, 1, n);
    vector<vector<int>> ck(n+5, vector<int>(n+5));
    for (int l=1; l<=n; l++)
    {
        vector<int> cod(n+5);
        int top=0;
        for (int r=l; r<=n; r++)
        {
            top = max(top, ++cod[a[r]]);
            ck[l][r] = top;
        }
    }
    auto f = [&](int l, int r) -> int {        // 查询区间[l,r]的最少剩余元素个数
        if (l>r)    return 0;
        int len = r-l+1;
        int res = ck[l][r]*2 - len;
        return max(res, (len%2 ? 1ll : 0ll));
    };
    vector<int> dp(n+5);    // dp[x]=y表示1~x元素最后剩余a[x]的数目为y
    int ans=0;
    for (int i=1; i<=n; i++)
    {
        dp[i] = 1 - f(1, i-1);        // 注意这里可以是负数
        for (int j=1; j<i; j++)
            if (a[i]==a[j] && f(j+1, i-1)==0)        // 转移方程
                dp[i] = max(dp[i], dp[j]+1);
        ans = max(ans, dp[i] - f(i+1, n));
    }
    cout<<ans<<endl;
    return;
}

Three Days Grace

算法本质

思维

题目大意

给定n个元素其范围是[1~m]，玩家可以进行任意次操作：

• 选择元素x，将其分解为a b，需要保证a*b==x

输出最小化的极致差。

n <= 1e6
m <= 5e6

思路推演

一个朴素的想法是，人为规定最小值或者最大值，然后检查。
观察规则，对于x分解成1 x肯定是不聪明的，所以可以知道每个数至多分解成log个数——考验玩家如何利用。

比如玩家规定最小值，则需要计算所有数的情况。
显然遍历的复杂度都达到了O(nm)，思考能否用dp重复利用。

写到这发现，题解有一些错误（或者个人理解有误）

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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

title

算法本质

题目大意

思路推演

ac核心代码

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