QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#245875 | #4669. Genetic Modifications | Myrrh | WA | 1ms | 3644kb | C++14 | 2.5kb | 2023-11-10 14:19:17 | 2023-11-10 14:19:17 |
Judging History
answer
/*
有几种情况:
考虑先构造一组带上p[0]和p[m+1]之后合法的方案
s中每个连续段
要不然左右边界外面都有被选
1000001
要不然选左右边界
或者一样一半
1000001
如果视作把选的位置删掉会怎样
好转化:T往相邻两个元素中间塞一堆相同数字,使得=S
先考虑用T的一段前缀构造出S
再调整
如果一段前缀都构造不出来直接无解
0/1 0/1
上一个在当前连续段开头/上一个连续段末尾 当前和上一个颜色相反/相同
00 除非当前连续段长度为1,此时放在下一个连续段末尾 否则无解
01 长度为1:下下个连续段开头 否则这个连续段末尾
10:放末尾
11:下一个连续段开头
f[i][j]:T[i]和S[j]匹配是否可行
g[i][j]:S[i]和T[j]匹配是否可行
f[i][j]=f[i-1][k]&[k+1,j-1]颜色相等&T[i]=S[j]
*/
#include <bits/stdc++.h>
using namespace std;
const int MAXN=5e6+50;
int N,M;
char S[MAXN],T[MAXN];
int f[MAXN];
bool Have[MAXN];
int GetId(int i,int j)
{
return i*(N+1)+j+1;
}
void Solve2()
{
int i=1,j=1;
while(i<=N&&S[i]!=T[j])
{
i++;
}
if(i>N)
{
puts("No");
return;
}
vector<int>ans;
ans.push_back(i);
while(j+1<=M)
{
j++;
while(i<=N&&S[i]!=T[j])
{
i++;
}
if(i>N)
{
puts("No");
return;
}
ans.push_back(i);
}
puts("Yes");
for(int i=0;i<ans.size();i++)
{
printf("%d ",ans[i]);
}
}
int main()
{
// freopen("sequence.in","r",stdin);
// freopen("sequence.out","w",stdout);
scanf("%s%s",&S[1],&T[1]);
N=strlen(S+1);
M=strlen(T+1);
Have[GetId(0,0)]=true;
int Id;
bool flagB=false;
for(int i=1;i<M;i++)
{
if(T[i]==T[i+1])
{
flagB=true;
}
}
if(flagB==false&&N>2000)
{
Solve2();
return 0;
}
for(int i=1;i<=M;i++)
{
int flag=0;
int l=0,r=0,Last=-1;
for(int j=1;j<=N;j++)
{
if(Have[GetId(i-1,j-1)])
Last=j-1;
while(S[l+1]!=S[j-1]&&l+1<=j-1)
{
l++;
}
if(T[i]==S[j]&&Last>=l)
{
f[GetId(i,j)]=Last;
Have[GetId(i,j)]=true;
if(i==M)
{
flag=j;
}
// cout<<i<<" "<<j<<" "<<l<<" "<<j-1<<endl;
}
}
if(i==M)
{
if(flag)
{
puts("Yes");
Id=flag;
break;
}
else
{
puts("No");
return 0;
}
}
}
vector<int>ans;
// cout<<ans.size()<<" "<<Id<<endl;
for(int i=M;i>=1;i--)
{
ans.push_back(Id);
Id=f[GetId(i,Id)];
}
for(int i=M-1;i>=0;i--)
{
printf("%d ",ans[i]);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3644kb
input:
BBAAABBAAABAAA BAAB
output:
Yes 2 5 8 11
result:
ok good solution
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3632kb
input:
ABABABABAB ABAB
output:
Yes 1 2 3 4
result:
wrong answer wrong solution [2]