CSPS-S 模拟47

考试考得一般般,改题改到天昏地暗

T1 TLE10分, T2 TLE90,T3~不用说了(目前还没读懂题)

并列的有十个人

T1 Emotional Flutter

  先把题意理解一下,千万不要按点来干,应该按照一个个长度为1的格来看,比如脚长为2时,占两格,脚尖部分(第二个格)不能在下一个黑条的第一个格上

  所以先把脚长S(缩成脚后跟)整成一个格 1,只要把白条减去最后S-1个格(脚跟不能在这几个格里,但从后往前数的第S个格是可以放脚跟的),那么黑条的长度加上这S-1个格,表示脚跟不能在这个区域内,注意第一个黑条不需要加上 S-1

  因为从第一个黑条的最左边(0的位置)(也可以从更靠左的位置)开始,那么,以第一个黑格第一个格作为1,一步下最多跳到K的格(不管是白  是黑),而后跳下去会形成几个长度为K的条(条长为K)的连续,且一定是第一个条的第i格跳到第二个条的第i格

  一个条内有黑格有白格,脚跟不能跳到黑格,而一条路径上(i 跳到 k+i -> k*2+i ->k*3+i……) 只要有一个格是黑格,此路不通

  那么把黑格的坐标%k(如果模K为0 的话,它是第k个格),因为黑条是连续的,可以把[1,k]上一段连续区间盖上,表示此路不通,

  最后扫一遍看[1,k]上是否有没被盖上的块,有则有路(输出TAK),无则无路(输出NIE)

  如果一个白条长度(减去S-1后)大于K的话,内部会有一个整条(全是白的),这一个条对答案没有影响,但是统计的话会浪费时间,所以长度模一下K

  同样如果一个黑条(加上S-1后)大于等于K,整个[1,k]都会被盖上,不需要在处理判断了,直接NIE

T2 Endless Fantasy

  线段树水题(然而我没一刀切)

  线段树合并,O(NlogN)100分

  启发式合并 O(NlogN^2) TLE 90

  所以一定要注意时间复杂度(听说有的题更适合用启发式合并)

T3 字符消除2

  ~目前不会~

原文地址:https://www.cnblogs.com/heoitys/p/11558717.html