怎样不让网站自动跳转wap,wordpress 短代码 插件,厦门市建设区网站,网页设计与制作期末考试试题及答案C(分段) 题意#xff1a; 分析#xff1a; 我们分别考虑p2和p3的情况 当p2的时候#xff0c;个数明显是[L,R]内完全平方数的个数 当p3的时候#xff0c;我们注意到这样的数字个数是1e6级别的#xff0c;且a最多也不超过1e6 我们可以对于每个a去枚举对应的p 分析 我们分别考虑p2和p3的情况 当p2的时候个数明显是[L,R]内完全平方数的个数 当p3的时候我们注意到这样的数字个数是1e6级别的且a最多也不超过1e6 我们可以对于每个a去枚举对应的p然后丢到一个set里去重 还有一点要注意的p2可能会和p3的情况重复所以我们还要从set里去除所有的完全平方数 于是对于每个询问就在我们构造出的set里二分[l,r]内完全平方数的个数 D(扩展kmp) 题意 给出一个长度为n的字符串s一个长度为m的字符串t。nm 输入一个整数k你需要从字符串s中拿出两个不重合的长度为k的子串并拼接起来形成一个长度为2k的字符串f 请问是否存在一种取法使得t是字符串f的子串 n,m,k5e5 分析 我们来枚举字符串t的前缀把这个前缀作为第一个切片的后缀把t的对应后缀作为第二个切片的前缀看看是否可行 为了让两个切片不相交我们肯定想让第一个切片尽量靠左第二个切片尽量靠右 我们注意到处理右边切片和处理左边切片恰好是对称的这个我们只需要把字符串逆序再同样的做法求就行了所以我们不妨就只讨论处理左切片 现在问题就变成了在原串s中寻找一个尽量靠左的长度为k的子串这个子串的长度为i的后缀恰好是pret[i] 我们可以用exkmp预处理求出extend[i]表示s[i..n-1]与t的最长公共前缀那么对于每个i本质上就是找到最小的j使得extend[j]i且jk-i 我们可以从小到大枚举i用一个set去维护满足extend[]i的所有下标就行了 时间复杂度O(nlogn) E(去绝对值) 题意 给定长度为n的数组a[i]你需要自己决定一个T1Tn那么b[i]a[i]|T-i| b[i]表示b[i]秒后位置i上空的冰锥就会掉落到底面你就无法通过该位置了 现在有一个人从左边位置1向右边跑如果某一时刻该人前面的位置中有冰锥掉下来了并且后面的位置中也有冰锥掉了下来那么他就被困住了。 现在你需要定一个T使得该人被困住的时刻尽量早。 如果不存在这样的T那么输出-1 n1e5 分析 最简单的想法就是枚举所有的T然后求出该人被困住的时刻取个最小值就行了 假设现在我们枚举了一个T那么b[i]就已经确定了我们先来看个简单的问题就是如何判断该人是否会被困住 被困住的话那么就是一定会存在一个i使得b[i]i我们找一个满足条件的最小的i那么该人就在i前面被挡住了不能再跑了但要注意一点就是有可能后面某个冰锥很早就掉下来了他前方其实早就被封住了 然后这个时候的答案还需要等他后方最早的冰锥掉落 所以该情况下的困住时刻是max(min(b[1..i-1]),min(b[i1..n])) 这样还是O(n^2)的我们得优化我们的判定 我们把b[i]中的绝对值去掉那么就是 b[i]a[i]T-i (iT) b[i]a[i]i-T (iT) 我们可以考虑分类讨论两种情况下满足b[i]i的最小的i是谁这个东西的处理和D题的是一样的用一个set来维护就行了 找到这个分界点i之后问题就是对前半部分取min,对后半部分取min 我们注意到每次T的递增只是使得整体的一段1一段-1然后我们需要求区间最小值那么这用线段树就解决了 时间复杂度O(nlogn) F(dp计数) 题意 给出一个n点的有根树根是1。 dp[u][k]表示在以u为根的子树里我们需要去寻找一个子图它是一个满k叉树并且这个子图的深度最大dp[u][k]就是这样的最大深度 我们需要对所有1un,1kn的dp[u][k]去求和将结果输出 n3e5 分析 我们如果按照题目的这样去设计状态那么状态就直接爆炸了更不需要提转移了 我们把问题分成k1和k2k1的情况直接树形dp就行了 对于k2的情况我们发现所有dp[u][k]中有很多数字都是重复的且连续的因为深度不可能会很大最多是20 于是我们可以反过来设计状态dp[u][dep]表示以u为根的深度为dep的子树最大的k值是多少(因为如果存在深度为dep的k叉树那么一定存在深度为dep的k-1叉树) 这样状态数就是O(nlogn)了我们再来考虑转移 考虑枚举dep然后就是dp[v][dep]转移到dp[u][dep] 很明显是我们对所有的dp[v][dep]从大到小排序然后去找个最大的k满足a[k]k这个我们直接sort暴力 复杂度是O(nlog^2n)的 转载于:https://www.cnblogs.com/wmrv587/p/8687179.html
