四糸智乃

2021-11-13 11:36 已编辑深信服_算法工程师

关注

【题解】2021牛客OI赛前集训营-提高组（第五场）

T1智乃的差分

Tag：排序、构造、分情况讨论

20pt

比较想当然的写法，当 ${x>0}$ 时降序， ${x<0}$ 时升序。（没有考虑还有0这种特殊情况）

20pt

全排列枚举，检查差分数组中是否出现x即可

100pt

其实细节比较多，你要考虑x是否为非0。

先按照x的大小分成三种情况

x>0

当x>0时，有一种特殊情况，就是x正好等于最大值，且最小值为0的情况。这个时候无论直接升序还是降序都不能满足条件，这个时候可以拿出一个非0且非x的其他数字放在第一位，然后放最大的数字，剩下的就可以随便放了。

否则不是这种特殊情况的你就可以直接降序排序输出。

x=0

当x=0时问题可以转化成：0不能放第一个，并且任意两个相同数字不能相邻，这其实是一个经典的鸽巢问题，即只要出现次数最多的数字不多于一半即可。

但是实际构造的过程中可以借助一个优先队列，每次都出队当前次数最多的数字即可。

x<0

因为输入的数组全部为非负整数，所以x<0时最简单，直接升序输出即可。

但是实际上你代码完全不用写的这么麻烦，你只用尝试一下升序、降序、相邻不相同这三种方法是不是有一种可行，如果三种都不可行，说明无解。

时间复杂度 ${O(NlogN)}$ ，空间复杂度 ${O(N)}$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int n,x,T;
int a[MAXN],b[MAXN],c[MAXN],ex[MAXN];
unordered_map<int,int>mp;
priority_queue<pair<int,int> >q;
bool check(int *arr)
{
    for(int i=1;i<=n;++i)
    {
        if(arr[i]-arr[i-1]==x)
        {
            return false;
        }
    }
    return true;
}
int get_next(int val)
{
    if(q.empty())return false;
    pair<int,int> now=q.top();
    if(now.second==val)
    {
        q.pop();
        if(!q.empty())
        {
            pair<int,int> now2=q.top();
            q.pop();
            now2.first--;
            if(now2.first)
            {
                q.push(now2);
            }
            q.push(now);
            return now2.second;
        }
        else
        {
            q.push(now);
            return -1;
        }
    }
    else
    {
        q.pop();
        now.first--;
        if(now.first)
        {
            q.push(now);
        }
        return now.second;
    }
    return -1;
}
bool greed()
{
    mp.clear();
    while(!q.empty())
    {
        q.pop();
    }
    for(int i=1;i<=n;++i)
    {
        mp[a[i]]++;
    }
    for(auto &it:mp)
    {
        q.push(make_pair(it.second,it.first));
    }
    for(int i=1;i<=n;++i)
    {
        int temp=get_next(ex[i-1]);
        if(temp==-1)return false;
        ex[i]=temp;
    }
    return true;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d",&n,&x);
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&a[i]);
            c[i]=b[i]=a[i];
        }
        sort(b+1,b+1+n);
        sort(c+1,c+1+n,[](const int &A,const int &B){return A>B;});
        if(check(b))
        {
            printf("yes\n");
            for(int i=1;i<=n;++i)
            {
                printf("%d%c",b[i],i==n?'\n':' ');
            }
        }
        else if (check(c))
        {
            printf("yes\n");
            for(int i=1;i<=n;++i)
            {
                printf("%d%c",c[i],i==n?'\n':' ');
            }
        }
        else if(x==0 && greed() && check(ex))
        {
            printf("yes\n");
            for(int i=1;i<=n;++i)
            {
                printf("%d%c",ex[i],i==n?'\n':' ');
            }
        }
        else
        {
            printf("no\n");
            /*
            cout<<"----test----"<<endl;
            cout<<n<<" "<<x<<endl;
            for(int i=1;i<=n;++i)
            {
                printf("%d%c",a[i],i==n?'\n':' ');
            }
            */
        }
    }
    return 0;
}

