题目链接：http://uoj.ac/problem/238
题目大意：
有一个长度为n的黑白序列，告诉你所以k个极长连续黑段长度和顺序。有一些位置的颜色已知，需要判断剩下未知的位置哪
些颜色
一定是白或一定是黑。保证至少存在一组解。
分析:
先猜测，根据数据范围，虽然n很大，但是k却很小，可以考虑复杂度为O(n*k)的算法。(*￣︶￣)
我们再来具体看看，可以设状态：
f0[i][j] 表示前i个位置能匹配j段并且i位置为白是否合法。
f1[i][j] 表示前i个位置能匹配j段并且i位置为黑是否合法，可以O(n*k)求出。
但这样却又漏洞，我们只是保证了从前往后i,j合法，但是我们还不能保证在这种情况满足后面i+1到n-1是否合法，大概就是我们不能保证
剩下的位置够不够。
为了解决这个问题我们再定义两个状态，g0[i][j],g1[i][j]从后往前来记录。
这样状态转移就是：
if(a[i]!=X) f[i][j][0]=f[i-1][j][0]|f[i-1][j][1] (可以与前面一个组成一组，也可以接在一个黑色后面，有一种满足都合法)
if(i-b[j]>=0&&sum[i]-sum[i-b[j]]==0)f[i][j][1]=f[i-b[j]][j-1][0];(在i-b[j]+1-i直接没有X&&i-b[j]位置为白)
g的转移一样，只是从后往前处理。
答案：
如果f[i][j][0]==1&&g[i][j+1][0](表示从前往后第i个位置满足j段并且当前为白色时合法&&从i到n-1满足j+1到m段的块，并且当前
为白色合法)
两个都合法说明i就可以为白色，用y记录是否为白色。
如果f[i][j][1]==1&&g[i+1][j+1][0](上面类似，当前为黑，那么下一位就要为白）
两个都合法说明i就可以为黑色，用个x记录一个数能为黑色的数量，如果最后x>0说明可以为黑色。
统计：
如果y[i]&&x[i]，两个都可以输出?，其他x,y输出即可。
附上交互代码：
//g为从后往前 f为从前往后 是否合法
#include "paint.h"
#include<bits/stdc++.h>
using namespace std; const int N=2e5+;
const int K=;
bool g[N][K][],f[N][K][];//第i位 满足j段 并现在为0/1 白/黑
int x[N],y[N],last;
int tag[N];
char a[N];int b[N],sum1[N],sum2[N];
string res;
string solve_puzzle(std::string s, std::vector<int> c)
{
int n=s.length(),m=c.size();
for(int i=;i<=n;i++) a[i]=s[i-],sum1[i]+=sum1[i-]+(a[i]=='X'),sum2[i]+=sum2[i-]+(a[i]=='_');
for(int i=;i<=m;i++) b[i]=c[i-];
g[n+][m+][]=;
for(int i=n;i>=;i--)
{
for(int j=m+;j>=;j--)
{
if(a[i]^'X') g[i][j][]=g[i+][j][]|g[i+][j][];
if(j!=m+&&n-i+>=b[j]&&sum2[i+b[j]-]-sum2[i-]==) g[i][j][]=g[i+b[j]][j+][];
}
}
f[][][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(a[i]!='X') f[i][j][]=f[i-][j][]|f[i-][j][];
if(j&&i>=b[j]&&sum2[i]-sum2[i-b[j]]==) f[i][j][]=f[i-b[j]][j-][];
if(f[i][j][]&&g[i][j+][]) y[i]=;
if(f[i][j][]&&g[i+][j+][]) x[i-b[j]+]++,x[i+]--;
}
}
for(int i=;i<=n;i++)
{
x[i]+=x[i-];
if(a[i]=='.')
{
if(x[i]&&y[i]) res+='?';
else if(x[i]) res+='X';
else res+='_';
}else res+=a[i];
}
return res;
}
转载请声明！！！