序列染色【弱化版】

55 分

#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;
int ss[1005];
int th[15];
bool vis[550000];
vector<int> f;
queue<int> q;
int nowD[15];
int main()
{
    th[0] = 1;
    for (int i = 1; i <= 12; i++)
        th[i] = th[i - 1] * 3;

    cin >> n >> m;
    cin >> s;
    for (int i = 0; i < m; i++)
        if (s[i] == 'b')
            ss[i] = 1;
        else
            ss[i] = 2;
    f.push_back(0);
    vis[0] = true;
    for (int now = m - 1; now >= 0; now--)
    {
        for (int x : f)
        {
            for (int i = 0; i <= n - 1; i++)
                nowD[i] = x / th[i] % 3;
            for (int l = 0; l <= n - 1; l++)
                if (nowD[l] == 0)
                {
                    for (int r = l; r <= n - 1; r++)
                    {
                        if (nowD[r] == 0)
                        {
                            int temp = x;
                            for (int i = l; i <= r; i++)
                                if (nowD[i] == 0)
                                    temp += ss[now] * th[i];
                            if (!vis[temp])
                            {
                                q.push(temp);
                                vis[temp] = true;
                            }
                        }
                    }
                }
        }
        while (!q.empty())
        {
            f.push_back(q.front());
            q.pop();
        }
    }
    cout << f.size();
    return 0;
}

100 分

#include <bits/stdc++.h>
using namespace std;
int n, m;
string s;
int ss[1005];
int th[15];
bool vis[550000];
vector<int> f;
// f[0] ~ f[p1 - 1] 都不需要进行染色 1
// f[0] ~ f[p2 - 1] 都不需要进行染色 2
int p1, p2;
queue<int> q;
int nowD[15];
int main()
{
    th[0] = 1;
    for (int i = 1; i <= 12; i++)
        th[i] = th[i - 1] * 3;

    cin >> n >> m;
    cin >> s;
    for (int i = 0; i < m; i++)
        if (s[i] == 'b')
            ss[i] = 1;
        else
            ss[i] = 2;
    f.push_back(0);
    p1 = p2 = 0;
    vis[0] = true;
    for (int now = m - 1; now >= 0; now--)
    {
        int pp, len;
        if (ss[now] == 1)
            pp = p1;
        else
            pp = p2;
        len = f.size();
        for (; pp < len; pp++)
        {
            int x = f[pp];
            for (int i = 0; i <= n - 1; i++)
                nowD[i] = x / th[i] % 3;
            for (int l = 0; l <= n - 1; l++)
                if (nowD[l] == 0)
                {
                    for (int r = l; r <= n - 1; r++)
                    {
                        if (nowD[r] == 0)
                        {
                            int temp = x;
                            for (int i = l; i <= r; i++)
                                if (nowD[i] == 0)
                                    temp += ss[now] * th[i];
                            if (!vis[temp])
                            {
                                q.push(temp);
                                vis[temp] = true;
                            }
                        }
                    }
                }
        }
        while (!q.empty())
        {
            f.push_back(q.front());
            q.pop();
        }
        if (ss[now] == 1)
            p1 = pp;
        else
            p2 = pp;
    }
    cout << f.size();
    return 0;
}