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

牛客网暑期ACM多校训练营(第九场

程序员文章站 2022-04-02 18:48:01
...

C Gambling
一开始感觉这个题似乎没什么逻辑,博主只是跟着题解AC了一遍。。等写博客的时候大概想了想概率与此时应加的钱的关系,才觉得有点道理。
我们要明白两件事情。
第一,一开始的概率为1/2。
第二,题解上写的概率的转换。也就是设当前胜率为p,那么如果下一场赢了,胜率会变成p+q,输了胜率会变成p-q。
总之只需要明白胜率会进行加加减减知道最后变成1或者0。所以这也就说明了为什么**的钱为什么为2q22n1,因为胜率的变化只是线性变化,那么你的胜率从1/2到1与钱从0到22n1 的变化量应该成正相关的,所以你只要算出前面一次函数前面的系数就ok了,那么显然前面的系数就为222n1
可能说的不是很清楚,大家可以自己理解理解。。
那么现在关注点就在如何求胜率啦,这个参考题解就行了。

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

const int maxn=2e5+5;
const int mod=1000000007;

//***************************************************
//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
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;
}


long long tab1[maxn],tab2[maxn];
long long two[maxn];
void init()
{
    two[0]=1;
    for(int i=1;i<maxn;i++)
        two[i]=two[i-1]*2%mod;
    tab1[0]=1;
    for(int i=1;i<maxn;i++)
        tab1[i]=tab1[i-1]*i%mod;
    tab2[maxn-1]=mod_reverse(tab1[maxn-1],mod);
    for(int i=maxn-2;i>=0;i--)
        tab2[i]=tab2[i+1]*(i+1)%mod;
}
long long C(int a,int b)
{
    if(a<b)return 0;
    return tab1[a]*tab2[b]%mod*tab2[a-b]%mod;
}
long long gett(int a)
{
    return two[a];
}

int main()
{
    init();
    int n;
    scanf("%d",&n);
    int i=0,j=0;
    //printf("%lld\n",gett(1)*C(2*n-2,n-1)%mod);
    int tmp;
    while(1)
    {
        printf("%lld\n",gett(1+i+j)*C(2*n-2-i-j,n-i-1)%mod);
        scanf("%d",&tmp);
        if(tmp==0)i++;
        else j++;
        if(i==n||j==n)break;
    }
    return 0;


}

F Typing practice
第一次见trie图,没做出来。。赛后补题觉得这个思路十分正确啊,也没有什么拐弯的地方,属于套路题,这里mark一下。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct Trie
{
    int next[maxn][30],fail[maxn],End[maxn];
    int root,L;
    int newnode()
    {
        for(int i=0;i<26;i++)
            next[L][i]=-1;
        End[L++]=0;
        return L-1;
    }
    void init()
    {
        L=0;
        root=newnode();
    }
    void insert(char buf[],int idx)
    {
        int len=strlen(buf);
        int now=root;
        for(int i=0;i<len;i++)
        {
            if(next[now][buf[i]-'a']==-1)
                next[now][buf[i]-'a']=newnode();
            now=next[now][buf[i]-'a'];
        }
        End[now]=End[now]|(1<<idx);
    }
    void build()
    {
        queue<int>Q;
        fail[root]=root;
        for(int i=0;i<26;i++)
        {
            if(next[root][i]==-1)
                next[root][i]=root;
            else
            {
                fail[next[root][i]]=root;
                Q.push(next[root][i]);
            }
        }
        while(!Q.empty())
        {
            int now=Q.front();Q.pop();
            End[now]|=End[fail[now]];
            for(int i=0;i<26;i++)
            {
                if(next[now][i]==-1)
                    next[now][i]=next[fail[now]][i];
                else
                {
                    fail[next[now][i]]=next[fail[now]][i];
                    Q.push(next[now][i]);
                }
            }
        }
    }
    void debug()
    {
        for(int i=0;i<L;i++)
            {
                printf("id = %3d,fail = %3d,end = %3d,chi = [",i,fail[i],End[i]);
                for(int j=0;j<26;j++)
                    printf("%2d",next[i][j]);
                printf("]\n");
            }
    }
}ac;
char s[maxn];
int d[maxn];
vector<int>V[maxn];
stack<int>S;
void solve()
{
    memset(d,-1,sizeof(d));
    for(int i=0;i<ac.L;i++)
    {
        for(int j=0;j<26;j++)
            if(ac.next[i][j]!=-1)
            V[ac.next[i][j]].push_back(i);
    }
    queue<int>Q;
    for(int i=0;i<ac.L;i++)
        if(ac.End[i]!=0)
        Q.push(i),d[i]=0;
    while(!Q.empty())
    {
        int x=Q.front();Q.pop();
        for(int v:V[x])
        {
            if(d[v]==-1)
                d[v]=d[x]+1,Q.push(v);
        }
    }
    int now=ac.root;
    printf("%d\n",d[now]);
    S.push(now);
    int len=strlen(s);
    for(int i=0;i<len;i++)
    {
        if(s[i]=='-')
        {
            S.pop();
            if(S.size())
            {
                now=S.top();
            }
            else S.push(0),now=0;
            printf("%d\n",d[now]);
        }
        else
        {
            now=ac.next[now][s[i]-'a'];
            printf("%d\n",d[now]);
            S.push(now);
        }
    }
}

