TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P1761
  • 题目
  • P1761[CF1137B] 0101 | 内含题解
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    nodgd有一个很喜欢的01字符串,他恨不得全世界都写满这个字符串。

    有一天,nodgd捡来了另一个01字符串,决定把它改成自己喜欢的样子。nodgd可以调整字符串中每个字符的位置,但不能凭空创造字符或者丢弃字符。

    nodgd喜欢自己喜欢的字符串出现的次数尽量多,你知道应该如何修改吗?

    点击查看此题原内容“【Week9 Tech传奇】题解”

    第一题,刺杀:
    考点:拓扑排序+字符串处理
    解法:将每个姓名看成一个点,通过题目给出的先后关系构建成有向图,时间对应每个点的权值,若A kill B,那么A到B有一条有向边。然后按照拓扑排序的原理,每次取入度为0的点,从该点出发,记录它能到达的每个点的所需的最大时间。

    第二题,监狱:
    考点:动态规划
    方法一:合并动规,时间复杂度O(n^3)只能过60%的数据。
    f[i][j]表示将第 i到第j个人装入所需最少房间数
    若满足p[i][j][1]=0 或 p[i][j][2]=0 或 abs(p[i][j][1]-p[i][j][2])<=m
    (p[i][j][1]表示从i到j标号为1的人的个数 p[i][j][2]表示i到j标号为2的人数)
    f[i][j]=1
    否则 f[i][j]=min{f[i][t]+f[t+1][j]} i<=t<=j-1

    方法二:线性动规,时间复杂度O(n^2)
    f[i]表示将前i个人装入最少需要的房间数
    f[i]=min{f[k]+1} 1<=k<i
    需满足p[k+1][i][1]=0 或 p[k+1][i][2]=0 或 abs(p[k+1][i][1]-p[k+1][i][2])<=m
    (p[x][y][1]表示从x到y标号为1的人的个数 p[x][y][2]表示x到y标号为2的人数)
    表示将k+1到i这些人全部放入同一房间

    第三题,逃亡:
    考点:堆+贪心
    贪心原则:车能开多远开多远,如果走到x位置邮箱空了,意味着之前应该加油,在哪里加油呢?在0到x间没有加过油的油量最多的加油站加油。
    每次选出油量最多的加油站,用大根堆即可。
    输入格式

    第一行一个01字符串,是nodgd捡来的。
    第二行一个01字符串,是nodgd喜欢的。

    输出格式

    输出改后的01字符串,如果有多种方案可以任意输出一种。

    提示

    样例 1

    样例输入 1
    101101
    110
    
    样例输出 1
    110110
    

    修改后nodgd喜欢的字符串“110”出现了两次。

    样例 2

    样例输入 2
    10010110
    100011
    
    样例输出 2
    01100011
    

    修改后nodgd喜欢的字符串“100011”出现了。答案不唯一。

    样例3

    样例输入 3
    10
    11100
    
    样例输出 3
    01
    

    数据范围

    输入的两个字符串长度都不超过 $5\times 10^5$ 。