博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
BZOJ 4236~4247 题解
阅读量：6652 次
发布时间：2019-06-25

本文共 16548 字，大约阅读时间需要 55 分钟。

BZOJ 4236 JOIOJI

f[i][0..2]表示前i个字符中′J′/′O′/′I′的个数
将二元组<f[i][0]−f[i][1],f[i][1]−f[i][2]>扔进map，记录一下最早出现的时间
对于每一个位置去map里面查一下就可以
时间复杂度O(nlogn)

#include #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define M 200200using namespace std;int n,ans;char s[M];map
           
            
             ,int> m;int sum[3][M];int main(){ int i; cin>>n; scanf("%s",s+1); m[make_pair(0,0)]=0; for(i=1;i<=n;i++) { sum[0][i]=sum[0][i-1]+(s[i]=='J'); sum[1][i]=sum[1][i-1]+(s[i]=='O'); sum[2][i]=sum[2][i-1]+(s[i]=='I'); if( m.find( make_pair(sum[0][i]-sum[1][i],sum[1][i]-sum[2][i]) )==m.end() ) m[make_pair(sum[0][i]-sum[1][i],sum[1][i]-sum[2][i])]=i; else ans=max(ans,i-m[make_pair(sum[0][i]-sum[1][i],sum[1][i]-sum[2][i])]); } cout<
             
              <

BZOJ 4237 稻草人

按y坐标分治。每层分治内部按x坐标排序后。上层维护一个单调递减的单调栈，下层维护一个单调递增的单调栈
然后对于上层每一个元素去下层二分就可以
时间复杂度O(nlog2n)

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define M 200200using namespace std;struct Point{    int x,y;    friend istream& operator >> (istream &_,Point &p)    {        return scanf("%d%d",&p.x,&p.y),_;    }}points[M],_points[M];bool Compare_x (const Point &p1,const Point &p2){    return p1.x < p2.x ;}bool Compare_y (const Point &p1,const Point &p2){    return p1.y < p2.y ;}int n;long long ans;Point stack1[M],stack2[M];int top1,top2;void Divide_And_Conquer(int l,int r){    if(l==r) return ;    int i,j,mid=l+r>>1;    int _l=l,_r=mid+1;    for(i=l;i<=r;i++)        if(points[i].y<=mid)            _points[_l++]=points[i];        else            _points[_r++]=points[i];    memcpy(points+l,_points+l,sizeof(Point)*(r-l+1) );    for(top1=top2=0,j=l,i=mid+1;i<=r;i++)    {        for(;j<=mid&&points[j].x
          
           stack2[top2].y)                top2--;            stack2[++top2]=points[j];        }        while(top1&&points[i].y
           
             b[M]; int i; cin>>n; for(i=1;i<=n;i++) cin>>points[i]; for(i=1;i<=n;i++) b[i]=make_pair(points[i].x,&points[i].x); sort(b+1,b+n+1); for(i=1;i<=n;i++) *b[i].second=i; for(i=1;i<=n;i++) b[i]=make_pair(points[i].y,&points[i].y); sort(b+1,b+n+1); for(i=1;i<=n;i++) *b[i].second=i; sort(points+1,points+n+1,Compare_x); Divide_And_Conquer(1,n); cout<
            
             <

BZOJ 4238 电压

看到这题想要直接上动态二分图的举手……
任选一棵生成树。考虑选择树边或者非树边
定义一条非树边为好边当且仅当两个端点在树上的距离为奇数。否则为坏边
假设坏边仅仅有一条那么这条坏边是可选的
假设一条树边被全部的坏边覆盖并且不被好边覆盖那么这条边是可选的
DFS一遍就可以
因为DFS树没有横叉边仅仅有返祖边因此求LCA是O(1)的 这样复杂度就是O(n+m)的了

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define M 200200using namespace std;struct abcd{    int to,next;}table[M<<1];int head[M],tot=1;int n,m,ans,good_cnt,bad_cnt;int dpt[M],fa[M],good[M],bad[M];bool v[M];void Add(int x,int y){    table[++tot].to=y;    table[tot].next=head[x];    head[x]=tot;}void DFS(int x,int from){    int i;    v[x]=true;    dpt[x]=dpt[fa[x]]+1;    for(i=head[x];i;i=table[i].next)        if(i^from^1)        {            if(!v[table[i].to])            {                fa[table[i].to]=x;                DFS(table[i].to,i);                good[x]+=good[table[i].to];                bad[x]+=bad[table[i].to];            }            else            {                if(dpt[table[i].to]>dpt[x])                    continue;                if(dpt[x]-dpt[table[i].to]&1)                    good[x]++,good[table[i].to]--,good_cnt++;                else                    bad[x]++,bad[table[i].to]--,bad_cnt++;            }        }}int main(){    int i,x,y;    cin>>n>>m;    for(i=1;i<=m;i++)    {        scanf("%d%d",&x,&y);        Add(x,y);        Add(y,x);    }    for(i=1;i<=n;i++)        if(!v[i])            DFS(i,0);    for(i=1;i<=n;i++)        if(fa[i]&&bad[i]==bad_cnt&&!good[i])            ++ans;    if(bad_cnt==1)        ++ans;    cout<
          
           <

BZOJ 4239 巴士走读

将二元组<网站，时间>看做一个点，那么点数是O(m)的
每辆巴士连一条边。每一个点向下一个时间连边，然后将全部边反向
枚举终点站的每一个时间。增加队列广搜，得到最晚多久到达1号网站能够在这个时间到达终点站
然后对于每一个询问去数组中二分就可以
时间复杂度O((m+q)logm)

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define M 100100using namespace std;namespace Hash_Set{    struct List{        int x,y,val;        List *next;        List(int _,int __,List *___):            x(_),y(__),val(0),next(___) {}    }*head[3001][3001];    int& Hash(int x,int y)    {        int pos1=x%3001;        int pos2=y%3001;        List *temp;        for(temp=head[pos1][pos2];temp;temp=temp->next)            if(temp->x==x&&temp->y==y)                return temp->val;        return (head[pos1][pos2]=new List(x,y,head[pos1][pos2]))->val;    }}struct abcd{    int to,next;}table[900900];int head[600600],tot;int n,m,k,now=-1;pair
           
             ans[600600];int top;vector
            
              stack[M];int T;pair
             
               hash[600600];bool v[600600];int q[600600],r,h;void Add(int x,int y){ table[++tot].to=y; table[tot].next=head[x]; head[x]=tot;}int Hash(int x,int y){ int &val=Hash_Set::Hash(x,y); if( !val ) hash[val=++T]=make_pair(x,y); return val;}void BFS(){ int i; while(r!=h) { int x=q[++h]; for(i=head[x];i;i=table[i].next) if(!v[table[i].to]) { v[table[i].to]=true; q[++r]=table[i].to; } if(hash[x].first==1) now=max(now,hash[x].second); }}int main(){ int i,j,x,y,_x,_y; cin>>n>>m; for(i=1;i<=m;i++) { scanf("%d%d%d%d",&x,&y,&_x,&_y); stack[x].push_back(_x); stack[y].push_back(_y); Add( Hash(y,_y) , Hash(x,_x) ); } for(i=1;i<=n;i++) { sort(stack[i].begin(),stack[i].end()); for(j=1;j<(signed)stack[i].size();j++) if( stack[i][j]!=stack[i][j-1] ) Add( Hash(i,stack[i][j]) , Hash(i,stack[i][j-1]) ); } for(i=0;i<(signed)stack[n].size();i++) { int temp=Hash(n,stack[n][i]); if(v[temp]) continue; v[temp]=true;q[++r]=temp; BFS(); ans[++top]=make_pair(stack[n][i],now); } ans[0].second=-1; cin>>k; for(i=1;i<=k;i++) { scanf("%d",&x); printf("%d\n",(lower_bound(ans+1,ans+top+1,pair
              
               (x,0x3f3f3f3f) )-1)->second); } return 0;}

BZOJ 4240 有趣的家庭菜园

从小到大枚举高度，因为不管将这株草移动到左側还是右側都对照它高的植物没有影响，因此贪心选择代价最小的方向就可以
故答案为∑min(a[1…i-1]中大于a[i]的数的数量,a[i+1…n]中大于a[i]的数的数量)
用树状数组就可以 时间复杂度O(nlogn)

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define M 300300using namespace std;int n,m,a[M],f[M],g[M];long long ans;namespace BIT{    int c[M];    void Initialize()    {        memset(c,0,sizeof c);    }    void Update(int x)    {        for(;x;x-=x&-x)            c[x]++;    }    int Query(int x)    {        int re=0;        for(;x<=m;x+=x&-x)            re+=c[x];        return re;    }}int main(){    static pair
          
            b[M];    int i;    cin>>n;    for(i=1;i<=n;i++)    {        scanf("%d",&b[i].first);        b[i].second=&a[i];    }    sort(b+1,b+n+1);    for(i=1;i<=n;i++)    {        if(i==1||b[i].first!=b[i-1].first)            ++m;        *b[i].second=m;    }    for(i=1;i<=n;i++)    {        BIT::Update(a[i]);        f[i]=BIT::Query(a[i]+1);    }    BIT::Initialize();    for(i=n;i;i--)    {        BIT::Update(a[i]);        g[i]=BIT::Query(a[i]+1);    }    for(i=1;i<=n;i++)        ans+=min(f[i],g[i]);    cout<
           
            <

BZOJ 4241 历史研究

分块，记录第i块到第j块的答案以及前i块中数字j出现了多少次，然后每次询问先调用整块的答案，然后枚举零碎的部分进行更新就可以
时间复杂度O(qn√)

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define M 100100#define B 350using namespace std;int n,m,q,b;int a[M],ori[M];int l[B],r[B],belong[M];int block_cnt[B][M];//block_cnt[i][j]表示前i块中数字j的出现次数long long block_ans[B][B];//block_ans[i][j]表示从第i块到第j块的最大重要度long long Query(int l,int r){    static int cnt[M],tim[M],T;    int i,_l=belong[l],_r=belong[r];    long long re=block_ans[_l+1][_r-1];    ++T;    if(_l==_r)    {        for(i=l;i<=r;i++)        {            if(tim[a[i]]!=T)                tim[a[i]]=T,cnt[a[i]]=0;            re=max(re,(long long)ori[a[i]]*++cnt[a[i]]);        }        return re;    }    for(i=l;i<=::r[_l];i++)    {        if(tim[a[i]]!=T)            tim[a[i]]=T,cnt[a[i]]=block_cnt[_r-1][a[i]]-block_cnt[_l][a[i]];        re=max(re,(long long)ori[a[i]]*++cnt[a[i]]);    }    for(i=r;i>=::l[_r];i--)    {        if(tim[a[i]]!=T)            tim[a[i]]=T,cnt[a[i]]=block_cnt[_r-1][a[i]]-block_cnt[_l][a[i]];        re=max(re,(long long)ori[a[i]]*++cnt[a[i]]);    }    return re;}int main(){    static pair
           
             c[M]; int i,j,x,y; cin>>n>>q; b=int(sqrt(n)+1e-7); for(i=1;i<=n;i++) { scanf("%d",&c[i].first); c[i].second=&a[i]; } sort(c+1,c+n+1); for(i=1;i<=n;i++) { if(i==1||c[i].first!=c[i-1].first) ori[++m]=c[i].first; *c[i].second=m; } for(i=1;i<=n;i++) belong[i]=(i-1)/b+1; for(i=1;(i-1)*b+1<=n;i++) l[i]=(i-1)*b+1,r[i]=min(i*b,n); for(i=1;i<=n;i++) block_cnt[belong[i]][a[i]]++; for(i=1;l[i];i++) for(j=1;j<=n;j++) block_cnt[i][j]+=block_cnt[i-1][j]; static int cnt[M]; long long ans; for(i=1;l[i];i++) { memset(cnt,0,sizeof cnt);ans=0; for(j=l[i];j<=n;j++) { ans=max(ans,(long long)ori[a[j]]*++cnt[a[j]]); if(j==r[belong[j]]) block_ans[i][belong[j]]=ans; } } for(i=1;i<=q;i++) { scanf("%d%d",&x,&y); #ifdef ONLINE_JUDGE printf("%lld\n",Query(x,y)); #else printf("%I64d\n",Query(x,y)); #endif } return 0;}

BZOJ 4242 水壶

把每栋建筑物扔进队列跑BFS，对于每块空地记录这块空地是被哪栋建筑物搜到的。以及距离是多少
然后不同所属的空地之间连边，跑货车运输就可以
时间复杂度O(whα(p)+qlogp)

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define M 200200using namespace std;const int dx[]={
     0,0,1,-1};const int dy[]={
     1,-1,0,0};int n,m,k,Q;char map[2020][2020];pair
           
             v[2020][2020];pair
            
              q[4004004];int r,h;vector< pair
             
               > stack[4004004];int fa[M],dis[M],dpt[M];void BFS(){ int i; while(r!=h) { pair
              
                x=q[++h]; for(i=0;i<4;i++) { pair
               
                 y(x.first+dx[i],x.second+dy[i]); if( y.first==0 || y.second==0 || y.first==n+1 || y.second==m+1 || map[y.first][y.second]=='#' ) continue; if( v[y.first][y.second]==pair
                
                 (0,0) ) q[++r]=y,v[y.first][y.second]=pair
                 
                  (v[x.first][x.second].first+1,v[x.first][x.second].second); else if(v[y.first][y.second].second!=v[x.first][x.second].second) stack[v[y.first][y.second].first+v[x.first][x.second].first].push_back(pair
                  
                   (v[y.first][y.second].second,v[x.first][x.second].second)); } }}namespace Union_Find_Set{ int fa[M],rank[M]; int Find(int x) { if(!fa[x]||fa[x]==x) return fa[x]=x; return fa[x]=Find(fa[x]); }}void Kruskal(){ using namespace Union_Find_Set; int i,j; for(i=0;i<=n*m;i++) for(j=0;j<(signed)stack[i].size();j++) { int x=Find(stack[i][j].first); int y=Find(stack[i][j].second); if(x==y) continue; if(rank[x]>rank[y]) swap(x,y); if(rank[x]==rank[y]) ++rank[y]; Union_Find_Set::fa[x]=y; ::fa[x]=y;dis[x]=i; }}int Depth(int x){ if(dpt[x]) return dpt[x]; if(!fa[x]) return dpt[x]=1; return dpt[x]=Depth(fa[x])+1;}int Query(int x,int y){ if( Union_Find_Set::Find(x)!=Union_Find_Set::Find(y) ) return -1; int re=0; if(Depth(x)
                   
                    Depth(y)) re=max(re,dis[x]),x=fa[x]; while(x!=y) re=max(re,dis[x]),re=max(re,dis[y]),x=fa[x],y=fa[y]; return re;}int main(){ int i,x,y; cin>>n>>m>>k>>Q; for(i=1;i<=n;i++) scanf("%s",map[i]+1); for(i=1;i<=k;i++) { scanf("%d%d",&x,&y); v[x][y]=pair
                    
                     (0,i); q[++r]=pair
                     
                      (x,y); } BFS(); Kruskal(); for(i=1;i<=Q;i++) { scanf("%d%d",&x,&y); printf("%d\n",Query(x,y)); } return 0;}

BZOJ 4243 交朋友

把能进行会议的国家之间都用并查集连接起来。然后把每一个进行过会议的国家扔进队列跑BFS，将搜到的国家用并查集连接
终于答案等于每一个单点的出度个数+2*C(每一个集合的大小,2)
时间复杂度O((n+m)α(n))

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define M 100100using namespace std;int n,m;long long ans;set
           
             map[M];bool v[M];int q[M],r,h;namespace Union_Find_Set{ int fa[M],rank[M],size[M]; int Find(int x) { if(!fa[x]) fa[x]=x,size[x]=1; if(fa[x]==x) return x; return fa[x]=Find(fa[x]); } void Union(int x,int y) { x=Find(x);y=Find(y); if(x==y) return ; if(rank[x]>rank[y]) swap(x,y); if(rank[x]==rank[y]) ++rank[y]; fa[x]=y;size[y]+=size[x]; }}int main(){ using namespace Union_Find_Set; int i,x,y; set
            
             ::iterator it; cin>>n>>m; for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); map[x].insert(y); } for(i=1;i<=n;i++) for(it=map[i].begin();it!=map[i].end();it++) if( map[*it].find(i)!=map[*it].end() ) Union(i,*it); for(i=1;i<=n;i++) if(map[i].size()>1) { int temp=*map[i].begin(); for(it=map[i].begin(),it++;it!=map[i].end();it++) Union(*it,temp); } for(i=1;i<=n;i++) if(size[Find(i)]!=1) v[i]=1,q[++r]=i; while(r!=h) { x=q[++h]; for(it=map[x].begin();it!=map[x].end();it++) { Union(x,*it); if(!v[*it]) v[*it]=true,q[++r]=*it; } } for(i=1;i<=n;i++) if(Find(i)==i) { if(size[i]==1) ans+=map[i].size(); else ans+=(long long)size[i]*(size[i]-1); } cout<
             
              <

BZOJ 4244 邮戳拉力赛

从车站0沿上行车道到达车站n的路径必走，除掉这条路径后图中剩下了一些环
令fi,j表示已经经过了前i个邮戳台，并且从下行站台走到上行站台的次数-从上行站台走到下行站台的次数为j的最短时间
每层跑个全然背包就可以 时间复杂度O(n2)
顺便吐槽：官方能把スタンプラリー后面凝视一个“Collecting Stamps”我真是醉如烂泥。。。
谁能告诉我Stamp Rally究竟咋翻译……

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define M 3030using namespace std;int n,t;long long f[M][M];//f[i][j]表示已经到达过第1...i个邮戳，剩余的从上行站台走到下行站台的次数为j的最短时间int u[M],v[M],d[M],e[M];int main(){    int i,j;    cin>>n>>t;    for(i=1;i<=n;i++)        scanf("%d%d%d%d",&u[i],&v[i],&d[i],&e[i]);    memset(f,0x3f,sizeof f);    f[0][0]=0;    for(i=1;i<=n;i++)    {        for(j=0;j<=n;j++)            f[i-1][j]+=j*t*2;        for(j=1;j<=n;j++)            f[i][j]=min(f[i][j],f[i-1][j-1]+d[i]+v[i]);        for(j=0;j

BZOJ 4246 两个人的星座

这应该是这次合宿最难的一道题了……
考虑两个三角形。假设这两个三角形相离，那么一定能够做出两条内公切线，否则做不出来
枚举一个点，以这个点为中心按极角序枚举还有一个点。连接这两个点作出一条公切线，那么这两个三角形分别分布在这条线的两端，统计出两側每种颜色的点之后乘法原理就可以
时间复杂度O(n2logn)

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define M 3030#define PI 3.1415926535897932384626433832795028841971using namespace std;struct Point{    int x,y;    Point() {}    Point(int _,int __):        x(_),y(__) {}    friend Point operator + (const Point &p1,const Point &p2)    {        return Point(p1.x+p2.x,p1.y+p2.y);    }    friend Point operator - (const Point &p1,const Point &p2)    {        return Point(p1.x-p2.x,p1.y-p2.y);    }    friend double Arctan2(const Point &p)    {        double re=atan2(p.y,p.x);        if(re<=0) re+=PI;        return re;    }}O;pair
           
             points[M],stack[M]; int n,top;long long ans;void Calculate(int c){ static pair
            
              b[M]; static bool v[M]; static pair
             
               _stack[M]; int i,cnt[2][3]={ { 0,0,0},{ 0,0,0}}; for(i=1;i<=top;i++) b[i]=pair
              
               (Arctan2(stack[i].first-O),i); sort(b+1,b+top+1); for(i=1;i<=top;i++) _stack[i]=stack[b[i].second]; memcpy(stack+1,_stack+1,sizeof(stack[0])*top); for(i=1;i<=top;i++) if( stack[i].first.y
               
                O.x ) cnt[v[i]=false][stack[i].second]++; else cnt[v[i]=true][stack[i].second]++; for(i=1;i<=top;i++) { cnt[v[i]][stack[i].second]--; int cnt0=1,cnt1=1; if(c!=0) cnt0*=cnt[false][0]; if(c!=1) cnt0*=cnt[false][1]; if(c!=2) cnt0*=cnt[false][2]; if(stack[i].second!=0) cnt1*=cnt[true][0]; if(stack[i].second!=1) cnt1*=cnt[true][1]; if(stack[i].second!=2) cnt1*=cnt[true][2]; ans+=(long long)cnt0*cnt1; cnt0=cnt1=1; if(c!=0) cnt0*=cnt[true][0]; if(c!=1) cnt0*=cnt[true][1]; if(c!=2) cnt0*=cnt[true][2]; if(stack[i].second!=0) cnt1*=cnt[false][0]; if(stack[i].second!=1) cnt1*=cnt[false][1]; if(stack[i].second!=2) cnt1*=cnt[false][2]; ans+=(long long)cnt0*cnt1; cnt[v[i]^=1][stack[i].second]++; }}int main(){ int i,j; cin>>n; for(i=1;i<=n;i++) scanf("%d%d%d",&points[i].first.x,&points[i].first.y,&points[i].second); for(i=1;i<=n;i++) { top=0; for(j=1;j<=n;j++) if(i!=j) stack[++top]=points[j]; O=points[i].first; Calculate(points[i].second); } cout<

BZOJ 4247 挂饰

傻逼背包
时间复杂度O(n2)

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define M 2020using namespace std;int n;struct Array{    long long a[M<<1];    long long& operator [] (int x)    {        return a[min(max(x,-n),n)+2000];    }}f;int main(){    int i,j,x,y;    memset(&f,0xef,sizeof f);    cin>>n;f[0]=0;    for(i=1;i<=n;i++)    {        scanf("%d%d",&x,&y);        x=1-x;        if(x>0)        {            for(j=n;j>=-n;j--)                f[j+x]=max(f[j+x],f[j]+y);        }        else        {            for(j=-n;j<=n;j++)                f[j+x]=max(f[j+x],f[j]+y);        }    }    long long ans=0;    for(i=-n;i<=1;i++)        ans=max(ans,f[i]);    cout<
          
           <

转载地址：http://ytjto.baihongyu.com/

你可能感兴趣的文章
yarn upgrade 更新依赖包时yarn.lock更新但package.json不同步更新版本信息
查看>>
Vue基础指令集锦
查看>>
微信小程序中的iOS兼容性问题
查看>>
使用汇编语言编写加载器（加载用户程序）
查看>>
React中使用UEditor
查看>>
五分钟 Styled-components 高级实用技巧
查看>>
表单form的提交和servlet的取值
查看>>
文件系统&&磁盘管理(四)--文件系统管理
查看>>
全局作用域、函数作用域、块级作用域的理解
查看>>
算法-剑指offer
查看>>
端到端测试神器 cypress 浅入浅出
查看>>
二叉树实现按层 s型打印
查看>>
【跃迁之路】【542天】程序员高效学习方法论探索系列（实验阶段299-2018.08.01）...
查看>>
剥开比原看代码14：比原的挖矿流程是什么样的？
查看>>
兑吧：从自建HBase迁移到阿里云HBase实战经验
查看>>
SpringBoot @JmsListener(destination = ) 运行时动态修改
查看>>
【勘误】第3章 基本变量
查看>>
往ABAP gateway system上和Cloud Foundry上部署HTML5应用
查看>>
Java整型计算
查看>>
Excel快速批量导入生产Cavns并生成图片下载到本地
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2025-01-27 01:37:12   当前IP: 3.135.198.91   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我