2019牛客暑期多校训练营牛客数学竞赛（误）

亦凉 2021-10-18 12:42 285阅读 0赞

[A题][A]

线段树可卡时限过 （1500MS）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int inf=0x3f3f3f3f;
    const int M=1e5+5;
    int a[M],b[M],mpa[M],mpb[M];
    int treea[M<<2],treeb[M<<2];
    void up(int root){
        treea[root]=min(treea[root<<1],treea[root<<1|1]);
        treeb[root]=min(treeb[root<<1],treeb[root<<1|1]);
    }
    void build(int root,int l,int r){
        if(l==r){
            treea[root]=a[l];
            treeb[root]=b[l];
            return ;
        }
        int midd=(l+r)>>1;
        build(root<<1,l,midd);
        build(root<<1|1,midd+1,r);
        up(root);
    }
     
    int querya(int L,int R,int root,int l,int r){
        if(L<=l&&r<=R){
            return treea[root];
        }
        int midd=(l+r)>>1;
        int ans=inf;
        if(L<=midd)
            ans=min(ans,querya(L,R,root<<1,l,midd));
        if(R>midd)
            ans=min(ans,querya(L,R,root<<1|1,midd+1,r));
        return ans;
    }
    int queryb(int L,int R,int root,int l,int r){
        if(L<=l&&r<=R){
            return treeb[root];
        }
        int midd=(l+r)>>1;
        int ans=inf;
        if(L<=midd)
            ans=min(ans,queryb(L,R,root<<1,l,midd));
        if(R>midd)
            ans=min(ans,queryb(L,R,root<<1|1,midd+1,r));
        return ans;
    }
    int main(){
        int n;
        while(scanf("%d",&n)!=EOF){
                memset(treea,0x3f,sizeof(treea));
                memset(treeb,0x3f,sizeof(treeb));
            for(int i=1;i<=n;i++)
                scanf("%d",&a[i]),mpa[a[i]]=i;
            for(int i=1;i<=n;i++)
                scanf("%d",&b[i]),mpb[b[i]]=i;
            build(1,1,n);
            int now=1,i;
            int flag=1;
            for( i=1;i<=n;i++){
                for(int j=1;j<=i;){
                    int x=querya(j,i,1,1,n);
                    int y=queryb(j,i,1,1,n);
                   // cout<<i<<"!!!!!"<<j<<endl;
                    if(mpa[x]==mpb[y])
                        j=mpa[x]+1;
                    else{
                        flag=0;
                        break;
                    }
     
                }
                if(!flag)
                    break;
            }
            printf("%d\n",i-1);
        }
        return 0;
     
    }

