EagleBear2002 的博客

这里必须根绝一切犹豫,这里任何怯懦都无济于事

题目描述

牛牛有一块蛋糕,他想把蛋糕分给小朋友们。蛋糕一开始是圆形的,牛牛会在圆周上选择 n 个不重合的点,将这几个点两两用线段连接。这些线段将会把蛋糕分成若干块。

现在,牛牛想知道,蛋糕最多会被分成多少块,请你告诉他答案。

输入格式

输入包含至多 20 行,每行一个整数 n,含义见「题目描述」。保证 0n64

阅读全文 »

题目描述

n 个点的无向完全图删去一条边之后圈的个数,答案模 998244353

注:圈指的是任选一个顶点为起点,沿着不重复的边,经过不重复的顶点为途径,之后又回到起点的闭合途径。

输入格式

第一行一个整数 T,表示数据组数。

阅读全文 »

题目描述

聪明的 Cirno 开始学习计算,于是她很开心的算出了从 1 一直加到 n

得到了一个 n 项的数列 : {an=1+2+3+4+...+n}

为了验证自己算是否算错,她需要以某种规律从数列里取出两个元素 v1,v2(元素可以相同),并等概率的选出整数 a[1,v1]b[1,v2] 判断哪个比较大。

所以她需要你来计算 a>b 的概率。

阅读全文 »

题目描述

Zeit und Raum trennen dich und mich.

时空将你我分开。

B 君在玩一个游戏,这个游戏由 n 个灯和 n 个开关组成,给定这 n 个灯的初始状态,下标为从 1n 的正整数。

每个灯有两个状态亮和灭,我们用 1 来表示这个灯是亮的,用 0 表示这个灯是灭的,游戏的目标是使所有灯都灭掉。

但是当操作第 i 个开关时,所有编号为 i 的约数(包括 1i)的灯的状态都会被改变,即从亮变成灭,或者是从灭变成亮。

阅读全文 »

题目描述

sol 研发了一个神奇的随机数系统,可以自动按照环境噪音生成真·随机数。

现在 sol 打算生成 n[1,x] 的整数 a1,...,an,然后进行一些询问。

q 次询问,每次询问 i 有两个参数 liri,sol 会计算 minlijriaja 数组中下标在 li,ri 之间的数的最小值)。

最后测试结果会是这些询问得到的结果的最大值。

阅读全文 »

题目描述

C 有一棵 n 个结点的有根树,根是 1 号结点,且每个结点最多有两个子结点。

定义结点 x 的权值为:

1.若 x 没有子结点,那么它的权值会在输入里给出,保证这类点中每个结点的权值互不相同

2.若 x 有子结点,那么它的权值有 px 的概率是它的子结点的权值的最大值,有 1px 的概率是它的子结点的权值的最小值。

阅读全文 »

题目描述

H 国有 N 个城市。

在接下来的 M 天,小 c 都会去找小 w,但是小 c 不知道小 w 的具体位置,所以小 c 决定每次随机找一条路走,直到遇到了小 w 为止。

小 c 知道小 w 只有可能是在 c1,c2..cnn 个城市中的一个,小 c 想知道在最坏情况下,小 c 遇到小 w 期望要经过多少条道路。

H 国所有的边都是无向边,两个城市之间最多只有一条道路直接相连,没有一条道路连接相同的一个城市。

阅读全文 »

题目描述

给定一个 n 个点 m 条边的无向连通图,顶点从 1 编号到 n,边从 1 编号到 m

小 Z 在该图上进行随机游走,初始时小 Z 在 1 号顶点,每一步小 Z 以相等的概率随机选择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小 Z 到达 n 号顶点时游走结束,总分为所有获得的分数之和。 现在,请你对这 m 条边进行编号,使得小 Z 获得的总分的期望值最小。

输入格式

第一行是两个整数,分别表示该图的顶点数 n 和边数 m

阅读全文 »

题目描述

傲娇少女幽香是一个很萌很萌的妹子,而且她非常非常地有爱心,很喜欢为幻想乡的人们做一些自己力所能及的事情来帮助他们。

这不,幻想乡突然发生了地震,所有的道路都崩塌了。现在的首要任务是尽快让幻想乡的交通体系重新建立起来。幻想乡一共有 n 个地方,那么最快的方法当然是修复 n1 条道路将这 n 个地方都连接起来。 幻想乡这 n 个地方本来是连通的,一共有 m 条边。现在这 m 条边由于地震的关系,全部都毁坏掉了。每条边都有一个修复它需要花费的时间,第 i 条边所需要的时间为 ei。地震发生以后,由于幽香是一位人生经验丰富,见得多了的长者,她根据以前的经验,知道每次地震以后,每个 ei 会是一个 01 之间均匀分布的随机实数。并且所有 ei 都是完全独立的。

现在幽香要出发去帮忙修复道路了,她可以使用一个神奇的大魔法,能够选择需要的那 n1 条边,同时开始修复,那么修复完成的时间就是这 n1 条边的 ei 的最大值。当然幽香会先使用一个更加神奇的大魔法来观察出每条边 ei 的值,然后再选择完成时间最小的方案。 幽香在走之前,她想知道修复完成的时间的期望是多少呢?

输入格式

阅读全文 »

题目描述

给定一个无向连通图,其节点编号为 1N,其边的权值为非负整数。试求出一条从 1 号节点到 N 号节点的路径,使得该路径上经过的边的权值的“XOR 和”最大。该路径可以重复经过某些节点或边,当一条边在路径中出现多次时,其权值在计算“XOR 和”时也要被重复计算相应多的次数。

直接求解上述问题比较困难,于是你决定使用非完美算法。具体来说,从 1 号节点开始,以相等的概率,随机选择与当前节点相关联的某条边,并沿这条边走到下一个节点,重复这个过程,直到走到 N 号节点为止,便得到一条从 1 号节点到 N 号节点的路径。显然得到每条这样的路径的概率是不同的并且每条这样的路径的“XOR 和”也不一样。现在请你求出该算法得到的路径的“XOR 和”的期望值。

输入格式

输入文件的第一行是用空格隔开的两个正整数 NM,分别表示该图的节点数和边数。紧接着的 M 行,每行是用空格隔开的三个非负整数 u,vw(1u,vN0w109),表示该图的一条边 (u,v),其权值为 w。输入的数据保证图连通。

阅读全文 »