比赛链接

solved by bazoka13

给定$n(n\leq1e5)$个点，坐标$x,y$的范围为$0~1e9$，用三个正方形覆盖所有的点，求正方形的最小边长。

找出$x,y$坐标的最大/小值，显然最值点应该尽量位于正方形的边界上。考虑$dfs$做法，对当前的正方形，找出未标记点的四个最值，最多有四种搭配（比如：$(minx,maxy-d),(minx,miny)$），每个搭配中，找出当前正方形可以覆盖的点，标记。如果已经$dfs$到第三个正方形，就比较$x,y$最值的差值与当前边长，如果小于当前边长，就说明当前边长是合法的。

边长利用上述方法二分即可。

upsolved by JJLeo

给定$n$个模式串$t_i$，$q$个询问，求最短的字符串$S$，使得模式串$t_x$和$t_y$均是$S$的子串，输出最短长度。$n\le3\times10^5,\sum{|t|}\le3\times10^5,q\le1\times10^5$

对模式串建AC自动机，利用阿狸的打字机的套路，树剖fail树，dfs trie树，入栈+1，出栈-1。两个模式串组成的$S$如果可以缩短长度，要么$t_x$是$t_y$的子串，等价于$t_y$的某个前缀的某个后缀是$t_x$，此时缩短的长度为$|t_x|$；要么$t_x$的某个前缀等于$t_y$的某个后缀，此时缩短的长度是满足这个条件的最长后缀长度。前者即求$t_x$在fail树上的子树中是否有未回溯的点，后者即求$t_x$在fail树上到根节点未回溯的最深点，树剖即可。另外$t_x$和$t_y$可以交换，因此离线处理的时候要互相加入。

solved by 2sozx

给定字符串$S$与空集合$T$，第一种操作在$S$后面添加一个字符，第二种操作将$S$整体作为一个元素放入$T$中，第三种询问$T$中有多少个元素是$S$的后缀,操作次数$m{\le}12*10^5$，$|S|{\le}10^3$。

题目可转化为，有多少个特定长度的前缀等于等长的后缀，这与$KMP$的$fail$数组道理是一样的，在操作二时打标记，操作一时转移即可。

注：集合中不应有相同的元素。

solved by 2sozx

给定一个由数字组成的字符串，字符串中每两个字符一组，每次操作以组为单位，将这组变成$a$个$b$，$a$是组内第一个字符，$b$是第二个字符，求$k$此操作后$pos$位是多少,$k{\le}40$，$pos{\le}10^5$。

用$string$模拟一下即可

upsolved by JJLeo

长度为$n$的字符串$S$，位置$i$为$s_j$的概率为$p_{ij}$，给定$m$个模式串$t$，求$S$中不出现模式串的概率。字符集大小$\sum=6,n\le1024,\sum{|t|}\le32768$

对模式串建AC自动机，dp即可。 （好久不写忘记跳fail边标记调了一晚上）

solved by JJLeo

一个序列按如下顺序$A,B,C,\ldots,Z,AA,AB,AC,\ldots,ZZ,AAA,AAB,AAC\ldots$，从$0$开始编号，每个字母算一个编号，求第$n$个字母。

确定$n$所在的序列是几个字母为一组，然后按字典序确定每一位即可。

solved by JJLeo

求$\frac{m\times a_j}{a_i}(i<j)$的最大值。

扫一遍维护最小值即可。

solved by bazoka13

给定$n(1\leq n\leq5000)$个点，从一个点出发连点，对于依次连接的三个点$a,b,c$，要保证$c$在向量$ab$左侧，找出一个连接点数最多的方案。

显然是可以连接所有的点的。只需要根据凸包的求法螺旋向内连接即可。

最直接的想法就是用$Graham$ $n^2$暴力，每次向凸包内加点就标记，之后向凸包加点时就在未标记的点里找。但是这个做法过不去（貌似是卡常了（$20/21$））。

另一种做法就是一轮一轮求凸包，只不过每次都把当前轮的终点当作下一轮的起点。

solved by bazoka13

给定整数$n(1\leq n\leq44777444)$，将$n$变成$k$个数字的立方和，输出$k$的最小值和$k$个数字。

比赛时$dfs$深度应该不是特别大，就直接深搜+$剪枝$了。$dfs$时记录当前个数、剩余值、数字中的最大值，剩余为$0$就转移并更新最小步骤数，剪枝就考虑当前个数，如果当前个数$+1>=$最小个数或者$+$剩余值$/$所取数字立方的最大值$>=$最小个数就返回。

（赛时把初始最小值定成了$50$，结果刚刚发现最多不超过$10QAQ$）。

upsolved by

solved by bazoka13

给定两个字符串，判断能否将第二个字符串分成三部分后重新拼接成第一个字符串。字符串长度不超过$5000$。

因为数据范围不大，$hash+$枚举即可。先$hash$处理每个字符串$i~j$的子串，枚举第二个字符串的切割点判断即可。

-20min：CF坏了
-10min：CF还是坏了，跑到计蒜客找比赛
0min：开始看题
9min：CSK发现K是水题，开始写
20+min：CSK WA一发，MJX开始写另一道水题D
24min：MJX过D
25min：CSK过K，ZYF写G
7min：ZYF WA
33min：ZYF过G，开始写F(之后忘了啥时候WA了两发)
50+min：MJX写C，然后AC
56min：CSK写I，然后AC
60+min：ZYF过F，之后一起看A，ZYF,CSK讨论了一下发现A挺好写的，然后CSK写A
100min：CSK过A，然后看大家都没读懂题的B
?min：CSK写H，然后被卡常，改了几次终于过了
?min：ZYF写E，结果忘跳fail了
till end：在漫长的debug中结束了这场比赛

• CSK要改掉忘记关同步流就cin、cout的习惯。TLE后及时尝试换别的写法。
• ZYF要改掉不过脑子爆肝一道题而不和队友交流的坏习惯。
• MJX要改掉语言组织模糊不清的问题。