Scorpioch

分类

01分数规划(1) dp(4) gcd(2) NOIP膜你赛(1) OIer的刷题记录(25) poj(3) sgu(1) 【神奇的】模板(1) 二分(1) 动态规划 - 数位DP(1) 动态规划 - 概率DP(1) 动态规划 - 背包(2) 字符串 - KMP(1) 搜索(1) 数学(2) 数据结构 - 线段树(4) 数论(2) 未归档(72) 算法(1) 背包问题(1)

/ 注册

全部文章（共109篇）

【CodeForces617E】XOR and Favorite Number

题目链接： http://codeforces.com/problemset/problem/617/E 题解：莫队算法考虑如何进行转移，对于异或运算有一个性质，即 <nobr> a </nobr>^ <nobr> a &l...

2017-08-04

0 394

【POJ2157】Maze

题目链接：http://poj.org/problem?id=2157 题解： BFS爆搜建一个bool1数组表示一个门是否走过，一个bool2数组表示任意一个点是否走过每次走到一个钥匙，该钥匙数+1，如果这个钥匙对应的门曾经到过，而且钥匙数够了，把门放进队列里，没有到过就个普通的点一样...

2017-08-01

0 372

【POJ2828】Buy Tickets

题目链接：https://vjudge.net/problem/POJ-2828 题解：正序不好排，所以我们倒序考虑对于每个人要把它放在第 <nobr> pos[i] </nobr>个人之后，也就是在倒序的时候查找第 <nobr> ...

poj

2017-07-31

0 485

【SGU495】 Kids and Prizes

题目链接：传送门题意：n个盒子里装有礼物，m个人随机选择礼物，选完之后空盒子放回。问选中的礼物数的期望。题解：解法一：一个礼物m次不被选中的概率是 <nobr> (n−1n)m </nobr>，那么不被选的期望就是 <nobr> ...

sgu

2017-07-28

0 510

【POJ3744】Scout YYF I

题目链接：传送门题意：在一条有地雷的路上，你现在的起点在 <nobr> 1 </nobr>处。在 <nobr> N </nobr>个点处布有地雷， <nobr> 1<=N<=10 &...

poj

2017-07-28

0 469

【HDU4405】Aeroplane chess

题目链接：传送门题解：求期望从后往前递推 <nobr> f[i] </nobr>表示从 <nobr> i </nobr>到 <nobr> >=n </nobr>的期望 ...

2017-07-28

0 433

【HDU3853】LOOPS

题目链接：传送门题解：很容易想到用 <nobr> dp[i][j] </nobr>表示从 <nobr> (i,j) </nobr>走到 <nobr> (r,c) </nobr>的...

2017-07-28

0 412

【POJ2096】Collecting Bugs

题目链接：传送门题解：期望DP的第一题（说实话我被吓到了）转一个kuangbin大神的题解吧题意：一个软件有s个子系统，会产生n种bug 某人一天发现一个bug,这个bug属于一个子系统，属于一个分类每个bug属于某个子系统的概率是1/s,属于某种分类的概率是1/n ...

dp poj

2017-07-28

0 601

【洛谷1291】百事世界杯之旅

题意：https://www.luogu.org/problem/show?pid=1291 题解：假设当前已经得到k个名字，得到第k+1个名字的期望为 <nobr> nn−k </nobr> , 所以易得从第一个名字到最后一个名字的平均次数就是 &l...

2017-07-27

0 402

【模板】压位高精度

任何沾染了高精度的题都是恶心的题…… 看到高精度的题就烦呐TAT 干脆存一个高精度的模板好了 #include <cstdio> #include <cstring> #include <algorithm> using namespace std...

2017-07-26

0 991