/*
10
10 0
7 2 6 2 5 2 4 2 3 2
*/

T2牛牛的旅行

Tag：并查集、排序

30pt

暴力枚举两个端点，爬lca即可。

另10pt 单链

如果树退化为单链，也就是在数组上解这个问题，所以可以对数组做一个线段树实现一个下标RMQ（下标极大值查询）操作，每次取当前数组区间的最大值，然后这样如果左端点来自数组区间的左侧，右端点来自数组区间的右侧，则这些区间的极大值都是当前查询的RMQ，然后一旦处理完所有跨过当前区间RMQ的子数组，就可以将数组断成左右两个部分，递归分治即可。

另10pt 所有数字均相同

这个点的作用是提醒你，题目中的式子 ${\sum _{s \neq t}happy(s,t)}$ 可以拆解为 ${\sum _{s \neq t}val_{max}}$ 和 ${\sum _{s \neq t}-len(s,t)}$ 独立的两部分，分别求解。

对于第一部分，因为所有数字都相同，实际上它就是 ${n\times (n-1)\times val_{max}}$ 。

对于第二部分，我们可以通过“计算每一条边出现在所有路径中的次数”计算得到。

如图所示，我们可以预处理出子树的大小size[x]，假设遍历到图中红色的边，需要计算图中红色的边在整颗树种出现的贡献，这个贡献的大小就是size[x]*(n-size[x])。

100pt

这个题其实有点诈骗的意思，如果学树分治或者树DP学傻了可能往这两个方向去想就偏了，实际上这就是一个简单计算树上点、边贡献的题。

首先根据之前的sub task说的步骤拆解为 ${\sum _{s \neq t}val\_{max}}$ 和 ${\sum _{s \neq t}-len(s,t)}$ 独立的两部分，分别求解。

对于第二部分的求解，和另10pt中的方法一致，这里不再过多阐述。

对于第一部分，这里我们其实可以借助单链部分的一些思想。然后这个时候可能有人会觉得，这不是树分治么？

确实，诚然树分治确实可以解决问题，但是对于本题这样做费力又不讨好，我们只用一点点树分治的思想（具体来说是分治思想）即可。

首先对于每一个节点，我们提出一个“影响域”的概念，这个影响域是指域内所有点的点权均不大于当前计算贡献的节点x在树上形成的联通块。例如上面的例子中x点的点权是10，它形成的连通块就是蓝***域，对于蓝***域中，所有跨节点x的树上路径，其最大值一定为x，所以贡献的计算公式就是x乘上跨x的路径数，设当前影响域的大小为size[x]，与x直接相邻的节点在影响域中的子树为son[y]，这个贡献就是 ${(size[x]-size[son[y]])\times size[son[y]]}$ 。

由于树结构不是均分的，所以递归求解的复杂度不对，而且递归从上到下不好维护“影响域”，所以可以采用“时光倒流法”，把节点从小到大排序，然后依次加入合并影响域，用并查集维护影响域的尺寸即可。

时间复杂度 ${O(NlogN)}$ ，空间复杂度 ${O(N)}$ 。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
const long long mod=1e9+7;
int fa[MAXN];
int findf(int x)
{
    return fa[x]==x?x:fa[x]=findf(fa[x]);
}
long long siz[MAXN],sum[MAXN],ans,tsize[MAXN],n;
int u,v;
vector<int> G[MAXN];
bool vis[MAXN];
void unions(int x,int y)
{
    if(findf(x)!=findf(y))
    {
        siz[findf(y)]+=siz[findf(x)];
        fa[findf(x)]=findf(y);
    }
    return;
}
struct node
{
    int id;
    long long val;
}a[MAXN];

