1104d1+2

赛时ABCD，也是在最后时刻惊险通关D题，还不错

A

A题，由于每个位置可以操作一次，最终结果就是一个单调不增的序列，从头开始模拟即可。

B

Ja the Ghost is playing with rubber ducks. He has $n$ piles of rubber ducks arranged in a row, where the $i$-th pile contains $a_i$ ducks. Quack the Duck gives Ja a strictly increasing sequence $b_1,b_2,\ldots,b_n$ and commands him to make the piles $a_1,a_2,\ldots,a_n$ become exactly this sequence.

Ja performs the process in the following two stages:

1. Ja may add any number of ducks to each pile.

   Formally, for each pile $i$, he chooses a non-negative integer $x_i$ and replaces $a_i$ with $a_i+x_i$.

2. Ja may repeatedly swap two adjacent piles.

   Formally, he may perform the following operation any number of times, possibly zero: choose an index $i$ such that $1\le i\le n-1$, and swap the values of $a_i$ and $a_{i+1}$.

A process is called valid if, after both stages end, the sequence of pile sizes is exactly $b_1,b_2,\ldots,b_n$.

Find the minimum possible number of operations performed in the second stage among all valid processes. If there is no valid process, output $-1$.

注意到数据范围为2000，可以接受$N^2$的复杂度。

分析

我们只能增加a序列的数值，并且可以对a序列相邻元素进行交换使之和b序列相同，要求最小化交换次数。
由于b序列严格递增，且a序列元素只能变大不能变小，转换思路：
将b序列打乱，让b序列每个值和a对应（a中元素增大后，和打乱的b序列相同），此时再将b序列还原回来，交换次数实际上就是打乱后的序列b的逆序对。
考虑贪心算法：
对于每一个$a_i$，我们找到第一个$b_j\ge a_i$，将i和j匹配，令$c_i=j$（或者等于$b_j$也行，因为b序列递增，统计逆序对时，j和$b_j$等价）。如果找不到，则说明$a_i>\max(b_j)$，此时输出-1。
随后统计c序列中的逆序对数就是最终答案。

Code

void sol()
{
    int n,res=0;
    cin>>n;
    vector<int>a(n),b(n),c(n);
    bitset<2001>vis;
    vis.reset();
    for(auto &x:a)cin>>x;
    for(auto &x:b)cin>>x;
    for(int i=0;i<n;i++)
    {
        int j=0;
        for(;j<n;j++)
        {
            if(a[i]<=b[j]&&vis[j]==0)
            {
                c[i]=j;
                vis[j]=1;
                break;
            }
        }
        if(j==n)
        {
            cout<<"-1\n";
            return;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(c[i]>c[j])res++;
        }
    }
    cout<<res<<'\n';
}

C

Ja the Ghost is playing with rubber ducks again! There are $n$ piles of rubber ducks arranged in a row from left to right. Initially, the $i$-th pile contains $a_i$ rubber ducks.

While the sequence $a$ is not sorted in nondecreasing order, Ja must perform the following operation:

• Choose two adjacent piles such that the left pile contains more ducks than the right pile. Ja swaps these two piles, and then adds the number of ducks in the new left pile to the new right pile.

  Formally, choose an index $i$ such that $1\le i \lt n$ and $a_i \gt a_{i+1}$. Then replace the adjacent pair $(a_i,a_{i+1})$ with $(a_{i+1},a_i+a_{i+1})$.

For example, if two adjacent piles contain $7$ and $3$ rubber ducks, then after the operation they contain $3$ and $10$ rubber ducks.

Ja may choose any index satisfying the condition above at each step. It can be shown that, regardless of his choices, the process eventually ends with the sequence sorted in nondecreasing order.

Ja wants the largest pile at the end of the process to contain as few rubber ducks as possible. Determine the minimum possible value of the largest pile.

又是一道序列题
虽然有minimum possible value of the largest pile，但是这并不是一道二分答案问题，而是一道简单的贪心题。

分析

考虑连续交换的变化：如果一个元素从i向右交换到j，那么最终$a_j=\sum\limits_{k=i}^{j}a_k$，也就是这一段的区间和。
我们最终需要将序列变成一个非严格递增的序列，也就是我们只需要最小化最后一个值（最后的值就是最大值）。而在一段连续交换的过程中，中间量的大小关系是不变的，但哪怕他们之间无序，交换成到有序的情况后，其最大值仍然不可能超过最右侧的值（因为最右侧的值是这一段的区间和，而其他的只是部分和）。
因此我们从左往右贪心求解。如果遇到逆序对，就交换两者。在若干次交换后，如果碰上更大的值，此时交换就终止了，答案需要更新为更大的值，再继续向右进行交换操作即可得出答案。

