XJOI 3393序列 题解

时间：1s 空间：128M

题目描述：

f(0)=0 f(2∗x)=f(x) f(2∗x+1)=f(x)+1 你有一个序列a1,a2,a3…an 现在你想知道有多少对的f(ai)=f(aj)(1<=i< j<=n)

输入格式：

第一行输入一个整数n 第二行输入n个整数ai

输出格式：

输出一个整数

样例输入1：

3 1 2 4

样例输出1：

3

样例输入2：

3 5 3 1

样例输出2：

1

约定：

1<=n<=10^5,1<=ai<=10^9

提示：

首先，如何求f(x)，可以用递归解决。时间复杂度较小，而且如果用记忆化，空间会开不下。求f(x)的代码如下：

int mrz_key ( int k ) { if ( k == 0 ) return 0; if ( k % 2 == 0 ) return mrz_key ( k / 2 ) ; if ( k % 2 == 1 ) return mrz_key ( k / 2 ) + 1 ; }

其次，我们会发现，f(x)的值其实不是很大，甚至可以用桶来存储。tonnn数组就是一个桶。我们不妨做一个假设，tonnn[i]=5，也就是说f(x)值是i的有5个，则可得相等的值有（4+3+2+1）对，就可以用等差数列求和公式来做。代码如下：

#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <string> using namespace std ; int tonnn [ 1000000 ] , a [ 100001 ] , n ; int mrz_key ( int k ) { if ( k == 0 ) return 0; if ( k % 2 == 0 ) return mrz_key ( k / 2 ) ; if ( k % 2 == 1 ) return mrz_key ( k / 2 ) + 1 ; } int main ( ) { scanf ( "%d" , & n ) ; memset ( tonnn , 0 , sizeof ( tonnn ) ) ; int maxx = 0 , d ; tonnn [ 0 ] = 1 ; for ( int i = 1 ; i <= n ; i ++ ) { scanf ( "%d" , & a [ i ] ) ; d = mrz_key ( a [ i ] ) ; if ( d > maxx ) maxx = d ; tonnn [ d ] ++ ; } int ans = 0 ; for ( int i = 1 ; i <= maxx ; i ++ ) if ( tonnn [ i ] > 1 ) ans += ( tonnn [ i ] - 1 ) * tonnn [ i ] / 2 ; printf ( "%d" , ans ) ; return 0 ; }

相关链接：

XJOI 题解小全： https://blog.csdn.net/zj_mrz/article/details/80949787

XJOI 3265 Climb the stairs 爬楼梯 题解： https://blog.csdn.net/zj_mrz/article/details/80970052