「POI2010」Antisymmetry-后缀数组
· ✏️ 790 words · ☕ 2 mins read
对于一个 $0/1$ 字符串,如果将这个字符串 $0$ 和 $1$ 取反后,再将整个串反过来和原串一样,就称作“反对称”字符串。比如 $00001111$ 和 $010101$ 就是反对称的, $1001$ 就不是。
现在给出一个长度为 $n$ 的 $0/1$ 字符串,求它有多少个子串是反对称的。
对于一个 $0/1$ 字符串,如果将这个字符串 $0$ 和 $1$ 取反后,再将整个串反过来和原串一样,就称作“反对称”字符串。比如 $00001111$ 和 $010101$ 就是反对称的, $1001$ 就不是。
现在给出一个长度为 $n$ 的 $0/1$ 字符串,求它有多少个子串是反对称的。
可读版题意:
给定 $n$ 个字符串,第 $i$ 个字符串的长度为 $M_i$ ,求每个字符串在所有字符串中出现的次数。
数据范围:$n \leq 100,\ M = \sum M_i \leq 10^6$.
阿申准备报名参加 $GT$ 考试,准考证号为 $n$ 位数 $X_1X_2\cdots X_n(0\le X_i\le 9)$,他不希望准考证号上出现不吉利的数字。
他的不吉利数字 $A_1A_2\cdots A_m(0\le A_i\le 9)$ 有 $m$ 位,不出现是指 $X_1X_2\cdots X_n$ 中没有恰好一段等于 $A_1A_2\cdots A_m$,$A_1$ 和 $X_1$ 可以为 $0$。
阿申想知道不出现不吉利数字的号码有多少种,输出模 $K$ 取余的结果。
二进制病毒审查委员会最近发现了如下的规律:某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码,那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段,试问,是否存在一个无限长的安全的二进制代码。
HH
是个喜欢变化的人,所以他不会立刻沿着刚刚走来的路走回。 又因为 HH
是个喜欢变化的人,所以他每天走过的路径都不完全一样,他想知道他究竟有多少种散步的方法。
现在给你学校的地图(假设每条路的长度都是一样的都是 $1$ ),问长度为 $t$ ,从给定地点 $A$ 走到给定地点 $B$ 共有多少条符合上述条件的路径。
有一个无向图 $G$ ,每个点有个权值,每条边有一个颜色。这个无向图满足以下两个条件:
在这个图上,你要支持以下三种操作:
对于 100% 的数据,保证颜色不多于 $10$ 种。
简单版题意:
给定一个长度为 $n$ 的字符串,和一个长度为 $n$ 的数列 ${a_n}$ ,求对于 $r$ 从 $0$ 到 $n-1$ ,所有满足 $1 \leq p < q \leq n$ 且 $lcp(p,q) \geq r$ 的数对个数以及满足上述条件的数对中 $a_p \times a_q$ 的最大值。( $a_i$ 可以为负数)
系统将依次随机抛出 $k$ 次宝物,每次你都可以选择吃或者不吃。宝物一共有 $n$ 种,系统每次抛出这 $n$ 种宝物的概率都相同且相互独立。
吃一次第 $i$ 种宝物将得到 $P_i$ 分,但并不是每种宝物都是可以随意获取的。第 $i$ 种宝物有一个前提宝物集合 $S_i$ 。只有当 $S_i$ 中所有宝物都至少吃过一次,才能吃第 $i$ 种宝物。注意,$P_i$ 可以是负数。
假设你采取最优策略,平均情况你一共能在奖励关得到多少分值?
现在有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有 $n$ 个叶子节点,满足这些权值为 $1…n$ 的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换,使得最终所有叶子节点的权值按照前序遍历序写出来,逆序对个数最少。
有 $m$ 个骑士攻占 $n$ 个城池。除 $1$ 号城池外,城池 $i$ 会受到另一座城池 $f_i$ 的管辖,其中 $f_i < i$。也就是说,所有城池构成了一棵有根树。第 $i$ 个骑士的初始战斗力为 $s_i$,第一个攻击的城池为 $c_i$。
每个城池有一个防御值 $h_i$,如果一个骑士的战斗力大于等于城池的生命值,那么骑士就可以占领这座城池;否则占领失败,骑士将在这座城池牺牲。占领一个城池以后,骑士的战斗力将发生变化,然后继续攻击管辖这座城池的城池,直到占领 $1$ 号城池,或牺牲为止。
除 $1$ 号城池外,每个城池 $i$ 会给出一个战斗力变化参数 $a_i$;$v_i$。若 $a_i = 0$,攻占城池 $i$ 以后骑士战斗力会增加 $v_i$;若 $a_i = 1$,攻占城池 $i$ 以后,战斗力会乘以 $v_i$。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池,不管结果如何,均不会影响其他骑士攻击这座城池的结果。
对于每个城池,输出有多少个骑士在这里牺牲;对于每个骑士,输出他攻占的城池数量。
给定一棵有根树,每个点有一个代价 $C_i$ ,权值 $L_i$ ,要求从这个树某个节点 $k$ 的子树(包含该节点)选取若干个节点,使得选取节点的个数乘上节点 $k$ 的权值最大,且这若干个节点的代价和不超过给定的限制 $M$ 。
左偏树是一种以二叉树为基础的数据结构,可以用来实现可以在$O(\log n)$时间内合并的堆。
一个无向连通图,顶点从 $1$ 编号到 $N$ ,边从 $1$ 编号到 $M$ 。 小 Z 在该图上进行随机游走,初始时小 Z 在 $1$ 号顶点,每一步小 Z 以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小 Z 到达 N 号顶点时游走结束,总分为所有获得的分数之和。 现在,请你对这 $M$ 条边进行编号,使得小 Z 获得的总分的期望值最小。
题面以图片显示,请点击“阅读全文”查看。
Y901
高速公路是一条由 $N-1$ 段路以及 $N$ 个收费站组成的东西向的链,我们按照由西向东的顺序将收费站依次编号为 $1 \sim N$ ,从收费站 $i$ 行驶到 $i+1$ (或从 $i+1$ 行驶到 $i$ )需要收取 $V_i$ 的费用。高速路刚建成时所有的路段都是免费的。
政府部门根据实际情况,会不定期地对连续路段的收费标准进行调整,根据政策涨价或降价。
求对于给定的 $l,r(l < r)$ ,在第 $l$ 个到第 $r$ 个收费站里等概率随机取出两个不同的收费站 $a$ 和 $b$ ,那么从 $a$ 行驶到 $b$ 将期望花费多少费用呢?