http://community.topcoder.com/stat?c=round_overview&er=5&rd=15845

A题水过。
B题把所有素因子都加起来就行——贪心yy下搞定。
C题。。还是看官方题解吧,或者看下面的注释:(从dp数组的大小可以看出复杂度为,这里是bit位数的最大值)

A

#include<bits/stdc++.h>
using namespace std;

class LeftAndRightHandedDiv2
{
    public:
        int count(string S)
        {
            int c = 0;
            for (int i = 0; i + 1 != S.size(); i++)
                if (S[i] == 'R' && S[i + 1] == 'L') ++c;
            return c;
        }
};

B

#include<bits/stdc++.h>
using namespace std;

class EmoticonsDiv2
{
    public:
        int printSmiles(int s)
        {
            int res = 0;
            for (int x = 2; x * x <= s; x++)
            {
                while (s % x == 0)
                {
                    s /= x;
                    res += x;
                }
            }
            if (s != 1) res += s;
            return res;
        }
};

C

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) a.begin(), a.end()
const int mx = 60;

vector<ll> X(mx);
ll dp[mx + 1][50];

class PowersOfTwo
{
    public:
        /// 如何进行状态转移?把目光放在“和值第k位是0还是1上”
     /// b是进位数
     ll f(vector<ll> &X, int k, int b)
        {
            ll res = dp[k][b];
            if (res == -1)
            {
                if (k == X.size()) res = 1;
                else
                {
                    int x_k = X[k] + b;
                    res = f(X, k + 1, x_k / 2); /// 0 can be in the k-th bit
                 if (x_k) res += f(X, k + 1, (x_k - 1) / 2); /// 1 can be in the k-th bit
             }
                dp[k][b] = res;
            }
            return res;
        }

        ll count(vector<ll> powers)
        {
            for (int i = 0; i < X.size(); i++)
                X[i] = ::count(all(powers), 1LL << i); /// 统计每个元素有多少个
         memset(dp, -1, sizeof(dp));
            return f(X, 0, 0);
        }
};

Comments

comments powered by Disqus