http://community.topcoder.com/stat?c=round_overview&rd=15846

A题水过。。
推广
若文本和子序列的长度均达到,下面代码的做法必然会TLE,所以需要一个的做法:
很简单,只需用一个26字节大小的bool数组统计中没出现的字母,然后同时遍历即可。

B题暴力,复杂度(也可以只判断与分界点的狗的相对位置,复杂度
待解决
是否存在一个的算法呢?

C题状压,复杂度,关键在于把数字分成1~10和大于10两组,作为两个维度。

A

#include<bits/stdc++.h>
using namespace std;
const int mx = 55;

char s[mx];
int cnt[30];

class TaroString
{
    public:
        string getAnswer(string S)
        {
            int i;
            strcpy(s, S.c_str());
            char *a = strchr(s, 'C');
            char *b = strchr(s, 'A');
            char *c = strchr(s, 'T');
            if (a && a < b && b < c)
            {
                for (i = 0; s[i]; ++i)
                    ++cnt[s[i] & 31];
                if (cnt['C' & 31] > 1 || cnt['A' & 31] > 1 || cnt['T' & 31] > 1) return "Impossible";
                return "Possible";
            }
            return "Impossible";
        }
};

B

#include<bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()

class TaroFriends
{
    public:
        int getNumber(vector<int> a, int x)
        {
            int n = a.size(), i, j, ans;
            vector<int> tmp;
            sort(all(a));
            ans = a[n - 1] - a[0];
            for (i = 0; i < n; ++i)
            {
                tmp = a;
                for (j = 0; j < i; ++j) tmp[j] += x;
                for (; j < n; ++j) tmp[j] -= x;
                sort(all(tmp));
                ans = min(ans, tmp[n - 1] - tmp[0]);
            }
            return ans;
        }
};

C

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

ll dp[1024][51][41]; ///这样写能增加cache命中
vector<int> first, second;

class TaroCards
{
    public:
        int K, n, cmask, cr, j;

        /// We can represent the set of current cards by just a pair (S,r),
     /// where S(mask) is the set of numbers from 1 to 10 that are already included
     /// and r is the number of integers from 11 to 40 that are already included.
     ll f(int i, int mask, int r)
        {
            ll res = dp[mask][i][r];
            if (res == -1)
            {
                /// if |S| + r <= K, |S| is equal to the number of 1 bits in mask
             if (i == n) res = (__builtin_popcount(mask) + r <= K);
                else
                {
                    res = f(i + 1, mask, r);/// Don't use card i
                 int o[2] = {first[i], second[i]};
                    cmask = mask, cr = r;
                    for (j = 0; j <= 1; ++j)
                    {
                        if (o[j] <= 10) cmask |= 1 << (o[j] - 1);
                        else ++cr; /// update S and r
                 }
                    res += f(i + 1, cmask, cr);/// Use card i
             }
                dp[mask][i][r] = res;
            }
            return res;
        }

        ll getNumber(vector<int> fi, vector<int> s, int k)
        {
            ///把参数存给全局变量
         first = fi, second = s, K = k, n = fi.size();
            memset(dp, -1, sizeof(dp));
            return f(0, 0, 0);
        }
};

Comments

comments powered by Disqus