Oql's Blog

发表于 分类于 ，

题意

你喜欢字符串。有人送了你一个仅含小写字母的字符串。

由于你是一名优秀的 𝑂𝐼er，所以你决定对这个字符串展开研究。

定义两个字符串是相似的，当且仅当存在至多一个 $i$ ，使得这两个字符串中只有第 $i$ 个字母不同。

你取出了这个字符串中所有长度为 $m$ 的子串。你想知道，对于每个长度为 $m$ 的子串，有多少个其它长度为 $m$ 的子串与它相似。

$n\leq 10^5$

阅读全文 »

发表于 分类于 ，

题意

有一张 $n$ 个点，$m$ 条边的无向图，你想选出一个非空点集，使得仅保留这个点集中的点和两个端点都在这个点集里的边后得到的图是连通的。你想知道有多少种可能的选点集的方案。

对 $2$ 取模。

$n\leq 50$，对于所有的边 $(x,y)$，均有 $|x-y|\leq 12$。

阅读全文 »

发表于 分类于 ，

题意

有一个挖宝游戏，它在一棵 n 个点的树上进行，宝藏埋在某个未知的点 $𝑥$ 。每次挖掘一个点 $u$，玩家得到的反馈信息是一个数值 $d$，表示 $u$ 号点到 $𝑥$ 号点简单路径上的边数。这个游戏会进行 $q$ 次，每次游戏藏宝的位置不一定相同。

你作为一名优秀的 OIer，对自己无比自信。你希望用最少的挖掘次数来找出宝藏。于是你挑了两个不同的点 $a,b$ 进行挖掘，并得到了反馈信息，分别为 $d_a,d_b$。接下来的第三次挖掘中，你想要直接奔着一个可能的 $𝑥$ 进行挖掘。由于树太大了，凭借人眼无法找出 $𝑥$ 的确切位置，你便转向了电脑，开始写一个程序，帮助你解决这个问题。

$n,q\leq 10^6,1\leq d \leq n$

阅读全文 »