单调队列做法（160MS）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    vector<int>aa,bb;
    const int M=1e5+5;
    int a[M],b[M];
    int main(){
        int n;
        while(~scanf("%d",&n)){
                aa.clear();
            bb.clear();
            for(int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            for(int i=1;i<=n;i++)
                scanf("%d",&b[i]);
            int i;
            for(i=1;i<=n;i++){
                while(!aa.empty()&&aa.back()>a[i])
                    aa.pop_back();
                while(!bb.empty()&&bb.back()>b[i])
                    bb.pop_back();
                aa.push_back(a[i]);
                bb.push_back(b[i]);
                if(aa.size()!=bb.size())
                    break;
            }
            printf("%d\n",i-1);
    
            //cout<<"!!"<<endl;
        }
        return 0;
    }

[B题][B]

参考博客：https://www.cnblogs.com/Dillonh/p/11209476.html

小队的人推到第3项是正确的，有兴趣的小伙伴可以尝试推推第4项

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int M=1e3+3;
    const int mod=1e9+7;
    ll a[M];
    ll ni(ll x,ll y=mod-2){
        ll t=1;
        while(y){
            if(y&1)
                t=t*x%mod;
            x=x*x%mod;
            y>>=1;
        }
        return t;
    }
    int main(){
        int n;
        while(~scanf("%d",&n)){
            for(int i=1;i<=n;i++)
                scanf("%d",&a[i]);
            ll ans=0;
            for(int i=1;i<=n;i++){
                ll t=1ll;
                for(int j=1;j<=n;j++){
                    if(i==j)
                        continue;
                    t=(t*((a[j]*a[j]-a[i]*a[i])%mod+mod)%mod)%mod;
                }
                t=(t*2*a[i]%mod)%mod;
                ans=(ans+ni(t))%mod;
            }
            printf("%lld\n",ans);
        }
    }

[E题][E]

题意：就是要你构造出一个含‘A’和‘B’的序列，然后要求可以分成n个AB和m个BA（其中一旦某个字符被拿去构成AB或BA那么下次就不能再用他来构造了）

分析：我们先考虑当前序列只有n个A可拿来进行构造，没有B，那么在下一位中是不是只能是B？答案是肯定的，因为，你只能构成AB或BA的俩种，而后者已经明确不能构成（因为前面没有B可拿来构造），那么只能是AB这种顺序的。也就是说当i（我们认为可以是可用来构造序列的A的个数）-j（我们认为可以是可用来构造序列的A的个数）<n的话，我们可以加A，即那么下一个\[i+1\]\[j\]的方案数一定包含当前的方案数也就是直接加上\[i\]\[j\],即使用dp来完成这个步骤。加B的操作也是类似

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int M=2e3+2;
    const ll mod=1e9+7;
    ll dp[M][M];
    int main(){
        int n,m;
        while(~scanf("%d%d",&n,&m)){
            int len=n+m;
            for(int i=0;i<=len;i++)
                for(int j=0;j<=len;j++)
                    dp[i][j]=0;
            dp[0][0]=1;
            for(int i=0;i<=len;i++)
            for(int j=0;j<=len;j++){
                if(i-j<n)
                    dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
                if(j-i<m)
                    dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
            }
            printf("%d\n",dp[len][len]);
        }
        return 0;
    }

[ F题][F]

理解粗：https://blog.csdn.net/monochrome00/article/details/98205456

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int M=5e3+3;
    int head[M],match[M],a[M],book[M],col[M],vis[M];
    int n,tot;
    struct node{
        int v,nextt;
    }e[M*M];
    void addedge(int u,int v){
        e[tot].v=v;
        e[tot].nextt=head[u];
        head[u]=tot++;
    }
    bool check(int x){
        for(int i=0;i<=30;i++){
            if((1<<i)==x)
                return true;
        }
        return false;
    }
    bool dfs(int x){
        book[x]=1;
        for(int i=head[x];~i;i=e[i].nextt){
            int v=e[i].v;
            if(!book[v]){
                book[v]=1;
                if(!match[v]||dfs(match[v])){
                    match[v]=x;
                    match[x]=v;
                    return true;
                }
            }
        }
        return false;
    }
    int main(){
        memset(head,-1,sizeof(head));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            int x=a[i],countt=0;
            while(x){
                countt+=x&1;
                x>>=1;
            }
            col[i]=countt&1;
        }
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++){
                {
                    //cout<<"@@"<<(a[i]^a[j])<<endl;
                    if(check(a[i]^a[j])){
                        if(col[i]==0)
                            addedge(i,j);
                        else
                            addedge(j,i); 
                        
                    }
                }
            }
        int ans=0;
        for(int i=1;i<=n;i++)
            if(col[i]==0){
                for(int j=1;j<=n;j++)
                    book[j]=0;
                if(dfs(i))
                    ans++;
        }
        printf("%d\n",n-ans);
        for(int j=1;j<=n;j++)
            book[j]=0;
        for(int i=1;i<=n;i++){
        //    cout<<match[i]<<endl;
            if(col[i]==0&&!match[i])
                dfs(i);
        } 
        for(int i=1;i<=n;i++){
            if((col[i]==0&&book[i])||(col[i]==1&&!book[i]))
                printf("%d ",a[i]);
        }
        return 0;
    }

[ H题][H]

题意：给定n（我们要构造除的字符串长度）m（m\*（m-1）/2组条件）每个条件的意思是：删除构造字符串中除了c1，c2以外的字符剩下来的字符串

