hihoCoder 2 * problem-白红宇

hihoCoder 2 * problem

阅读量：4634 次

发布时间：2019-06-09

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

1792

模拟，转化为二进制后逐位比较

1819

线段树维护区间加

维护每个数加了多少

每次弹出栈顶元素后栈顶位置注意清空

1792

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int N = 40;int a[N], b[N];int n;int Tow(int A[], int x) {    static int c[N];    int js = 0;    while(x) {        c[++ js] = x % 2;        x /= 2;    }    for(int i = 1; i <= js; i ++) A[i] = c[js - i + 1];    return js;}int main() {    cin >> n;    int Max = max(Tow(a, n), Tow(b, n - 1));    int Answer = 0;    for(int i = 1; i <= Max; i ++) Answer += (a[i] != b[i]);    cout << Answer;        return 0;}

1819

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define LL long long#define int long long#define gc getchar()inline int read() { int x = 0; char c = gc; while(c < '0' || c > '9') c = gc;while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}inline LL read_LL() {LL x = 0; char c = gc; while(c < '0' || c > '9') c = gc;while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}#undef gcconst int N = 2e5 + 10;LL W[N << 2], F[N << 2], Size[N << 2];int n;int Num[N], js;#define lson jd << 1#define rson jd << 1 | 1void Build_tree(int l, int r, int jd) { Size[jd] = (r - l + 1); if(l == r) return ; int mid = (l + r) >> 1; Build_tree(l, mid, lson), Build_tree(mid + 1, r, rson); }void Push_down(int jd) { W[lson] += Size[lson] * F[jd], W[rson] += Size[rson] * F[jd]; F[lson] += F[jd], F[rson] += F[jd]; F[jd] = 0;}LL Poi_A(int l, int r, int jd, int x) { if(l == r) { return W[jd]; } if(F[jd]) Push_down(jd); int mid = (l + r) >> 1; if(x <= mid) Poi_A(l, mid, lson, x); else Poi_A(mid + 1, r, rson, x);}void Sec_G(int l, int r, int jd, int x, int y, int num) { if(x <= l && r <= y) { W[jd] += Size[jd] * num; F[jd] += num; return ; } if(F[jd]) Push_down(jd); int mid = (l + r) >> 1; if(x <= mid) Sec_G(l, mid, lson, x, y, num); if(y > mid ) Sec_G(mid + 1, r, rson, x, y, num); W[jd] = W[lson] + W[rson];}main() { n = read(); Build_tree(1, n, 1); for(int i = 1; i <= n; i ++) { char opt[10]; scanf("%s", opt); if(opt[0] == 'p' && opt[1] == 'u') { int x = read(); Num[++ js] = x; } else if(opt[0] == 'p' && opt[1] == 'o') { LL Answer = Poi_A(1, n, 1, js); cout << Answer + Num[js] << "\n"; Sec_G(1, n, 1, js, js, - Answer); js --; } else { int k = read(), x = read(); Sec_G(1, n, 1, 1, k, x); } } return 0;}