牛客网暑期ACM多校训练营（第四场

A Ternary String
主要是要推出公式。剩下的和之前做的牛客那题差不多，这种要降幂的还是写递归比较好啊。
降幂用拓展欧拉定理就行了。可参考博主另一篇博客
式子为
if s[i]==’0’ f[i]=f[i-1]+1
if s[i]==’1’ f[i]=2*f[i-1]+2
if s[i]==’2’ f[i]=2^f[i-1]*6-3
如果每次都要算一次模的欧拉值会T，所以我们可以提前预处理出来。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
char s[maxn];
map<int,int>M;
long long fmod(long long a,int p)
{
    return a%p+(a>=p?p:0);
}

int eular(int n)
{
    int ans=n;
    for(int i=2;1LL*i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans-=ans/i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)ans-=ans/n;
    return ans;
}



long long quick_mul(long long a,long long b,int mod)
{
    int res=1;
    while(b)
    {
        if(b%2)res=fmod(1LL*res*a,mod);
        b/=2;
        a=fmod(a*a,mod);
    }
    return res;
}

long long dfs(int d,int mod)
{
    if(d==0)return 0;
    if(s[d]=='0')
    {
        int num=fmod(1LL+dfs(d-1,mod),mod);
        //cout<<num<<endl;
        return num;
    }
    else if(s[d]=='1')
        return fmod(dfs(d-1,mod)*2+2,mod);
    else
    {
        int thephi=M[mod];
        if(thephi==1)
            return fmod(9,mod);
        else
            return fmod(quick_mul(2,dfs(d-1,thephi),mod)*6-3,mod);
    }
}


void init()
{
    int p=1e9+7;
    while(p!=1)
    {
        int tmp=eular(p);
        M[p]=tmp;
        p=tmp;
    }
}

int main()
{
    init();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1);
        int p=1e9+7;
        printf("%lld\n",dfs(strlen(s+1),p)%p);
    }
    return 0;
}

B Interval Revisited
可以发现每个区间都顶多被覆盖2次，所以首先将区间按照右端点从小到大排序，设dp[i][j] 为从前i个区间，第i个必选，且j到a[i].r只被选了1次的答案的最小值。
可以惊人的发现这样定义后竟然所有的状态都可以表示出来。
具体转移看代码。

#include<bits/stdc++.h>
using namespace std;

const int maxn=2005;
const int inf=0x3f3f3f3f;
int dp[maxn][maxn];
int dd[maxn][maxn];
struct node
{
    int l,r,w;
    node(int l,int r,int w):l(l),r(r),w(w) {}
    node() {}

} P[maxn];
bool cmp(node a,node b)
{
    if(a.r!=b.r)
    return a.r<b.r;
    return a.l<b.l;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;

        scanf("%d %d",&n,&m);
        for(int i=0;i<=n;i++)
            for(int j=0;j<=m;j++)
            dp[i][j]=dd[i][j]=inf;
        int l,r,w;
        for(int i=1; i<=n; i++)
        {
            scanf("%d %d %d",&l,&r,&w);
            P[i]=node(l,r,w);
        }
        sort(P+1,P+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            if(P[i].l==1)
                for(int j=1;j<=P[i].r;j++)
                dp[i][j]=dd[i][j]=P[i].w;
        }

        for(int i=2; i<=n; i++)
        {
            for(int k=1; k<i; k++)
            {
                if(P[k].r==P[i].l-1)
                    dd[i][P[i].l]=min(dd[i][P[i].l],max(dp[k][P[k].r],P[i].w));
                else if(P[k].r>=P[i].l)
                {
                    if(P[k].r==P[i].r)continue;
                    dd[i][P[k].r+1]=min(dd[i][P[k].r+1],max(dp[k][P[i].l],P[i].w+P[k].w));
                }
            }
            for(int j=P[i].l;j<=P[i].r;j++)
                dp[i][j]=min(dd[i][j],dp[i][j-1]);
        }
        int ans=inf;
        for(int i=1;i<=n;i++)ans=min(ans,dp[i][m]);
        if(ans==inf)ans=-1;
        printf("%d\n",ans);
    }
    return 0;
}

C Chiaki Sequence Reloaded
打了个表后可以发现当n%4为0或3，那么a(n)=a([n/2])+1，否则a(n)=a([n/2])-1.所以我们可以把其转成2进制，记相邻的两位相等的个数为p，不等的为q，那么该数就等于p-q，对答案的贡献就为abs(p-q)。大家可以想想为啥这样。
所以做到这里显然就是数位dp了，我们要维护上一位是多少，到现在相等的个数为多少，不等的个数是多少，再注意前导零该如何处理就可以了。

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long dp[65][2][65][65];
int a[65];

