- 博客(39)
- 问答 (7)
- 收藏
- 关注
RSS订阅原创 操作系统-磁盘分区
磁盘分区MBR磁盘分区表目前有两种格式MBR（Master-Boot-Record）和GPT（GUID-partition-table）对于一个磁盘，由多个磁碟盘组成，磁盘碟上面又可细分出扇区(Sector)与磁道(Cylinder)两种单位， 其中扇区每个为512bytes那么大。假设只有一个磁碟盘，那么磁碟盘有点像底下这样：第一个扇区非常重要，主要记录了两个重要的信息，分别是：1、...
2020-03-21 23:31:56
1331
1
原创 一道算法题
看到一道有意思的题目，在这里记录一下： 题目意思是一副从1到n的牌，每次从牌堆顶取一张放桌子上，再取一张放牌堆底，直到手机没牌，最后桌子上的牌是从1到n有序，设计程序，输入n，输出牌堆的顺序数组看到这个题目的时候自己思考了一下 然后给出了一种解法， 其实题目中排列可以理解为一层递归，对于1-n，那么开始填数的时候不考虑相隔的那一个位置 第一趟就应该填1 2 3 4….. 但是相隔...
2018-07-22 15:55:18
437
原创 渲染流水线-透视投影矩阵 透视除法 空间裁剪 视口变换 数学原理理解
透视投影矩阵推导：参考：https://www.cnblogs.com/graphics/archive/2012/07/25/2582119.html具体推到就不写了就说一下推导流程，如下图： 首先是把p（x,y,z）p（x,y,z）p（x,y,z）点映射到p′(x′,y′,z′)p′(x′,y′,z′)p'(x',y',z')让后根据宽高比把坐标规范到[-1,1]之间，得到p′′(...
2018-03-01 21:08:05
1105
原创 春招预热-腾讯电话面
首先感谢我的巨佬学长推的这次面试，其实之前自己完全没有准备好，但是仔细思考了一下，反正面不上，不如去看看面试的流程是怎么样的，于是就在完全没有准备的情况下投了简历，迎来了人生第一场专业面试。主要说下这次的面试内容吧，问题其实不是很难，但是自己太方了，大脑一片空白，导致刚开始的时候发挥的像一坨屎一样。1、首先是聊了一下项目，主要在问网络那块，但是那块不是我写的，就只有乱吹了，结束后又微信问了...
2018-01-12 16:09:04
285
原创 codeforces 842C dp
题目大意：给你一棵树，树上的每一个节点有一个值，定义一个节点的美丽值为这个节点到根节点的的路径上的每一个个节点（包括自己）的所有的值的最大公约数，现在给定一种操作，对于某一个点的美丽值现在可以把路径上的任意一个点的值变为0，（规定GCD（x,0）=x）问对于每一个个点单独考虑，输出每一个点的美丽值的最大值。思路：在大佬的帮助下明白了dp的思路，定义dp[i][0]表示从根节点到i已经有一个被改变为0
2017-08-31 13:55:51
277
原创 2017多校9 Two string hdu 6170 dp
题目链接 题目大意：给你两个字符串A B，A由大小写字母组成，B由大小写字符和 . 和 *组成现在问你AB能够匹配 其中 . 可以匹配任何字符 * 表示其前面一位的字符可以出现任意多次 可以为0次。思路：首先来考虑dp[i][j]表示A串1-i用B串的1-j能否匹配 转移的时候就考虑B串 如果当前字符是 . 那么dp[i][j]=dp[i-1][j-1] 如果是普通字符 dp[i][j] =
2017-08-26 21:08:52
184
原创 hdu6138 多校2017 ac自动机or后缀数组
题目链接 题目大意：给定n个字符串，m个询问，对于每一个询问，给出x，y 问第x个串和第y个串的相同连续子串当中，作为其他（包括自己）串的前缀的最长长度。两种思路：第一种ac自动机 首先把所有的串建立一个fail树，那么对于询问把第一个串在树上跑一遍，把所有匹配的节点标记，然后让第二串跑一遍，如果遇到相同匹配的节点，记录当前的最大深度就可以了。 代码：#include<iostream>#i
2017-08-23 21:03:39
428
原创 2017 CCPC网络赛 hdu6153 KMP
题目链接 题意：给你连个字符串，s,t 求出t的所有后缀在s中出现的次数乘后缀的长度。 一开始想的后缀数组，tle，最后才知道是kmp 首先把s 和 他翻转一下，这是后就相当于求前缀了，然后求出t的next数组，然后对s跑kmp，跑的时候记录每一个长度匹配的次数，然后对于某个长度，如果他匹配了 比他小的也就匹配了，所以最后在类似求一个后缀和。 代码：#include<iostream>#i
2017-08-20 13:44:43
321
原创 2017 多校7场 hdu6129 蜜汁规律
首先来考虑前面每个数在m次变换后对后面的某一个数的异或次数，因为偶次异或相当于没有异或，奇次相当于异或一次。我们来考虑一下第一个数对后面的贡献次数 第一次 1 0 0 0 0 第二次 1 1 1 1 1 第三次 1 2 3 4 5 第四次 1 3 6 10 15 斜着看其实就是一个杨辉三角。 那么对于每一个次数就是C(x+y-2,x-1),然后就是判断这个值的奇偶就可以了，可以去百度一发
2017-08-16 21:51:20
642
原创 关于曼哈顿距离的最小生成树 POJ3241
题目地址 题目就是给你n个点 求n个点的曼哈顿距离的最小生成树 输出所有边中第k大的的边的权重。 n个点那么有有n∗(n−1)n*(n-1)条边如果采用朴素的prim算法建边就是O(n2)O(n^2)的复杂度，我们来考虑一下曼哈顿距离的特殊性，其实不是所有的边都需要，在建边的时候就可以去掉很多多余的边。 如图，对于给定的一些点我们选取一个点那么可以以这个点为原点建立一个直角坐标系，然后把每一个
2017-08-09 21:57:37
982
原创 hdu6070 多校第四场 线段树+二分
看了题解才知道这怎么做，其实之前做过一道类似的线段树的题这里，但是比赛的时候还是没有做出来。根据官方给的题解 其实我们要求的就是这个size(l,r)r−l+1\frac{size(l,r)}{r-l+1} 那么我们令ans=size(l,r)r−l+1ans = \frac{size(l,r)}{r-l+1} 现在就是求一个最小的ans，我们来二分枚举答案，也就是说如果存在：mid>size(
2017-08-06 15:55:30
292
原创 codeforces 835D 区间dp
简单的区间dp dp[i][j]dp[i][j]表示区间i-j的回文度数 转移方程就是在si=sj且dp[i+1][j−1]>0s_i=s_j 且 dp[i+1][j-1]>0时dp[i][j]=dp[i+1][(i+j)/2]+1dp[i][j]=dp[i+1][(i+j)/2]+1#include<iostream>#include<cstdio>#include<cmath>#in
2017-08-02 17:07:27
239
原创 codeforces #426 div2（The Bakery）834d
题目链接 本菜感觉这个题目真是难，看了好久的题解才懂起，大致题意就是给一个数组，把数组连续的分为k部分，每一部分的值等于这部分不同的数字的个数，要让所有的值加起来最大，问怎样分。首先我们来看一下dp： dp[i][j]dp[i][j]表示前i个数字分成j组的的最优方案，那么很容易就能够得出一个状态转移公式 dp[i][j]=max(dp[t][j−1]+F(t+1,i),j−1<=t<i)dp
2017-08-01 21:52:24
98
原创 hdu6053 多校第二场（莫比乌斯函数，枚举）
之前不知道莫比乌斯反演，看了一波，然后有些许理解，这个题其实就是使用了莫比乌斯函数U的定义，详细的解题报告这里说的比较清楚#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<string>#include<set>#include<map>#include<queue>#includ
2017-07-30 15:32:54
331
原创 hdu3507 斜率优化dp入门
刚开始接触斜率优化dp，做的一道简单的入门题目，这里有一篇论文，前半部分讲的就是这个浅谈数形结合思想在信息学竞赛中的应用 分析： 我们假设k<j<ik<j<i。如果在j的时候决策要比在k的时候决策好，那么也就是 dp[j]+M+(sum[i]−sum[j])2<dp[k]+M+(sum[i]−sum[k])2dp[j]+M+(sum[i]-sum[j])^2<dp[k]+M+(sum[i]-s
2017-07-29 21:48:46
293
原创 codeforces 832c #425 DIV.2
题目链接 二分答案，对时间进行二分，假设每得到的时间是x，那么就以该时间来判断是否可以，满足条件 判断方法： 对于时间x，指定的某个人算出这个人要跑到终点，那么炸弹应该放置的区间，这样把所有向左跑的人区间算出来，然后同样的算出向右的人的区间，如果这些区间有整点重合（因为炸弹只能放在整点），那么就是满足的二分的右区间减小，反之亦然。 这里处理区间可以使用扫描线，对左端点的对应的数组值加一，右端
2017-07-27 22:44:39
368
原创 2017多校第一场（HDU6038）
还是太菜了这么多人过的一道题目，自己却想了这么久，然而到现在还是不是很清楚这个东西，先写一个题解吧，题目给的是一个公式 f(i)=bf(ai)\displaystyle f(i) = b_{f(a_i)} 给定了b数组和a数组，然后问有多少种映射的方案满足上式， 首先来看下样例 f(0)=bf(1)f(0) = b_{f(1)} f(1)=bf(0)f(1) = b_{f(0)}
2017-07-27 22:26:07
352
原创 Ural1519 Formula 1 插头dp入门
看了几天才懂，自己也说不太清楚，推荐看CDQ的论文基于连通性状态压缩的动态规划问题 这个看完之后这里有一篇比较详细的解题报告http://blog.sina.com.cn/s/blog_51cea4040100gmky.html 然后说说自己的理解吧，因为先学的轮廓线，做了几道题目，所以在状态转移上面还是比较清楚是怎么回事，这道题一直没有弄懂的是怎么用hash存状态，因为以前从来没有用过hash
2017-07-22 22:54:34
384
原创 hdu1693 插头dp
学习插头dp 真是艰难，做的第一道题。 题意，现在给一个n*m的矩阵 矩阵中有一些障碍，障碍不能通过，现在要把能通过的点全部连起来，形成哈密顿回路，但是可以连成多个哈密顿回路，问有多少种方法。 直接说做法吧，首先是用轮廓线不懂的，可以先看看这 看图 在轮廓线上每一位如果有一个插头那么这一位就表示位1没有就表示为0，插头是是在回路上的线，如果有插头表示上一格经过了这一条边，如图状态表示为1
2017-07-21 15:17:26
219
转载 hdu2167 轮廓线动态规划
相对上一题方格取数，这一题要高级很多了。首先输入比较难处理，其次周围8格数字不可取，上一题的方法不能直接使用了。因为必须要记录当前格左上角的数字有没有取得情况，我们需要在状态中加一位，并且换行时要更新一下状态。如下图： 状态记录及转移 在取11格的数字时，我们需要判断10，6，7，8格是否有取数字。在更新11格的状态的同时，丢弃掉第6格的状态值。在遇到换行时，第8格的状态可以直接丢弃
2017-07-19 16:40:22
254
原创 hdu1565 轮廓线动态规划
也是比较经典的轮廓线动态规划问题，每一个格子可以放或者不放，0和1表示，那么就是判断上一个状态的左边和上边是否已经选了，注意一下列首的时候不用判断前一个是否放了，有一个地方要注意一下，因为对于每一个状态 枚举的时候可能枚举到不符合要求的状态，如果判断单独来判断该状态是否符合规范 比较麻烦 因为首列的两个1可以并列，所以比较麻烦，这里的处理办法就是初始化为-1，更新了的状态肯定是符合要求的那么对于上一
2017-07-19 14:23:29
293
原创 poj3311 动态规划 轮廓线 或者状态压缩
题目大致意思就是给你1*2的矩形砖块 让你填充满h*w的矩形区域 有多少种填充方法？hw的值小于12， 两种解法： 1. 状态压缩dp 思路很简单，对于每一个格子，我们考虑这个格子上面我们是竖向放砖块还是横向放砖块，如果横向放 我们就有横着的两个11表示，竖向放我们就用竖着的01表示，那么每一行就可以表示为一个状态，在其中一行的时候，首先判断当前行的状态是否符合上一行的要求，即上一行为0的地
2017-07-18 21:28:53
436
原创 poj3311 状态压缩dp
比较经典的状态压缩dp，题目说了可以重复的走点，而且到一个点的最短路可能是通过其他的点间接到达，所以首先用Floyd处理一下，然后dp就可以了 状态转移公式 dp[i | (1<<(k-1))][k] = min(dp[i | (1<<(k-1))][k],dp[i][j]+mp[j][k]);表示在状态i的时候，到达目的j的最短路最后扫一遍就可以了
2017-07-17 15:13:37
256
原创 Codeforeces #420 E. Okabe and El Psy Kongroo 递推加矩阵快速幂
比较好的一道题，首先是是递推，递推很容易想到，我们假设dp[i][j]表示走到i，j的方案数 那么其实就是求出每一段a[i]-b[i]的值 就可以得出来了可以得到dp[i][j+1] += dp[i-1][j]; j+1dp[i][j-1] += dp[i-1][j]; j-1>=0dp[i][j] += dp[i-1][j];因为i的范围很大，看了解法后知道要用矩阵快速幂
2017-07-07 10:31:36
200
原创 玲珑acm 倍增
地址：http://www.ifrog.cc/acm/problem/1112官方题解很详细：这里就不做过多的解释了，注意一下long long就可以了和倍增超过最大限度就好了#include#include#include#includeusing namespace std;#define LL long longLL arr[300005];LL v[300005]
2017-04-07 13:27:37
259
原创 hdu 6012
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6012bc91的题 官方题解已经写的很清楚了，离散化其实只要用map来存就可以达到离散的目的#include#include#include#include#include#include#include#include#include#includeusing names
2017-02-09 09:48:27
276
原创 hdu 5749 公式
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5749参考文章：http://m.blog.csdn.net/article/details?id=52020617题目要求求出这个公式的值，首先来看S（a，b），其实对于一个矩阵，可以手动画一下，一个矩阵的鞍点至多只有一个，那么s（a,b）其实就是矩阵中这个鞍点的值，那么如何来求鞍点。
2017-01-17 17:05:15
235
原创 hdu5778 枚举
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5778过了很久才来写题解，以前不会做，看了题解，有一个地方不是很懂，一直不是很明白为什么只需要找出10^5内的素数就可以了，现在有遇到这到题，突然想通了，来说一下我的理解吧。题目要求给定x 要找到y-x的绝对值最小，y满足以下条件，y的质因数分解中所有的质因数都恰好只出现了两次，那么很容易就知道
2017-01-15 20:27:00
232
原创 hdu5996 阶梯nim博弈
第一次接触到阶梯nim博弈 看了这篇博客，讲得比较清楚：http://blog.csdn.net/kk303/article/details/6692506题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5996大意就是给一颗树 树的节点上放有石子，每次只能把石子往父节点移动一下，规定不能移动者输。看了阶梯博弈后大概就能懂这题的意思了，直接
2016-12-28 22:18:03
349
原创 玲珑oj 1074
链接：http://www.ifrog.cc/acm/problem/1074http://www.ifrog.cc/acm/problem/1074区间dp问题 好难啊 不会 看了题解后 慢慢磨出来的 dp[i][j]表示区间区间i到j的硬币取出来能取得的最大值，不包括i 和 j硬币 如果包括的话因为该区间两边硬币会变化 不能确定，状态转移方程：dp[i][j] = max(dp[i][j]
2016-12-26 15:26:26
301
原创 hdu4734(数位dp)
基本的数位dp这几天在学 ，巩固一下，记忆化 dp[i][j] 表示长度为i位的时候不超过j的数的种数 记录的时候就用f(a)减去当前的记录的sum值就是后面的不超过的值了#include#include#includeusing namespace std;#define MAXN 10int dp[MAXN][5000];int dat[20];int dfs(int len
2016-11-22 22:43:12
166
原创 Hdu 3709 Balanced Number
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3709记忆化 ，用的数位dp的模式感觉 ，数位dp也是菜开始学的 感觉很难看了一些博客 最终艰难的把它a了，写个题解来巩固一下把尽量写得详细点。网上很多博客都说直接枚举支点 其实对这个不是很熟，下面就用我的话来表述一下这个题吧。首先是暴力dfs，对于指定长度的一个数，小于它的数有多少是平横数
2016-11-22 22:34:07
182
原创 hdu 1175 深搜
简单深搜，主要记录转弯次数。题目http://acm.hdu.edu.cn/showproblem.php?pid=1175#include#includeint mov[4][2] = {1,0,0,1,-1,0,0,-1};int map[1001][1001];int book[1001][1001];int n,m,ex,ey;int dfs(int sx,int sy
2015-11-29 17:35:19
262
原创 hdu 149 胜利大逃亡(续)
http://acm.hdu.edu.cn/showproblem.php?pid=1429第一次接触位运算，被坑了好久，一直不知道怎么标记，代码有点乱#include#include#includeusing namespace std;int n,m,t;char map[20][20];int mov[4][2] = {1,0,0,1,-1,0,0,-1};struct
2015-11-23 13:31:48
205
原创 hdu2102
http://acm.hdu.edu.cn/showproblem.php?pid=2102不多说，被两层相同位置都是#坑惨了，一开始没有考虑到，简单的bfs，上代码#include#include#includeusing namespace std;struct node{ int floor,x,y; int t;};char map[2][10][10];i
2015-11-19 12:53:35
67
原创 HDU 1072 nightmare
用dfs没问题 但是本题有一个重置时间的地点，从样例3可以知道，如果已经走过的的点也有可能被重复走，用二维数组标记地图走过的方法似乎就不行了。那么该怎么办呢？我们来观察一下样例三，当第一次走到红色数字时，时间剩余3分钟，根据题意，这时肯定只有走一次左边的4在返回 才有可能走到终点，那么这次返回之后第二次走到红色数字时剩余时间就变成了5，也就是说要重复走一个地方的条件就是下一
2015-11-18 09:19:04
295
原创 FZU 1894，单调队列入门
http://acm.fzu.edu.cn/problem.php?pid=1894主要用单调队列网上看了很多单调队列的博客，略有理解，简单说一下吧。单调队列就是队列是有序的的队列，对于每个入队的的元素，首先和队尾元素比较，是否满足升序（降序）的规则，不满足则删除队尾元素，继续比较，直到满足规则，把入队元素放在队尾，这样就是有序的队列，可以用来标记队列中最大的元素。#inclu
2015-11-17 08:50:32
350
空空如也
计祘客的一道线段树 一直超时 实在不会了 求解答
2017-03-08
hdu 3823 prime friend 求大神为什么wa，已经wa怕了
2015-12-11
指针，简单链表输入输出，编译器
2015-12-01
hdu 1236一直re，跪求解释
2015-11-02
C语言题目，跪求大神给个代码，实在不会啊
2015-10-18
一道acmC语言题目，求大神解答
2015-10-17
关于HDU 1045题，一直wa，求大神解释
2015-10-10
TA创建的收藏夹 TA关注的收藏夹
TA关注的人