2 Dunyb

尚未进行身份认证

我要认证

坚毅

等级
TA的排名 2w+

单符号位的溢出和修正(计算机组成原理)

#include<bits/stdc++.h>using namespace std;/*单符号位的修正算法 思路: 1)不溢出就不修正 2)溢出就修正 判断溢出原理:数值最高位和符号最高位是否进位 a)都进位,不溢出 b)只有其中一个进位,则溢出 根据溢出来修正 1) 只有符号位溢出, 则是两个负数相加 溢出了 答案 -2^n 2)只有最高数值位溢出, 则是两个正数相加溢出了 答案+ 上2 ^ n 本次使用4位机器码 表示范围 .

2020-06-05 09:51:08

双符号位补码(用于修正单符号位补码+法溢出)

代码:/* 用两个符号位进行修正 正数符号位为 00 , 负数符号位为 11 当两位符号位 为 01, 10时就是溢出,这时取最高位为符号位,其他位为数值位 */ #include<bits/stdc++.h>using namespace std;int binary_x[6];int binary_y[6]; void BaseConversion(int n, int b, int base[]) { //10进制转换为2进制并求补码 if(n != -...

2020-05-31 14:19:04

D 景区路线规划 (期望 DP 牛客算法周周练1)

题目连接 期望DP 题意 : n个点, m条边,每个点代表一个景点, 第i个景点游览需要耗费ci分钟,会让男性游客和女性游客的满意度分别增加h1i和h2i(满意度初始值都为0 ) 每条边表示从 x-y , y-x需要消耗的时间ti 每个游客在景区中最长可以游览k分钟 ...

2020-05-04 21:20:56

身体训练 (牛客算法周周练1)期望

题目连接 题意: 求数学期望: n个人 两两相聚 u米, 每个人正常速度为v m/s 当某个配送员排在最后的时候, 他需要以当时自己的最高速度往前跑. 直到超过排头的人 u 米, 然后降回到初始速度, 每人最初的最高速度为c[i] m/s 每轮衰减d[i] m /s n个人初始以随机的顺...

2020-05-04 15:48:13

Borrow Classroom (LCA 倍增 )

题目连接 题意: 一个N 个节点的树 N-1条边, 1号节点是根节点,Q次询问,每次询问3个整数 A B C 3个人(3个整数代表3个人所处的位置), 要求A 在文件交到根节点前进行拦截 如果A C同时到1则算失败 数据范围 3s 最多5组样例 n q &...

2020-05-03 18:21:36

HDU-2586 (LCA Tarjan & 倍增)

题目连接题意: 求一棵树上任意两点的最短距离,n个点,m次询问数据范围: 2 < n < 40000, 2 < m < 200思路:(Tarjan) LCA板子题,需要一个dis [] 数组, dis[ x ] 记录一下该点 ( x) 到父亲节点 ( find(x)) 的距离,当找到一个匹配...

2020-05-03 15:17:22

洛谷 P3379 (LCA Tarjan && 倍增)

题目连接题意: N 个点 ,N - 1条边,M 个询问每个寻问两个整数X, Y。 求 X, Y 的LCA (最近公共祖先), S点是根节点思路: LCA模板题LCA Tarjan AC :#include<iostream>#include<math.h>#include<stdio.h&g...

2020-05-03 11:33:21

LCA (最近公共祖先) Tarjan & 倍增

LCA Tarjan:实现原理理解:离线算法,建好树后再查询,一次DFS 吧所有查询解决完。时间复杂度:O(n+q);n个点 q次询问代码/*LCA算法(最近公共祖先算法) Tarjan算法 */#include<iostream>#include<cstring>#include<math.h>#include<...

2020-05-01 09:40:57

Tarjan(总结)

1)求强联通分量 Tarjan求强联通分量2)缩点 Tarjan缩点3)求割点和桥 割点和桥的模板4)求双连通分量 待补...

2020-05-01 09:27:58

Tarjan (桥和割点模板)

补习Tarjan割点 定义:若从图中删除节点 x 以及所有与 x 关联的边之后,图将被分成两个或两个以上的不相连的子图,那么称 x 为图的割点。 如何求割点:在深搜树中,如果对于某个点u,与它相连的点v(v不是u的父亲)。 那么如果low[v]>=dfn[u], 那么也就是以v为根的深搜子树中的点所连接的点没有已...

2020-04-28 22:54:40

POJ1144 Network(Tarjan求割点)

