1099d2

本场比赛赛时只做出两道题，A题不必多说，秒了。
对于B题，我最开始复杂度想错了，将每个测试点中的多次遍历当场$O(n^2)$复杂度了，因此一直在想是否有$O(\log n)$的解法，知道最后一小时才反应过来，但由于最初的写法很复杂又浪费很长时间，随后灵光乍现想到了贪心解。
然后去做C题，把C题的输出当成了最优情况下的数字求出来了，而非答案所要的次数，直到最后五分钟才发现，也是惨败了…

Codefoeces的题相比AtCoder差别还是蛮大的，前者有很多思维题

A

问题陈述

给你一个整数 $n$ 。你需要构造一个整数数组 $a_1, a_2, \ldots, a_n$ 以满足以下条件：

• 从 $1$ 到 $n$ 的所有 $i$ 都是 $1 \leq a_i \leq 2 \cdot n$ 。
• 数组的所有元素和相邻元素的和都是成对不同的。换句话说，在数字 $\{a_1, a_2, \ldots, a_n, a_1 + a_2, a_2 + a_3, \ldots, a_{n - 1} + a_n\}$ 中，不应有两个相等的数字。

分析：

本题需要构造一个数列，满足每个元素之间以及相邻两个元素的和不能重复，换个表达就是：$\forall i,1\le i\le n，a_i\in \mathbb{B}\And a_i+a_{i-1}\in \mathbb{B}$，而$\mathbb{B}$中没有重复元素。

思路：

很容易想到，对于一个奇数列${1,3,5,...,2n-1}$，任意相邻两者之和为偶数，显然和奇数列不重复，因此奇数列符合条件，输出奇数列即可。

Code

void sol()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cout<<2*i-1<<' ';
    }
    cout<<'\n';
}

B

问题陈述

给你一个数组 $a_1, a_2, \ldots, a_n$ 。你最多可以对这个数组执行一次下面的操作：

• 选择一个正整数 $k$ 以及数组 $a$ $^{\text{∗}}$ 的子序列 $b_1, b_2, \ldots, b_m$ 并将 $k$ 加到该子序列的每个元素上，即对每个 $i$ 执行 $a_{b_i} := a_{b_i} + k$ 操作。

您需要确定是否有可能通过最多执行一次此操作，对数组进行非递减排序。
$^{\text{∗}}$ 如果从 $a$ 中删除任意位置上的几个元素（可能是零，也可能是全部）就可以得到 $b$ ，那么序列 $b$ 就是序列 $a$ 的子序列。

分析：

给定一个数列，我们需要选定其中的某些数增加$k$，尝试让该数列变为非严格递增$or$单调不减数列，如果可以则输出YES，否则输出NO。

1. 由于选中某些数并将它们增加$k$，并不会改变它们本来的大小关系，那么很显然，将所有需要增加k的数按照原顺序放在一个数组中，该数组只能单调不减，否则输出NO。
2. 将数列分为若干个最长的连续的递增数列（可以仅含一个元素），也就是在每次出现递减的地方作分割，设 $a_i>a_{i+1}$，那么就在$i$处分割，同时右边的连续子序列的前缀需要增加至少$k=a_i-a_{i+1}$。

思路：

这里直接将贪心的方法：对于每处 $a_i>a_{i+1}$，我们记录$k$至少为多少，即 $k=\max(a_i-a_{i+1})$，逆序遍历数组$a$，如果 $a_i+k<=a_{i+1}$，那么我们就令$a_i=a_i+k$。显然，最后一个元素$a_n$增加$k$是更优的。
在此过程中，如果存在$a_i>a_{i+1}$，则无法满足条件，输出NO，否则输出YES。
不严谨证明：
上述过程实际上为，对于一个元素$a_i$，能增加$k$就增加。由于是倒序，遍历到$a_i$时，我们能够保证$a_i$为这一处可能的最大值，从而让左侧的数据更有可能实现增序列。（简单说就是要让右边的数越大，越有可能变成增序列）
为什么取最小的$k$：取最小的$k$能够保证，在尝试实现增数列的同时，最大化可增加$k$的$a_i$的个数，减少增加$k$后大于右侧数的可能性。