void dfs(int x,int pre)
{
    tsize[x]=1;
    for(auto &i:G[x])
    {
        if(i!=pre)
        {
            dfs(i,x);
            tsize[x]+=tsize[i];
            ans-=tsize[i]*(n-tsize[i])%mod;
            if(ans<0)ans+=mod;
        }
    }

}
int main()
{

    scanf("%lld",&n);
    assert(2<=n&&n<=1000000);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld",&a[i].val);
        a[i].id=i;
        fa[i]=i;
        siz[i]=1;
    }

    for(int i=1;i<n;++i)
    {
        scanf("%d %d",&u,&v); 
        assert(u!=v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs(1,0);

    sort(a+1,a+n+1,[](const node &A,const node &B){return A.val<B.val;});

    for(int i=1;i<=n;++i)
    {
        for(auto &j:G[a[i].id])
        {
            if(vis[j])
            {
                ans+=a[i].val*siz[findf(a[i].id)]%mod*siz[findf(j)]%mod;
                if(ans>=mod)ans-=mod;
                unions(a[i].id,j);
            }
        }
        vis[a[i].id]=true;
    }
    printf("%lld\n",ans*2%mod);
    return 0;
}
/*
2
1 1
1 2

4
1 5 1 1
1 2
2 3
2 4
*/

T3

Tag：dfs、动态规划、矩阵乘法、前缀和

这个题的本质是一类DAG图上K短路问题，但是如果我叫它“k短路”它就超纲了。这个题换个角度讲，它叫“dfs利用动态规划进行剪枝”。它就变成dfs，DAG图，动态规划，矩阵乘法，它就都不超纲了。我建议是不要太相信这个东西，稍微多学一点总是没坏处的。

20pt

puts("-1")

别想了，正赛不会给你这么高的。

10~50pt

暴力搜，大力搜。

这40pt包括前30%的测试点以及x=0的情况（实际上x=0既然没限制就全填'P'就好了，因为'P'的字典序最大），所以一般来讲，纯暴力都能搜到这40分，然后加上一个-1档可以拿到50分

50~100pt

提到K短路，你会想到用一个假的或者不准的贪心算法去对暴力进行一个剪枝的操作，也就是写一个贪心搜索，或者A*之类的启发式搜索。

但是贪心有个问题，就是贪心的界不是很好控制，如果贪心的界收缩的很小，甚至收缩过头，就可能导致WA，反之如果贪心过于宽泛没有有效剪枝，就可能TLE。

但总之，在OI制下你采取这种办法都是“没有办法的办法”，属于有点骗分的算法。

我这个题的本意就是给选手一些乱搞的空间，但是真正的联赛未必会这样给，反正我是认为乱搞也是选手实力的一部分体现。（这个观点并不是所有人都认可）

100pt

从那种“贪心剪枝搜索”的思路过来，我们发现这个算法有问题的原因在于，贪心对于候选分支的权值预测不准，它并不是真正搜过去以后能够获得的权值。

假设，现在有一种理想算法，它可以预测当前搜索到的部分结果往下任意答案中权值最大的答案是多少，那是不是这个暴力算法用正确的权值剪枝之后，正确性和时间复杂度都对了？

好像是这个道理，假设我们能用O(1)的时间预判出当前搜索状态向下延伸的任意解中解的最大值是多少，那么显然用这个剪枝之后首先正确性能得到保证，其次，因为这样每次枚举到合法解的复杂度变为 $O(N)$ ，那么就可以暴力枚举k次找到第k个符合条件的解，所以复杂度上限就是 ${O(N \times K)}$ 。

这个“理想算法”是什么呢，它其实就是变形后的矩阵乘法。

我们知道，矩阵乘法可以表示一些求和类的动态规划转移方程，实际上对于max,min类的动态规划，它也是可以表示的。

由于max，min运算对于加减运算具有结合律，即存在 $max(a\pm b,a\pm c)=a\pm max(b,c)$ ，所以可以构造矩阵运算

$(A\times B)[i][j]=MAX_{k=0}^{N-1}(A[i][k]+B[k][j])$

然后本题可以讲动态规划转移方程改写为矩阵形式，虽然动态规划本身不支持修改和变化，但是将其表示成矩阵就可以带修了。

我们求一个后缀的矩阵连乘，然后搜索到的部分可以维护一个头矩阵，可以不维护，直接把数字加上去。这样就能够O(1)实现这个理想的预判算法，然后用这个预判算法对dfs进行剪枝，就得到了 ${O(N\times K)}$ 的复杂度求解DAG图k短路。

时间复杂度 ${O(N\times K)}$ ，空间复杂度 ${O(N)}$

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1005;
const long long INF=(1LL<<60);
const int MAX_MAT=4;
long long x;
int n,k,cnt;
bool flag;
char s[MAXN],t[MAXN];
int is[MAXN],it[MAXN];
const int order[4]={4,2,1,3};
struct Mat
{
    long long a[MAX_MAT][MAX_MAT];
    Mat()
    {
        for (int i = 0; i < MAX_MAT; ++i)
        {
            for (int j = 0; j < MAX_MAT; ++j)
            {
                a[i][j] = -INF;
            }
        }
        for (int i = 0; i < MAX_MAT; ++i)
        {
            a[i][i] = 0;
        }
    }
    long long query(int row)
    {
        long long ret=-INF;
        for(int i=0;i<MAX_MAT;++i)
        {
            ret=max(ret,a[row][i]);
        }
        return ret;
    }
}suf[MAXN],base[5],head[4];
Mat operator * (Mat x, Mat y)
{
    Mat c;
    for (int i = 0; i < MAX_MAT; ++i) {
        for (int j = 0; j < MAX_MAT; ++j) {
            c.a[i][j] = -INF;
        }
    }
    for (int i = 0; i < MAX_MAT; ++i) {
        for (int j = 0; j < MAX_MAT; ++j) {
            for (int k = 0; k < MAX_MAT; ++k) {
                c.a[i][j] = max(c.a[i][j], x.a[i][k] + y.a[k][j]);
            }
        }
    }
    return c;
}
void debug_print_mat(const Mat &A)
{
    for(int i=0;i<MAX_MAT;++i)
    {
        for(int j=0;j<MAX_MAT;++j)
        {
            cout<<A.a[i][j]<<" ";
        }
        cout<<endl;
    }
    return;
}
int _(char C)
{
    switch (C)
    {
        case '?':
            return 0;
        case 'N':
            return 1;
        case 'O':
            return 2;
        case 'I':
            return 3;
        case 'P':
            return 4;    
        default:
            assert(0);
    }
    return -1;
}
void dfs(int deep,long long val)
{
    if(deep==n+1)
    {
        if(val>=x)
        {
            if(++cnt==k)
            {
                flag=true;
            }
        }
        return;
    }
    if(s[deep]=='?')
    {
        for(int i:order)
        {
            if(!flag&&val+(deep==1?0:base[0].a[it[deep-1]-1][i-1])+(head[i]*suf[deep+1]).query(i-1)>=x)
            {
                t[deep]="NOIP"[i-1];
                it[deep]=i;
                dfs(deep+1,val+(deep==1?0:base[0].a[it[deep-1]-1][i-1]));
            }
        }
    }
    else
    {
        t[deep]=s[deep];
        it[deep]=is[deep];
        dfs(deep+1,val+(deep==1?0:base[0].a[it[deep-1]-1][it[deep]-1]));
    }
}

int main()
{
    scanf("%d %lld %d",&n,&x,&k);
    scanf("%s",s+1);
    for(int i=0;i<4;++i)
    {
        for(int j=0;j<4;++j)
        {
            scanf("%lld",&base[0].a[i][j]);
        }
    }
    for(int i=1;i<=4;++i)
    {
        base[i]=base[0];
        for(int j=0;j<4;++j)
        {
            for(int k=0;k<4;++k)
            {
                if(k!=i-1)
                {
                    base[i].a[j][k]=-INF;
                    head[i].a[j][k]=-INF;
                }
                else
                {
                    head[i].a[j][k]=0;
                }
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        is[i]=_(s[i]);
    }
    for(int i=n;i>1;--i)
    {
        suf[i]=base[_(s[i])]*suf[i+1];
    }
    /*
    debug_print_mat(suf[n-1]);
    cout<<"max first char of NOIP:"<<endl;
    cout<<(head[1]*suf[2]).query(0)<<endl;
    cout<<(head[2]*suf[2]).query(1)<<endl;
    cout<<(head[3]*suf[2]).query(2)<<endl;
    cout<<(head[4]*suf[2]).query(3)<<endl;
    */

    dfs(1,0);
    printf("%s\n",flag?t+1:"-1");
    /*
    cout<<"all mat :"<<endl;
    debug_print_mat(suf[1]);
    for(int i=0;i<=4;++i)
    {
        cout<<"-------------"<<endl;
        cout<<"the NOIP["<<i<<"]"<<endl;
        debug_print_mat(base[i]);
    }
    */
    return 0;
}
/*
10 0 1
??????????
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 10


4 3 108
????
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

4 3 109
????
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0

2 10 6
??
0 0 10 0
10 10 0 0
10 0 10 10
0 10 10 0
*/

T4牛牛的border

Tag：字符串、并查集、数学

20pt

按照题意模拟，大力搞

30pt

枚举子串的头部，然后求kmp可以线性求出所有头部相同子串的所有border，然后dp一下即可。

另10pt

直接计算答案，全a时是一个等差数列求和乘以子串出现次数的贡献式子。

另10pt

根据border的定义，border它是一个字符串的前后缀自我匹配，换句话说就是字符串的子串至少要出现2次，它才有可能成为一个border。即，重复出现2次，并且出现在头部和尾部的才是border，我们想，在随机字符串的情况下，字符串越长，它们相同的概率就越低，它是一个关于 $(\frac{1}{26})^{len}$ 的等比数列的概率形式，然后你可以估算一个值，比如说是50（实际上远远小于这个值），通过数学计算，随机字符串中出现长度为50的重复子串的概率大概为 ${1.7^{-71}}$ ,它是一个不可能事件。就是说随机数据下，不可能产生长度为50的随机子串。

我们可以这么想，既然要求所有子串的border，我们不直接计算子串的border，而是反过来枚举所有子串看每个字符串能成为多少个子串的border。

比如这个"abaccababa"，假设我们现在想计算"aba"能在多少个字符串中成为一个border，那么首先我们知道aba在原串中出现了3次，那么一前一后两个相同的字符串一头一尾可以组成一个字符串的border，所以这里的贡献就是C(3,2)=3，然后乘以长度3，对答案的影响就是9。

好了，因为我们知道在随机情况下这个长度不会大于50，所以按照30pt中的算法，暴力kmp，每次处理到50即可，时间复杂度 ${O(50N)}$ 。

100pt

从上面另10pt的思路中，我们知道这个题实际上就是反过来计算每个子串能够成为多少个字符串的border，相当于我们要枚举所有的子串，求子串的出现次数。这里可以借助后缀数组进行一个后缀排序。

对于字符串，有一个重要等式：子串=后缀的前缀（有的时候也会用到前缀的后缀）。

所以我们先观察一下字符串的后缀排序。

比如这个ab串，它这个后缀排序很有意思，我们根据他们相同的前缀划分区间。

比如说长度为1的字符串有a,b，那么第一层第一个区间就是1~7，表示a，第二个区间就是8~14表示b。

长度为2的字符串有aa,ab,ba,bb,那么第二层就有四个区间，分别是2~2表示aa,3~7表示ab，8~12表示ba，13~14表示bb。

可以划分出一个“类二叉树”结构。（其实它也是后缀树的一种表现形式）。如果你把一开始分成"a"和"b"的部分前面补一个根节点的话其实可以很形象的把它理解成二叉树。

如果不是ab串，而是a~z呢，它就是26叉树咯。

然后问题就转化成了对于树上每个节点的贡献=树节点深度*节点所覆盖的区间长度。

然后这个问题发现树不好从根往下建，不好维护每个节点的覆盖区间。

但是发现如果从叶节点倒退回来合并，问题就变得非常简单，因为有个叫height的数组，储存了后缀排序后每个字符串与他下面字符串的lcp，所以倒推回来，只要在 ${i==height[x]}$ 的时候合并x与他下面的字符串就可以了。

然后过程中维护这个所谓“后缀树”的节点信息即可。

当然，本题也可以使用真的后缀树来做，只需要遍历后缀树的节点即可。

时间复杂度 ${O(NlogN)}$ ，空间复杂度 ${O(N)}$

#include<bits/stdc++.h>
using namespace std;
const int MAXN=500005;
//以下为倍增算法求后缀数组
int wa[MAXN],wb[MAXN],wv[MAXN],Ws[MAXN];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
/**< 传入参数：str,sa,len+1,ASCII_MAX+1 */
void da(const char r[],int sa[],int n,int m)
{
      int i,j,p,*x=wa,*y=wb,*t;
      for(i=0; i<m; i++) Ws[i]=0;
      for(i=0; i<n; i++) Ws[x[i]=r[i]]++;//以字符的ascii码为下标
      for(i=1; i<m; i++) Ws[i]+=Ws[i-1];
      for(i=n-1; i>=0; i--) sa[--Ws[x[i]]]=i;
      /*cout<<"SA"<<endl;;
      for(int i=0;i<n+1;i++)cout<<sa[i]<<' ';*/
      for(j=1,p=1; p<n; j*=2,m=p)
      {
            for(p=0,i=n-j; i<n; i++) y[p++]=i;
            for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
            for(i=0; i<n; i++) wv[i]=x[y[i]];
            for(i=0; i<m; i++) Ws[i]=0;
            for(i=0; i<n; i++) Ws[wv[i]]++;
            for(i=1; i<m; i++) Ws[i]+=Ws[i-1];
            for(i=n-1; i>=0; i--) sa[--Ws[wv[i]]]=y[i];
            for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)
                  x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
      }
      return;
}
int sa[MAXN],Rank[MAXN],height[MAXN];
//求height数组
/**< str,sa,len */
void calheight(const char *r,int *sa,int n)
{
      int i,j,k=0;
      for(i=1; i<=n; i++) Rank[sa[i]]=i;
      for(i=0; i<n; height[Rank[i++]]=k)
            for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
      // Unified
      for(int i=n;i>=1;--i) ++sa[i],Rank[i]=Rank[i-1];
}

void cal_all(char str[])
{
      int len=strlen(str);
      da(str,sa,len+1,130);
      calheight(str,sa,len);
}
char s1[MAXN];
vector<int>pos[MAXN];
int n;
long long cal(long long x)
{
    return x*(x+1)/2;
}
long long deff()
{
    long long ret=0;
    for(long long i=1;i<=n;++i)
    {
        ret+=i*(n-i+1);
    }
    return ret;
}
long long ans,nowval;
int fa[MAXN],sz[MAXN];
bool vis[MAXN];
int findf(int x)
{
    return x==fa[x]?x:fa[x]=findf(fa[x]);
}
void unions(int x,int y)
{
    if(findf(x)!=findf(y))
    {
        sz[findf(y)]+=sz[findf(x)];
        fa[findf(x)]=findf(y);
    }
    return;
}
int main()
{
    /*
    freopen("10.in","r",stdin);
    freopen("10.out","w",stdout);
    */
    scanf("%d%s",&n,s1);
    cal_all(s1);
    for(int i=0;i<=n+1;++i)
    {
        pos[i].clear();
        fa[i]=i;
        sz[i]=1;
        vis[i]=false;
    }
    for(int i=1;i<=n;++i)
    {
        pos[height[i]].push_back(i);
    }
    for(int i=n;i;--i)
    {
        vis[sa[n-i+1]]=true;
        nowval++;
        for(auto &it:pos[i])
        {
            nowval-=cal(sz[findf(it)]);
            nowval-=cal(sz[findf(it-1)]);
            unions(it,it-1);
            nowval+=cal(sz[findf(it)]);
        }
        ans+=nowval*i;
    }
    printf("%lld\n",ans-deff());
}