CVBB ACM Team

• 日期：2020.5.2

• 比赛地址： 传送门

• 做题情况：lxh(BG)，tyx(D)，gyp(J)

• A - Avaricious Maryanna
  • solved by -, upsolved by tyx,lxh,gyp
  • 题意：给定T个询问，每次询问一个$N$，要求输出所有$N$位的数$x$的满足$x*x$的后$N$位等于$x$.(不妨假设$x$为$i$位)。
  • 数据范围：$N \le 500$，$T \le 1000$。
  • 题解：首先我们不难想到满足条件的1位数分别为0，1，5，6。我们可以想到，满足条件的两位数的个位必定是满足条件的一位数…N位后面的数字必定是N-1位满足条件的数字，由于有这样的性质，我们可以在这4个数的基础上在前面添数字进行验证，由于最多有500位，需要高精度，复杂度应为$(N*N*4*10)$,特别的，我们需要注意，满足条件的还前导0的N位数我们也要考虑，例：我们需要从0625推出90625，4位不保存则会少解。然后可以发现，这样到N位满足的不会超过4个，且必定有两个为000…1和000…0.然后发现用高精预处理答案会T(或许写万进制或者亿进制不会？)，其实只要通过高精度的算法把500位的两个解弄出来每次去掉最高位就可以了(无前导0即为解，有则不为)。
• B - Boring Homework
  • solved by lxh
  • 题意：给定$T$个询问，每次给定一个数字从$1-n$的序列，按序列生成BST，并在每列只允许出现一个点(代表树上的点)的情况下输出BST，要求有左右子树的情况下需要在o一边加+号，通过添加-号来维护每列只能有一个点的限制，最小化-号的个数。（具体可以看原题）
  • 数据范围：$N \le 80$，$T \le 2500$。
  • 题解：经过分析样例和思考之后我们不难发现，对于一个点所处的位置，一定是处在它的权值那一列的，在这种构造情况下，对于一个点o,我们需要从它的编号-1-它的左子树这一位置开始插入它的左子树的右子树这么多个-…(后面的减号和空格同理可以推得)，用宽搜和打标记(处理|)的方式输出即可。
• D - Detection of Extraterrestrial
  • solved by tyx
  • 题意：$T$组询问$(T \le 200)$，每次给出一个字符串$s(|s| \le 1000)$，问字符串中有循环节且循环了$k(1 \le k \le |s|)$次的子串最大长度，每个字符串的$1$到$|s|$都要回答。
  • 数据范围：$N \le 1000$，$T \le 200$。
  • 题解：我们知道在KMP算法中，如果有$i\ mod\ (i\ -\ next[i])\ ==\ 0$，说明这个字符串存在循环节，我们根据这一结论枚举字符串的起点和终点即可，复杂度$O(n^2T)$（本来以为过不了，没想到只跑了120+ms）。
• E - Entertainment
  • solved by -, upsolved by gyp
  • 题意：给定一个人本方发球的胜率和对方发球的胜率，计算这个人一场网球比赛的胜率。网球比赛发一次球，胜者得一分。一个人在一局获胜的条件是至少赢四分且超过对手两分；一个人在一盘获胜条件是赢至少六局且超过对手两局；先赢得三盘的人获得一场的胜利。每局的发球人不变，一盘中的相邻两局发球人交替。一场的相邻两局率先发球者交替。所计算的人率先发球
  • 数据范围：$T \le 10^4$。
  • 题解：先算出这个人一局中先发球和后发球各自的胜率。然后计算一盘中先发球和后发球各自的胜率。然后计算率先赢得三盘的胜率。计算时，可以先假设每局赛满6球，每盘赛满10局，每场赛满5盘进行计算。如果一局3:3或一盘5:5，再用级数求和算得这种情况下的获胜几率。
• G - Google is Feeling Lucky
  • solved by lxh
  • 题意：给$N$个字符串和权值，输出权值最大的字符串(有多个全部输出)
  • 数据范围：$N = 10$，$T$没给。
  • 题解：排序输出。
• J - Juice Extractor
  • solved by gyp
  • 题意：切水果游戏，给定每个水果出现的时间区间。每次切水果切掉此时所有的水果。每次若切i（i>2）个得i分，否则不得分。问最多得分
  • 数据范围：$N \le 1000$，$T \le 200$。
  • 题解：显然只有在有水果刚出现时才考虑切。dp，枚举上一次切的时间。

第一小时：tyx在写H题，但是没有写出来；gyp和lxh想出了A题思路，lxh发现G题有很多人过于是A了G题。

第二小时：三个人一起在想D题，没有想出来。tyx和lxh想出了B题怎么写，lxh开始写B题。

第三小时：gypA了J题，lxhA了B题，tyx在想D题。

第四小时：gyp发现数据比较水，tyx由此想到了$O(n^2T)(n \le 1000,T \le 200)$的方法A了D题。lxhA题的高精度超时。

尽量不要三个人同时想一道题；在别的题没有明确解法的情况下，有想法的题一定要尝试一下；一定要先把所有题都看一遍。