long long dfs(int d,int pre,int x,int y,bool lead,bool limit)
{
    if(d==0)return abs(x-y);
    if(!limit&&!lead&&~dp[d][pre][x][y])return dp[d][pre][x][y];
    int up=limit?a[d]:1;
    long long ans=0;
    for(int i=0;i<=up;i++)
    {
        if(i==0)
        {
            if(lead)
                (ans+=dfs(d-1,0,0,0,true,limit&&i==a[d]))%=mod;
            else
            {
                int newx=x,newy=y;
                if(pre==0)newx++;
                else newy++;
                (ans+=dfs(d-1,0,newx,newy,0,limit&&i==a[d]))%=mod;
            }
        }
        else
        {
            if(lead)
                (ans+=dfs(d-1,1,0,0,0,limit&&i==a[d]))%=mod;
            else
            {
                int newx=x,newy=y;
                if(pre==1)newx++;
                else newy++;
                (ans+=dfs(d-1,1,newx,newy,0,limit&&i==a[d]))%=mod;
            }
        }
    }
    if(!limit&&!lead)dp[d][pre][x][y]=ans;
    return ans;
}

long long solve(long long n)
{
    int cnt=0;
    while(n)
    {
        a[++cnt]=n%2;
        n/=2;
    }
    return dfs(cnt,0,0,0,true,true);
}

int main()
{
    memset(dp,-1,sizeof(dp));
    int T;
    scanf("%d",&T);
    while(T--)
    {
        long long n;
        scanf("%lld",&n);
        printf("%lld\n",solve(n));
    }
    return 0;


}

E Skyline
真的是好题啊。
题意为坐标系中有n个点，每个点被选进集合S里的概率为p，定义F(S)是它左下(也就是那个台阶形状)的面积，求面积的期望。
正着其实不好求，我们倒过来想，我们算每个点不被计入答案的期望是多少，那么答案就为总点数-所有点不被计入答案的期望和。
一个点不被计入答案的期望显然就是它右上角没有一个点被选进去。那么我们可以将点按照y值从大到小排个序，从上往下扫，计算当前行都不被算进去的期望是多少，那么这一行到下一个出现行中间的点对答案的贡献就可以算出来了。
可能博主解释的不太清楚，总之，就是对一个出现的行从上往下扫，累积(因为每个点不出现的概率是互不影响的，所以该区间不出现点的期望个数就应该为所有能影响到该区间的点不出现的概率的乘积再乘上区间长度)每个区间不出现点的概率，再乘上区间长度就完事了。该过程可以利用线段树完成。具体看代码吧。
好久没写线段树了，对lazy的pushdown都写错了QAQ。。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int mod=1e9+7;
struct node
{
    int x,y;
    int p;
    node(int x,int y,int p):x(x),y(y),p(p){}
    node(){}
    bool operator<(const node&b)const
    {
        return y>b.y;
    }

}points[maxn];
long long extgcd(long long a,long long b,long long &x,long long &y)
{
    if(a==0&&b==0)return -1;//无最大公约数
    if(b==0){x=1;y=0;return a;}
    long long d=extgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;//返回gcd(a,b)
}
//****************求逆元******************************
//ax=1(mod n)
long long mod_reverse(long long a,long long n)
{
    long long x,y;
    long long d=extgcd(a,n,x,y);
    if(d==1)return (x%n+n)%n;
    return -1;
}

int X[maxn];

#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
struct node2
{
    int l,r;
    int lazy;
    int E;
    node2(int l,int r,int lazy,int E):l(l),r(r),lazy(lazy),E(E){}
    node2(){}
}nodes[maxn<<2];
void pushup(int rt)
{
    nodes[rt].E=(0LL+nodes[rt<<1].E+nodes[rt<<1|1].E)%mod;
}
void build(int l,int r,int rt)
{
    nodes[rt].l=l,nodes[rt].r=r;
    nodes[rt].lazy=1;
    if(l==r)
    {
        nodes[rt].E=X[l]-X[l-1];
        return;
    }
    int m=l+r>>1;
    build(ls);
    build(rs);
    pushup(rt);
}

void pushdown(int rt)
{
    if(nodes[rt].lazy!=1)
    {
        nodes[rt<<1].lazy=1LL*nodes[rt<<1].lazy*nodes[rt].lazy%mod;
        nodes[rt<<1|1].lazy=1LL*nodes[rt<<1|1].lazy*nodes[rt].lazy%mod;
        nodes[rt<<1].E=1LL*nodes[rt<<1].E*nodes[rt].lazy%mod;
        nodes[rt<<1|1].E=1LL*nodes[rt<<1|1].E*nodes[rt].lazy%mod;
        nodes[rt].lazy=1;
    }
}

