神奇的K短路(弗洛伊德) 众所周知，我们的q神666，这不，近来q神自己搭了个OJ玩，拉着我来测题。今天AC了q神的第一个题，写个博客记录一下。 打个广告daf_φ(❐_❐✧ 人丑就要多读书 欢迎访问q神OJ 题目： 一天，HighLights实在是闲的不行，他选取了n个地点，n各地点之间共有m条路径，他想找到这m条路径组成的第k短路，你能帮助他嘛？ 输入 第一行三个正整数，地点的数量n（2 <= n <= 2e5），边的数量m（1 <= m <= 2e5），k（1 <= k <= min(m, 200)）。 接下来m行，每行三个整数，边的一个顶点u（1&l...

这题是翻译了八数码问题（POJ — 2893），然后稍加修改。 Description 小D在地下世界探索时，找到了一座藏有无数奇珍异宝的王国，可是进入王国有一扇门，当且仅当你将门上的矩阵变成国王心中的完美矩阵时，大门方可打开。一向不喜欢数字的小D傻眼了，现求助于你，请你帮助他看他是否能进入王国，获得奇珍异宝。 规则如下： 给定一个MN的矩阵（M和N其中必有一个奇数），矩阵上滑贴的编号为1 – (M N – 1)，请你通过移动滑板（滑板在矩阵中用0表示），在不越界的情况下可上下左右移动。请你判断通过变换它是否能变成一个国王心中的顺序矩阵 例：一个3*3的顺序矩阵如下： 1 2 3 4 5 6 ...

金砖问题 一家公司的老板现在又一袋金砖，共n块，现进行分配。其中，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。现假设有一台可以比较重量的仪器，老板希望用最少的比较次数找出其中最重和最轻的金砖。 /* 金砖问题：分治法 */ #include<iostream> #include<algorithm> using namespace std; const int maxn = 1e4 + 5; int SolveMax(int g[], int l, int r){ int lmax, rmax; if(l == r) return g[l]; if(r...

最近点对问题 问题简述： 给你n个点，让你求出最近的两个点的距离。 第一行输入一个整数n，接下来n行，每行两个数，表示点的横纵坐标。 测试样例： 12 -1 3 -2 -2 1 -4 2 1 1 5 3 3 3 0 5 1 7 3 7 6 5 6 3 7 输出结果： 1.41421 Solve方法 暴力法： 理所当然，就是遍历所有的点，求出所有可能的结果，取最小值。 时间复杂度：O(n^2） /* 最近点对问题------暴力法 */ #include<iostream> #include<float.h> #include<math.h> using na...

题目： You are given an array a of length n and array b of length m both consisting of only integers 0 and 1. Consider a matrix c of size n×m formed by following rule: ci,j=ai⋅bj (i.e. ai multiplied by bj). It’s easy to see that c consists of only zeroes and ones too. How many subrectangles of size (ar...

题目： A bracketed sequence is called correct (regular) if by inserting “+” and “1” you can get a well-formed mathematical expression from it. For example, sequences “(())()”, “()” and “(()(()))” are correct, while “)(”, “(()” and “(()))(” are not. The teacher gave Dmitry’s class a very strange task — ...

题目： You are given two integers n and m (m<n). Consider a convex regular polygon of n vertices. Recall that a regular polygon is a polygon that is equiangular (all angles are equal in measure) and equilateral (all sides have the same length).  Your task is to say if it is possible to build another...

题目： You are given an array a1,a2,…,an. Array is good if for each pair of indexes i<j the condition j−aj≠i−ai holds. Can you shuffle this array so that it becomes good? To shuffle an array means to reorder its elements arbitrarily (leaving the initial order is also an option). For example, if a=[1...

题目： Suppose you are performing the following algorithm. There is an array v1,v2,…,vn filled with zeroes at start. The following operation is applied to the array several times — at i-th step (0-indexed) you can: either choose position pos (1≤pos≤n) and increase vpos by ki; or not choose any position...

第二章（物理层） 接受数据链路层发过来的01字符串，主要任务描述为确定与传输媒体的接口的一些特性 机械特性、电气特性、功能特性、规程特性 DTE：数据终端设备 DCE：数据电路端接设备 路由器是（双宿主堡垒主机） 防火墙是一种特殊的路由器，加了安全功能的路由器 IDS/IPS：入侵检测系统和入侵防护系统 DTE：计算机、路由器、防火墙、IDS、IPS DCE：交换机、光猫、中继器、集线器、机顶盒 实验 ：做网线 568B：橙绿蓝棕 ​ 弹片朝地：把所有带白的排到左边 ​ 4和6对换 568A：绿橙蓝棕 通信系统 ​ 一个通信系统包含三部分：源系统（或发射端、发送方）、传输系统（或传输网络）、目...

题目： You are given a positive integer x. Find any such 2 positive integers a and b such that GCD(a,b)+LCM(a,b)=x. As a reminder, GCD(a,b) is the greatest integer that divides both a and b. Similarly, LCM(a,b) is the smallest integer such that both a and b divide it. It’s guaranteed that the solution ...

题目： Ehab has an array a of length n. He has just enough free time to make a new array consisting of n copies of the old array, written back-to-back. What will be the length of the new array’s longest increasing subsequence? A sequence a is a subsequence of an array b if a can be obtained from b by d...

题目： You are given a tree consisting of n nodes. You want to write some labels on the tree’s edges such that the following conditions hold: Every label is an integer between 0 and n−2 inclusive. All the written labels are distinct. The largest value among MEX(u,v) over all pairs of nodes (u,v) is as ...