CodeForces 234Div2-白红宇

CodeForces 234Div2

阅读量：4678 次

发布时间：2019-06-09

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

E. Inna and Binary Logic

显然对于一次更新应该一位一位的来，对于第k位的改变，通过找规律可以发现，被更新的数字数量为(k前面有多少个连续的1 + 1) * (k后面有多少个连续的1 + 1) ，找到这个规律时候，直接开线段树或者用set维护连续是1的区间就好了。

这里我是用set写的，毕竟时间给的比较松，STL果然是方便啊。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;#define MP(a,b) make_pair(a,b)typedef long long LL;typedef pair
                  
                    pii;const int maxn = 100000 + 5;int n,m;int a[maxn];set
                   
                     seg[32];LL add(set
                    
                      &sg,int pos,int k) { pii now = MP(pos,n + 1); set
                     
                      ::iterator it = sg.lower_bound(now); int cnt_prev = 0,cnt_next = 0,nl = pos,nr = pos; if(it != sg.begin()) { it--; if(it->second == pos - 1) { cnt_prev = it->second - it->first + 1; nl = it->first; sg.erase(it); } } it = sg.lower_bound(now); if(it != sg.end()) { if(it->first == pos + 1) { cnt_next = it->second - it->first + 1; nr = it->second; sg.erase(it); } } sg.insert(MP(nl,nr)); return (1LL << k) * (cnt_prev + 1) * (cnt_next + 1);}LL del(set
                      
                        &sg,int pos,int k) { pii now = MP(pos,n + 1); set
                       
                        ::iterator it = sg.upper_bound(now); it--; int cnt_prev = pos - it->first,cnt_next = it->second - pos; if(pos != it->first) sg.insert(MP(it->first,pos - 1)); if(pos != it->second) sg.insert(MP(pos + 1,it->second)); sg.erase(it); return (1LL << k) * (cnt_prev + 1) * (cnt_next + 1) * -1;}LL update(int p,int v) { LL ret = 0; for(int i = 0;i < 32;i++) { int bita = (bool)(a[p] & (1 << i)),bitb = (bool)(v & (1 << i)); if(bita == 0 && bitb == 1) ret += add(seg[i],p,i); if(bita == 1 && bitb == 0) ret += del(seg[i],p,i); } a[p] = v; return ret;}int main() { scanf("%d%d",&n,&m); LL sum = 0; for(int i = 1;i <= n;i++) { int tmp; scanf("%d",&tmp); sum += update(i,tmp); } for(int i = 1;i <= m;i++) { int p,v; scanf("%d%d",&p,&v); sum += update(p,v); cout << sum << endl; } return 0;}

D. Dima and Bacteria

先开一个并查集然后只把权值为0的边插进去统计同一种类的是否都在一个集合里面，如果不是的话直接No

然后因为同一种类型的细菌相互之间转化肯定是0，因此加入所有的边，只要两边不属于同一种类就更新种类之间的转换关系即可。

快速判断一个点属于哪一类可以先对c数组求前缀和，然后进行二分查找即可。

