3.20二面的有出结果了吗？IT岗 #23届找工作求助阵地#

BaiLian4080 Huffman编码树 解题思路 所求即为最短路径之和, 也等于新生成节点频率之和.所以可以使用优先队列每次获取一个最小值和次小值, 所求之和即为新生成节点的频率…再依次获取即可. 这个题还用到了priority_queue.使用如下: Priority_queue:优先队列, 不仅可以存储数据还可以按照某种规则进行排序.每次的push, 和pop操作, 里面数据都会进行动态调整, 把优先级高的放在前面. 使用 : template <class T, class Container = vector, class Compare = less > ...

POJ—3253 Fence Repair Description Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just l...

POJ—Entropy 题目描述 英文 熵编码器是一种数据编码方法，其通过对去除了“浪费”或“额外”信息的消息进行编码来实现无损数据压缩。 考虑文本“AAAAABCD”。使用ASCII，编码需要64位。由于字形“A”以更高的频率出现，可以通过用更少的位编码来做得更好吗？最佳编码是将“A”编码为“0”，将“B”编码为“10”，将“C”编码为“110”，和“D”与“111”。（这显然不是唯一的最佳编码，因为很明显，对于任何给定的编码，B，C和D的编码可以自由地互换，而不会增加最终编码消息的大小。）使用此编码，消息编码为只有13位到“0000010110111”，压缩比为4.9:1（也就是...

UVA12676 Inverting Huffman 题目描述： 静态哈夫曼编码是一种主要用于文本压缩的编码算法。给定一个由 N 个不同字符组成的特定长度的文本，算法选择 N 个编码，每个不同的字符一个编码。使用这些编码压缩文本，当选择编码算法构建一个具有 N 个叶子的二叉树时，对于 N≥2，树的构建如下： 对文本中的每个不同字符，构建一个仅包含单个结点的树，并为其分配权值，权值与文本中该字符出现的次数一致。 构建一个包含上述 N 棵树的集合 s。 当 s 包含多于一棵树时： （a） 选择最小的权值 t1∈s，并将其从 s 中删除； （b） 选择最小的权值 t2∈s，并将其...

UVA240 可变基数霍夫曼编码 题目描述 哈夫曼编码是一种最优编码方法。根据已知源字母表中字符出现的频率，将源字母表中字符编码为目标字母表中字符，最优的意思是编码信息的平均长度最小。在该问题中，你需要将 N 个大写字母（源字母 S 1 …S N ，频率 f 1 …f N ）转换成 R 进制数字（目标字母 T 1 …T R ）。 当 R=2 时，编码过程分几个步骤，每个步骤中，有两个最低频率的源字符 S 1 、 S 2 ，合并成一个新的“组合字母”，频率为 S 1 、 S 2 的频率之和。如果最低频率和次低频率相等，则字母表中最早出现的字母被选中。经过一系列的步骤后，最后只剩两个字母...

UVA11175 有向图D和E From D to E and Back 题目描述 采用任意有n个顶点和m个边的有向图D. 您可以通过以下方式制作D的Lying图E. E将有m个顶点，每个用于表示D的每个边。例如，如果D具有边(u,v)，则E将具有称为uv的顶点。现在，每当D具有边(u,v)和(v,w)时，E将具有从顶点uv到顶点vw的边。 E中没有其他边。您将获得一个图E，并且必须确定E是否可能是某个有向图D的Lying图。 输入 输入的第一行给出案例数N (N < 220)。接下来是N个测试用例。每一个开始两行分别包含m(0≤m≤300)和k。接下来的k行每一行包含一对...

图的存储 一.邻接矩阵 邻接矩阵是表示顶点之间关系的矩阵。邻接矩阵存储方法，需要用一个一维数组存储图中顶点的信息，用一个二维数组存储图中顶点之间的邻接关系，存储顶点之间邻接关系的二维数组称为邻接矩阵。 1.1邻接矩阵的表示方法 （1）无向图的邻接矩阵在无向图中，如果vi到vj有边，则邻接矩阵M[i][j]=M [j][i]=1，否则M [i][j]=0。 无向图邻接矩阵的特点如下。 1）无向图的邻接矩阵是对称矩阵，并且是唯一的。 2）第i行或第i列非零元素的个数正好是第i个顶点的度。 （2）有向图的邻接矩阵有向图中，如果vi到vj有边，则邻接矩阵M[i][j]=1...