Code

void sol()
{
    int n;
    cin>>n;
    vector<int>a(n+1,0);
    int cur=0;//cur=sum[l,r]
    for(int l=1;l<=n;l++)
    {
        cin>>a[l];
        if(a[l]>=cur)
        {
            cur=a[l];
        }
        else
        {
            cur+=a[l];
        }
    }
    cout<<cur<<'\n';
}

D

A binary string is a string consisting only of characters $0$ and $1$. The two characters $0$ and $1$ are called opposite values.

Consider a binary string $t$. Let $|t|$ be the length of $t$. When $|t| \ge 2$, for every $1 \le i \lt |t|$, the characters $t_i$ and $t_{i+1}$ are adjacent.

A binary string $t$ is called beautiful if it can be reduced to a string of length exactly $1$ by applying the following operation any number of times, possibly zero:

• Choose two equal adjacent characters, remove both of them, and insert one character with the opposite value in their place.

For example, the string $\mathtt{10001}$ can become $\mathtt{1101}$ by replacing the first adjacent pair $\mathtt{00}$ with $\mathtt{1}$. Then it can become $\mathtt{001}$, then $\mathtt{11}$, and finally $\mathtt{0}$. Therefore, $\mathtt{10001}$ is beautiful.

On the other hand, $\mathtt{111}$ is not beautiful. After one operation, it becomes $\mathtt{01}$, and then no operation can be applied.

You are given a binary string $s$. Compute the number of non-empty beautiful substrings$^{\text{∗}}$ of $s$.

$^{\text{∗}}$A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

一道极其神秘的题

分析

可以将相邻的2个1变成0，将相邻的2个0变成1。
考虑数值变化，前者$\Delta=0-2=-2$，后者$\Delta=1-0=1$，如果我们将权值增加1，即1的权值为2，0的权值为1，那么前者$\Delta=1-4=-3$，后者$\Delta=2-2=0$。
这样我们每一次消除操作后，权值要么不变，要么-3，要求最后只剩一个数，也就是最终权值为1或2。
显然，当这个序列总权值为3的倍数时，无论如何操作都不能只剩一位数。
此时我们得到了变成一位数的序列的必要条件。
很容易想到，如果一个序列01交替，那么无法进行任何操作。这肯定是不beautiful的。（实际上充分条件就是存在一个可以操作的位置，具体的证明很复杂，我也不会。。。）
设条件1为序列权值和模3非0，条件2为存在可操作位置。
现在考虑如何求beautiful的子串数量。
我们枚举右端点r，对于条件2，我们只需要记录最后一个可操作位置$last$，那么满足条件2的区间就是左端点$l\le last$的区间，共有last个。显然，last在r增加时不会减少。
然后考虑条件1，我们的目的是要删去子区间里权值和为3的倍数的值。我们通过预处理一个权值前缀和模3的特殊前缀和$pref$，如果$pref_r=k$，那么我们就要删去子区间里面$pref$同样为k的数量。记录从1到$last$的$pref$的值的数量$cnt$，那么以r为右端点的beautiful子区间数量就是$last-cnt_{pref_r}$。

Code

void sol()
{
    int n;
    cin>>n;
    string s;
    vector<int>a(n+1,0);
    cin>>s;
    for(int i=0;i<n;i++)
    {
        char c=s[i];
        if(c=='0')a[i+1]=1;
        else a[i+1]=2;
    }
    vector<int>pre(n+1,0);
    for(int i=1;i<=n;i++)
    {
        pre[i]=(pre[i-1]+a[i])%3;
    }
    int res=0,l=1,lst=0;
    int cnt[3]={1,0,0};
    for(int r=1;r<=n;r++)
    {
        if(r>=2&&a[r]==a[r-1])
        {
            lst=r-1;
        }
        while(l<lst)
        {
            cnt[pre[l]]++;
            l++;
        }
        if(lst>0)
        {
            res+=lst-cnt[pre[r]];
        }
        res++;
    }
    cout<<res<<'\n';
}