Educational Codeforces Round 56 (Rated for Div. 2)-白红宇

Educational Codeforces Round 56 (Rated for Div. 2)

阅读量：6214 次

发布时间：2019-06-21

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

涨rating啦。。

不过话说为什么有这么多数据结构题啊，难道是中国人出的？

A - Dice Rolling

傻逼题，可以用一个三加一堆二或者用一堆二，那就直接。。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;const int Maxn=610000;int main() { int t,x; scanf("%d",&t); while(t--) { scanf("%d",&x); printf("%d\n",x>>1); } return 0;}

B - Letters Rearranging

统计一下如果全部相同输出-1，否则排个序就好了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;const int Maxn=610000;char s[Maxn];int b[110];int main() { int t,x; scanf("%d",&t); while(t--) { scanf("%s",s); memset(b,0,sizeof(b)); int lens=strlen(s); for(int i=0;i

C - Mishka and the Last Exam

大概就是让前面的尽量小，让后面的尽量大，那就直接扫就好了。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;const int Maxn=610000;int n;ll b[Maxn],a[Maxn];int main() { scanf("%d",&n); for(int i=1;i<=n/2;i++) scanf("%I64d",&b[i]); ll temp=0,tempp=0x7fffffffffffffff; for(int i=1;i<=n/2;i++) { ll x=b[i]-temp; if(x>tempp) x=tempp; temp=a[i]=b[i]-x; tempp=a[n-i+1]=x; } for(int i=1;i<=n;i++) printf("%I64d ",a[i]); return 0;}

D - Beautiful Graph

二分图染个色就好了。。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;const int Maxn=610000;const ll mod=998244353;ll powp(ll a,ll b) { ll ans=1; while(b) { if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans;}int vis[Maxn],col[Maxn],to[Maxn],nxt[Maxn],first[Maxn],tot;int t,n,m,u,v,flag;ll bj0,bj1;void work(int root) { vis[root]=1; for(int i=first[root];i;i=nxt[i]) if(!vis[to[i]]) { col[to[i]]=col[root]^1; if(col[to[i]]) bj1++; else bj0++; work(to[i]); } else if(col[to[i]]==col[root]) flag=1;}inline void add(int u,int v) { to[tot]=v; nxt[tot]=first[u]; first[u]=tot++; to[tot]=u; nxt[tot]=first[v]; first[v]=tot++;}int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) first[i]=0,vis[i]=0; tot=1; for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); add(u,v); } ll ans=1;flag=0; for(int i=1;i<=n;i++) if(!vis[i]) { bj0=bj1=0;bj0++;col[i]=0; work(i); if(flag) { ans=0; break; } ans=ans*(powp(2,bj0)+powp(2,bj1))%mod; } printf("%d\n",ans); } return 0;}

G - Multidimensional Queries

大概就是有n个k维空间上的点，每次修改一个点或查找区间内选两个点的曼哈顿距离最大值。

首先如果k==2，那就可以转切比雪夫距离。

考虑转切比雪夫的时候，把原来的坐标\((x,y)\)变成了\((x+y,x-y)\)，这么做的原因就是x与y的大小关系相同或不同。那么如果扩展到k维，那就是k个坐标的大小关系相同或不同。比如三维的情况：\((x,y,z)\)转成\((x+y+z,x+y-z,x-y+z,x-y-z)\)。那么k维的就可以转成\(2^{k-1}\)维，那就直接开这些线段树就好了。

时空复杂度:\(O(2^{k-1}n\log n)\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;const int Maxn=610000;const int inf=0x7fffffff;int n,k,tmp[10],tot,b[110][10];void dfs(int now) { if(now==k) { tot++; for(int i=1;i
             
              >1; build(root<<1,l,mid); build((root<<1)|1,mid+1,r);}struct segtree { int tn[Maxn],tm[Maxn]; int update(int root) { tn[root]=min(tn[root<<1],tn[(root<<1)|1]); tm[root]=max(tm[root<<1],tm[(root<<1)|1]); } void change(int root,int x,int y) { int l=tl[root],r=tr[root]; if(l==r) { tn[root]=tm[root]=y; return; } int mid=l+r>>1; if(x<=mid) change(root<<1,x,y); else change((root<<1)|1,x,y); update(root); } int qmin(int root,int l,int r) { int lc=tl[root],rc=tr[root]; int mid=lc+rc>>1; if(l<=lc&&r>=rc) return tn[root]; int ans=inf; if(l<=mid) ans=min(ans,qmin(root<<1,l,r)); if(r>mid) ans=min(ans,qmin((root<<1)|1,l,r)); return ans; } int qmax(int root,int l,int r) { int lc=tl[root],rc=tr[root]; int mid=lc+rc>>1; if(l<=lc&&r>=rc) return tm[root]; int ans=-inf; if(l<=mid) ans=max(ans,qmax(root<<1,l,r)); if(r>mid) ans=max(ans,qmax((root<<1)|1,l,r)); return ans; }}t[21];int main() { scanf("%d%d",&n,&k); dfs(1);build(1,1,n); for(int i=1;i<=n;i++) { for(int j=1;j<=k;j++) scanf("%d",&tmp[j]); for(int j=1;j<=tot;j++) { int temp=tmp[1]; for(int l=1;l

转载于:https://www.cnblogs.com/shanxieng/p/10128033.html

你可能感兴趣的文章