最后做一遍Folyd直接输出矩阵即可

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;typedef long long LL;const int maxn = 100000 + 5;const int maxk = 600;const int INF = INT_MAX / 3;int fa[maxn],c[maxk];int n,m,k,mp[maxk][maxk];int findp(int x) { return x == fa[x] ? x : fa[x] = findp(fa[x]);}inline int getid(int x) { return lower_bound(c + 1,c + 1 + k,x) - c;}void solve() { for(int p = 1;p <= k;p++) { for(int i = 1;i <= k;i++) { for(int j = 1;j <= k;j++) { mp[i][j] = min(mp[i][j],mp[i][p] + mp[p][j]); } } } puts("Yes"); for(int i = 1;i <= k;i++) { for(int j = 1;j <= k;j++) { if(j > 1) putchar(' '); if(mp[i][j] >= INF) printf("-1"); else printf("%d",mp[i][j]); } puts(""); }} int main() { scanf("%d%d%d",&n,&m,&k); for(int i = 1;i <= k;i++) scanf("%d",&c[i]); for(int i = 1;i <= k;i++) c[i] += c[i - 1]; for(int i = 1;i <= k;i++) { for(int j = 1;j <= k;j++) { mp[i][j] = INF; } mp[i][i] = 0; } for(int i = 1;i <= n;i++) fa[i] = i; int u,v,w,pa,pb,idu,idv; for(int i = 1;i <= m;i++) { scanf("%d%d%d",&u,&v,&w); if(w == 0) { pa = findp(u); pb = findp(v); if(pa != pb) fa[pa] = pb; } idu = getid(u); idv = getid(v); mp[idu][idv] = mp[idv][idu] = min(mp[idu][idv],w); } bool bad = false; for(int i = 1;i <= k;i++) { int nowfa = findp(c[i - 1] + 1); for(int j = c[i - 1] + 1;j <= c[i];j++) { if(findp(j) != nowfa) { bad = true; break; } } if(bad) break; } if(bad) puts("No"); else solve(); return 0;}

C. Inna and Huge Candy Matrix

本质上之后两种变化，一种是转置，一种是水平翻转。知道了之后随便搞一下就好了

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;typedef long long LL;int n,m,a,b,c,p;void swap(int &a,int &b) { int tmp = a; a = b; b = tmp;}void hr(int &x,int &y,int &n,int &m) { y = m - y + 1;}void c90(int &x,int &y,int &n,int &m) { swap(x,y); swap(n,m); hr(x,y,n,m);}void rc90(int &x,int &y,int &n,int &m) { hr(x,y,n,m); swap(x,y); swap(n,m);}void work(int x,int y,int n,int m) { for(int i = 0;i < a % 4;i++) c90(x,y,n,m); for(int i = 0;i < b % 2;i++) hr(x,y,n,m); for(int i = 0;i < c % 4;i++) rc90(x,y,n,m); printf("%d %d\n",x,y);}int main() { scanf("%d%d%d%d%d%d",&n,&m,&a,&b,&c,&p); for(int i = 1;i <= p;i++) { int nx,ny; scanf("%d%d",&nx,&ny); work(nx,ny,n,m); } return 0;}

B. Inna and New Matrix of Candies

水题，统计一下有几个不同的距离，有负数直接输出不行

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;typedef long long LL;const int maxn = 1005;set
                  
                    st;int main() { int n,m; scanf("%d%d",&n,&m); bool bad = false; for(int i = 1;i <= n;i++) { int ns,ng; for(int j = 1;j <= m;j++) { char tmp; scanf(" %c",&tmp); if(tmp == 'G') ng = j; if(tmp == 'S') ns = j; } if(ns - ng < 0) bad = true; st.insert(ns - ng); } if(bad) puts("-1"); else printf("%d\n",(int)st.size()); return 0;}

A. 随便模拟一下就好

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;typedef long long LL;const int maxn = 15;char buf[maxn];char mp[maxn][maxn];vector
                  
                    aa,ab;int main() { int T; scanf("%d",&T); while(T--) { scanf("%s",buf + 1); aa.clear(); ab.clear(); for(int r = 1;r <= 12;r++) if(12 % r == 0) { int cnt = 1; for(int i = 1;i <= r;i++) { for(int j = 1;j <= 12 / r;j++) { mp[i][j] = buf[cnt++]; } } bool ok = false; for(int j = 1;j <= 12 / r;j++) { ok = true; for(int i = 1;i <= r;i++) { if(mp[i][j] != 'X') ok = false; } if(ok) break; } if(ok) { aa.push_back(r); ab.push_back(12 / r); } } printf("%d",(int)aa.size()); for(int i = 0;i < aa.size();i++) printf(" %dx%d",aa[i],ab[i]); puts(""); } return 0;}

转载于:https://www.cnblogs.com/rolight/p/3893815.html

你可能感兴趣的文章