欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

IOI2016Day2. Paint

程序员文章站 2022-03-25 22:04:15
题目链接:http://uoj.ac/problem/238 题目大意: 有一个长度为n的黑白序列,告诉你所以k个极长连续黑段长度和顺序。有一些位置的颜色已知,需要判断剩下未知的位置哪 些颜色 一定是白或一定是黑。保证至少存在一组解。 分析: 先猜测,根据数据范围,虽然n很大,但是k却很小,可以考虑 ......

 

题目链接: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输出即可。


 附上交互代码:

 

IOI2016Day2. Paint
//g为从后往前 f为从前往后 是否合法 
#include "paint.h"
#include<bits/stdc++.h>
using namespace std;

const int N=2e5+12;
const int K=105;
bool g[N][K][2],f[N][K][2];//第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=1;i<=n;i++) a[i]=s[i-1],sum1[i]+=sum1[i-1]+(a[i]=='X'),sum2[i]+=sum2[i-1]+(a[i]=='_');
    for(int i=1;i<=m;i++) b[i]=c[i-1];
    g[n+1][m+1][0]=1;
    for(int i=n;i>=1;i--)
    {
        for(int j=m+1;j>=1;j--)
        {
            if(a[i]^'X') g[i][j][0]=g[i+1][j][0]|g[i+1][j][1];
            if(j!=m+1&&n-i+1>=b[j]&&sum2[i+b[j]-1]-sum2[i-1]==0) g[i][j][1]=g[i+b[j]][j+1][0];
        }    
    }
    f[0][0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(a[i]!='X') f[i][j][0]=f[i-1][j][0]|f[i-1][j][1];
            if(j&&i>=b[j]&&sum2[i]-sum2[i-b[j]]==0) f[i][j][1]=f[i-b[j]][j-1][0];
            if(f[i][j][0]&&g[i][j+1][0]) y[i]=1;
            if(f[i][j][1]&&g[i+1][j+1][0]) x[i-b[j]+1]++,x[i+1]--;
        }
    }
    for(int i=1;i<=n;i++)
    {
        x[i]+=x[i-1];
        if(a[i]=='.') 
        {
            if(x[i]&&y[i]) res+='?';
            else if(x[i]) res+='X';
            else res+='_';
        }else res+=a[i];
    }
    return res;
}
View Code

转载请声明!!!