【题解】第五届石家庄铁道大学程序设计竞赛题解

投稿用户 • • 免费办理POS机 • 阅读 55

本次校赛出题人有7个，每人2道（一道中文，一道英文），总共14道

题意：

第1行输入一个字符串，代表每一位加法运算所遵循的进制表规则，第2,3行输入两个运算数，按照进制表规则输出运算结果

思路：

先把2个字符串都在开头补0，使其等长，然后把这2个数加起来，之后进制转换，最后注意输出格式就可以了

思路：

每个人都可以拿（给自己加分）或者禁（不让对分加禁了的数字的分），所以是拿还是禁就是看能拿的选择和能禁的选择中谁的贡献大（就是面值大），确定了操作方式就可以模拟了

题意：

一共有N组条件，每一组有2个字符串（B和H），若H可以由B截取其中K个连续字符并放到最前面得到，那么这组就可以匹配成功，问这N组中有几组可以匹配成功

思路:

考点：字符串哈希

  • 直接使用储存Hash值，计算时不处理算术溢出问题(产生溢出时相当于自动对【题解】第五届石家庄铁道大学程序设计竞赛题解取模，这样可以避免低效的mod运算)，且一般取哈希进制数P为131或13331
  • 区间【题解】第五届石家庄铁道大学程序设计竞赛题解的字符串哈希值公式为：【题解】第五届石家庄铁道大学程序设计竞赛题解
  • 在 【题解】第五届石家庄铁道大学程序设计竞赛题解 串中找连续的 【题解】第五届石家庄铁道大学程序设计竞赛题解 个字符，和 【题解】第五届石家庄铁道大学程序设计竞赛题解 串前 【题解】第五届石家庄铁道大学程序设计竞赛题解 个字符匹配上，之后检验其余部分是否能匹配上即可，最终复杂度为【题解】第五届石家庄铁道大学程序设计竞赛题解，其中 【题解】第五届石家庄铁道大学程序设计竞赛题解 为字符串总长度

代码：

思路:

也是签到题，认真想一下，从1到n检查有没有空缺就可以了

思路:

每个测试样例不超过 【题解】第五届石家庄铁道大学程序设计竞赛题解 组测试数据，实现实数长度 【题解】第五届石家庄铁道大学程序设计竞赛题解 不超过 【题解】第五届石家庄铁道大学程序设计竞赛题解 的大实数加法，注意是否输出小数点，省略无意义的0
时间复杂度 【题解】第五届石家庄铁道大学程序设计竞赛题解

思路:

考点：背包DP，树形 DP

我们可以抽象为有根树中一个点最多只有一个父亲结点，这是一个森林，方便起见，我们可以新增一篇开心度为 【题解】第五届石家庄铁道大学程序设计竞赛题解 的文章（设这篇文章的开心度为 【题解】第五届石家庄铁道大学程序设计竞赛题解 ），作为所有无先导诗文篇章的先导诗文，这样我们就将森林变成了一棵以 【题解】第五届石家庄铁道大学程序设计竞赛题解 号诗文为根的树，而且恰好满足题意输入

设【题解】第五届石家庄铁道大学程序设计竞赛题解表示以 【题解】第五届石家庄铁道大学程序设计竞赛题解 号点为根的子树中，已经遍历了 【题解】第五届石家庄铁道大学程序设计竞赛题解 号点的前 【题解】第五届石家庄铁道大学程序设计竞赛题解 棵子树，选了 【题解】第五届石家庄铁道大学程序设计竞赛题解 篇文章的当前累计最大开心值之和，转移的过程中，我们枚举 【题解】第五届石家庄铁道大学程序设计竞赛题解 点的每个子结点 【题解】第五届石家庄铁道大学程序设计竞赛题解，同时枚举以 【题解】第五届石家庄铁道大学程序设计竞赛题解 为根的子树选的文章数（设为 【题解】第五届石家庄铁道大学程序设计竞赛题解 ），将子树的结果合并到 【题解】第五届石家庄铁道大学程序设计竞赛题解 上，另外，设以 【题解】第五届石家庄铁道大学程序设计竞赛题解 为根的子树大小为【题解】第五届石家庄铁道大学程序设计竞赛题解，点 【题解】第五届石家庄铁道大学程序设计竞赛题解 的儿子个数为 【题解】第五届石家庄铁道大学程序设计竞赛题解 ，有状态转移方程：

【题解】第五届石家庄铁道大学程序设计竞赛题解