int main()
{
    ac.init();
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s",s);
        ac.insert(s,i);
    }
    ac.build();
    //ac.debug();
    scanf("%s",s);
    solve();
}

H Prefix Sum
首先呢,你需要推出第k行的每个数与第一项的关系(化繁为简)。也就是题解中的式子。
然后在按照题解一步步的推,似乎没什么逻辑上的问题啊。。
总之就是推推推。。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int mod=1000000007;
//***************************************************
//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
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;
}

long long tab1[maxn],tab2[maxn];
void init()
{
    tab1[0]=1;
    for(int i=1;i<maxn;i++)
        tab1[i]=tab1[i-1]*i%mod;
    tab2[maxn-1]=mod_reverse(tab1[maxn-1],mod);
    for(int i=maxn-2;i>=0;i--)
        tab2[i]=tab2[i+1]*(i+1)%mod;
}

long long C(int a,int b)
{
    if(a<0)
    {
        if(b%2)return C(-a+b-1,b)*-1;
        return C(-a+b-1,b);
    }
    else
    {
        if(a<b)return 0;
        return tab1[a]*tab2[b]%mod*tab2[a-b]%mod;
    }
}

long long sum[45][maxn];
#define lowbit(x) x&(-x)
void add(int x,long long val,long long sum[])
{
    while(x<maxn)
    {
        sum[x]=(sum[x]+val)%mod;
        x+=lowbit(x);
    }
}

long long query(int x,long long sum[])
{
    long long res=0;
    while(x)
    {
        res=(res+sum[x])%mod;
        x-=lowbit(x);
    }
    return res;
}

//
int n,m,k;
long long a[maxn];
void update(long long x,long long y)
{
    for(int j=0;j<=k;j++)
    {
        long long tmp=(y*C(k-x,k-j)%mod+mod)%mod;
        add(x,tmp,sum[j]);
    }
}

void Query(long long x)
{
    long long ans=0;
    for(int j=0;j<=k;j++)
    {
        long long tmp=C(x,j);
        long long tmp2=query(x,sum[j]);
        ans=(ans+tmp*tmp2%mod)%mod;
    }
    printf("%lld\n",ans);
}

void solve()
{
    int opt;
    long long x,y;
    while(m--)
    {
        scanf("%d",&opt);
        if(opt==0)
        {
            scanf("%lld %lld",&x,&y);
            update(x,y);
        }
        else
        {
            scanf("%lld",&x);
            Query(x);
        }
    }
}
int main()
{
    init();
    scanf("%d %d %d",&n,&m,&k);
    k--;
    solve();
}

G Longest Common Subsequence
这题是整套题研究时间最长的题了,因为博主不知道怎么分治求四维偏序。所以特意去学了下cdq分治。
第一步你首先可以记录每个数组中的每个数所在的位置,然后依题解所说建立一个四维的点,找到一个最长上升子序列即可。
所以学会四维偏序后,因为这不是求点的偏序个数,而是求最长上升子序列,所以你分治的顺序和树状数组维护的东西需要改变。因为你要保证求左边对右边的影响时,左边必须已经被处理。所以分治的顺序应该把处理右边的放在合并后面。
而求最长上升子序列,那么树状数组只需要维护前缀最大值即可了。
详细见代码吧。
如果不清楚cdq分治的同学请戳此链接

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

const int maxn=8e4+5;

struct Item
{
    int d1,d2,d3,d4,part;
    int idx;
    Item(int tmp[])
    {
        d1=tmp[1];
        d2=tmp[2];
        d3=tmp[3];
        d4=tmp[4];
    }
    Item() {}
} a[maxn];

int acnt;

