2 Riypo_Yian

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 1w+

NKOJ 5140 大吉大利 晚上吃鸡

问题描述何老板养了n只鸡(编号1到n)。何老板打算从今天开始,连续m晚都吃鸡。每晚,何老板会选一对指定编号的鸡出来。若两只鸡都活着,那么他会随便吃掉其中一只;若只有一只活着,另一只之前已经被吃了,就吃还活着那只;若两只鸡都已被吃掉了,当晚就不吃鸡。何老板想知道,m天后,可能有多少对鸡同时活着?请你帮他算一算。(如果一对鸡存活的概率>0,我们认为他们可能活着)输入格式第一行,两...

2018-11-16 23:15:17

「NOIP模拟」礼物【状态压缩】【期望DP】

Description夏川的生日就要到了。作为夏川形式上的男朋友,季堂打算给夏川买一些生日礼物。商店里一共有种礼物。夏川每得到一种礼物,就会获得相应喜悦值Wi(每种礼物的喜悦值不能重复获得)。每次,店员会按照一定的概率Pi(或者不拿出礼物),将第i种礼物拿出来。季堂每次都会将店员拿出来的礼物买下来。众所周知,白毛切开都是黑的。所以季堂希望最后夏川的喜悦值尽可能地高。求夏川最后最大的喜悦...

2018-11-16 23:14:59

「NOIP模拟」通讯【tarjan缩点】【似乎要拓扑?但是好麻烦啊】

【问题描述】“这一切都是命运石之门的选择。”试图研制时间机器的机关SERN截获了中二科学家伦太郎发往过去的一条短信,并由此得知了伦太郎制作出了电话微波炉(仮)。为了掌握时间机器的技术,SERN总部必须尽快将这个消息通过地下秘密通讯网络,传达到所有分部。SERN共有N个部门(总部编号为0),通讯网络有M条单向通讯线路,每条线路有一个固定的通讯花费Ci为了保密,消息的传递只能按照固定的方式...

2018-11-16 23:14:38

简单记录一下费马小定理与欧拉定理

费马小定理如果ppp是质数,且gcd(a,p)=1gcd(a,p)=1gcd(a,p)=1,则有ap−1≡1 (mod  p)a^{p-1} ≡ 1\ (mod\ \ p)ap−1≡1 (mod  p)应用:求逆元已知ppp是质数,且gcd(a,p)=1gcd(a,p)=1gcd(a,p)=1,求aaa在模ppp意义下的乘法逆元。...

2018-11-09 20:51:23

BZOJ 2657: [Zjoi2012]旅游(journey)【树DP找树的直径】

最开始没看懂题…看了这篇题解后才懂题…https://blog.csdn.net/Clove_unique/article/details/53004733将每个三角形看成点然后相邻的话就连边于是就得到一棵树,答案显然就是树的直径#include <bits/stdc++.h>using namespace std;const int N=6e5+5;const int ...

2018-11-08 19:51:05

简单复习一下Manacher算法(求最长回文子串)

对于串ABCDCBCABCDCBCABCDCBC,我们在每两个字符之间添加其他字符#\##得到A#B#C#D#B#C#DA\#B\#C\#D\#B\#C\#DA#B#C#D#B#C#Dp[i]p[i]p[i]表示并且iii为回文中心并且回文半径为p[i]p[i]p[i]。我们考虑求这个东西。maxpmaxpmaxp表示当前回文串的最右边的位置,midmidmid表示maxpmaxpmaxp所...

2018-11-08 15:50:10

「记录NOIp2018」(退役or省选)

Day-1今天上午是最后一场NOIp2018NOIp2018NOIp2018前的训练赛。千万不要把欧气用完了呀QvQ

2018-11-08 00:36:03

「NOIP模拟」成绩【类卡特兰数】

题目描述在成都某中学有 m 个男生与 n 个女生排队,这个学校的女生比较古怪,从某个位置(包含这个位置)开始往前数,男生的数量超过了女生的数量,女生会感觉不安全,于是会大叫起来,为了构建和谐校园,安排队伍时应该避免这样的情况。请你计算出不会引发尖叫的排队方案的概率。(排队方案不同定义:当且仅当某个某个位置人不一样,如男生A、男生B ,与男生B、男生A ,2个排列是不同方案)原题SCOI...

2018-11-07 15:52:43

BZOJ 1856: [Scoi2010]字符串【类卡特兰数】

类比卡特兰数。ans=Cn+mm−Cn+mm−1ans=C_{n+m}^{m}-C_{n+m}^{m-1}ans=Cn+mm​−Cn+mm−1​#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include &lt

