一定要分析清楚复杂度再打！！！窝再也不要花2h20min用暴力对拍暴力啦！！！

雨露均沾(滑稽)，尽量避免孤注一掷。先把暴力分拿全再回来刚正解。

即使剩下的时间不多了也优先考虑认真读题+打暴力而非乱搞(当然是在乱搞得分没有保证的情况下)。

明明是最近几套题中最难的却改的最顺利？大概是因为也就这次考场上认真思考了吧。

A.简单的区间

考场启发式合并复杂度写假了……和暴力没区别QAQ

首先考虑题目中柿子的具体含义：对于一段区间，以最大值所在处为界(不含)劈成两半，如果这两半的和是K的倍数就符合条件。

那这道题就和之前那道english十分相像了，考虑单调栈预处理每个数作为最大值控制的区间，因为这些区间构成一棵完全二叉树所以可以启发式合并。

由于要计算符合条件区间的个数，所以维护一个桶，下标为$\% K$的余数。如果两个数$\% K$同余那么他们的差一定是K的倍数，所以用前缀和实现桶的更新与查询。

那么具体怎么启发式合并呢？

首先比较左右儿子区间长度，首先把短区间递归下去处理，然后把桶清空(因为待会统计答案的时候不能算它自己这一段的)。接着递归处理长区间，之后桶里已经有了长区间的信息了，所以可以暴力枚举短区间，把与枚举到的点的前缀和同余的区间个数计入答案。当然因为不计入最大值本身，所以枚举计算贡献时如果是左区间要加上最大值，右区间则减去最大值。

细节很多，而且左右儿子作为短区间时考虑的东西不太一样……主要就是左区间要用前缀和涉及到$sum[l-1]$的问题。另外处理完一个区间要把短区间啥也没选的情况减去。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<stack>

#include<vector>

using namespace std;

typedef long long ll;

const int N=3e5+5;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int n,K,L[N],R[N],ls[N],rs[N];

ll a[N],ans,bu[1000005],sum[N];

stack<int> q;

void work(int i)

{

    int l=L[i],r=R[i];

    if(l==r){bu[sum[i]%K]++;return ;}

    if(r-i<i-l)

    {

        if(rs[i])work(rs[i]);

        for(int j=i;j<=r;j++)

            bu[sum[j]%K]=0;

        if(ls[i])work(ls[i]);

        bu[sum[l-1]%K]++;

        for(int j=i;j<=r;j++)

            ans+=bu[(sum[j]-a[i])%K];

        for(int j=i;j<=r;j++)

            bu[sum[j]%K]++;

        bu[sum[l-1]%K]--;

    }

    else

    {

        if(ls[i])work(ls[i]);

        for(int j=l;j<=i;j++)

            bu[sum[j]%K]=0;

        if(rs[i])work(rs[i]);

        bu[sum[i]%K]++;

        for(int j=l;j<=i;j++)

            ans+=bu[(sum[j-1]+a[i])%K];

        for(int j=l;j<=i-1;j++)

            bu[sum[j]%K]++;

    }

    ans--;

}

int main()

{

    /*freopen("dt.in","r",stdin);

    freopen("my.out","w",stdout);*/

    n=read();K=read();

    for(int i=1;i<=n;i++)

        a[i]=read(),sum[i]=sum[i-1]+a[i];

    for(int i=1;i<=n;i++)

    {

        while(!q.empty()&&a[q.top()]<=a[i])q.pop();

        if(!q.empty())L[i]=q.top()+1,rs[q.top()]=i;

        else L[i]=1;

        q.push(i);

    }

    while(!q.empty())q.pop();

    for(int i=n;i;i--)

    {

        while(!q.empty()&&a[q.top()]<a[i])q.pop();

        if(!q.empty())R[i]=q.top()-1,ls[q.top()]=i;

        else R[i]=n;

        q.push(i);

    }

    for(int i=1;i<=n;i++)

        if(L[i]==1&&R[i]==n){work(i);break;}

    /*for(int i=1;i<=n;i++)

        cout<<i<<' '<<L[i]<<' '<<R[i]<<' '<<ls[i]<<' '<<rs[i]<<endl;*/

    cout<<ans<<endl;

    return 0;

}

