Codeforces 1009G
题意略。
思路:
首先是贪心, 我们从前往后依次从小到大考虑放哪个字符, 重点是判断放了这个字符后, 对于剩下的后缀是否存在合法解。
考虑每个位置的允许放的字符集合只有2 ^ 6种, 我们预处理一个后缀和f[i][j], 表示i~n中被集合j包含的个数。
考虑第i个位置放了字符c后, 要使得f[i+1][j]都 <= 对应的剩下的个数才能是合法的。
这里涉及到一个霍尔定理:二部图G中的两部分顶点组成的集合分别为X, Y;
G中有一组无公共点的边,一端恰好为组成X的点的充分必要条件是:X中的任意k个点至少与Y中的k个点相邻。
由于是选择任意k个(1 <= k <= |x|),所以我们需要考虑的是极端情况,如果极端情况满足了,那么剩余的情况也会被满足。
现在假设我们在当前位置填上了某个字符,我们最关心的是剩下能否合法,也就是剩下的位置能否被剩余字符填满。
其实所有的位置可以分为2 ^ 6 = 64种,如果我们选择的k个来自不同的种类,也就会给我们带来更多可以填入这k个位子的字符。
我所说的极端情况就是尽量减少可以填入这k个位子的字符,扩大我的k个位子。如果这种情况可以被满足,那么其他情况自然也就满足了。
开始我认为选择来自同一种的位子就是最极端的,其实这仅仅做到了字符数最小,没有做到位子最多。
比如我选择了状态为j的位子,我可以选择j的子集来扩大我的k,而且这不会给字符数带来任何增益。
详见代码:
#include<bits/stdc++.h> using namespace std; const int maxn1 = 1e5 + 5; const int maxn2 = (1<<6); int f[maxn1][maxn2],mask[maxn1],cnt[maxn2],m; char str[maxn1],tmp[10],ans[maxn1]; int main(){ scanf("%s%d",str,&m); int len = strlen(str); if(m == 0){ sort(str,str + len); printf("%s\n",str); return 0; } for(int i = 0;i < len;++i){ for(int j = 1;j < maxn2;++j){ if(j & (1<<(str[i] - 'a'))) ++cnt[j]; } } for(int i = 1;i <= len;++i) mask[i] = maxn2 - 1; int pos; for(int i = 0;i < m;++i){ scanf("%d%s",&pos,tmp); int l = strlen(tmp); mask[pos] = 0; for(int j = 0;j < l;++j) mask[pos] += (1<<(tmp[j] - 'a')); } for(int i = len;i >= 1;--i){ for(int j = 1;j < maxn2;++j){ f[i][j] = f[i + 1][j]; if((mask[i] & j) == mask[i]) f[i][j] += 1; } } for(int i = 1;i <= len;++i){ bool finish = false; for(int j = 0;j < 6;++j){ if((mask[i] & (1<<j)) == 0 || !cnt[1<<j]) continue; bool ok = true; for(int k = 1;k < maxn2 && ok;++k){ if(f[i + 1][k] > cnt[k] - ((k>>j) & 1)){ ok = false; } } if(ok){ for(int k = 1;k < maxn2;++k) if((k>>j) & 1) cnt[k] -= 1; ans[i] = 'a' + j; finish = true; break; } } if(!finish){ printf("Impossible\n"); return 0; } } for(int i = 1;i <= len;++i) printf("%c",ans[i]); printf("\n"); return 0; }