hdu 5587 Array

　　题目链接：hdu 5587

　　前两周 bc 上的题了，因为赶大作业所以没有去打，看了下官方给出的思路，感觉好强大~~竟然能转化成求二进制数 1 的个数：

　　然后数位 dp 就行了，

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
#define  For(i,s,t)  for(int i = s; i <= t; ++i)

ull C[60][60];      // 组合数
inline void init_C(int n) {
    For(i,0,n)  C[i][0] = 1;
    For(i,1,n)  For(j,1,i) {
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
}

// dp[i] 表示所有 i 位二进制数里'1'的个数总数，p2[i] 即 i 位二进制数的总个数
ull dp[60], p2[60] = {1, 2};
inline void init(int n = 56) {
    init_C(n);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= i; ++j)
            dp[i] += j * C[i][j];
    For(i,2,n)
        p2[i] = p2[i - 1] * 2;
}

int digit[60];       // digit 数组保存的是 x 的二进制表示法
ull solve(ull x) {
    int len = 0;
    while(x) {
        digit[++len] = x % 2;
        x /= 2;
    }
    int num1 = 0;           // num1 记录的是 digit 里第 i 位前面的'1'的个数
    ull res = 0;
    for(int i = len; i; --i) {
        // 只处理第 i 位为'1'的情况就行，'0'的话在该位没有比它更小的了，所以不用处理
        if(digit[i] == 1) {
            // p2[i - 1] * num1 统计的是第 i 位前面的'1'的个数总数(因为此时第 i 位取'0'，后面的 i-1 位可以任取)
            // dp[i - 1] 统计后面 i-1 位里'1'的个数总数
            res += p2[i - 1] * num1 + dp[i - 1];
            ++num1;
        }
    }
    return res;
}

int main() {
    int t;
    ull m;
    init();
    scanf("%d",&t);
    while(t--) {
        scanf("%I64u",&m);
        printf("%I64u\n",solve(m + 1));     // 因为上面统一处理的是比 x 小的数，所以在这里 +1
    }
    return 0;
}

　　网上好像有很多思路可以递归或者递推找规律的，我学习了下，感觉也很强大：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int N = 103;
const ull maxLen = 1e16 + 8;

ull preLen[N], preSum[N];

inline void init(int n = 101) {
    preLen[1] = preSum[1] = 1;
    for(int i = 2; i <= n; ++i) {
        preLen[i] = preLen[i - 1] * 2 + 1;
        preSum[i] = preSum[i - 1] * 2 + (preLen[i] - preLen[i - 1]);
        if(preLen[i] > maxLen)  return ;
    }
}

ull dfs(ull mlen) {
    if(mlen == 0)   return 0;
    int pos;
    for(int i = 1; i <= 101; ++i) {
        if(mlen < preLen[i + 1]) {
            pos = i;
            break;
        }
    }
    ull remainLen = (mlen == preLen[pos] ? 0: mlen - preLen[pos] - 1);
    return preSum[pos] + dfs(remainLen) + (mlen - preLen[pos]);
}

int main() {
    init();
    int t;
    ull m;
    scanf("%d",&t);
    while(t--) {
        scanf("%I64u",&m);
        printf("%I64u\n",dfs(m));
    }
    return 0;
}

　　因为不是比赛时做，所以时间比较充裕，变量名写得有点长了，看着像在写工程代码

　　这题，必须好好琢磨才行，它和刚过去的 2015CCPC 南阳的热身赛的第一题很像，都是递归的思想，当时现场想不出来，却被身旁的师弟秒掉了，好惭愧的感觉 -_-||   看来自己还要勤加练习啊，弱渣就需多努力~

　　顺便贴一下 5586 Sum 的代码，自己1A掉的：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100005;
#define  For(i,s,t)  for(int i = s; i <= t; ++i)

int a[N], b[N];

inline int trans(const int &x) {
    return (1890 * x + 143) % 10007;
}

int maxSum(int *b, int n) {
    int res = b[1], cur = b[1];
    for(int i = 2; i <= n; ++i) {
        cur = max(cur + b[i], b[i]);
        res = max(res, cur);
    }
    return max(res, 0);
}

int main() {
    int n;
    while(~scanf("%d",&n)) {
        int sum = 0;
        For(i,1,n) {
            scanf("%d",a + i);
            sum += a[i];
            b[i] = trans(a[i]) - a[i];
        }
        printf("%d\n", sum + maxSum(b, n));
    }
    return 0;
}