UVa 11729 - Commando War

题目地址

描述

你有$n$个部下,每个部下需要完成一项任务。第$i$个部下需要你花$B_{i}$分钟交待任务,然后他会立刻独立地、无间断

地执行$J_{i}$分钟任务。你徐亚选择交待任务的顺序,使得所有任务尽早执行完毕(即最后一个执行完的任务应尽早

结束)。注意,不能同时给两个部下交待任务,但是部下可以同时执行他们各自的任务。

每组数据第一行$N(1\leq N\leq 1000)$为部下的人数。以下$N$行每一行有两个正整数$B$和$J$$(1\leq B,J\leq 10000)$,即

交待任务的时间和完成任务的时间。输入结束标志为$N = 0$。

输出完成任务所需的最短的时间。

자세히 보기

Partager

UVa 1659 - Help Little Laura(最小费用循环流)

题目地址

描述

平面上有$m$条有向线段连接了$n$个点。你从某一个点出发顺着有向线段行走,给沿途经过的每条线段涂一种不同的

颜色,最后回到起点。你可以多次行走,给多个回路涂色。可以重复经过一个点,但是不能重复经过一条有向线

段。

如图所示是一种涂色方法(虚线表示未涂色)。

자세히 보기

Partager

UVa 10735 - Euler Circuit(混合图的欧拉回路)

题目地址

描述

给出$V$个点$E$条边($1\leq V\leq 100$, $1\leq E\leq 500$)的混合图(即有的边是有向边描述为$D$,有的边是无向边描述为$U$

),试求出它的一条欧拉回路,如果没有输出无解信息。

连通的无向图$G$存在欧拉回的充要条件是:$G$中每个顶点的度都是偶数。

자세히 보기

Partager

UVa 1639 - Candy

题目地址

描述

有两个盒子各有$n(n \leq 2 \times 10^{5})$个糖,每天随机选一个盒子并打开它(概率分别为$p$,$1 - p$),如果里面有糖,

他会吃掉其中一个;否则他会打开另一个盒子,然后吃一颗糖。他已经每天吃一颗糖吃了几天了,有一天,他打开

盒子一看,没糖啦(;´д`)ゞ!打开另一个盒子之前,他希望你帮他算一下另一个盒子里剩余糖的个数的数学

期望。

有多组测试数据,对每一组测试数据包含每一个盒子中糖的个数$n(n \leq 2 \times 10^{5})$以及实数

$p(0\leq p\leq 1,小数点后6位)$,以$EOF$终止。

对于每组测试数据,以$”Case X:Y”$形式输出,其中$X$是测试数据的编号(从$1$开始),$Y$是另一个盒子里剩余糖的

个数的数学期望,任何答案绝对误差必须$\leq 10^{-4}$。

자세히 보기

Partager

同余与模运算

好啦,要开始学习模运算啦,只是紫书上一点微小的部分,还是先膜一下为敬0w0。。。

无关紧要的话:我觉得作为一个合格的Oler应该对于每一个基础的知识点都有一个符合自己代码风格和习惯的模

板,最好是能深刻理解这个算法之后写的模板,这样我们才不会在考场上出现低级的错误!比如有的人取区间喜

欢左闭右开,有人喜欢让左右都是闭区间;有的人循环喜欢从1开始,有人喜欢从0开始;当然,各有各的好处,

只是要做到在考场上部分因为低级错误而丢分甚至于调试很长的时间就可以啦。

자세히 보기

Partager

埃及分数问题

这篇Blog意在通过埃及分数问题学习和理解迭代加深搜索。

定义

​迭代加深搜索通常是从小到大枚举不超过 Maxd 或是不小于 Mind 的结点,每次执行的时候只考虑在结点深度不超

过 Maxd 或是不小于 Mind 的结点。这样只要解的深度有限那么有限时间内就可有搜索完。

简而言之,就是对深度优先搜索进行了一定改进,对搜索树的深度进行控制,即有界深度优先搜索。

자세히 보기

Partager

最优配对问题

第一次学状态压缩DP,在学长的指导下(雾)终于弄明白了。现在就要用算法竞赛入门经典上的一道题来了解状

压DP吧,希望这次学过状压DP之后可以不看题解自己做出NOIP Day2T3。感觉自己学新的知识学得好慢。

最优配对问题

空间里有 n 个点 $P_{0}, P_{1}, P_{2},···,P_{n - 1}$,你的任务是把它们配成 $\frac{n}{2}$ 对(n 是偶数),使得每一个点恰好在一个点对

中。所有点对中两点的距离之和应尽量小。$n \leq 20 ,\ |x_{i}|, |y_{i}|, |z_{i}| \leq 10000$。

자세히 보기

Partager

Uva 816 - Abbott's Revenge

表示蒟蒻搜索弱爆了,还是做题太少了。

题目地址

描述

有一个最多包含$9\times 9$个交叉点的迷宫。输入起点, 离开起点时的朝向和终点,求一条最短路(多解时任意输出一个即可)。

자세히 보기

Partager

UVa 10976 - Fractions Again?!

题目描述

描述

输入正整数K,找出所有得正整数 $x\geq y$,使得$\frac{1}{k}=\frac{1}{x}+\frac{1}{y}$。

자세히 보기

Partager

UVa 839 - Not so Mobile

题目地址

描述

输入一个树状天平,根据力矩相等原则判断是否平衡($W_{l}\cdot D_{l} = W_{r}\cdot D_{r}$)。采用先序(递归)方式输入:每一

个天平的格式为$W_{l},D_{l},W_{r},D_{r}$,当$W_{l}$ 或 $W_{r}$为$0$时,表示该砝码实际上是一个子天平,接下来会描述这个子天

平。当$W_{l} = W_{r} = 0$时,会先描述左子天平,然后是右子天平。

자세히 보기

Partager