2022牛客多校·第七场（J.DP,K.博弈+莫队）

周一有robocom，所以这场比赛就随便乱打了，前一个小时签到，打完回来再写一个走人。

不过其他题还是挺不错的，例如本场的J,K，待补，这里先放上ygg的题解：2022牛客暑期多校训练营7 个人题解 更新至5题。

C.Constructive Problems Never Die（构造）

题意：给你一个长度为$n$的数组$a$，求构造一个$1...n$的排列$P$使得对于任意的$i$都满足$a_i\neq P_i$，不能则输出NO。

思路：经过长期cf的训练，这个题还是能秒的，不过有点乱一直在debug...
首先判断什么时候是NO，那当然是全部一样的时候，其他都是YES。
我们对$a$进行从小到大排序，例如$\lbrace 3,2,1\rbrace$我们首先变成$\lbrace 1,2,3\rbrace$，那么如果想让更多的冲突（相等），那么我也对于这几个进行填入答案$\lbrace 1,2,3\rbrace$，但是我这里需要不冲突，所以我需要错一位变成$\lbrace 2,3,1\rbrace$，现在按照原来的下标填入原来的则为$\lbrace 1,3,2\rbrace$。

那么其他情况呢？例如$a[] = \lbrace 1,1,4,5,4,4\rbrace$，经过排序变成$\lbrace 1,1,4,4,4,5\rbrace$，经过错位应该填入$\lbrace2,3,4,5,6,1\rbrace$，填入原来的则变成：
$$
\lbrace 1,1,4,5,\underline{4},4\rbrace \Rightarrow \lbrace 2,3,5,1,\underline{4},6\rbrace
$$

这个时候可以发现有冲突的$4$，那么这时候扫一遍找到一个满足不冲突的即可，交换一下就好。

那么还有其他情况吗？当然是有的，还有其他多个冲突的时候。这个时候就需要在冲突的里面再错位一下即可。

代码：

struct node
{
    int v,id;
    node(int _x,int _y):v(_x),id(_y){}
    node(){}
}a[N];
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i].v;
        a[i].id = i;
    }
    sort(a+1,a+1+n,[](const node& a,const node& b){return a.v<b.v;});
    if (a[1].v==a[n].v) {cout<<"NO"<<endl;return;}
    cout<<"YES"<<endl;
    for (int i=1;i<n;i++)
        ans[a[i].id] = i+1;
    ans[a[n].id] = 1;
    vector<int> v;
    for (int i=1;i<=n;i++)
        if (ans[a[i].id]==a[i].v)
            v.push_back(a[i].id);
    m = v.size();
    if (m==1)
    {
        x = v[0];
        for (int i=1;i<=n;i++)
        {
            if (ans[x]==a[i].v) continue;
            swap(ans[x],ans[a[i].id]);
            break;
        }
    }
    else if (m>0)
    {
        x = ans[v[0]];
        for (int i=0;i<m-1;i++)
            ans[v[i]] = ans[v[i+1]];
        ans[v[m-1]] = x;
    }
    sort(a+1,a+1+n,[](const node& a,const node& b){return a.id<b.id;});
    for (int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    cout<<endl;
}

F.Candies（双端队列deque）

题意：给你一个长度为$n$的环形数组$a$，以及一个数$k$你可以选择其中任意两个相邻数$u,v$的若满足条件即可相消除：

• 若$u,v$满足$u=v$
• 若$u,v$满足$u+v=k$

求能够消除的最大个数

思路：
这里没有证明，只是随便举了些例子表示就按任意顺序先后取，最后都是一样的，我后面一想不难理解，如果有连续的$u,u,k-u,u$无论是先$u,u$相撞还是$k-u,u$相撞都不改变个数。

那么这个题就跟上周的AcWing周赛很像了，总结链接在这——（填坑）

我用双端队列模拟，每次来一个数则比较队列的队首dq.front()，如果能与之消除那就dq.pop_front()就不用进队的；不能的话则需要进队。

    deque<int> dq;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        if (!dq.empty()&&(dq.front()==x||dq.front()+x==k)) dq.pop_front();
        else dq.push_front(x);
    }

我用到了环形吗？没有，那么这一路下来我再比较首尾，这样就是环形了，直到dq.size()<2就结束，因为有可能你取的front和back是一个数，这样肯定是不行的。

    while (dq.size()>=2&&(dq.front()==dq.back()||dq.front()+dq.back()==k))
    {
        dq.pop_back();
        dq.pop_front();
    }

代码：代码就是上面啦，最后输出cout<<(n-dq.size())/2;即可。

G.Regular Expression（正则表达式，思维）

题意：给你一个原串$s$，询问用正则表达式能表示的最短长度以及该长度有多少个字符串。

正则表达式中的*，+，？，^ ， $，范围和次数用法

思路：主要注意.*，这就可以表示所有。.表示任意一个字符，*表示前面有任意个。例如现在有s="carry"，那么我也可以用.*表示，这时候其实是.....，然后由.变成carry。

然后就是分情况，全部一样，长度只有1，长度为2，其他。

代码：

inline void Case_Test()
{
    cin>>s;
    n = s.size();
    if (n==1) {cout<<1<<" "<<2<<endl;return;}
    if (n==2)
    {
        if (s[0]==s[1]) cout<<2<<" "<<8<<endl;
        else cout<<2<<" "<<6<<endl;
    }
    else
    {
        bool ok=true;
        for (auto c:s) if (c!=s[0]) ok=false;
        if (ok) cout<<2<<" "<<4<<endl;
        else cout<<2<<" "<<2<<endl;
    }
}