const int LEFT=0;
const int RIGHT=1;
//
int arr[maxn];
inline int lowbit(int num)
{
    return num&(-num);
}
void add(int idx,int val)
{
    while(idx<maxn)
    {
        arr[idx]=max(arr[idx],val);
        idx+=lowbit(idx);
    }
}
int query(int idx)
{
    int ans=0;
    while(idx)
    {
        ans=max(ans,arr[idx]);
        idx-=lowbit(idx);
    }
    return ans;
}
void clear(int idx)
{
    while(idx<maxn)
    {
        if(arr[idx]==0)break;
        arr[idx]=0;
        idx+=lowbit(idx);
    }
}
//
Item tmp3d[maxn];
Item tmp2d[maxn];
int dp[maxn];
bool cmpb(const Item &a,const Item &b)
{
    return a.d2<b.d2;
}

bool cmpc(const Item &a,const Item &b)
{
    return a.d3<b.d3;
}

bool cmpa(const Item &a,const Item &b)
{
    return a.d1<b.d1;
}

Item tmp4[maxn];
void cdq3d(int L,int R)
{
    if(R-L<=1)return;
    int M=(L+R>>1);
    cdq3d(L,M);
    sort(tmp2d+L,tmp2d+M,cmpc);
    for(int i=M;i<R;i++)
        tmp4[i]=tmp2d[i];
    sort(tmp2d+M,tmp2d+R,cmpc);
    int p=L,q=M,o=L;
    while(p<M&&q<R)
    {
        if(tmp2d[p].d3<tmp2d[q].d3)
        {
            if(tmp2d[p].part==LEFT)add(tmp2d[p].d4,dp[tmp2d[p].idx]);
            tmp3d[o++]=tmp2d[p++];
        }
        else
        {
            if(tmp2d[q].part==RIGHT)dp[tmp2d[q].idx]=max(dp[tmp2d[q].idx],query(tmp2d[q].d4-1)+1);
            tmp3d[o++]=tmp2d[q++];
        }
    }
    while(p<M)tmp3d[o++]=tmp2d[p++];
    while(q<R)
    {
        if(tmp2d[q].part==RIGHT)dp[tmp2d[q].idx]=max(dp[tmp2d[q].idx],query(tmp2d[q].d4-1)+1);
        tmp3d[o++]=tmp2d[q++];
    }
    for(int i=L; i<R; i++)
    {
        if(tmp3d[i].part==LEFT)clear(tmp3d[i].d4);
        //tmp2d[i]=tmp3d[i];
    }
    for(int i=M;i<R;i++)
        tmp2d[i]=tmp4[i];
    cdq3d(M,R);
}
Item tmp3[maxn];



void cdq2d(int L,int R)
{
    if(R-L<=1)return;
    int M=L+R>>1;
    cdq2d(L,M);

    sort(a+L,a+M,cmpb);
    for(int i=M; i<R; i++)
        tmp3[i]=a[i];
    sort(a+M,a+R,cmpb);
    int p=L,q=M,o=L;
    while(p<M&&q<R)
    {
        if(a[p].d2<a[q].d2)
        {
            a[p].part=LEFT;
            tmp2d[o++]=a[p++];
        }
        else
        {
            a[q].part=RIGHT;
            tmp2d[o++]=a[q++];
        }
    }
    while(p<M)
    {
        a[p].part=LEFT;
        tmp2d[o++]=a[p++];
    }
    while(q<R)
    {
        a[q].part=RIGHT;
        tmp2d[o++]=a[q++];
    }
    //for(int i=L;i<R;i++)a[i]=tmp2d[i];
    cdq3d(L,R);
    for(int i=M; i<R; i++)
        a[i]=tmp3[i];
    cdq2d(M,R);
}
vector<int>p[5][10005];
int tmp[5];
void dfs(int x,int d)
{
    if(d==5)
    {
        a[acnt]=Item(tmp);
        a[acnt].idx=acnt;
        acnt++;
        return;
    }
    for(int u:p[d][x])
    {
        tmp[d]=u;
        dfs(x,d+1);
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    int aa;
    for(int i=1; i<=4; i++)
    {
        for(int j=1; j<=n; j++)
        {
            scanf("%d",&aa);
            p[i][aa].push_back(j);
        }
    }
    for(int i=1; i<=n; i++)
        dfs(i,1);
    for(int i=0; i<acnt; i++)
        dp[i]=1;
    sort(a,a+acnt,cmpa);
    cdq2d(0,acnt);
    int ans=0;
    for(int i=0; i<acnt; i++)
        ans=max(ans,dp[i]);
    printf("%d\n",ans);
    return 0;
}
相关标签: 牛客 多校