欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NOIP2017提高组 模拟赛21(总结)

程序员文章站 2022-03-14 19:27:50
...

NOIP2017提高组 模拟赛21(总结)

第一题 纸牌游戏 (分解质因数,尺取法)

【题目描述】

【解题思路】

  问题转化为有多少个【L,R】使得a[]的L~R这个区间乘起来是k的倍数。
  k的时间分解k的质因数。
  枚举L,可以发现R具有单调性,也就是若【L,R】合法,那么【L,R+1】也合法。
  用尺取法就可以解决。
  时间复杂度:O(2n+k)

【代码】

#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long ll;

int n,k;
const int N=1e5;
int d[N+100],kl,sl,ty[N+100],cnt;
ll f[N+100];
ll ans;

int pck(int x,int v)
{
    for(int i=1;i<=cnt;i++)
    {
        for(;!(x%ty[i]);)
        {
            x/=ty[i];
            f[i]+=v;
        }
    }
    return x;
}

bool check()
{
    if(sl<0) return 0;
    for(int i=1;i<=cnt;i++)
    if(f[i]<0) return 0;
    return 1;
}

int main()
{
    freopen("1979.in","r",stdin);
    freopen("1979.out","w",stdout);
    scanf("%d%d",&n,&k);
    cnt=0; ans=0ll; kl=k;
    for(int i=2;i*i<=k;i++)
    {
        if(!(k%i))
        {
            ty[++cnt]=i;
            for(;!(kl%i);) kl/=i,f[cnt]--;
        }
    } sl=-1;
    for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    int la=0;
    for(int i=1;i<=n;i++)
    {
        int yu;
        while(!check() && la<n)
        {
            la++;
            yu=pck(d[la],1);
            if(!(yu%kl)) sl++;
        }
        if(check()) ans+=(n-la+1);
        yu=pck(d[i],-1);
        if(!(yu%kl)) sl--;
    }
    printf("%lld\n",ans);
    return 0;
}

第二题 XOR (线段树)

【题目描述】

【解题思路】

  异或有结合律,交换律。
  但题目需要求和,加法不能跟异或同时做。
  其实把每一个数字x,分解成2ki,也就是把x转化为二进制来做。建立logx个线段树,分别表示二进制的第k位的情况(也就是【L,R】这一区间,xi转化成二进制,第k位多少个1,L≤i≤R)。
  若【L,R】这一区间xor 2^k,则把线段树k中的【L,R】范围的1变成0,0变成1。(统计1的个数sum1就行,打反转标记。反转的话1的个数就等于R-L+1-sum1)

【代码】

#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long ll;

const int N=1e5+10;
const int kp=20;
int n;
int d[N];
struct data
{
    int s,la;
} T[21][N<<2];
ll ans;

int gd(int x,int y)
{
    return ((x&(1<<y))>0);
}

void build(int w,int ro,int L,int R)
{
    if(L==R)
    {
        T[w][ro].s=gd(d[L],w);
        return;
    }
    int Mid=(L+R)>>1;
    build(w,ro<<1,L,Mid); build(w,ro<<1|1,Mid+1,R);
    T[w][ro].s=T[w][ro<<1].s+T[w][ro<<1|1].s;
}

void down(int w,int ro,int L,int R)
{
    if(T[w][ro].la)
    {
        int Mid=(L+R)>>1;
        T[w][ro].la=0;
        T[w][ro<<1].la^=1; T[w][ro<<1|1].la^=1;
        T[w][ro<<1].s=(Mid-L+1)-T[w][ro<<1].s;
        T[w][ro<<1|1].s=(R-Mid)-T[w][ro<<1|1].s;
    }
}

void updata(int w,int ro,int L,int R,int li,int ri)
{
    if(L>ri || R<li ) return;
    if(li<=L && R<=ri)
    {
        T[w][ro].la^=1;
        T[w][ro].s=(R-L+1)-T[w][ro].s;
        return;
    }
    int Mid=(L+R)>>1;
    down(w,ro,L,R);
    updata(w,ro<<1,L,Mid,li,ri); updata(w,ro<<1|1,Mid+1,R,li,ri);
    T[w][ro].s=T[w][ro<<1].s+T[w][ro<<1|1].s;
}

int query(int w,int ro,int L,int R,int li,int ri)
{
    if(L>ri || R<li ) return 0;
    if(li<=L && R<=ri) return T[w][ro].s;
    int Mid=(L+R)>>1;
    down(w,ro,L,R);
    int x1=query(w,ro<<1,L,Mid,li,ri),x2=query(w,ro<<1|1,Mid+1,R,li,ri);
    T[w][ro].s=T[w][ro<<1].s+T[w][ro<<1|1].s;
    return x1+x2;
}

