这种题应该诸位处理

HDU 4588 Count The Carries

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4588

求a~b求和在二进制情况下共发生多少次进位。

1、将i转化成二进制，因为每一位只有出现多个1的时候才会产生进位。

2、所以，统计每一位1的个数即可。

3、统计1~b每一位1的个数，1~a-1中1的个数，作差即可。

（对于怎么统计1~n的每一位1的个数，数学好的应该一眼能看出，数学不好的找找规律画画就行，不难的）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 
 5 using namespace std;
 6 long long a, b;
 7 
 8 long long cal( long long b, long long a ){
 9     b++, a++;
10     long long ans = 0;
11     unsigned long long p = 2, k = 1;
12     long long tmp = 0;
13     for( int i = 0; i < 62; ++i ){
14         long long cnt1_b = (b/p)*k;
15         long long cnt1_a = (a/p)*k;
16         if( b%p > k )
17             cnt1_b += (b%p)-k;
18         if( a%p > k )
19             cnt1_a += (a%p)-k;
20         long long cnt1 = cnt1_b - cnt1_a;
21         ans += ( cnt1 + tmp )/2;
22         tmp = ( cnt1 + tmp )/2;
23         p *= 2, k *= 2;
24     }
25     //cout << "p:" << p << " k:" << k << endl;
26 
27     return ans;
28 }
29 
30 int main(){
31     while( scanf("%I64d%I64d", &a, &b) != EOF ){
32         long long ans = cal( b, a-1 );
33         printf("%I64d
", ans);
34     }
35 
36     return 0;
37 }

View Code

BNUOJ 24250 Binary Operations

题目链接：http://www.bnuoj.com/v3/problem_show.php?pid=24250

弱校联盟最后一场的B题。

不难，但本人太弱，好在周爸比较机智。

思路还是诸位处理，顶多32位。

1、对于相&的情况，只有连续的1才有效，统计连续1的情况乘上改位权值即可。

2、对于相|的情况，求反面，统计连续0的情况，再用总情况一减就行。

3、对于异或，因为奇数个1会产生1，统计每个数到目前为止奇数个1和偶数个1的情况数，

如果，改位为止有奇数个1，ans加上偶数个1的情况，还得加1，因为自身也合法；相反，加上奇数个1的情况。

（这应该是处理连续子区间∑f(i,j)最常用的方法~）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 
  5 using namespace std;
  6 const int maxn = 5e4 + 10;
  7 int bit[maxn][35], a[maxn];
  8 long long n;
  9 
 10 void change( int k, int p ){
 11     int cnt = 0;
 12     while(p){
 13         bit[k][cnt++] = p&1;
 14         p >>= 1;
 15     }
 16 }
 17 
 18 void input(){
 19     scanf("%lld", &n);
 20     memset( bit, 0, sizeof(bit) );
 21     for( int i = 1; i <= n; ++i ){
 22         scanf("%d", &a[i]);
 23         change( i, a[i] );
 24     }
 25 }
 26 
 27 void solve(){
 28     long long ans1 = 0;
 29     //与运算
 30     long long k = 1;
 31     for( int i = 0; i < 32; ++i ){
 32         long long cnt1 = 0;
 33         long long tmp = 0;
 34         for( int j = 1; j <= n; ++j ){
 35             while( j <= n && bit[j][i] == 1 ){
 36                 cnt1++;
 37                 j++;
 38             }
 39             tmp += cnt1*(cnt1+1)/2;
 40             cnt1 = 0;
 41         }
 42         ans1 += tmp * k, k *= 2;
 43     }
 44     //printf("%lld
", ans1);
 45 
 46     //或运算
 47     long long ans2 = 0;
 48     k = 1;
 49     for( int i = 0; i < 32; ++i ){
 50         long long cnt1 = 0;
 51         long long tmp = 0;
 52         for( int j = 1; j <= n; ++j ){
 53             while( j <= n && bit[j][i] == 0 ){
 54                 cnt1++;
 55                 j++;
 56             }
 57             tmp += cnt1*(cnt1+1)/2;
 58             cnt1 = 0;
 59         }
 60         ans2 += k*(n*(n+1)/2 - tmp), k *= 2;
 61     }
 62     //printf("%lld
", ans2);
 63 
 64     //异或运算
 65     long long ans3 = 0;
 66     k = 1;
 67     for( int i = 0; i < 32; ++i ){
 68         int ji = 0, ou = 0, tmp = 0;
 69         long long res = 0;
 70         for( int j = 1; j <= n; ++j ){
 71             if( bit[j][i] == 1 ){
 72                 tmp++;
 73             }
 74             if(tmp%2){
 75                 res += ou+1;
 76                 ji++;
 77             }else{
 78                 res += ji;
 79                 ou++;
 80             }
 81         }
 82         ans3 += res * k, k *= 2;
 83     }
 84 
 85     long long tot = n*(n+1)/2;
 86     printf(" %.6lf %.6lf %.6lf
", ans1/(1.0*tot), ans2/(1.0*tot), ans3/(1.0*tot) );
 87 }
 88 
 89 int main(){
 90     int T, cas = 1;
 91     scanf("%d", &T);
 92 
 93     while(T--){
 94         input();
 95         printf("Case #%d:", cas++);
 96         solve();
 97     }
 98 
 99     return 0;
100 }

View Code