复杂度$O(n)$

这里给出了逆序和顺序两个版本：

Code

//逆序版本
void sol()
{
    int n;
    cin>>n;
    bool ans=1;
    int mink=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(i==1)continue;
        if(!ans)continue;
        if(a[i-1]>a[i])mink=max(mink,a[i-1]-a[i]);
    }
    a[n+1]=MAX;
    for(int i=n;i>=1;i--)
    {
        if(a[i]+mink<=a[i+1])
        {
            a[i]+=mink;
        }
        if(a[i]>a[i+1])
        {
            ans=0;
            break;
        }
    }
    if(ans)cout<<"YES\n";
    else cout<<"NO\n";
}

//顺序版本（仅循环处）
for(int i=2;i<=n;i++)
{
    if(a[i-1]>a[i])
    {
        if(a[i-1]<=a[i]+mink)
        {
            a[i]+=mink;
        }
        else
        {
            ans=0;
            break;
        }
    }
}

补题

C

问题陈述

在探索互联网深处时，花栗鼠西奥多发现了一个非常有趣的正整数序列，于是决定玩一玩。
在一次操作中，他选择了序列中的一个元素，并执行了以下操作：

• 如果所选元素是偶数，它就除以 2。
• 如果选择的元素是奇数，它就将其增加 1。

西奥非常喜欢平等，所以他想让数列中的所有数字都相等（否则，有些数字可能会感到不舒服）。因为他需要计划午餐时间，所以帮他确定使所有数字相等所需的最少运算次数。

分析：

对于一个数x进行以下操作：

• 若x为偶数，则除以2
• 若x为奇数，则加1。

目的是让数列中所有数都相等，求最小操作次数。

思路：

显然这个数字最终的路径一定是... -> 2 -> 1 ，而且变化的路径是固定的。
我们对于每个数$a_i$，将它变成1的路径放入$S_i$序列中，设$S_i$长度为$L_i$，则操作次数为$L_i-1$。
我们将所有$S_i$相同的后缀去掉，因为这些去掉的数就是重复路径，那么我们只需要留下去掉的序列中最前面的数即可，然后就可以统计答案了。

• 设去掉的重复路径长度为$x$，则$ans=(\sum L)-x\times n$。

这时我们提交会发现WA了…

！！！由于1过于特殊，它的变化为1 -> 2 -> 1 -> ...，我们单独讨论数组$a$中含有1的情况。对于含有1的数组，最终变成的相同数一定是1或者2。

• 如果变成1，那么$ans=\sum L_i$。
• 如果变成2，那么 $ans=(\sum L_i)-1\times n+2\times sum_1$ 。

对于第二条的解释：我们将所有$S_i$最后的1去掉，减少一次操作，得到$(\sum L_i)-n$，但对于$a_i=1$处，我们应该增加一次操作，而不是减少一次操作，因此需要额外补充两倍的1的个数，即$sum_i$。

复杂度略大于$O(n\log a_{max})$

Code

void sol()
{
    int ans1=0,sum1=0;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==1)
        {
            sum1++;
        }
        cnt[i]=0;
        while(a[i]>1)
        {
            lst[i][++cnt[i]]=a[i];
            if(a[i]%2)
            {
                a[i]++;
            }
            else a[i]>>=1;
            ans1++;
        }
        lst[i][++cnt[i]]=1;
    }
    if(sum1)
    {
        ans1=min(ans1,ans1-n+2*sum1);
        cout<<ans1<<'\n';
        return;
    }
    int x=0;
    while(cnt[1])
    {
        int sm=lst[1][cnt[1]];
        cnt[1]--;
        bool fg=0;
        for(int i=2;i<=n;i++)
        {
            if(sm!=lst[i][cnt[i]])
            {
                fg=1;
                break;
            }
            cnt[i]--;
            if(cnt[i]<0)
            {
                fg=1;
                break;
            }
        }
        if(fg)break;
        x++;
    }
    x--;
    ans1=ans1-x*n;
    cout<<ans1<<'\n';
}