四糸智乃

2021-10-13 22:01 深信服_算法工程师

关注

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

T1牛牛数三角形

Tag：简单数学

25pt

按照题意模拟，二维数组打表直接输出答案。

50pt

通过找规律或者数学的方式可以将第x行第y列拆解成一个关于x的等差数列求和的形式，然后因为数组从上到下从左到右是0到9循环。所以其实就是对10取余数后的结果。然后直接开一个long long类型计算即可。

100pt

在50pt的基础上，发现N非常大会爆掉long long，然后由于对10取余的模系下，2无乘法逆元，所以可以采取以下几种方式处理：

1、利用快速幂的方式实现一个快速乘。

2、等差数列求和公式中 ${n\times (n-1)}$ 这一项中必有一个偶数，所以可以先把2给除下去。

std中采取的是第二种方式（即temp1和temp2这两个变量的奇偶性互逆，当一者为奇数时，另一者就必定为偶数）

时空复杂度 ${O(1)}$

#include<bits/stdc++.h>
using namespace std;
long long n,x,y;
const long long mod=10;
int main()
{

    scanf("%lld %lld %lld",&n,&x,&y);
    long long delta=0;
    long long temp1 = (n<<1)-x+2;
    long long temp2 = x-1;
    if(temp1&1)temp2>>=1;
    else temp1>>=1;
    delta=(temp1%mod*temp2%mod)%mod;
    printf("%lld\n",((delta+y-1)%mod+mod)%mod);
    return 0;
}

T2牛牛的四则运算

Tag：模拟、排序

30pt

30pt一般是写炸了，比如用字符数组存储了答案并且数组大小开了正好的 ${10^6}$ 。

另10pt

10pt这个点的用意是为了提醒选手，不必储存输出内容，直接遍历输入的字符串，碰到"+-"号的时候就输出一个[++cnt]即可。

100pt

这个题的本质是一个结构体排序问题，首先把输入数据中所有的符号取出来，然后建一个{下标、优先级}的结构体数组，进行一个结构体排序，然后对每个符号赋一个计算顺序的值，最后排序回来输出即可。

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

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
struct node
{
    int id,***ode(){}
    node(int _id,int _v,int _p)
    {
        id=_id;
        v=_v;
        p=_p;
    }
}a[MAXN];
int tot,n;
char s[MAXN];
int main()
{
    scanf("%d %s",&n,s);
    assert(strlen(s)==n);
    for(int i=0;s[i];++i)
    {
        switch (s[i])
        {
            case '+':
            case '-':
                a[++tot]=node(i,0,0);
                break;
            case '*':
            case '/':
                a[++tot]=node(i,0,1);
        }
    }
    sort(a+1,a+1+tot,[](const node &A,const node &B){
        if(A.p!=B.p)return A.p>B.p;
        return A.id<B.id;
    });
    for(int i=1;i<=tot;++i)
    {
        a[i].v=i; 
    } 
    sort(a+1,a+1+tot,[](const node &A,const node &B){
        return A.id<B.id;
    });
    tot=0;
    for(int i=0;s[i];++i)
    {
        printf("%c",s[i]);
        switch (s[i])
        {
            case '+':
            case '-':
            case '*':
            case '/':
                printf("[%d]",a[++tot].v);    
        }
    }
    return 0;
}

T3牛牛的灯笼

Tag：树状数组、sort、前缀和、思维

从T3开始上难度了，这个问题的本质是一个双重限制条件的一维数点问题，但是只要逐步拆解限制条件，并不是一道很难的题目。

用到的trick比较多，比如使用前缀和的差值表示一段区间，利用单调性预处理限制区间等。

题目的主体部分其实只用一个离线的树状数组就解决了。

10~30pt

纯暴力，如果是写的 ${O(N^{3})}$ 的算法则有可能被卡常。除此之外还有用std::set维护种类数的 ${O(N^{2}logN)}$ 算法，但是实际上可以利用单调性优化到 ${O(N^{2})}$ ，这里我没有进行数据分段（因为这几个算法本质都是暴力，实际上在 ${10^3}$ 数量级下差距不大，拉不开差距）

30pt

直接讲最快的 ${O(N^{2})}$ 的算法，我们考虑题目中的两个限制条件

权值和大于 ${X}$
种类数小于 ${M}$

因为数字有正有负，1不具备单调性，但是1可以用前缀和来维护，换句话说就是给定l，r，可以 ${O(1)}$ 的复杂度知道sum(l,r)。