题目连接题意: 让求一个图中的关键节点(割点),输入稍微有点麻烦,不给你一个点有几个边,直接输入边,读到换行才结束。思路: 1)Tarjan求一下改图割点的数量。 2)注意输入读到换行才停止,用getchar()。点击补习读入方式AC代码/*Tarjan 割点 //如果这个点时根节点,并且儿子>=2则这个点就是割点...

2020-04-28 22:37:41

UVA - 796 Critical Links (Tarjan 求图中的桥)

题目连接题意: 1)给你一个图,然后让你求图中桥的个数 2)要求按字典序输出 3)并且要求第一个点的值小于第二个点的值思路: 1)Tarjan求桥 2)要求按字典序输出,所以可以用set+ pair 来储存 3)在插入set时比较一下大小再插入。AC :#include&...

2020-04-27 16:29:36

Tarjan 缩点模板 (将有向有环图缩点成为有向无环图DAG)

缩点的作用 1)缩点的实际作用:把一个有向带环图,变成一个有向无环图(DAG) ,这样基于DAG的算法就能跑了。 2)可以算缩点后个点的出度基本思想 一我们既然能在有向图中找到环,那么我们就可以吧环给缩成点了(利用Tarjan缩点),缩点基于一种染色实现,在DFS搜索的过程中,尝试吧属于同一个强连通分量的点都染成一个颜色,同一颜色的点就相当...

2020-04-20 22:58:37

Tarjan(强连通模板)

强连通分量: 1)有向图中,该图中的任意两点之间可互达。 2)一个一个点也是强连通分量两个概念:1)时间戳 dfn[ x ]​ 时间戳是用来标记图中每个节点在进行深度优先搜索时被访问的时间顺序,当然,你可以理解成一个序号(这个序号由小到 大),用 dfn[x] 来表示(搜到该点的最早时间)2)low数组 2)low...

2020-04-20 21:14:15

POJ-2553 The Bottom of a Graph (Tarjan强联通+缩点)

题目连接题意: 一个有向图,然后让你求这个图的底部(求出所有没有出度的强联通分量),如果没有底部输出空行,升序输出数据范围:n < 5000思路: Tarjan缩点后,判断某个点是否有出度,找到出度为0的点,把这个点(缩点后的点,缩点前是强联分量),把这个点内的所有点升序输出AC代码:/* Tarjan 缩点 我们既然能在有向图中找到环,那么我...

2020-04-12 23:00:40

HDU-1269(Tarjan模板-求强连通分量)

题目连接题意: 求一个有向图n个点 m 条边,是否是强连通分量,如果是输出Yes, 不是输出No.数据范围 n < 10000, m < 100000思路: Tarjan模板题补习:AC code:/* Tarjan求有向图的强连通分量, */ #include<iostream>#...

2020-04-11 10:50:09

链式向前星

一种数据结构存图方式理论知识:点击此处通用代码:存图 :const int MAXN = ;int head[MAXN], cnt = 1;bool vis[MAXN];struct Edge{ //根据需要+变量 int to, dis, next;}edge[MAXN << ];void add_edge(int u, int v, int di...

2020-04-09 14:07:25

八皇后问题

递归的入门题:写一下主要是回想一下 回溯和非回溯。非回溯,就把所有情况搜出来,把不满足规定的情况扔掉。回溯,如果递递归再到达边界之前。由于一些事实已经不需要往任何一个子问题递归,就可以直接返回上一层(或者不用再向下搜),这种方法就叫回溯。#include<iostream>#include<stdio.h>#include<math.h>...

2020-03-26 13:55:01

HDU-1007 Quoit Design(分治求平面内最近两点间距离)

题目连接题意: 找到平面内,最近两个点间距离, 最后答案除以2数据范围: N (2 <= N <= 100,000) N 个点,思路: 如果暴力解法O()必然是 所以应该有 O()算法。 O()树,分治,等等,这题应该用分治算法。 1)既然用分治,就应该吧问题分成几份,先分两份...

2020-03-26 10:12:43

One fihgt one HDU-2813 (最小权匹配)

题目链接题意:吕布的士兵和曹操对打,选取合适的对阵使吕布军队受伤最小思路:存负边,跑KM()我用scanf Timi 了 2页,然后用 cin 关了输入输出流 A了 Debug一下午 真坑AC代码:#include<iostream>#include<cstring>#include<stdio.h>#include&lt...

2019-07-25 17:17:41

查看更多

勋章 我的勋章
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。