Educational Codeforces Round 135 D.博弈+区间DP | E.扩展欧几里得

比赛链接：Dashboard - Educational Codeforces Round 135 (Rated for Div. 2) - Codeforces

又是一场edu，不过这场掉大分，做的太慢，心态有点炸，A还读错题。

---

A. Colored Balls: Revisited

题意：给你$n$个颜色的球，每个颜色有$a_i$个，都放在一个盒子里面，你每次拿出两个不同颜色的球，求最后盒子里只有一种颜色是第几种，输出任意一个即可。

思路：读错题是因为觉得问的是一共有多少种可能，那不就是感觉都有可能嘛，但又一想每次要拿出不同颜色的，那又不简单了..再一读题发现是输出任意一个即可，我就用了一个队列模拟了一遍...

实际上用最大的那个数字的下标在第几个就可以了。

代码：

inline void Case_Test()
{
    cin>>n;
    vector<int> v(n);
    for (auto &e:v) cin>>e;
    cout<<max_element(v.begin(),v.end())-v.begin()+1<<endl;
}

---

B. Best Permutation（构造）

题意：给你一个$n$，求构造一个长度为$n$的排列，求以下定义最大的排列“值”：

• 一开始有一个$x=0$
• 如果当前$x\lt a[i]$，那么$x:=x+a[i]$
• 否则$x:=0$

思路：通过看样例可以大胆猜测，一个排列的最大值只有$(n-1)+n$也就是后面两个，具体证明我也没去证明。

那么想象出来这个数列的后面两位，也就是长这个样_,_,_,...,_,n-1,n。那么前面的目的就是清零，也就是倒数第三个需要清零，那么就一直变小？比如：4,3,2,1,5,6，这样可以得到x: 4,0,2,0,5,11。

但是这只是偶数的时候是可以的，奇数的时候是不可以的，比如3,2,1,4,5，这样的x: 3,0,1,5,0，所以需要做一点小操作，只需要错开一位即可，也就是1,3,2,4,5，把1放在前面就好。

代码：

inline void Case_Test()
{
    cin>>n;
    if (n%2==1)
    {
        cout<<1<<" ";
        for (int i=n-2;i>1;i--) cout<<i<<" ";
    }
    else
    {
        for (int i=n-2;i>=1;i--) cout<<i<<" ";
    }
    cout<<n-1<<" "<<n<<endl;
}

---

C. Digital Logarithm

题意：给你两个长度为$n$的数组$a,b$，你有一个操作可以对于其中一个数字（a数组或者b数组中的）使其变化，求最小的操作数可以使他们变得一样。

• 选择一个数$x$，使其变成$x:=f(x)$，$f(x)$是$x$的十进制位数。

思路：主要是注意到一点，因为数组的范围最大是$10^9$，所以只需要执行一次的$f(x)$即可变成个位数，所以操作没有那么多。

我原来写法很复杂，现在有Wolfycz的代码很好看，在这里写他的。

一开始设置一个[x,y]:map用来存放数字x出现了y次。

然后读入$a$数组的时候加入到map里面，使其个数++，然后$b$数组的时候会有抵消的作用，为什么呢？因为如果有相同的，那么就肯定不用管的。

那么该如何做呢？就是倒序遍历：
for (auto it = mp.rbegin();it!=mp.rend();it++)
用结构化绑定[x,y]:*it，x就是数字，y就是出现的次数（有可能出现负数，负数的意义就是上面的）

如果y==0的话，那么就continue，因为此时不用管，不然怎么办呢？那就需要进行y次操作（每一个都需要，一共y个），
然后在map中将新的加入，因为是倒序遍历的，所以最后也是可以遍历到的。答案也需要加上Abs(y)，因为y有负数，但是实际上算肯定是需要算正数的。

代码：

map<int,int> mp;
inline void Case_Test()
{
    mp.clear();
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        mp[x]++;
    }
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        mp[x]--;
    }
    ans = 0;
    auto f = [&](int x)
    {
        int res = 0;
        while (x) x/=10, res++;
        return res;
    };
    for (auto it = mp.rbegin();it!=mp.rend();it++)
    {
        auto [x,y] = *it;
        if (y==0) continue;
        mp[f(x)] += y;
        ans += Abs(y);
    }
    cout<<ans<<endl;
}

---

D. Letter Picking（博弈+区间DP）

题意：给你一个长度是偶数的字符串，Alice和Bob互相拿走当前字符串两端的，并且放在自己手中的最前面，最后都取完之后字典序最小的赢，或者平局。

思路：首先需要知道的是，一定不会有Bob的赢得情况，所以要么是一定平局，要么是Alice赢。
区间DP的思路当然就是dp[i][j]表示区间[i,j]是否有一定平局的情况。

注意一定是一定，大部分人都是这个地方错bbabba，比如我在判断dp[1][6]发现转移的时候可以从dp[3][6]的时候转移过来（这里很容易得出dp[3][6]=1也就是有平局的情况）

但是这个情况是基于Alice选择最左边的也就是s[1]='b'，但是实际上这个字符串是Alice赢而不是Draw平局。因为这时候Alice选择的是最右边的a（可以手动模拟一下）

所以需要如何思考呢？因为要求的是一定平局，所以对于当前需要判断的dp[l][r]无论Alice选择的是s[l]还是s[r]，都要有平局的情况才可以使得dp[l][r]=1。

那么对于当前区间[l,r]分为四种情况：

• 1)Alice选择的是s[l]，Bob选择的是s[l+1]。这时候首先需要dp[l+2][r]=1.
• 2)Alice选择的是s[l]，Bob选择的是s[r]。这时候首先需要dp[l+1][r-1]=1.
• 3)Alice选择的是s[r]，Bob选择的是s[r-1]。这时候首先需要dp[l][r-2]=1.
• 4)Alice选择的是s[r]，Bob选择的是s[l]。这时候首先需要dp[l+1][r-1]=1.

也就是Alice选择s[l]的情况1和情况2的两种情况里，至少需要一个满足条件。Alice选择s[r]的情况3和情况4的两种情况里，至少需要满足一个条件。

所以在两两取或的之后再取并。也就是说不论Alice选择是s[l]还是s[r]，都有一定平局的情况，才可以转移到dp[i][j]=1。

inline bool check(int l,int r)
{
    bool r1 = ((dp[l][r-2])&&(s[r-1]==s[r])||(dp[l+1][r-1])&&(s[l]==s[r]));
    bool r2 = ((dp[l+2][r])&&(s[l]==s[l+1])||(dp[l+1][r-1])&&(s[l]==s[r]));
    return r1&&r2;
}

初始化的话就是基础区间DP的操作，相邻的相等的赋值为1即可，然后每次区间+2扩展。

代码：

int dp[N][N];
inline bool check(int l,int r)
{
    bool r1 = ((dp[l][r-2])&&(s[r-1]==s[r])||(dp[l+1][r-1])&&(s[l]==s[r]));
    bool r2 = ((dp[l+2][r])&&(s[l]==s[l+1])||(dp[l+1][r-1])&&(s[l]==s[r]));
    return r1&&r2;
}
inline void Case_Test()
{
    cin>>s;
    n = s.size();
    for (int i=0;i<n-1;i++)
        dp[i][i+1] = (s[i]==s[i+1]);
    for (int k=3;k<n;k+=2)
        for (int i=0,j=k;j<n;i++,j++)
            dp[i][j] = check(i,j);
    if (dp[0][n-1]) cout<<"Draw"<<endl;
    else cout<<"Alice"<<endl;
}