BZOJ 4720 [NOIP2016]换教室

Description对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。在可以选择的课程中,有2n节课程安排在n个时间段上。在第i(1≤i≤n)个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室ci上课,而另一节课程在教室di进行。在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的n节安排好的课程。如果学生想更换第i节课程的教室,则需要提出申请。若申请通过,学生就可以在第i个     阅读全文
WildRage's avatar
WildRage 6月 25, 2017

BZOJ 1076 [SCOI2008]奖励关

Description 你正在玩你最喜欢的电子游戏,并且刚刚进入一个奖励关。在这个奖励关里,系统将依次随机抛出k次宝物,每次你都可以选择吃或者不吃(必须在抛出下一个宝物之前做出选择,且现在决定不吃的宝物以后也不能再吃)。 宝物一共有n种,系统每次抛出这n种宝物的概率都相同且相互独立。也就是说,即使前k-1次系统都抛出宝物1(这种情况是有可能出现的,尽管概率非常小),第k次抛出各个宝物的概率依然均为1/n。 获取第i种宝物将得到Pi分,但并不是每种宝物都是可以随意获取的。第i种宝物有一个前提宝物集合Si。只有当Si中所有宝物都至少吃过     阅读全文
WildRage's avatar
WildRage 6月 24, 2017

BZOJ 2337 [HNOI2011]XOR和路径

Description     阅读全文
WildRage's avatar
WildRage 6月 22, 2017

莫比乌斯反演的证明

莫比乌斯反演已知$$ F(n)=\sum_{d|n}{f(d)} $$则$$ f(n)=\sum_{d|n}{\mu(d)F(\frac {n}{d})} $$     阅读全文
WildRage's avatar
WildRage 6月 21, 2017

BZOJ 1415 [Noi2005] 聪聪和可可 概率DP

Description Input数据的第1行为两个整数N和E,以空格分隔,分别表示森林中的景点数和连接相邻景点的路的条数。 第2行包含两个整数C和M,以空格分隔,分别表示初始时聪聪和可可所在的景点的编号。 接下来E行,每行两个整数,第i+2行的两个整数Ai和Bi表示景点Ai和景点Bi之间有一条路。 所有的路都是无向的,即:如果能从A走到B,就可以从B走到A。 输入保证任何两个景点之间不会有多于一条路直接相连,且聪聪和可可之间必有路直接或间接的相连。     阅读全文
WildRage's avatar
WildRage 6月 21, 2017

BZOJ 3143 [Hnoi2013]游走 高斯消元 概率DP

Description一个无向连通图,顶点从1编号到N,边从1编号到M。小Z在该图上进行随机游走,初始时小Z在1号顶点,每一步小Z以相等的概率随机选 择当前顶点的某条边,沿着这条边走到下一个顶点,获得等于这条边的编号的分数。当小Z 到达N号顶点时游走结束,总分为所有获得的分数之和。现在,请你对这M条边进行编号,使得小Z获得的总分的期望值最小。     阅读全文
WildRage's avatar
WildRage 6月 21, 2017

BZOJ 1778 [Usaco2010 Hol] Dotp 驱逐猪猡 高斯消元 概率期望

Description奶牛们建立了一个随机化的臭气炸弹来驱逐猪猡。猪猡的文明包含1到N (2 <= N <= 300)一共N个猪城。这些城市由M (1 <= M <= 44,850)条由两个不同端点A_j和B_j (1 <= A_j<= N; 1 <= B_j <= N)表示的双向道路连接。保证城市1至少连接一个其它的城市。一开始臭气弹会被放在城市1。每个小时(包括第一个小时),它有P/Q (1 <= P <=1,000,000; 1 <= Q <= 1,000,000)的概率污染它所在的城市。如果这个小时内它没有污染它所在的城市,那麽它随机地选择一条道路,在这个小时内沿着这条道路走到一个新的城市。可以离开这个城市的所有道路被选择的概率均等。因为这个臭气弹的随机的性质,     阅读全文
WildRage's avatar
WildRage 6月 19, 2017

BZOJ 1013 [JSOI2008]球形空间产生器sphere 高斯消元

Description 有一个球形空间产生器能够在n维空间中产生一个坚硬的球体。现在,你被困在了这个n维球体中,你只知道球面上n+1个点的坐标,你需要以最快的速度确定这个n维球体的球心坐标,以便于摧毁这个球形空间产生器。     阅读全文
WildRage's avatar
WildRage 6月 19, 2017