长沙集训Ⅱ——Day8（Day6、Day7无）

· · 个人记录

T1

树状数组

在做本题前，先把“数位DP”学掉。

依题意，要将[l,r]区间加1，就要将[1,r]加1，再将[1,l-1]减1，所以有些cnt的节点既会加1，又会减1，即这两个操作改变的节点数为cnt[r]+cnt[l-1]-2*cnt(prefix(r,l-1)，其中cnt[i]指i二进制下1的个数，prefix(a,b)指a和b的最长公共前缀。

所以本题的答案就是——

\sum\limits_{0<=x<y<=n} cnt[x]+cnt[y]-2*cnt(prefix(x,y))

那么我们怎么去肝这个东西呢？我们要上一个大法，叫“数位DP”。
我们令f[i][0/1][0/1]表示扫到了第i为，x是否小于y，y是否小于n的贡献和。还需要记一个g[i][0/1][0/1]表示方案数。就可以转移了。

#include<cstdio>
#include<cstring>
using namespace std;

inline long long read()
{
    long long res=0; char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') res=res*10+c-'0',c=getchar();
    return res;
}
inline void write(long long x)
{
    char s[20]; long long top=0;
    while(x) { s[++top]=x%10; x/=10; }
    if(!top) s[+top]=0;
    while(top) putchar(s[top--]+'0');
    putchar('\n');
}

const long long p=1e9+7;
long long T,n,ans,a[70],g[70][2][2],f[70][2][2];

inline void solve(long long n)
{
    long long tot=0;
    while(n)
    {
        a[++tot]=n&1;
        n>>=1;
    }
    memset(g,0,sizeof(g));
    memset(f,0,sizeof(f));
    g[tot+1][0][0]=1;
    for(long long i=tot+1;i>=2;i--)
    for(long long j=0;j<=1;j++)
    for(long long k=0;k<=1;k++)
        if(g[i][j][k])
        {
            for(long long r=0;r<=(k?1:a[i-1]);r++)
            for(long long l=0;l<=(j?1:r);l++)
            {
                f[i-1][j|l<r][k|r<a[i-1]]+=(f[i][j][k]+g[i][j][k]*(l+r-2*(l&&r&&j==0))%p)%p;
                f[i-1][j|l<r][k|r<a[i-1]]%p;
                g[i-1][j|l<r][k|r<a[i-1]]+=g[i][j][k]%p;
                g[i-1][j|l<r][k|r<a[i-1]]%p;
            }
        }
    ans=(f[1][1][0]+f[1][1][1])%p;
}

int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        n=read();
        solve(n);
        write(ans);
    }
    return 0;
}

T2

雇佣妹抖

这题考的是树状数组的运用，不太好想。

本题相当于让我们统计有多少段连续的妹抖的能力值都大于等于B。
可以发现，一段长度为L的连续的妹抖，贡献了(L-1)对相邻的妹抖。
所以我们只要知道一共有多少个妹抖被选中，以及有多少对相邻的妹抖被选中，就可以知道答案了，即两者之差。

用两个树状数组分别维护这两个值。
查询不难，略。
修改的话，修改总的被选中的妹抖个数比较容易，略。修改被选中的相邻妹抖对数只要把每相邻的两个妹抖的能力值的最小值插入树状数组即可（因为这两个数中最小值大于等于B，这两个数就都大于等于B）。

因为能力值较大，所以得离线先离散好能力值再用树状数组维护。 

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

inline int read()
{
    int res=0; char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') res=res*10+c-'0',c=getchar();
    return res;
}
inline void write(int x)
{
    int s[20],top=0;
    while(x) s[++top]=x%10,x/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
    putchar('\n');
}

const int NQ=200010;
int n,q,num,ans,a[NQ],b[NQ*2],c[NQ*2],d[NQ*2],qq[NQ][3];

inline int lowbit(int x) { return x&(-x); }
inline void add(int x,int y,int g[])
{
    for(;x<=num;x+=lowbit(x)) g[x]+=y;
}
inline int ask(int x,int g[])
{
    int res=0;
    for(;x;x-=lowbit(x)) res+=g[x];
    return res;
}

int main()
{           
    n=read(); q=read();
    for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
    int cnt=n;
    for(int i=1;i<=q;i++)
    {
        int T=read();
        if(T==1) qq[i][1]=read();
        else qq[i][0]=read(),qq[i][1]=read();
        b[++cnt]=qq[i][1];
    }
    sort(b+1,b+cnt+1);
    num=unique(b+1,b+cnt+1)-b-1;
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(b+1,b+num+1,a[i])-b;
        add(a[i],1,c);
    }    
    for(int i=1;i<n;i++) add(min(a[i],a[i+1]),1,d);
    for(int i=1;i<=q;i++)
    {
        if(!qq[i][0])
        {
            int bb=lower_bound(b+1,b+num+1,qq[i][1])-b;
            ans=n-ask(bb-1,c)-(n-1-ask(bb-1,d));
            write(ans);
        }
        else
        {
            int wyh=qq[i][0],gyb=lower_bound(b+1,b+num+1,qq[i][1])-b;
            add(a[wyh],-1,c); add(gyb,1,c);
            if(wyh>1)
                add(min(a[wyh],a[wyh-1]),-1,d),add(min(gyb,a[wyh-1]),1,d);
            if(wyh<n)
                add(min(a[wyh],a[wyh+1]),-1,d),add(min(gyb,a[wyh+1]),1,d);
            a[wyh]=gyb; 
        }
    }
    return 0;
}

T3

建造

#include<cstdio>
#include<cstring>
using namespace std;

inline int read()
{
    int res=0; char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') res=res*10+c-'0',c=getchar();
    return res;
}
inline void write(long long x)
{
    int s[20],top=0;
    while(x) s[++top]=x%10,x/=10;
    if(!top) s[++top]=0;
    while(top) putchar(s[top--]+'0');
}

long long  n,x,p;
long long inv[100110],jc[100110],f[2][10010][110],ans;

inline int C(int x,int y) { return jc[x]*inv[y]%p*inv[x-y]%p; }

int main()
{
    n=read(); x=read(); p=read();
    inv[1]=1; jc[1]=1;
    for(int i=2;i<=x+n;i++) inv[i]=(p-p/i)%p*inv[p%i]%p;
    for(int i=2;i<=x+n;i++) inv[i]=inv[i]*inv[i-1]%p;
    for(int i=2;i<=x+n;i++) jc[i]=jc[i-1]*i%p;
    f[1][0][0]=1;
    for(int i=1;i<n;i++)
    {
        int now=i&1,nxt=(i+1)&1;
        memset(f[nxt],0,sizeof(f[nxt]));
        for(int j=0;j<=i*i;j++)
        for(int k=0;k<i;k++)
            if(f[now][j][k])
            {
                (f[nxt][j+2*i+2][k-1]+=f[now][j][k]*k%p)%=p;
                (f[nxt][j+i+1][k]+=f[now][j][k]*2*k%p)%=p;
                (f[nxt][j+i+1][k]+=f[now][j][k]*2%p)%=p;
                (f[nxt][j][k+1]+=f[now][j][k]*k%p)%=p;
                (f[nxt][j][k+1]+=f[now][j][k]*2%p)%=p;
            }
    }
    for(int i=0;i<=n*n;i++) 
        if(f[n&1][i][0]) (ans+=f[n&1][i][0]*C(x-i-1+n,n)%p)%=p;
    write(ans);
    return 0;
}