由于是有先后顺序的，所以考虑用拓扑排序来接，因为拓扑排序是以入度为0开始算，我们把这个入度为0在这里规定为当前位置之前没有比他位置小的字符，就顺理成章地可以用拓扑排序

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int M=1e4+4;
    int vis[30],visno[30];
    char str[2],ans[M],s[M];
    int tot,fuck[M*100],du[M*100],id[M];
    vector<int>mp[30],g[M*100];
    int main(){
        int n,m;
        scanf("%d%d",&n,&m);
        int t=m*(m-1)/2;
        int flag=1;
        memset(vis,-1,sizeof(vis));
        for(int i=1;i<=t;i++){
            scanf("%s",str);
            int len;
            scanf("%d",&len);
            
            int c1=str[0]-'a';
            int c2=str[1]-'a';
            if(len==0){
                visno[c1]=1;
                visno[c2]=1;
                continue;
            }scanf("%s",s);
            if(vis[c1]==-1){
                int countt=0;
                for(int j=0;j<len;j++){
                    if(str[0]==s[j]){
                        id[j]=++tot;
                        mp[c1].push_back(tot);
                        fuck[tot]=c1;
                        countt++;
                    }
                }
                vis[c1]=countt;
            }
            else{
                int countt=0;
                for(int j=0;j<len;j++){
                    if(s[j]==str[0]){
                        if(countt<mp[c1].size())
                            id[j]=mp[c1][countt];
                        countt++;
                    }
                }
                if(countt!=vis[c1])
                    flag=0;
            }
            if(vis[c2]==-1){
                int countt=0;
                for(int j=0;j<len;j++){
                    if(str[1]==s[j]){
                        id[j]=++tot;
                        mp[c2].push_back(tot);
                        fuck[tot]=c2;
                        countt++;
                    }
                }
                vis[c2]=countt;
            }
            else{
                int countt=0;
                for(int j=0;j<len;j++){
                    if(s[j]==str[1]){
                        if(countt<mp[c2].size())
                            id[j]=mp[c2][countt];
                        countt++;
                    }
                }
                if(countt!=vis[c2])
                    flag=0;
            }
            for(int j=0;j<len-1;j++){
                g[id[j]].push_back(id[j+1]);
                du[id[j+1]]++;
            }
        }
        for(int i=0;i<m;i++){
            if(vis[i]&&visno[i])
                flag=0;
        }
        if(!flag||n!=tot)
            return puts("-1"),0;
        int cnt=0;
        //cout<<"!!"<<endl;
        queue<int>que;
        for(int i=1;i<=tot;i++)
            if(du[i]==0)
                que.push(i);
        while(!que.empty()){
            int u=que.front();
                que.pop();
            ans[cnt++]=fuck[u]+'a';
            for(int i=0;i<g[u].size();i++){
                int v=g[u][i];
                du[v]--;
                if(du[v]==0){
                    que.push(v);
                }
            }
        }
        
        for(int i=1;i<=tot;i++)
            if(du[i]>0)
                return puts("-1"),0;
        ans[cnt]='\0';
        printf("%s",ans);
        return 0;
    }

[ G题][G]

题意：找出符合给定字符串都是星期五的0~9对应的A~J的全排列

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    vector<string>a;
    int ans[10];
    int mon[2][12] = {
        {
          31,28,31,30,31,30,31,31,30,31,30,31},
        {
          31,29,31,30,31,30,31,31,30,31,30,31}
    };
    bool ck(int x){
        return (x%4==0&&x%100!=0)||x%400==0;
    } 
    int riqi(int year,int month,int date){
        if(year<1600||month>12||month==0)
            return 0;
        if(ck(year)){
            if(date==0||date>mon[1][month-1])
                return 0;
        }
        else{
            if(date==0||date>mon[0][month-1])
                return 0;
        }
        //蔡勒公式 
        if(month<=2)//月份的1，2月按13，14月来算 
            month+=12,year--;
        int cen=year/100;
        return ((cen/4-2*cen+year%100+year%100/4+26*(month+1)/10+date-1)%7+7)%7;
    }
    int main(){
        int t;
        cin>>t;
        for(int k=1;k<=t;k++){
            int n;
            cin>>n;
            a.resize(n);
            for(int i=0;i<n;i++)
                cin>>a[i];
            sort(a.begin(),a.end());
            a.erase(unique(a.begin(),a.end()),a.end());//去掉重复的，因为重复了再算一遍也是一样
            //枚举0~9的全排列，找答案 
            for(int i=0;i<10;i++)
                ans[i]=i; 
            printf("Case #%d: ",k);
            int ff=0;
            do{
                int flag=1;
                for(int i=0;i<a.size();i++){
                    int y=0,m=0,d=0;
                    for(int j=0;j<4;j++)
                        y=y*10+ans[a[i][j]-'A'];
                    for(int j=5;j<7;j++)
                        m=m*10+ans[a[i][j]-'A'];
                    for(int j=8;j<10;j++)
                        d=d*10+ans[a[i][j]-'A'];
                    if(riqi(y,m,d)!=5){
                        flag=0;
                        break;
                    }
                }
                if(flag){
                    ff=1;
                    for(int j=0;j<10;j++)
                        cout<<ans[j];
                    cout<<endl;
                    break;
                }
            }while(next_permutation(ans,ans+10));
            if(!ff)
                puts("Impossible");
        }
        return 0;
    }

