Southeastern Europe Regional Contest 2016¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| N/A | 8 | 10 | 11 |
A. Three Squares¶
solved by bazoka13
题意¶
给定\(n(n\leq1e5)\)个点，坐标\(x,y\)的范围为\(0-1e9\)，用三个正方形覆盖所有的点，求正方形的最小边长。
题解¶
找出\(x,y\)坐标的最大/小值，显然最值点应该尽量位于正方形的边界上。考虑\(dfs\)做法，对当前的正方形，找出未标记点的四个最值，最多有四种搭配（比如：\((minx,maxy-d),(minx,miny)\)），每个搭配中，找出当前正方形可以覆盖的点，标记。如果已经\(dfs\)到第三个正方形，就比较\(x,y\)最值的差值与当前边长，如果小于当前边长，就说明当前边长是合法的。
边长利用上述方法二分即可。
B. Favorite music¶
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\)可以交换，因此离线处理的时候要互相加入。
C. Castle¶
solved by 2sozx
题意¶
给定字符串\(S\)与空集合\(T\)，第一种操作在\(S\)后面添加一个字符，第二种操作将\(S\)整体作为一个元素放入\(T\)中，第三种询问\(T\)中有多少个元素是\(S\)的后缀,操作次数\(m{\le}12*10^5\)，\(|S|{\le}10^3\)。
题解¶
题目可转化为，有多少个特定长度的前缀等于等长的后缀，这与\(KMP\)的\(fail\)数组道理是一样的，在操作二时打标记，操作一时转移即可。
注：集合中不应有相同的元素。
D. Reading Digits¶
solved by 2sozx
题意¶
给定一个由数字组成的字符串，字符串中每两个字符一组，每次操作以组为单位，将这组变成\(a\)个\(b\)，\(a\)是组内第一个字符，\(b\)是第二个字符，求\(k\)此操作后\(pos\)位是多少,\(k{\le}40\)，\(pos{\le}10^5\)。
题解¶
用\(string\)模拟一下即可
E. Exam¶
upsolved by JJLeo
题意¶
长度为\(n\)的字符串\(S\)，位置\(i\)为\(s_j\)的概率为\(p_{ij}\)，给定\(m\)个模式串\(t\)，求\(S\)中不出现模式串的概率。字符集大小\(\sum=6,n\le1024,\sum{|t|}\le32768\)
题解¶
对模式串建AC自动机，dp即可。 （好久不写忘记跳fail边标记调了一晚上）
F. Letters¶
solved by JJLeo
题意¶
一个序列按如下顺序\(A,B,C,...,Z,AA,AB,AC,...,ZZ,AAA,AAB,AAC...\)，从\(0\)开始编号，每个字母算一个编号，求第\(n\)个字母。
题解¶
确定\(n\)所在的序列是几个字母为一组，然后按字典序确定每一位即可。
G. Pokemons¶
solved by JJLeo
题意¶
求\(\frac{m\times a_j}{a_i}(i<j)\)的最大值。
题解¶
扫一遍维护最小值即可。
H. Pub crawl¶
solved by bazoka13
题意¶
给定\(n(1\leq n\leq5000)\)个点，从一个点出发连点，对于依次连接的三个点\(a,b,c\)，要保证\(c\)在向量\(ab\)左侧，找出一个连接点数最多的方案。
题解¶
显然是可以连接所有的点的。只需要根据凸包的求法螺旋向内连接即可。
最直接的想法就是用\(Graham\) \(n^2\)暴力，每次向凸包内加点就标记，之后向凸包加点时就在未标记的点里找。但是这个做法过不去（貌似是卡常了（\(20/21\)））。
另一种做法就是一轮一轮求凸包，只不过每次都把当前轮的终点当作下一轮的起点。
I. Cubes¶
solved by bazoka13
题意¶
给定整数\(n(1\leq n\leq44777444)\)，将\(n\)变成\(k\)个数字的立方和，输出\(k\)的最小值和\(k\)个数字。
题解¶
比赛时\(dfs\)深度应该不是特别大，就直接深搜+\(剪枝\)了。\(dfs\)时记录当前个数、剩余值、数字中的最大值，剩余为\(0\)就转移并更新最小步骤数，剪枝就考虑当前个数，如果当前个数\(+1>=\)最小个数或者\(+\)剩余值\(/\)所取数字立方的最大值\(>=\)最小个数就返回。
（赛时把初始最小值定成了\(50\)，结果刚刚发现最多不超过\(10QAQ\)）。
J. Marathon¶
upsolved by
题意¶
题解¶
K. Cutting¶
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要改掉语言组织模糊不清的问题。