- 博客(39)
- 收藏
- 关注
RSS订阅原创 计算机中的原码，反码和补码问题
**计算机中的原码，反码和补码问题** 此文章参考[](https://blog.csdn.net/zl10086111/article/details/80907428/)1、原码纠正一点我长期以来的错误认知。八位二进制数的范围为[-127,127]，原因是最高位是符号位（0为）并不参与计算[1111 1111 , 0111 1111]2、反码正数的反码是其本身，例如：01010111的反...
2021-09-26 15:37:46
2043
1
原创 算法笔记上机指南———动规
最大连续子序列数据num（N）令d(i)表示num(i)最为末尾的连续序列的最大和。转移方程d(i)=max(d(i-1)+num(i),num(i))有一点需要注意，递归数组的最后未必是以num(N)最大最大核心代码 dp[0] = num[0]; for (int i = 1; i <N; i++) { if (dp[i - 1] + num[i] > num[i]) { dp[i] = dp[i - 1] + num[i]; //indx[i] = in
2020-07-01 18:43:14
225
原创 组合数计算及其求模
- 前言关于n!的一个小问题 -如何求n!有多个p；最直接的int cal(int n, int p) //计算n!有多少个p{ int ans = 0; for (int i = 2; i <= n; i++) { int temp = i; while (temp%p == 0) ans++, temp /= p; } return ans;}当n>...
2019-10-04 15:58:24
259
原创 训练指南-数论-课后入门习题
- 最小公约数和最大公倍数#include<iostream>#include<algorithm>#include<string.h>#include<cmath>using namespace std;long long G, L;int main() { int t; cin >> t; while (t--...
2019-10-04 10:38:55
314
原创 数字和与倍数 UVA 11361
这一道题目弄了两天，终于对数位dp有了新的理解.参考了一个大佬的代码大佬的博客题目大意:给定，,a,b,k.找出所有满足在a<=x<=b条件的整数，要求能被k整除,数位之和也能被k整除。分析递推题目的第一步大致相同，设f(x)表示不超过x的非负整数中满足条件的个数。那么我们所求答案便是f(b)-f(a-1);问题的关键就在于如何计算f函数.假设我们需要计算f(12345)就是...
2019-10-01 15:22:01
253
1
原创 蓝桥月赛
第一题dp一下就出来了设状态d[dist]表示行驶dist公里最小的花费;状态转移方程为d[dist]=min{d[dist-i]+cost[i]| 0<=i<dist}#include<iostream>#include<algorithm>#include<string.h>#define maxn 100+1#define I...
2019-09-29 19:41:48
230
原创 求逆元的两种方法
引论解释一下什么是逆元（此处指的是乘法逆元)，如果有三个数a,b,m(m>1)；有a*b=1(mod n),我们就说a与b互为模m的逆元，我们可以记住a=1/b(mod n)或者b=1/a(mod n)。通俗的说，如果两个整数的乘积模m后1，就称它们互为m的逆元。、为什么要求逆元?一般的我们对于ab(mod n)=((a mod n)(b mod n)) mod n,但是换到除法就...
2019-09-27 11:25:56
1085
原创 刘汝佳-数论-模方程
线性模方程。类似与x%m1=a1x%m2=a2x%m3=a3………………x%mn-1=an-1x%mn=a；求x的最小整数解强推这个博客大神我们引入中国剩余定理，首先我们将 所有的m相乘得出M=\prod_{i=1}^{n}|\...
2019-09-27 10:46:15
316
原创 LA3621 快速幂运算
题目大意给定正整数n和x，问最少需要几次乘除法可以得到x的n次方，每次可以乘上之前乘过的数分析运用迭代深搜，迭代深搜适用于那些所求值不大的情况给定的样例答案不大时应当考虑上代码/*理解错误:这个题目应该用广搜或者迭代深搜; 对于每一步来说，操作的步骤只有加+1或-1； 不是很懂;*/#include<iostream>#include<cstdio>...
2019-09-24 21:33:07
169
原创 刘汝佳-训练指南-数论-基本概念
素数 因子只有1和本身；#define maxn 100000int vis[maxn], prime[maxn];//vis为1-合数，vis为0-素数1int n;void seize(int n) { //筛掉素数 int m = sqrt(n) + 0.5; memset(vis, 0, sizeof(vis)); for (int i = 2; i <=...
2019-09-24 21:32:25
204
原创 LA 3716 突变区域
题目大意给定两条长度为n的DNA链A和B，你的任务找出突变率不小于p%的最长序列分析A和B可以进行比较，相同为0不同则为1，这样问题就转化为求一段0-1串，一开始还以为时数形结合问题，但是后来想想觉得单调队列无法维护。后来就是公式推演，进行排序，枚举求最大段。//*////*//题目大意;从两个字符串中找出不一样的一段连续字串，一一对应,字串要求，不一样的gailv//不应该超过一个值...
2019-09-22 20:13:09
166
原创 LA 3667 刻度尺
题目大意给定n和刻度d，设计一个拥有m个刻度的尺子，使得每个d都可以直接的量出来，要求在m尽量小的情况下保证尺子的总长度尽量短.分析此题目应该采用迭代深搜#include<iostream>#include<algorithm>#include<string.h>#include<queue>#define maxd 1000000+...
2019-09-22 20:04:59
217
原创 LA 4253 箭术
题目大意在一个平面上有n条线段，高度代表着y轴坐标 ，在x轴上找一个区间（0,M)使得能够在这个区间内放出一条射线能够击中所有的线段;分析二分+判断 重点时判断如何判断，因为是一条射线我们需要寻找到一个角度能够穿过所有的线段将线段按照高度进行排序，一一遍历，区间逐渐收拢，直到出现不可能的区间点（r<l)表示错误代码如下#include<iostream>#in...
2019-09-22 17:46:25
128
原创 UVA 10391复合词
题目大意 给定一个词典，要求找出所有的复合词，即恰好有两个单词连接而成的单词分析第一种方法 使用集合查看当前单词的分解手否存在#include<iostream>#include<algorithm>#include<set>#include<string>#include<string.h>#include<m...
2019-09-22 17:26:28
233
原创 restaurant LA 4851
题目大意有M*M网格,左下角(0,0),右上角(M-1,M-1).上面有n个餐厅,其中编号为1和2的分别是AB两宾馆的餐厅.对于一个位置,若存在与之前已有的任意餐厅位置相比,更靠近A或者B,就定义为”好位置”.问”好位置”的个数.(其中,两点间的距离为曼哈顿距离,即横纵坐标差的绝对值之和)分析主要是采用扫描线方法,在这里其实有一点不是很懂，为什么A和B的正上下不是好位置,不解```#inc...
2019-09-22 16:43:18
139
原创 LA 4726 平均值
题目大意给定一个长度为n的01序列选择一个长度至少为L的连续子序列，使得子序列中数值之和的平均值最小，选择尽量小尽量少的序列。分析这是一个好题 ，难点就在于单调队列的维护，删除上凸点，保留下凹点。原理见 周源大佬的数形结合上代码#include<iostream>#include<algorithm>#include<string.h>#d...
2019-09-22 16:38:19
218
转载 火势控制系统 LA 4356
题目大意平面上有n个目标点，你的任务是找出一个圆心在(0,0)点处的扇形2，至少覆盖K个点，，试求出最小的面积分析首先对这n个目标点求出至原点的距离以及角度，然后对这n个点进行排序后，依次使用每一种距离进行扫描，注意开而被数组 ，这个题目wrong了 几十次，就是因为对n和k的判定出了问题代码是参考大佬的转自大神代码子集有稍微修改了一下#include<iostream&g...
2019-09-22 16:32:24
174
原创 LA 2965侏罗纪
题目大意有n个大写字母组成的字符串选择尽量多的串使得每个大写字母能能够出现偶数次。n<20分析在一个字符串中每个字母出现的次数无关紧要重要的是字母出现的奇偶性，我们正好可以用二进制表示每个字符串的奇偶性奇数对应1 偶数对应0刘大神的代码一些地方不是特别懂，中途相遇法#include<iostream>#include<algorithm>#include...
2019-09-22 16:15:33
240
原创 UVA 10755废料堆 garbage Heap
题目大意有一个长方体形状的废料堆，由(A*B)*C个废料块组成，每一个废料块都有一个价值，现在想在其中找一个最大价值的长方体块分析首先，想一个正确但是低效的方法，枚举x,y,z的上下界坐标然后比较着这么多的长方体的价值和，而且每个长方体还需要n的三次方的时间累加价值和，显然太大；解决高维问题的常用方法就是降维，如果是一个二维情况，给定一个数字矩阵求最大的连续子矩阵，首先就是使用"前缀和"的...
2019-09-22 15:59:19
151
原创 LA 3695遥远的银河
题目大意给定平面上的n个点，找一个矩形，使得边界上包含尽量多的点。分析不难发现除非所有的点都在同一条直线上，否则矩阵的四条边至少会有一个点（一个角上的点同时算在两条边上）.这样，我们枚举4条边界所穿过的点，然后统计点数，这样做的复杂符很高，数据量无法承受。和子序列一样我们考虑部分枚举，只枚举矩形的上下界。用其他方法定义左右边界。当一个矩形的上下边界确定后，我们来计算左右边界点。我们定义l...
2019-09-22 12:49:16
209
原创 LA 3029 最大子矩阵 city game
题目大意给定一个m*n的矩阵，其中一些池子是空地，其他事障碍，求出最大的空地面积并将结果乘以三。分析最常用的方法暴力枚举，枚举矩形的两个顶角坐标。，然后判断求面积，复杂度十分大，对于本题目的数据显然通过不了，我们采用扫描发法，把每个格子向上的连续空格看作一个悬线，并且用up(i,j),left(i,j),right(i,j分别表示可以向上的悬线长度，向左向右的最大边界，注意边界保留的是空地的...
2019-09-22 12:19:49
160
原创 LA 2678 subsequece 子序列
题目大意给定有n个正整数构成的序列和整数S，求长度最短的连续序列，使他们的和等于S分析首先想到的方法就是暴力枚举,，枚举起点和终点for (int i = 0; i < n; i++) for (int j = i; j < n; j++) { int sum = 0; for (int k = i; k <= j; k++) sum =...
2019-09-22 11:27:15
256
原创 LA3905 meteor流星
题目大意给定一个矩形照相机，还有哪个流星的起始位置和速度，求能可以照到最多流星的时刻。在边框上的不计入总数。分析不难发现流星的轨迹没有任何意义，有意义的只是流星在照相机内部出现的时间段，我们可以把每一个流星经过的时间转化为一个区间，这样的话问题就转化位在最多区间覆盖的点。即，求求出一个数t，使得包含的区间数最多。我们把"扫描线碰上一个左端点"和“扫描线遇到一个右端点作为”作为一个事件，扫...
2019-09-22 10:55:22
148
原创 UVA 11549 calcular conundrum 计算机老谜题
题目大意用一个老式计算器，只显示n位数字，输入一个整数k后计算，计算器会反复平方，直至溢出，每次溢出只显示最高的n位，计算器会一直平方下去，直到出现重复的数字分析题目中已经暗示了计算器显示的数会出现循环，不妨一个一个的模拟，直至出现重复的数字，我们使用集合把出现过的数字进行记录。上代码#include<iostream>#include<algorithm>#...
2019-09-22 10:30:18
170
原创 UVA 11078 open credit system开放制学分式
题目大意给定一个整数序列A，找出两个整数Ai和Aj(i<j)，使得Ai-Aj的最大分析最简单的方法就是一个二重循环，枚举Ai和Aj两个值上代码 for (int i = 0; i <= n; i++) { for (int j = i + 1; j <= n; j++) maxq = max(A[i] - A[j], maxq); }我们还可...
2019-09-22 10:06:16
154
原创 点集配对问题 蓝书dp
题目大意给定空间中的n个点把他们配对成n/2个点对，使得所有点对的距离之和最小;n<20分析应为n比较小，我们可以采取状压dp用二进制保存集合.设 d(s)为集合s配对后的最小距离 转移方程为:d(s)=min{d(s-i-j)+dist(i,j)|i,j属于S集合}核心代码为d[0] = 0;for (int i = 0; i < n; i++) for (i...
2019-09-21 22:26:09
237
原创 UVA 10817 headmaster's headache 校长的烦恼
题目大意每个学校有n个教师和m个求职者。已经知道每个的工资和能教的课程集合，要求支付最少的工资使得某门课都哦至少有两名教师教 m<20,s<8;分析当数据量小的时候首先考虑状压dp因为每门课程有至少有两名老师来教，因此用一个二进制集合难以满足要求，但是用三进制又是不可能的，因此我们需要两个值s1,s2来表示课程集合。状态就可以用三个量来表示了d(i,s1,s2) 表示前i...
2019-09-21 22:01:51
218
原创 UVA e 11795 洛克人的难题
题目大意洛克人有一个武器，它需要按照一定的顺序消灭n个其他的机器人，每消灭一个机器人将会得到他的武器，而且某些机器人只能用特定的武器才能将其消灭。统计出可以消灭所有机器人的顺序总数.分析由于题目中给定的n值很小可以采用状压Dp，用二进制的每一个位来表示每一个机器人我们可以构成一个集合q表示消灭i后，获得武器可以消灭的敌人q(i); for (int i = 0; i <=n; i...
2019-09-21 20:30:14
112
原创 UVA11552 fewest flops 最小的块数
题目大意给定以个正整数n和字符串 S，字符串的长度保证为k的整数倍. 把S的字符按照从左向右的顺序没k个分为一组，每组之间可以任意重排，但是组与组之间的顺序不可以调换，你的任务是让重排后的字符串包含尽量少的"块"，其中连续的相同字符为一块。分析典型的动态规划,我们设状态为d(i,j)表示前i个块以第i个块中的第j个字符结尾所包含的最小的块数.转移方程为分为三种 注:coun为第i块字...
2019-09-21 19:54:42
118
原创 UVA 10534wavio sequence 波浪子序列
题目大意:给定一个长度为n整数序列求一个最长子序列，长度为2k+1,要求前k个上升，后k个数下降分析对这样一个整数序列分别求最长上升序列和最长下降序列然后对同一点进行相加求最大;这个题目的重点时LIS问题参考刘汝佳的蓝书如何求LIS，最笨的方法，我们用d(i)表示从0-i个整数序列的最长上升序列用P数组保存序列状态转移方程为;d(i)=max{d(j)|1<j<i且p(j...
2019-09-21 16:17:42
205
原创 LA 4256 salesman 商人
题目大意给定一个包含n个点的无向连通图和一个长度为L的序列A，要求修改尽量少的数，使得序列中的任意两个相邻数或者相同，或者对应图中两个相邻节点.分析因为给定的节点N《100，所以我们把其纳入动态规划的状态当中去用一个邻接矩阵g表示两个点之间的联通关系,并且重要的一点，我们把自身与自身连通设为1，即g(i,i)=1;方便我们状态转移;我们设d(i,j)表示前i个数以第j个结尾的最小修改数，这...
2019-09-21 15:53:16
251
原创 UVA 11584 划分回文子串
题目大意一个小写字母组成的字符串，将它们划分为若干个回文串，谁求最少能划分为多少个回文子串分析首先就是打表，用一个mark数组表示 mark(i,j)表示i-j是否是一个回文子串然后用递推公式递推我们用d(i)表示从1-i的字符串可以划分为最少多少个回文串 ，初始化为:d(i)=d(i-1)+1状态转移方程为:d(i)=min{d(j-1)+1|i<j,mark(j,i)...
2019-09-21 15:33:50
181
原创 LA 4794 sharing chocolate 分享巧克力
题目大意给定一块长为x宽为y的矩形巧克力，每次操作可以沿着一条直线把一块巧克力切割成两块长宽均为整数的巧克力. 给定n个面积的巧克力试求能不能切成.n<15分析注意到n的规模很小。可以把n有关的子集作为动态规划的一部分. 设f(r,c,s)表示r行c列的巧克力是否可以切割成面积为S集合。对于一块面积为（r0c0)的巧克力,状态转移为:存在1<=r0<r和s中的集合s0...
2019-09-21 15:18:01
224
原创 LA 3983 robotruck 捡垃圾的机器人
题目大意在一个平面上有n个垃圾，坐标为(Xi,Yi),重量为Wi.有一个机器人，要求按照编号从小至大的顺序捡起垃圾放入垃圾桶（位于原点（0，0））,机器人可以捡起几个垃圾一起扔掉，但是任何时候的垃圾重量不能超过C，机器人的行走轨迹是哈密顿距离即横坐标之差的绝对值加上纵坐标之差的绝对值。分析设d[i]为清理完前i个垃圾后回到原点所走的距离;d[i]=min{d[j]+dist(j+1,i),d...
2019-09-21 11:48:41
620
原创 UVA10859 placin glampposts（放置街灯）
题目大意给定一个有n个节点的无向无环图，在尽量少的节点上放灯，使得所有的被照亮，每盏灯可以照亮以他为一个端点的所有边，在灯的总数最小的前提下，被两盏灯照亮的边应该尽量大;分析注意题意，给定的是无向无环图,即“森林”,有多棵树组成，经典的树上的动态规划此题目要求的优化量有两个,一个是a尽量小,a为灯的总数，另一个是b尽量小，b为被两盏灯照亮的边为了统一起见我们把b尽量大替换为尽量小，c是被...
2019-09-21 10:41:22
130
原创 hacker's Crackdown UVA 11825
题目大意;有n台计算机（从0开始编号至n-1的网络.一共运行着n中服务,对于每一台计算机,你可以选择终止一项服务,这样就会终止与这台计算机所有相邻的计算机的这项服务，对于一项服务来说,如果没有一台计算机运行，就判定提供这项服务瘫痪， 试着求出瘫痪的最大服务的数量分析本题的数学模型是:把n个集合分成尽量多的组,使得每组中的所有集合的并集等于全集，这里的计算机p就是计算机i 与相邻计算机的一个集...
2019-09-21 10:02:10
124
原创 Game of Sum UVA10891转自刘汝佳蓝书
题目大意;给定一个连续的序列，A和B进行博弈，两个人轮流取数，A先取数，每次只能从序列的右端或者左端取一个数，不可以两端都取。所有数字被取完后游戏结束，统计每个人取走的所有数之和作为各自的得分.两人采取的策略都是让自己的得分尽量高，并且两人都十分聪明。分析博弈问题这个题百思不得其解，尤其是关于状态转移的，不是规定取一个数为什么会会有那么多状态，先记下，回头在看看.整数的总和是一定的,所以...
2019-09-21 09:24:53
208
原创 ## **算法竞赛入门经典-训练指南**
dp动态规划; **嵌套矩形**题目大意:有n个矩形，每个矩形可以用两个整数a,b表示长和宽，一个矩形X(a,b)可以去嵌套另一个矩形Y(c,d)的条件是:a<c及b<d 或者a<d&&b<c；在这些矩形当中选出最多的矩形，排序之后前面的可以嵌套后面的;本文是经典的DAG最长路问题,设d(i)为以...
2019-09-20 19:08:05
171
原创 区间dp
Code vs 1154 能量项链在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠...
2019-08-12 12:19:02
105
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人