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

题目地址

描述

平面上有$m$条有向线段连接了$n$个点。你从某一个点出发顺着有向线段行走,给沿途经过的每条线段涂一种不同的颜色,最后回到起点。你可以多次行走,给多个回路涂色。可以重复经过一个点,但是不能重复经过一条有向线段。
如图所示是一种涂色方法(虚线表示未涂色)。

Read More

Compartir

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

题目地址

描述

给出$V$个点$E$条边($1\leq V\leq 100$, $1\leq E\leq 500$)的混合图(即有的边是有向边描述为$D$,有的边是无向边描述为$U$),试求出它的一条欧拉回路,如果没有输出无解信息。

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

Read More

Compartir

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}$。

Read More

Compartir

同余与模运算

好啦,要开始学习模运算啦,只是紫书上一点微小的部分,还是先膜一下为敬0w0。。。
无关紧要的话:我觉得作为一个合格的Oler应该对于每一个基础的知识点都有一个符合自己代码风格和习惯的模板,最好是能深刻理解这个算法之后写的模板,这样我们才不会在考场上出现低级的错误哒!比如有的人取区间喜欢左闭右开,有人喜欢让左右都是闭区间;有的人循环喜欢从1开始,有人喜欢从0开始;当然,各有各的好处,只是要做到在考场上部分因为低级错误而丢分甚至于调试很长的时间就可以啦。

定义

如果存在 $a\pmod n\equiv b\pmod n$,即a,b除以m所得的余数相等,那么我们记作$a\equiv \ b \pmod n$。

基本性质

和其他的运算一样,模运算也有自己的运算法则。
如果存在$a\equiv \ b\pmod n$,且有$c\equiv \ d pmod n$,那么下面的运算率成立。
$a + c\equiv \ b + d \pmod n$
$a - c\equiv \ b - d \pmod n$
$a \times c\equiv \ b \times d \pmod n$
我们经常利用这三个性质对输出答案较大的程序取模,一般是模完再加,加减乘均满足的这个性质,不过除法是不满足的。

Read More

Compartir

埃及分数问题

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

定义

迭代加深搜索通常是从小到大枚举不超过$Maxd$或是不小于$Mind$的结点,每次执行的时候只考虑在结点深度不超过$Maxd$或是不小于$Mind$的结点。这样只要解的深度有限那么有限时间内就可有搜索完。
简而言之,就是对深度优先搜索进行了一定改进,对搜索树的深度进行控制,即有界深度优先搜索。

Read More

Compartir

最优配对问题

第一次学状态压缩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$。

Read More

Compartir

Uva 816 - Abbott's Revenge

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

题目地址

描述

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

Read More

Compartir

UVa 10976 - Fractions Again?!

题目描述

描述

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

Read More

Compartir

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$时,会先描述左子天平,然后是右子天平。

Read More

Compartir

路径寻找问题及哈希表

这一篇Blog着重写的应该是Hash吧,路径寻找问题在应用中会稍微提到一点。

定义

  • 若关键字为k,则其值存放在f(k) 的存储位置上。由此,不需比较便可直接取得所查记录。称这个对应关系 f为散列函数,按这个思想建立的表为散列表
  • 对不同的关键字可能得到同一散列地址,即k1 ≠ k2 ,而 f(k1) = f(k2),这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述,根据散列函数 f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置,这种表便称为散列表,这一映射过程称为散列造表或散列,所得的存储位置称散列地址
  • 若对于关键字集合中的任一个关键字,经散列函数映象到地址集合中任何一个地址的概率是相等的,则称此类散列函数为均匀散列函数,这就是使关键字经过散列函数得到一个“随机的地址”,从而减少冲突。

Read More

Compartir