竞赛讨论区 > 【题解】2021牛客OI赛前集训营-普及组(第五场)

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

头像
四糸智乃
发布于 2021-10-13 22:01:49 APP内打开
赞 5 | 收藏 0 | 回复3 | 浏览474

T1牛牛数三角形

Tag:简单数学

25pt

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

50pt

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

100pt

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

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

2、等差数列求和公式中这一项中必有一个偶数,所以可以先把2给除下去。

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

时空复杂度

#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一般是写炸了,比如用字符数组存储了答案并且数组大小开了正好的

另10pt

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

100pt

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

时空复杂度

#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

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

30pt

直接讲最快的算法,我们考虑题目中的两个限制条件

  1. 权值和大于
  2. 种类数小于

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

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

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

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

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

这样就相当于开了一个a数组,并且a数组的有效下标是左闭右开区间。

另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都不是很难,但是综合起来还是需要一定的综合能力。

时间复杂度,空间复杂度

#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商圈

环型DPdfs状态压缩矩阵快速幂

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的方式搜索出这个转移矩阵,而非构造出转移矩阵。

时间复杂度,空间复杂度

#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;
}

3条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