返回信息流题目链接：http://codeforces.com/problemset/problem/778/A
大意是说，给定两个字符串t和p，其中p是t的子序列，1 ≤ |p| < |t| ≤ 200000
然后给出一个数组a，从字符串t中依次删掉位置为a[1], a[2], ... , a[i], ... 的字符
当删掉a[j]后，字符串p不再是字符串t的子序列，求满足条件的最小的j
求思路......谢谢......
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #92030同步于 2017/2/26
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
[问题] codeforces 778A
lzj0218
2017/2/26镜像同步8 回复
订阅后，新回复会通过你的通知中心匿名送达。
8 条回复
【 在 fuuko 的大作中提到: 】
: 二分答案，验证这些字符去掉之后还是不是子序列。验证的时候俩指针扫一遍就行，总复杂度O(NlogN)
又见谷歌大神！按照你的思路coding了一段，AC了
def isSubSet(t,p):
i,j=0,0
while(i<len(t) and j<len(p)):
if(t[i]==p[j]):i,j = i+1,j+1
else: i+=1
return True if(j==len(p)) else False
def deleteLeastChar(t,p,a):
left ,right = 1,len(a)
ret = 0
while(left<=right):
mid = left + (right-left)/2
tmp = list(t)
for x in a[:mid]:
tmp[x-1] = '0'
if isSubSet(filter(lambda x:x!='0',tmp),p):left = mid+1
else: ret,right = mid,mid-1
return ret-1
def main():
t = raw_input()
p = raw_input()
a = map(int,raw_input().split())
print deleteLeastChar(t,p,a)
if __name__ == "__main__":
main()
膜
【 在 fuuko 的大作中提到: 】
: 二分答案，验证这些字符去掉之后还是不是子序列。验证的时候俩指针扫一遍就行，总复杂度O(NlogN)
:
发自「贵邮」