对于限制2，当区间左端点l固定时，随着r端点向右扩展，包括颜色的种类数一定是单调递增的。所以对于每一个l，直接向右滑动，直到发现颜色的种类数多余M就break即可。

维护颜色可以使用一个桶数组维护颜色出现的次数，当发现桶数组中某个颜色出现的次数从0变为1时，就记录cnt++。

对于桶数组的声明方式，在c语言下有一个小trick，就是比如你想用数组的负数下标，可以这样。

int base[MAXN*2];
int *a=base+MAXN;

这样就相当于开了一个a数组，并且a数组的有效下标是 ${[-MAXN,MAXN)}$ 左闭右开区间。

另30pt

我这里分的3个另10pt其实都是提示性的测试点，大家打比赛的时候注意子任务subtask除了部分得分的作用以外，有一些是具有引导性的，但是也不一定都是正向的引导，有些就比较偏，还是需要自己斟酌一下。

1.另10pt M=N

当M=N时，限制1不生效，题目转化成求区间和大于X的区间数目。

因为区间和可能很大，不好维护（维护起来要离散化），我们转换思路，首先构造一个结构体{前缀和,下标}，然后按照前缀和的顺序排序。

换句话说就是先求的前缀和数组，然后把前缀和数组绑定下标后，按照前缀和的大小进行排序。

这样排序后，右侧的前缀和的值一定大于左侧，取原数组的一段区间可以视为是在前缀和数组中去取两个元素。

问题转化成给一个有序数组，任取两个元素的差值大于X。

你发现转化后的问题，假设左边取的数字下标为j，右侧取的数字下标为i，如果[j,i]是符合条件的，则[j,i+1],[j-1,i]必定也符合条件（因为数组从左到右递增）

所以使用一个滑动窗口的写法，枚举i，然后while移动j。讲符合条件的区间端点用树状数组在原数组中标出，然后直接计算即可。

2.另10pt X=-1e9

当x=-1e9时，限制2不生效，题目转化为求区间元素种类数小于M的区间数目。

这个其实就将暴力改成一个划窗的枚举方式就好了，也就是枚举固定的右端点i，这个时候如果发现种类数较多，就把左端点j向右移动一下即可。

3.另10pt like>=0

这个是作为提示用的测试点，和100pt的做法的区别仅在不用对前缀和进行sort，因为每个数都>=0，那么前缀和肯定是单调增的，实际上是一个起提示作用的点。（提示你需要处理的前缀和必须单调递增）。

100pt

100pt就是将上面的几个sub task合起来做一下。

首先你想一下对于1、2这两个限制条件，它们有没有联合产生的新影响。

显然是没有的，那就说明，这两个限制条件可以单独拆解，单独做。

首先按照X=-1e9的思路，预处理出每一个i，最左边延伸到最小的合法的j是谁，我们记录limit[x]表示，右端点为x时，在不考虑限制1的情况下，合法解左端点的最小值。

然后接下来就按照M=N这个subtask里面去做，前缀和，sort，用树状数组标记符合条件的下标。

区别在于原本是求一个前缀

ans+=qt(id[i]-1)

现在不能全求，必须限制解的下标在limit的范围内，所以做一个前缀和的差分容斥即可，改为

if(id[i])ans+=qt(id[i]-1)-qt(limit[id[i]]-1);

这个题的每一个sub task都不是很难，但是综合起来还是需要一定的综合能力。

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

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
int a[MAXN],base[MAXN],sum[MAXN],id[MAXN],limit[MAXN],bit[MAXN],C,n,k,x,p;
int *cnt=base+50000;
long long ans;
void ct(int x)
{
    x++;
    while(x<=n+1)bit[x]++,x+=(x&-x);
}
int qt(int x)
{
    int ret=0;
    x++;
    while(x)ret+=bit[x],x-=(x&-x);
    return ret;
}
int cal_diff()
{
    int ret=0;
    for(int i=1;i<=n;++i)
    {
        ret+=a[i]>=x;
    }
    return ret;
}
int main()
{
    scanf("%d %d %d",&n,&k,&x);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        sum[i]=sum[i-1]+a[i];
        C+=(cnt[a[i]]++)==0;
        while(C>k)C-=(--cnt[a[++p]])==0;
        limit[i]=p;
        id[i]=i;
    }
    sort(id,id+1+n,[](const int &x,const int &y){
        return sum[x]<sum[y];
    });
    p=-1;
    for(int i=0;i<=n;++i)
    {
        while(p<n&&sum[id[i]]-sum[id[p+1]]>=x)ct(id[++p]);
        if(id[i])ans+=qt(id[i]-1)-qt(limit[id[i]]-1);
    }
    printf("%lld\n",ans*2-cal_diff());
    return 0;
}