int main()
{
    freopen("1980.in","r",stdin);
    freopen("1980.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&d[i]);
    for(int i=0;i<kp;i++) build(i,1,1,n);
    int Q;
    scanf("%d",&Q);
    while(Q--)
    {
        int a,b,c,d;
        scanf("%d",&c);
        if(c==1)
        {
            scanf("%d%d",&a,&b);
            ans=0ll;
            for(int i=0;i<kp;i++)
            {
                int yu=query(i,1,1,n,a,b);
                ans+=(ll)yu*(1<<i);
            }
            printf("%lld\n",ans);
        } else
        if(c==2)
        {
            scanf("%d%d%d",&a,&b,&d);
            for(int i=0;i<kp;i++)
            if(gd(d,i))
            {
                updata(i,1,1,n,a,b);
            }
        }
    }
}

第三题 豆腐 (数位DP+AC自动机)

【题目描述】

【解题思路】

  首先想到的就是数位DP(LR那么大,除此之外也没什么可以做的了)。
  DP的状态:F[第i位][字符串的状态][当前的麻辣值][是否有前导零][是否达到上界]=方案数
  但,如果把所有的字符串的状态直接记下来,是很难转移的,不可能再重新匹配。
  所以想到建AC自动机来维护,字符串的状态也就是在AC自动机上的位置T(先预处理出字符串所对应的麻辣值)。枚举下一位的数字x(0~19),直接转移到T->c[x]的位置,再加上麻辣值,累计方案数。
  最后统计所有位置,麻辣值不超过k的方案数的和。

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int mods=1000000007;
const int Ln=505;
struct data { int fail,fa,r[21],s; } T[Ln];
int dl[210],dr[210],q[210];
int root,n,m,k,cnt;
int f[2][205][705][2][2];

void buildfail()
{
    T[root].fail=root; T[root].fa=root; T[root].s=0;
    int head=1,tail=1; q[1]=root;
    while(head<=tail)
    {
        int fnow=q[head++];
        for(int i=0;i<m;i++)
        if(T[fnow].r[i])
        {
            int v=T[fnow].r[i];
            int k=T[fnow].fail;
            bool flag=(fnow!=root);
            while(!T[k].r[i])
            {
                if(k==root) { flag=0; break; }
                k=T[k].fail;
            }
            if(flag) T[v].fail=T[k].r[i]; else T[v].fail=root;
            (T[v].s+=T[T[v].fail].s)%=mods;
            q[++tail]=v;
        } else T[fnow].r[i]=T[T[fnow].fail].r[i];
    }
}

int getans(int A[])
{
    memset(f,0,sizeof(f)); f[0][0][0][0][0]=1;
    for(int i=0,w=0;i<A[0];i++,w^=1)
    {
        memset(f[w^1],0,sizeof(f[w^1]));
        for(int j=0;j<=cnt;j++)
            for(int h=0;h<=k;h++)
                for(int p1=0;p1<2;p1++)
                for(int p2=0;p2<2;p2++)
                if(f[w][j][h][p1][p2])
                {
                    for(int g=0;g<=((p2)?(m-1):(A[i+1]));g++)
                    {
                        int nex=((p1) || (g>0))?(T[j].r[g]):(0);
                        (f[w^1][nex][h+T[nex].s][p1|(g>0)][p2|(g<A[i+1])]+=f[w][j][h][p1][p2])%=mods;
                    }
                }
    }
    int res=0;
    for(int i=0;i<=cnt;i++)
    for(int h=0;h<=k;h++)
    for(int p1=0;p1<2;p1++)
    for(int p2=0;p2<2;p2++)
    (res+=f[(A[0]&1)][i][h][p1][p2])%=mods;
    return res;
}

int main()
{
    freopen("1981.in","r",stdin);
    freopen("1981.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k); cnt=0; root=0;
    scanf("%d",&dl[0]); for(int i=1;i<=dl[0];i++) scanf("%d",&dl[i]);
    scanf("%d",&dr[0]); for(int i=1;i<=dr[0];i++) scanf("%d",&dr[i]);
    dl[dl[0]]--;
    for(int i=dl[0];i>=1;i--)
        if(dl[i]<0) dl[i]+=m,dl[i-1]--; else break;
    for(int i=1;i<=n;i++)
    {
        int a,cd;
        scanf("%d",&a);
        int now=root;
        for(int i=1;i<=a;i++)
        {
            scanf("%d",&cd);
            if(!T[now].r[cd]) { cnt++; T[cnt].fa=now; T[now].r[cd]=cnt; }
            now=T[now].r[cd];
        }
        scanf("%d",&cd);
        (T[now].s+=cd)%=mods;
    }
    buildfail();
    printf("%d\n",((getans(dr)-getans(dl))%mods+mods)%mods);
    return 0;
}