夏荷浅梦

分类

未归档(117) 读书笔记(1) 题解(6)

/ 注册

全部文章（共124篇）

SP1026 FAVDICE - Favorite Dice

题目描述一个\(n(n \leq 1000)\)面的骰子，求期望掷几次能使得每一面都被掷到。输入输出样例输入样例#1： 2 1 12 输出样例#1： 1.00 37.24 思路：期望\(dp\)中典型的赠券收集问题，用f[i]表示还剩i个面没有掷到，那么掷到之前没有掷到过的面的概...

期望期望DP DP SPOJ

2019-05-03

0 540

UVA12230 过河 Crossing Rivers

题目描述一个人每天需要从家去往公司,然后家与公司的道路是条直线,长度为 \(D\)。同时路上有 \(N\)条河,给出起点和宽度\(W_i\) , 过河需要乘坐速度为\(V_i\) 的渡船; 船在河中的位置随机,固定往返时间. 且该人在陆地上行走速度为 \(1\) .求该人去公司的路途的期望时间...

UVA 期望

2019-05-03

0 467

洛谷 P1052 过河

题目描述在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：\(0,1,…,L\)（其中\(L\)是桥的长度）。坐标为\(0\)的点表示桥的起...

DP 洛谷

2019-05-03

0 779

洛谷 P1896 [SCOI2005]互不侵犯

题目描述在\(N×N\)的棋盘里面放\(K\)个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共\(8\)个格子。注：数据有加强\(（2018/4/25）\) 输入输出格式输入格式：只有一行，包含两个数\(N，K ...

洛谷 DP 状压DP

2019-05-03

0 729

洛谷 P1879 [USACO06NOV]玉米田Corn Fields

题目描述农场主\(John\)新买了一块长方形的新牧场，这块牧场被划分成\(M\)行\(N\)列\((1 ≤ M ≤ 12; 1 ≤ N ≤ 12)\)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。遗憾的是，有些土地相当贫瘠，不能用来种草。并且，...

DP 状压DP 洛谷

2019-05-03

0 552

洛谷 P1231 教辅的组成

题目背景滚粗了的\(HansBug\)在收拾旧语文书，然而他发现了什么奇妙的东西。题目描述蒟蒻\(HansBug\)在一本语文书里面发现了一本答案，然而他却明明记得这书应该还包含一份练习题。然而出现在他眼前的书多得数不胜数，其中有书，有答案，有练习册。已知一个完整的书册均应该包含且仅包含...

最大流洛谷网络流

2019-05-03

0 514

洛谷 P4016 负载平衡问题

题目描述 \(G\) 公司有 \(n\) 个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使 \(n\) 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。输入输出格式输入格式：文件的第 \(1\) 行中有 \(1\) 个正整数 \(n\)，表示...

费用流网络流洛谷

2019-05-03

0 557

洛谷 P3381 【模板】最小费用最大流

题目描述如题，给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。输入输出格式输入格式：第一行包含四个正整数\(N、M、S、T\)，分别表示点的个数、有向边的个数、源点序号、汇点序号。接下来\(M\)行每行包含四个正整...

费用流网络流洛谷

2019-05-03

0 451

洛谷 P3931 SAC E#1 - 一道难题 Tree

题目背景冴月麟和魏潇承是好朋友。题目描述冴月麟为了守护幻想乡，而制造了幻想乡的倒影，将真实的幻想乡封印了。任何人都无法进入真实的幻想乡了，但是她给前来救她的魏潇承留了一个线索。她设置了一棵树（有根）。树的每一条边上具有割掉该边的代价。魏潇承需要计算出割开这棵树的最小代价，这就是冴...

最小割洛谷网络流

2019-05-03

0 533

洛谷 P1343 地震逃生

题目描述汶川地震发生时，四川**中学正在上课，一看地震发生，老师们立刻带领x名学生逃跑，整个学校可以抽象地看成一个有向图，图中有\(n\)个点，\(m\)条边。\(1\)号点为教室，\(n\)号点为安全地带，每条边都只能容纳一定量的学生，超过楼就要倒塌，由于人数太多，校长决定让同学们分成几批逃生...

最大流洛谷网络流

2019-05-03

0 499