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 #include2 #include 3 #include 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\n", ans);34 }35 36 return 0;37 }
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 #include2 #include 3 #include 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\n", 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\n", 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\n", 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 }