2018-11-07 15:48:00

「NOIP模拟」【2018.11.6晚间训练赛】ping【树状数组】【树上点差分】【dfs序】

问题描述TgopknightTgopknightTgopknight所连接的网络共有nnn个站点,由于经费问题,每两个站点之间有且仅有一条线路,这些站点中有一些损坏了,TgopknightTgopknightTgopknight进行了kkk次测试,每次测试两个站点之间是否连通,由于TgopknightTgopknightTgopknight手气太好,他每次测试的两个站点之间都不连通。Tgopkn...

2018-11-07 00:30:05

「NOIP模拟」【2018.11.6晚间训练赛】Snake vs Block【动态规划】

题目描述TgopknightTgopknightTgopknight最近迷上了一款叫做Snake vs BlockSnake\ vs\ BlockSnake vs Block的游戏,他总觉得自己玩出的不是最优解,但是他忙于享受游戏的乐趣,只好请你帮忙找出最优解。Snake vs BlockSnake\ vs\ BlockSnake&

2018-11-06 23:41:20

BZOJ 3296: [USACO2011 Open] Learning Languages【并查集】

last[x]last[x]last[x]表示xxx这门语言上一个掌握的奶牛。然后合并。答案就是最后的集合个数-1。#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define db dou...

2018-11-06 15:55:05

BZOJ 1046: [HAOI2007]上升序列【动态规划】

f[i]f[i]f[i]表示以a[i]a[i]a[i]为开头的最长上升子序列的长度。显然可以暴力O(n2)O(n^2)O(n2)转移得到fff对于每一个询问,直接O(n)O(n)O(n)扫一遍即可。#include <cmath>#include <cstdio>#include <cstring>#include <iostream>...

2018-11-06 15:13:39

NKOJ 4284 路径数【最短路计数】

我们把对角线下面的权值放到上面,然后将对角线上任意一点作为终点。然后最短路计数一下就好了。#include <bits/stdc++.h>#define ll long longusing namespace std;const ll N=2e2+5;const ll Inf=1e18;const ll Mod=1e9+9;ll n,t,mp[N][N],id[N...

2018-11-06 11:58:29

「NOIP模拟」建设图【tarjan缩点】

【问题描述】企鹅国现在准备建设一些新的道路,使得这些新的道路建设完毕之后,可以满足以下条件——任何一条道路损坏之后,任意两个城市还是可以互相到达。注意所有的道路都是双向的。【输入格式】第一行两个整数 N,M 代表城市个数和原有道路条数。接下来 M 行,每行 2 个数字 F 和 T,表示从 F 到 T 有一条无向道路。保证没有自环和重边。保证原有道路可以使得所有城市连通。【输出格式】...

2018-11-06 11:58:15

「NOIP模拟」蒜头君的排序【伪莫队】【树状数组】

求冒泡排序的交换次数即求逆序对数。按照正常的求逆序对的方法和莫队方法添加删除即可。注意不要把每次的ans清零。#include <cmath>#include <bitset>#include <cstdio>#include <cstring>

2018-11-06 11:58:03

「NOIP模拟」蒜头君救人【动态规划】

#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#defin

2018-11-06 11:57:50

「NOIP模拟」蒜头君的兔子【矩阵快速幂】

推一下矩阵就好了:#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include &a

2018-11-06 11:57:29

BZOJ 2750: [HAOI2012]Road【最短路】

首先介绍一个概念,最短路图(不是很重要只是方便我叙述)。我们以SSS为起点对图GGG做一次最短路算法,如果GGG的子图G′G'G′满足:G′G'G′的任意一条边都在某一条最短路径上,且不在G′G'G′的任意一条边都不在任意一条最短路径上,则将G′G'G′称为点SSS的最短路图。于是我们可以考虑枚举每个点作为起点,跑最短路。...

2018-11-05 16:28:12

BZOJ 2752 [HAOI2012]高速公路(road)【线段树】【概率期望】

显然, 概率期望是一个幌子。设i−>i+1i->i+1i−>i+1的边长为a[i]a[i]a[i],那么对于询问区间[l,r][l,r][l,r],易知答案为(注意边转点对区间的小影响):ans=∑i=lra[i]∗(r+1−i)∗(i+1−l)Cr+2−l2ans=\frac{\sum_{i=l}^ra[i]*(r+1-i)*(i+1-l)}{C_{r+2-...

2018-11-04 21:20:20

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得