Allowed Letters CodeForces – 1009G（状压思维）

题意：

　　给出一个字符串 给出几个定点必须是哪个字母（或者是几个字母中的一个）  然后求在满足所有定点后的最小字符串

解析：

　　没错 这题是暴力 用状压暴力

　　　“a – f” 用”0 – 5“ 这几个数字代替   输入字符串  num[i]为字母i的个数，然后输入定点必须为哪个字母，ti[i]中用六位二进制来存储当前位置i的可以放的字母

1代表放 0不放

　　设cnt = 1<<6 – 1; 即为所有状态的上界

　　然后从后向前遍历一遍，统计对于位置i到n  状态k还需要多少个 sum[i][j]来表示

　然后暴力就好了。。就是从前向后遍历每一个位置，对于位置i 我们遍历所有字母挨个试，又对于每一个字母，统计一下在这个位置放了这个字母后，我们去检查是否还能满足后边的所有状态（挨个状态遍历一遍求出当前状态所需要的字母总和判断一下） 如果可以 则下一个位置  不可以下一个试字母 如果所有字母都不符合 那就impossible

#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = , INF = 0x7fffffff, cnt = (<<) - ;
char str[maxn];
int num[], ti[maxn*], sum[maxn][cnt+], zt[cnt+];
int m;
vector<char> v;int main()
{
    cin>> str;
    int n, len;
    n = len = strlen(str);
    for(int i=; i<len; i++)
        num[str[i]-'a']++;  //统计每个字母的数量
    cin>> m;
    int id;
    for(int i=; i<m; i++)
    {
        cin>> id >> str;
        len = strlen(str);
        for(int j=; j<len; j++)
        {
            ti[id-] |= (<<(str[j] - 'a'));    //统计能放在位置id-1 的字母集合
        }
    }
    for(int i=; i<n; i++)
        if(!ti[i]) ti[i] = cnt;     //如果为0 说明没有被指定 所以都可以放
    for(int i=n-; i>=; i--)       //从后向前遍历一遍，统计对于位置i到n  状态k还需要多少个
    {
        for(int j=; j<=cnt; j++)   //对当前i 遍历所有状态
        {
            if((ti[i] & j) == ti[i])    //子集
                zt[j]++;
            sum[i][j] = zt[j];
        }
    }
    int _sum = ;
    for(int i=; i<n; i++)     //遍历每个位置 暴力判断即可
    {
        int flag1 = ;
        for(int j=; j<; j++)
        {
            int flag2 = ;
            if(!num[j] || (ti[i]&(<<j)) == ) continue;
            num[j]--;
            for(int k=; k<=cnt; k++)
            {
                _sum = ;
                for(int r=; r<; r++)
                    if(k & (<<r))
                        _sum += num[r];
                if(_sum < sum[i+][k])
                {
                    flag2 = ; break;
                }
            }
            if(flag2)
            {
                flag1 = ; v.push_back('a'+j); break;
            }
            num[j]++;
        }
        if(!flag1)
            return puts("Impossible"), ;
    }
    for(int i=; i<v.size(); i++)
    {
        printf("%c", v[i]);
    }
    cout<<endl;    return ;
}