[ C题][C]

分析：以高度排序，枚举每一高度，对当前枚举到的这个高度视为最高高度，数目由num棵，然后后面肯定要砍掉因为比他高，然后再考虑比他小的，因为要构成俩倍的关系，所以最多保留num-1棵。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=205;
    const int M=1e5+5;
    ll tree[N][2];
    struct node{
        ll h,p,c;
    }a[M];
    ll sufc[M],sufp[M];
    bool cmp(node p,node q){
        return p.h<q.h;
    }
    void add(int u,ll x,int i){
        while(u<=200){
            tree[u][i]+=x;
            u+=-u&u;
        }
    }
    ll SUM(int u,int i){
        ll ans=0ll;
        while(u){
            ans+=tree[u][i];
            u-=-u&u;
        }
        return ans;
    }
    int main(){
        int n;
        while(~scanf("%d",&n)){
            memset(tree,0ll,sizeof(tree));
            ll sum=0,maxc=0,minc=M;
            for(int i=1;i<=n;i++){
                scanf("%lld%lld%lld",&a[i].h,&a[i].c,&a[i].p);
                sum+=a[i].p;
                maxc=max(maxc,a[i].c);
                minc=min(minc,a[i].c);
            }
            sort(a+1,a+1+n,cmp);
            for(int i=n;i>=1;i--){
                sufc[i]=sufc[i+1]+a[i].p*a[i].c;//后缀代价总和
                sufp[i]=sufp[i+1]+a[i].p;//后缀树木总数和 
            }
            ll ans=sufc[1];
            int i=1;
            /*for(int i=1;i<=n;i++)
                cout<<sufc[i]<<" ";
            cout<<endl;*/
            while(i<=n){
                int l=i,r=i;
                ll num=0ll,needcost=0ll;
                while(r<=n&&a[r].h==a[l].h)
                    num+=a[r++].p;
                
                needcost+=sufc[r];
                ll need=sum-num-sufp[r]-(num-1);//枚举到当前认定为最高高度，比当前高的肯定要砍掉，然后再考虑前面因为要俩倍，所以最多砍掉num-1棵树 
                if(need<=0)
                    ans=min(ans,needcost);
                else{
                    ll L=minc,R=maxc,s=0ll;
                    while(L<=R){
                        ll midd=(L+R)>>1;
                        if(SUM(midd,0)>=need)
                            s=midd,R=midd-1;
                        else
                            L=midd+1;
                    }
                    need-=SUM(s,0);
                    needcost+=SUM(s,1);
                    //因为要保持贪心，所以出现前缀和大于要砍的树的时候要减掉多出来的代价 
                    needcost-=s*abs(need);
                }
                ans=min(ans,needcost); 
                while(l<r){
                    add(a[l].c,a[l].p,0);
                    add(a[l].c,a[l].c*a[l].p,1);
                    l++;
                }
                i=r;//cout<<r<<endl;
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/starve/p/11211157.html

[A]: https://ac.nowcoder.com/acm/contest/881/A
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211018/189780f0cac24dbbb2bbd4a00bdadabc.png
[B]: https://ac.nowcoder.com/acm/contest/881/B
[E]: https://ac.nowcoder.com/acm/contest/881/E
[F]: https://ac.nowcoder.com/acm/contest/885/F
[H]: https://ac.nowcoder.com/acm/contest/885/H
[G]: https://ac.nowcoder.com/acm/contest/886/G
[C]: https://ac.nowcoder.com/acm/contest/887/C