B.简单的玄学

竟然是个古典概型……还以为要容斥或者递推什么的……

“至少两个变量相同”显然与“没有任何变量相同”互斥，所以只要求出后者后用1减一下即可。

那么这个答案显然为$\frac{A_{2^n}^m}{2^{nm}}$

化简一下，得到

$\frac{\prod_{i=2^n-m+1}^{2^n-1}}{2^{n(m-1)}}$

可以发现，如果$m>mod$，那么分子一定会被模成0，所以不用考虑m过大的情况。

接下来的问题是约分。分母中的质因子只有2，所以需要求出分子中2的个数。根据$2^k-i$中2的个数等于$i$中2的个数，可以把问题转化为求$(m-1)!$中2的个数。可以$O(log\ m)$求。

接下来逆元搞一下就得到了答案。$1-\frac{a}{b}=\frac{b-a}{b}$。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;

typedef long long ll;

const ll mod=1e6+3,inv=500002;

ll n,m;

ll qpow(ll a,ll b)

{

    ll res=1;

    while(b)

    {

        if(b&1)res=res*a%mod;

        a=a*a%mod;

        b>>=1;

    }

    return res;

}

int main()

{

    scanf("%lld%lld",&n,&m);

    if(log2(m)>n){puts("1 1");return 0;}

    ll mi=qpow(2,n),mot=qpow(mi,m),res=1;

    for(ll i=0;i<m&&res;i++)

        res=res*(mi-i)%mod;

    ll cnt2=n;

    for(ll i=2;i<m;i<<=1)cnt2+=(m-1)/i;

    mot*=qpow(inv,cnt2)%mod,mot%=mod;

    res*=qpow(inv,cnt2)%mod,res%=mod;

    printf("%lld %lld\n",(mot-res+mod)%mod,mot);

    return 0;

}

C.简单的填数

最不擅长这种乱搞题了……

定义u为使$a[n]$最大的每个位置填数方案，d为使$a[n]$最小的每个位置填数方案。

那么显然u尽量2个进1，d尽量5个进1。

然后根据已经填的数调整u和d的值和左端点位置，中间特判掉无解情况。

这样扫一遍就可以得到最大的$a[n]$。

然后倒着扫一遍构造方案即可。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=2e5+5;

int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int n,a[N],num[N];

struct node

{

    int x,pos;

}

u[N],d[N];

int main()

{

    n=read();

    for(int i=1;i<=n;i++)

        a[i]=read();

    if(a[1]!=1&&a[1]!=0){puts("-1");return 0;}

    u[1].pos=u[1].x=d[1].pos=d[1].x=1;

    for(int i=2;i<=n;i++)

    {

        d[i]=d[i-1];u[i]=u[i-1];

        d[i].pos++;u[i].pos++;

        if(u[i].pos>2)u[i].x++,u[i].pos=1;

        if(d[i].pos>5)d[i].x++,d[i].pos=1;

        if(!a[i])continue;

        if(u[i].x>a[i])u[i]=(node){a[i],2};

        else if(u[i].x==a[i])u[i].pos=min(u[i].pos,2);

        if(d[i].x<a[i])d[i]=(node){a[i],1};

        if(u[i].x<a[i]||d[i].x>a[i]){puts("-1");return 0;}

    }

    if(u[n].pos==1)u[n].x--,u[n].pos=u[n-1].pos+1;

    if(u[n].x<d[n].x){puts("-1");return 0;}

    a[n]=u[n].x;

    printf("%d\n",a[n]);

    num[a[n]]=1;

    for(int i=n-1;i;i--)

    {

        if(!a[i])

        {

            int val=min(a[i+1],u[i].x);

            if(num[val]==5)val--;

            a[i]=val;

        }

        num[a[i]]++;

    }

    for(int i=1;i<=n;i++)

        printf("%d ",a[i]);

    putchar('\n');

    return 0;

}

/*

7

0 1 0 0 0 3 0

*/

巴特西

[NOIP模拟测试37]反思+题解

A.简单的区间

B.简单的玄学

C.简单的填数

最新文章

热门文章