void update(int L,int C,int l,int r,int rt)
{
    if(L>=r)
    {
        nodes[rt].E=1LL*nodes[rt].E*C%mod;
        nodes[rt].lazy=1LL*nodes[rt].lazy*C%mod;
        return;
    }
    pushdown(rt);
    int m=l+r>>1;
    update(L,C,ls);
    if(L>m)
        update(L,C,rs);
    pushup(rt);
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int xnum=0;
        int n;
        scanf("%d",&n);
        int x,y,a,b;
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d %d %d",&x,&y,&a,&b);
            int p=1LL*a*mod_reverse(b,mod)%mod;
            points[i]=node(x,y,p);
            X[++xnum]=x;
        }
        sort(X+1,X+1+xnum);
        xnum=unique(X+1,X+1+xnum)-X-1;
        //cout<<X[xnum]<<endl;
        sort(points+1,points+1+n);
        build(1,xnum,1);
        int j;
        long long ans=0;
        points[n+1].y=0;
        for(int i=1;i<=n;i++)
        {
            j=i;
            for(;j+1<=n&&points[j+1].y==points[i].y;j++);
            for(int k=i;k<=j;k++)
            {
                int idx=lower_bound(X+1,X+1+xnum,points[k].x)-X;
                update(idx,(1LL+mod-points[k].p)%mod,1,xnum,1);
            }
            ans=(ans+1LL*(points[i].y-points[j+1].y)*(0LL+X[xnum]-nodes[1].E+mod)%mod)%mod;
            i=j;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

J Hash Function
按照题意模拟其实就能过了。。
我们可以将已经可以放进去的数放入一个优先队列里面，输出一个最小的后再将该下标后的第一个没被放进去的数拿出来判断是否现在能放到hash表里面，一直重复就行了。
该过程可以利用并查集来完成。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
struct pii
{
    int first,second;
    pii(int f,int s):first(f),second(s) {}
    pii() {}
    bool operator<(const pii &b)const
    {
        return first>b.first;
    }
};
priority_queue<pii>Q;

vector<int>V;
int f[maxn];
int a[maxn];
int find(int a)
{
    return a==f[a]?a:f[a]=find(f[a]);
}
int vis[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        V.clear();
        int n;
        scanf("%d",&n);
        int cnt=0;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            if(a[i]%n==i)
                Q.push(pii(a[i],i));
            f[i]=i;
            if(a[i]!=-1)cnt++;
        }
        while(!Q.empty())
        {
            pii x=Q.top();
            Q.pop();
            if(vis[x.second])continue;
            vis[x.second]=1;
            V.push_back(x.first);
            int idx=(x.second+1)%n;
            int fidx=find(idx);
            f[x.second]=fidx;
            int num=a[fidx];
            if(num!=-1)
            {
                int tmp=num%n;
                tmp=find(tmp);
                if(tmp==fidx)
                    Q.push(pii(a[fidx],fidx));
            }
        }
        if(V.size()!=cnt)puts("-1");
        else
        {
            for(int i=0; i<V.size(); i++)
            {
                if(i!=0)printf(" ");
                printf("%d",V[i]);
            }
            puts("");
        }
    }

    return 0;

}

而这题题解给的是可以建图完成，建图的依据就是该点的下标到该点本应该在的下标这一段区间都应该出现在这个点的前面，所以这一区间的点都要连上这个点。
那么我们再进行拓扑排序就可以完成了。
按照上面的说法，普通的建图复杂度就得n^2了，那么现在可以利用线段树建图，因为线段树每个结点就包含一个区间，所以这样建图就能减少时间复杂度了。

#include<bits/stdc++.h>
using namespace std;
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
const int maxn=2e5+5;
int in[maxn<<2];
int a[maxn];
vector<int>G[maxn<<2];
int id[maxn<<2];
int to[maxn];

void addedge(int a,int b)
{
    G[a].push_back(b);
    in[b]++;
}

void build(int l,int r,int rt)
{
    if(l==r)
    {
        id[rt]=l;
        to[l]=rt;
        return;
    }
    int m=l+r>>1;
    build(ls);
    build(rs);
    id[rt]=-1;
    addedge(rt<<1,rt);
    addedge(rt<<1|1,rt);
}

void addedge(int L,int R,int v,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        addedge(rt,v);
        return;
    }
    int m=l+r>>1;
    if(L<=m)
        addedge(L,R,v,ls);
    if(R>m)
        addedge(L,R,v,rs);
}

typedef pair<int,int>pii;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {

        int n;
        scanf("%d",&n);
        for(int i=0;i<=4*n;i++)G[i].clear(),in[i]=0;
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            if(a[i]!=-1)cnt++;
        }
        build(0,n-1,1);
        priority_queue<pii,vector<pii>,greater<pii> >Q;
        for(int i=0;i<n;i++)
        {
            if(a[i]==-1)continue;
            int s=a[i]%n,t=i;
            if(s==t)
                Q.push(pii(a[i],to[i]));
            else
            {
                if(s<t)
                    addedge(s,t-1,to[i],0,n-1,1);
                else
                {
                    if(t!=0)addedge(0,t-1,to[i],0,n-1,1);
                    addedge(s,n-1,to[i],0,n-1,1);
                }
            }
        }
        vector<int>V;
        while(!Q.empty())
        {
            pii x=Q.top();Q.pop();
            if(x.first!=-1)V.push_back(x.first);
            for(int v:G[x.second])
            {
                in[v]--;
                if(in[v]==0)
                {
                    int tmp=id[v];
                    if(tmp==-1)Q.push(pii(-1,v));
                    else Q.push(pii(a[tmp],v));
                }
            }
        }
        if(V.size()==cnt)
        {
            for(int i=0;i<V.size();i++)
            {
                if(i!=0)printf(" ");
                printf("%d",V[i]);
            }
            puts("");
        }
        else puts("-1");
    }
    return 0;
}

终于补完了，虽然比赛的时候还是不会做QAQ…