2020-2021:teams:hotpot:acmgooglecup2011invitationalprogrammingcontest
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:acmgooglecup2011invitationalprogrammingcontest [2020/05/08 17:22] misakatao 更新 |
2020-2021:teams:hotpot:acmgooglecup2011invitationalprogrammingcontest [2020/05/09 18:16] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 9: | 行 9: | ||
| =====题解===== | =====题解===== | ||
| - | * A - Avaricious Maryanna | + | ====A - Avaricious Maryanna==== |
| - | * solved by -, upsolved by tyx,lxh,gyp | + | |
| - | * 题意：给定T个询问，每次询问一个$N$，要求输出所有$N$位的数$x$的满足$x*x$的后$N$位等于$x$.(不妨假设$x$为$i$位)。 | + | ===solved by -, upsolved by tyx,lxh,gyp=== |
| - | * 数据范围：$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个询问，每次询问一个$N$，要求输出所有$N$位的数$x$的满足$x*x$的后$N$位等于$x$.(不妨假设$x$为$i$位)。 |
| - | * 题意：给定$T$个询问，每次给定一个数字从$1-n$的序列，按序列生成BST，并在每列只允许出现一个点(代表树上的点)的情况下输出BST，要求有左右子树的情况下需要在o一边加+号，通过添加-号来维护每列只能有一个点的限制，最小化-号的个数。（具体可以看原题） | + | |
| - | * 数据范围：$N \le 80$，$T \le 2500$。 | + | ===数据范围=== |
| - | * 题解：经过分析样例和思考之后我们不难发现，对于一个点所处的位置，一定是处在它的权值那一列的，在这种构造情况下，对于一个点o,我们需要从它的编号-1-它的左子树这一位置开始插入它的左子树的右子树这么多个-...(后面的减号和空格同理可以推得)，用宽搜和打标记(处理|)的方式输出即可。 | + | |
| - | * D - Detection of Extraterrestrial | + | $N \le 500$，$T \le 1000$。 |
| - | * 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）。 | + | 首先我们不难想到满足条件的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即为解，有则不为)。 |
| - | * E - Entertainment | + | |
| - | * solved by -, upsolved by gyp | + | ====B - Boring Homework==== |
| - | * 题意：给定一个人本方发球的胜率和对方发球的胜率，计算这个人一场网球比赛的胜率。网球比赛发一次球，胜者得一分。一个人在一局获胜的条件是至少赢四分且超过对手两分；一个人在一盘获胜条件是赢至少六局且超过对手两局；先赢得三盘的人获得一场的胜利。每局的发球人不变，一盘中的相邻两局发球人交替。一场的相邻两局率先发球者交替。所计算的人率先发球 | + | |
| - | * 数据范围：$T \le 10^4$。 | + | ===solved by lxh=== |
| - | * 题解：先算出这个人一局中先发球和后发球各自的胜率。然后计算一盘中先发球和后发球各自的胜率。然后计算率先赢得三盘的胜率。计算时，可以先假设每局赛满6球，每盘赛满10局，每场赛满5盘进行计算。如果一局3:3或一盘5:5，再用级数求和算得这种情况下的获胜几率。 | + | |
| - | * G - Google is Feeling Lucky | + | ===题意=== |
| - | * solved by lxh | + | |
| - | * 题意：给$N$个字符串和权值，输出权值最大的字符串(有多个全部输出) | + | 给定$T$个询问，每次给定一个数字从$1-n$的序列，按序列生成BST，并在每列只允许出现一个点(代表树上的点)的情况下输出BST，要求有左右子树的情况下需要在o一边加+号，通过添加-号来维护每列只能有一个点的限制，最小化-号的个数。（具体可以看原题） |
| - | * 数据范围：$N = 10$，$T$没给。 | + | |
| - | * 题解：排序输出。 | + | ===数据范围=== |
| - | * J - Juice Extractor | + | |
| - | * solved by gyp | + | $N \le 80$，$T \le 2500$。 |
| - | * 题意：切水果游戏，给定每个水果出现的时间区间。每次切水果切掉此时所有的水果。每次若切i（i>2）个得i分，否则不得分。问最多得分 | + | |
| - | * 数据范围：$N \le 1000$，$T \le 200$。 | + | ===题解=== |
| - | * 题解：显然只有在有水果刚出现时才考虑切。dp，枚举上一次切的时间。 | + | |
| + | 经过分析样例和思考之后我们不难发现，对于一个点所处的位置，一定是处在它的权值那一列的，在这种构造情况下，对于一个点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，枚举上一次切的时间。 | ||
| =====Replay===== | =====Replay===== | ||
| 行 46: | 行 111: | ||
| 第二小时：三个人一起在想D题，没有想出来。tyx和lxh想出了B题怎么写，lxh开始写B题。 | 第二小时：三个人一起在想D题，没有想出来。tyx和lxh想出了B题怎么写，lxh开始写B题。 | ||
| - | 第三小时：gypA了J题 | + | 第三小时：gypA了J题，lxhA了B题，tyx在想D题。 |
| - | 第四小时： | + | 第四小时：gyp发现数据比较水，tyx由此想到了$O(n^2T)(n \le 1000,T \le 200)$的方法A了D题。lxhA题的高精度超时。 |
| =====总结===== | =====总结===== | ||
| + | |||
| + | * 尽量不要三个人同时想一道题 | ||
| + | * 在别的题没有明确解法的情况下，有想法的题一定要尝试一下 | ||
| + | * 一定要先把所有题都看一遍。 | ||
2020-2021/teams/hotpot/acmgooglecup2011invitationalprogrammingcontest.1588929771.txt.gz · 最后更改: 2020/05/08 17:22 由 misakatao
