2017-Sp80-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，yzc上机'''A1y5'''。yzc继续上机写C获得wa，cjb开了F和K，上机写了一部分，sub上机写B，'''B1y61'''。yzc和sub讨论了下C，换下写F的cjb，'''C1y68'''。sub读了I，发现很傻逼，上机'''I1y88'''。cjb写完F，wa了，帮sub上机写了K的一小部分，sub完成剩下的部分，cjb给yzc讲了讲F，发现了一个bug，改了之后'''F2y120'''。sub发现cjb的小部分写错了，yzc上机重写，之后tle了，三个人发现算法有点问题，修正了之后终于'''K2y160'''。yzc开了E，上机写了E，wa了。sub上机写G，cjb开J，提出了大概的做法，和yzc理论了很久E都找不到错，sub终于搞定了G，'''G1y248'''。最后yzc一直在调E，写了对拍但是一直拍不对，无功而返，7题收尾打出GG。
== 总结 ==
=== chenjb ===
好气气，E好伤伤，自己sb地因为在有向图上乱找桥wa了一发好傻逼啊QAQ md! J亏大了啊！！！！！！！
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * E：
  * 题意：给定两个长度为n的01序列，每一次可以选一段长度不超过k的置为0或1，求第一个序列变成第二个的最少步数。n，k<=5*10^5^
  * 题解：显然，最优解肯定分为很多个互不相交的区间分别做。对于一个区间，最少步数显然为不同的连续段数/2上取整+1（考虑先刷一层数字，再一段段完成另一个数字）。然后dp方程显然，由于只能取距离不超过k的最优值，可以用线段树或单调队列维护。
 * J：
  * 题意：一个长度为n的串，给出其中a个位置，再切成b段，每一段若在其前面有一段相同的，则给出前面一段的起点的信息。q个询问，询问某个位置能否确定为某个字母。n<=10^9^,a,b,q<=1000
  * 题解：对于每个位置，显然都有一个唯一的最靠前的等价位置（即字母相同），于是对于每个已知字母，找到最前的代表位置，对于询问同样找到代表位置，判断此代表位置是否已知字母即可。
== 补题 ==
 * ~~E~~ by yzc
 * ~~J~~ by yzc
 * ~~H~~ by sub
 * D

流水账

开场各自看题，yzc上机A1y5。yzc继续上机写C获得wa，cjb开了F和K，上机写了一部分，sub上机写B，B1y61。yzc和sub讨论了下C，换下写F的cjb，C1y68。sub读了I，发现很傻逼，上机I1y88。cjb写完F，wa了，帮sub上机写了K的一小部分，sub完成剩下的部分，cjb给yzc讲了讲F，发现了一个bug，改了之后F2y120。sub发现cjb的小部分写错了，yzc上机重写，之后tle了，三个人发现算法有点问题，修正了之后终于K2y160。yzc开了E，上机写了E，wa了。sub上机写G，cjb开J，提出了大概的做法，和yzc理论了很久E都找不到错，sub终于搞定了G，G1y248。最后yzc一直在调E，写了对拍但是一直拍不对，无功而返，7题收尾打出GG。

总结

chenjb

好气气，E好伤伤，自己sb地因为在有向图上乱找桥wa了一发好傻逼啊QAQ md! J亏大了啊！！！！！！！

oipotato

subconscious

题解

  • E：
    • 题意：给定两个长度为n的01序列，每一次可以选一段长度不超过k的置为0或1，求第一个序列变成第二个的最少步数。n，k<=5*105
    • 题解：显然，最优解肯定分为很多个互不相交的区间分别做。对于一个区间，最少步数显然为不同的连续段数/2上取整+1（考虑先刷一层数字，再一段段完成另一个数字）。然后dp方程显然，由于只能取距离不超过k的最优值，可以用线段树或单调队列维护。
  • J：
    • 题意：一个长度为n的串，给出其中a个位置，再切成b段，每一段若在其前面有一段相同的，则给出前面一段的起点的信息。q个询问，询问某个位置能否确定为某个字母。n<=109,a,b,q<=1000
    • 题解：对于每个位置，显然都有一个唯一的最靠前的等价位置（即字母相同），于是对于每个已知字母，找到最前的代表位置，对于询问同样找到代表位置，判断此代表位置是否已知字母即可。

补题

  • E by yzc
  • J by yzc
  • H by sub
  • D
附加文件