T4牛牛的NOIP商圈

环型DP、dfs、状态压缩、矩阵快速幂

20pt

老老实实写一个dfs，或者二进制枚举。

40pt

可以发现这是一个环形DP，环形DP的处理方式一般来讲是把环从第一个位置断开，然后就变成了数组上的简单DP。

区别在于最后还要额外判断收尾相接后是否合法。因为需要状态转移无后效性（无环性），所以一般来讲是先去除收尾之间的限制条件，改为最后再判断，如果不合法就不记录到最终答案当中。

以M=2为例，M=2时转移方程如下：

dp[0]=dp[1]+dp[2]+dp[3]

dp[1]=dp[0]+dp[1]+dp[2]

dp[2]=dp[0]+dp[1]+dp[3]

dp[3]=dp[0]+dp[1]+dp[2]

M=3时，状态转移方程开始变得很复杂（多了一个维度），所以实现起来建议将所有情况都先当做合法的，然后单独写一个合法性校验的函数来check。

100pt

在40pt的基础上，将状态转移改写为矩阵的形式，利用矩阵快速幂进行加速，由于转移矩阵相同，在实际处理上没必要枚举所有的初始状态单独进行矩阵快速幂。

整个矩阵的构造不建议手动构造（这个矩阵过大，而且对于M=2,3,4的转移矩阵不同）。

使用dfs或者枚举的方式进行搜索，也就说你可以对于40pt的部分写一个类似记忆化搜索的东西，然后把搜索和枚举过程中如果对于不同的阶段，存在状态i对状态j的状态转移，就把它填到一个初始为全0的矩阵中。也就是说用dfs的方式搜索出这个转移矩阵，而非构造出转移矩阵。

时间复杂度 ${O(2^{6M}logN)}$ ，空间复杂度 ${O(2^{M})}$ 。

#include <bits/stdc++.h>
using namespace std;
const int MAX_MAT=1<<6;
const long long mod=1e9+7;
struct Mat
{
    long long a[MAX_MAT][MAX_MAT];
    Mat(bool E = false)
    {
        for (int i = 0; i < MAX_MAT; ++i)
        {
            for (int j = 0; j < MAX_MAT; ++j)
            {
                a[i][j] = 0;
            }
        }
        if(E)
        {
            for (int i = 0; i < MAX_MAT; ++i)
            {
                a[i][i] = 1;
            }
        }

    }
};
Mat operator * (const Mat &x,const Mat &y)
{
    Mat c;
    for (int i = 0; i < MAX_MAT; ++i) {
        for (int j = 0; j < MAX_MAT; ++j) {
            c.a[i][j] = 0;
        }
    }
    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] = (c.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;
            }
        }
    }
    return c;
}
void operator *= (Mat &x,const Mat &y)
{
    x=x*y;
}
Mat quickpow(Mat A,long long x)
{
    Mat ans(true);
    while(x)
    {
        if(x&1)
        {
            ans*=A;
        }
        A*=A;
        x>>=1;
    }
    return ans;
}
Mat A;
long long n,ans;
int m,bits,mask;
bool legal(int x)
{
    int first=x&3;
    for(int i=1;i<m;++i)
    {
        x>>=2;
        if(first!=(x&3))return true;
    }
    return false;
}
bool legalEx(int x)
{
    for(int i=1;i<m;++i)
    {
        if(!legal(x))return false;
        x>>=2;
    }
    return true;
}
void get_A()
{
    int u,v;
    for(int i=0;i<bits;++i)
    {
        u=i;
        for(int j=0;j<4;++j)
        {
            v=(u<<2)|j;
            A.a[u][v&mask]+=legal(v);
        }
    }
}

int main()
{
    scanf("%lld %d",&n,&m);
    bits=1<<((m-1)<<1);
    mask=bits-1;
    get_A();
    A=quickpow(A,n-m+1);
    for(int i=0;i<bits;++i)
    {
        for(int j=0;j<bits;++j)
        {
            if(legalEx((j<<((m-1)<<1))|i))
            {
                ans+=A.a[i][j];
                if(ans>=mod)ans-=mod;
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}