bitset用法 介绍 bitset大概就是类似于bool数组一样的东西. 但是它的每个位置只占1bit（特别特别小） bitset的原理大概是将很多数压成一个，从而节省空间和时间（暴力出奇迹）一般来说bitset会让你的算法复杂度 /32（具体是什么要看计算机） 定义与初始化 使用bitset类型需#include bitset类型在定义时就需要指定所占的空间，例如 bitset<233>bit; bitset类型可以用string和整数初始化（整数转化成对应的二进制） #include<iostream> #include<bitset...

P2881 [USACO07MAR]Ranking the Cows G 题目描述 FJ想按照奶牛产奶的能力给她们排序。现在已知有N头奶牛（1 ≤ N ≤ 1,000）。FJ通过比较，已经知道了M（1 ≤ M ≤ 10,000）对相对关系。每一对关系表示为“X Y”，意指X的产奶能力强于Y。现在FJ想要知道，他至少还要调查多少对关系才能完成整个排序。 输入格式 Line 1: Two space-separated integers: N and M Lines 2…M+1: Two space-separated integers, respectively: X and Y...

图的遍历 介绍 是从图的某一顶点出发，按照某种搜索方式对图中所有顶点访问一次且仅一次。图的遍历可以解决很多搜索问题，在实际中应用非常广泛。图的遍历根据搜索方式的不同，分为广度优先搜索和深度优先搜索。 一.深度优先遍历 1.1介绍 深度优先搜索（Depth First Search, DFS）是最常见的图搜索方法之一。深度优先搜索沿着一条路径一直走下去，无法行进时，回退到刚刚访问的节点，似“不撞南墙不回头，不到黄河不死心”。深度优先遍历是按照深度优先搜索的方式对图进行遍历。 深度优先遍历秘籍：后被访问的顶点，其邻接点先被访问。 根据深度优先遍历秘籍，后来先服务，可以借助于栈实现。...

POJ3278—Catch That Cow 题目描述 农夫约翰已被告知逃亡牛的位置，并希望立即抓住她。他开始于一个点N（0≤ N≤100,000）和牛是在点K （0≤ K≤100,000），他们在同一条线上。农夫约翰有两种交通方式：步行和乘车。 行走：约翰可以在一分钟内从任意点X移动到X -1或X + 1 点 乘车：约翰可以在一分钟内从任意点X移动到点2× X . 如果母牛不知道它的追赶，根本不动，那么农夫约翰需要多长时间才能找回它？ 输入 第1行：两个以空格分隔的整数：N和K 输出 第1行：农夫约翰用最少的时间（以分钟为单位）捉住逃犯。 输入样例 5 17 ...

POJ2488 骑士的旅程 题目描述 骑士一次又一次地看到相同的黑白方块而感到厌倦，并决定环游世界。每当骑士移动时，它是一个方向上的两个正方形和一个垂直于此的正方形。骑士的世界是他生活的棋盘。我们的骑士生活在棋盘上，棋盘面积比普通的8 * 8棋盘小，但它仍然是长方形的。你能帮助这个冒险骑士做出旅行计划吗 输入 找到一条路径，使骑士可以拜访每个广场一次。骑士可以在棋盘的任何正方形上开始和结束。 输出 输入在第一行中以正整数n开头。以下各行包含n个测试用例。每个测试用例由一行包含两个正整数p和q的行组成，因此1 <= p * q <=26。这表示 p * q棋盘，其...

UVA572油藏 Oil Deposits 题目描述 某石油勘探公司正在按计划勘探地下油田资源，工作在一片长方形的地域中。他们首先将该地域划分为许多小正方形区域，然后使用探测设备分别探测每一块小正方形区域内是否有油。 含有油的地块称为油田。如果两个油田相邻，则它们是相同油藏的一部分。油藏可能非常大并且可能包含许多油田。您的工作是确定长方形的地域中包含多少不同的油藏。 输入 文件包含一个或多个网格。每个网格以包含m和n的行开始，n是数字 网格中的行和列，用一个空格隔开。如果m = 0，表示输入结束; 否则，1≤m≤100,1≤n≤100。接下来是m行，每行n个字符(不包括在内) 行...