【题解】第五届石家庄铁道大学程序设计竞赛题解 的第二维可以用滚动数组的方式省略掉，这时设【题解】第五届石家庄铁道大学程序设计竞赛题解为在 【题解】第五届石家庄铁道大学程序设计竞赛题解 及 【题解】第五届石家庄铁道大学程序设计竞赛题解 以下的子树上选 【题解】第五届石家庄铁道大学程序设计竞赛题解 篇文章（范围在 【题解】第五届石家庄铁道大学程序设计竞赛题解 至 【题解】第五届石家庄铁道大学程序设计竞赛题解 ）所能得到的当前累计最大开心值之和，注意这时需要倒序枚举 【题解】第五届石家庄铁道大学程序设计竞赛题解 的值，对于 【题解】第五届石家庄铁道大学程序设计竞赛题解 ，从 【题解】第五届石家庄铁道大学程序设计竞赛题解 至 【题解】第五届石家庄铁道大学程序设计竞赛题解 枚举就好了，而且我们可以证明，该做法的时间复杂度为【题解】第五届石家庄铁道大学程序设计竞赛题解

代码：

思路：

签到题，直接输出对应校赛的举办时间即可

代码：

思路：

本题所需解决的问题有3个：

  1. 计算蛋糕的大小：观察题目，我们可以知道蛋糕的宽都是相同的，因此判断每块蛋糕的面积的大小只需要判断蛋糕上下底边的和的大小即可
  2. 统计每块蛋糕上水果的个数：枚举每个水果的坐标，使用二分查找（通过向量的叉积判断水果在断口的左边还是右边）水果左边最右边的断口（或右边最左边的断口），统计每个断口被查找的次数即可求出每块蛋糕上水果的次数（蛋糕边缘的切割点的坐标可以利用前缀和求出）
  3. 找出所求蛋糕：可以通过记录当前最优解查找，也可使用结构体排序后直接选出

代码：

题意：

找到【题解】第五届石家庄铁道大学程序设计竞赛题解中的【题解】第五届石家庄铁道大学程序设计竞赛题解、【题解】第五届石家庄铁道大学程序设计竞赛题解，使得【题解】第五届石家庄铁道大学程序设计竞赛题解最大。

思路：

二分+位运算

给 l 的二进制补 1 ，只要没超过 r 就一直补，最后得到的数和 r 或运算就是结果

思路：

本题所需解决的问题有2个：

  1. 快速的求出范围内的所有质数：很明显使用定义来判断质数的总时间复杂度为【题解】第五届石家庄铁道大学程序设计竞赛题解，而本题的数据范围在1e7，肯定会超时，接下来采用埃氏筛，其效率是【题解】第五届石家庄铁道大学程序设计竞赛题解，虽然已经很快了，但是在残暴数据1e7面前仍会超时，最后便是本题的正解：欧拉筛（线性筛）正如名字那样，他的时间复杂度为【题解】第五届石家庄铁道大学程序设计竞赛题解，在利用线性筛打好表后，我们只需要枚举每个数，判断他们是否是素数，如果是则把他们存在一个数组中
  2. 对数组进行排序：大概有【题解】第五届石家庄铁道大学程序设计竞赛题解个素数，最后我们直接进行排序就好（排序使用时间复杂度不超过【题解】第五届石家庄铁道大学程序设计竞赛题解即可）

代码：

题意：

输入y，找出输入后函数在0-100上的最小值

思路：

算法：二分法求解

给原方程求导之后运用二分法求解。

思路：

给定一颗 【题解】第五届石家庄铁道大学程序设计竞赛题解 的无根树 (【题解】第五届石家庄铁道大学程序设计竞赛题解，保证无环)，注意到 【题解】第五届石家庄铁道大学程序设计竞赛题解 ，题目要求 【题解】第五届石家庄铁道大学程序设计竞赛题解 次树上修改，【题解】第五届石家庄铁道大学程序设计竞赛题解 次树上询问。因此使用邻接表建图之后，对每次修改和查询暴力 【题解】第五届石家庄铁道大学程序设计竞赛题解 求解即可，注意开 【题解】第五届石家庄铁道大学程序设计竞赛题解，时间复杂度【题解】第五届石家庄铁道大学程序设计竞赛题解

思路：

题目要求两个人到达同一地点所需时间最少，所以可以对每个人分别bfs一下，找到之和最小的那个点即可

思路：

签到题，为啥都不做捏QAQ，直接枚举所有的子串，然后判断是否回文就好了，因为输入字符串中间可能会有空格，所以输入方式推荐用getline

代码：

本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 sumchina520@foxmail.com 举报，一经查实，本站将立刻删除。
如若转载，请注明出处：https://www.zhidianwenhua.com/238.html
赞 (0)
投稿用户
0
上一篇 2023年8月9日 am4:41
下一篇 2023年8月9日 am8:41

相关推荐