0 cs张小菜

尚未进行身份认证

我要认证

ACM压行小能手,AI&MC科研大白。

等级
TA的排名 2w+

2020清华深圳国际研究院 计算机线上夏令营总结

今年入营了50人左右,十几个清本,剩下三十多应该都是985rank1+论文(已知985 rank2未入营的),难度也还可以,最终也是拿到了优营,注意今年情深cs是发offer的,也就是拿了优营9月想去直接报名就可,不再需要考核,过程主要分为了四个环节,【总成绩计算办法】总成绩=(机试成绩70+笔试成绩30)×20%+(专业面试成绩80+综合面试成绩20)×80%机试机试三道题,第一题简单dfs或者模拟即可,第二题dp或者最小费用流,今年线上,用了洛谷题目链接第三题差分约束系统,题解三道我都做

2020-07-09 14:33:15

POJ 1141 Brackets Sequence【题解报告|有趣的区间dp】

今天很高兴,十几个清华本科和30个左右985专业第一,经过三天的角逐,终于让我拿到了清深的offer,夏令营的第一个收获!可以安心的九推冲击清软了题目大意给一些括号,求让它们合法最少要加上多少括号,并输出加上后的结果,合法的定义:1.空串是合法的2.若S是合法的,则[S]和(S)均是合法的3.若A和B是合法的,则AB是合法的思路分析一道类似的区间dp问题,区间dp问题写的不多,右边这道回文子串算是一个,但是自己思维却是被这道题固化了,遇到最小括号匹配时也想用相同的dp方法来作,先附上我第一遍的

2020-07-09 14:15:05

【看了就懂】P问题、NP问题、NP完全问题和NP难问题

为了避免对这四个问题有一定理解基础的人看的很烦,个人简单理解的四个问题:P问题:有多项式时间算法,算得很快的问题。NP问题:算起来不确定快不快的问题,但是我们可以快速验证这个问题的解。NP-complete问题:属于NP问题,且属于NP-hard问题。NP-hard问题:比NP问题都要难的问题。详细说一下这四个问题:P类问题:存在多项式时间算法的问题。(P:polynominal,多项式)。我们为什么要研究这个P类问题呢?当计算机处理的数据达到100万个的时候,时间复杂度分别为 O(n2)O(

2020-07-07 19:09:59

【超详细】计算机组成原理考点总结

文章目录第一章 计算机系统概论冯诺依曼型计算机特点区别以运算器为中心的计算机还是存储器的方法计算机系统第三章 运算方法和运算部件数据的表示方法和转换带符号的二进制数据在计算机中的表示方法及加减法运算补,反,原,移码的相互转换定点数和浮点数二进制乘法原理第四章 主存储器主存储器的主要技术指标存储器相关概念存储器的组成与控制存储器的主要性能比较三级存储体系,两级存储层次cache的命中率第五章:指令系统指令分类-按照功能分类指令分类-按照操作码分类指令分类-按照地址码分类第一章 计算机系统概论冯诺依曼型计算

2020-07-06 23:52:01

题解 P3275 【[SCOI2011]糖果】

清深夏令营机考压轴题,对差分约束的认识还是不够深刻,算法写出来了图没建对,/(ㄒoㄒ)/~~#define inf 0x3f3f3f3f#define ll long long#define vec vector<int>#define P pair<int,int>#define MAX 100005int N, K, x, a, b, vis[MAX], cnt[MAX], dist[MAX];struct edge { int v, c; edge(i

2020-07-06 18:21:40

POJ 1942 Paths on a Grid【题解报告|DP巧妙的解决组合数问题】

题目大意给定一个矩形网格的长m和高n,其中m和n都是unsigned int32类型,一格代表一个单位,就是一步,求从左下角到右上角有多少种走法,每步只能向上或者向右走解题思路首先题目上说了答案不会超过int型变量,我们可以简单算一下,如果是2∗x2*x2∗x的图,大概xxx在100000左右就会超出int变量的范围,如果是3∗x,,,m∗x3*x,,,m*x3∗x,,,m∗x的图,那么xxx的范围会更小,当1∗x1*x1∗x时,返回x+1x+1x+1,0∗x0*x0∗x时返回111,然后我们讨论m∗

2020-07-05 22:18:34

POJ 1836 Alignment【巧妙地LCS】

题目大意,令到原队列的最少士兵出列后,使得新队列任意一个士兵都能看到左边或者右边的无穷远处。就是使新队列呈三角形分布就对了。思路分析三角分布无非就是找一个人,在这个人左侧身高递增,这个人右侧身高递减即可。很容易联想到LCS,从左向右求上升子序列dp1[],从右向左求上升子序列dp2[],然后枚举n个点,取dp1[]+dp2[]-1最大的点,但是这样是有问题的,比如51 1 1 1 1 这组数据,其实只需要踢出三个人就够了,也就是说中间两个是可以等高的,要完成这个功能,我们不妨将序列分成两部分,

2020-07-05 18:03:10

POJ 1022 Packing Unit 4D Cubes【题解报告|4D纸老虎】

题目链接题目大意:这个题不算难,关键就是题意不好懂。这里我不介绍背景,从输入数据入手分析题意。1.第一行表示样例数目。每个样例的第一行整数n表示样例中含有的物体数目,其后n行描述n个物体。2.描述一个物体用一行,一行包含9个整数。第一个表示该物体的编号(相当于名字)。剩下的8个数字2个一组,共四组。3.每一组数字表示该物体在一个方向上的前后邻居情况。(如果一个物体是二维平面的,我们认为它有x,y两个坐标轴方向。如果物体是三维的,我们认为它有x,y,z三个方向。本题中物体是四位的,用x,y,z,k.

2020-07-04 20:59:35

POJ 1922 Ride to School【解题报告|贪心|规律】

题目链接题目大意起点与终点相隔4500米。现Charley 需要从起点骑车到终点。但是,他有个习惯,沿途需要有人陪伴,即以相同的速度, 与另外一个人一起骑。而当他遇到以更快的速度骑车的人时,他会以相应的速度跟上这个更快的人。先给定所有与Charley 同 路的人各自的速度与出发时间,问Charley 以这种方式跟人,骑完4500米需要多少时间。得出的结果若是小数,则向上取整。思路分析每次Charley选择的都是当前最快的单车,而且Charley最后一定是和那个最快到达Yanyuan的单车同时到达,因

2020-07-04 19:17:55

POJ 1838 Banana【题解报告|爆搜不够排序来凑】

题目链接题目大意有一只猴子喜欢吃香蕉,但他只能在相邻的两棵香蕉树之间行动,如果两棵树是在横方向或竖方向相邻的,那么这就组成一个区域,这个区域内猴子可以随意走动,有人可以把k个区域连接起来,从而使猴子在这k个区域内随意行动,问猴子最多可以在多少棵树内走动?给定n个树的坐标,和k。BFS+MAP使用MAP存储已有点对,然后对输入的N个点每个进行bfs,找到和他相邻的所有点,并将已访问过的点打上标记,这样做虽然看起来复杂度不高,但是一般用map存储点对很容易T,果不其然这里就T了。//TLE#defi

2020-07-04 15:11:36

POJ1227 RoboContest【题解报告|BFS】

题目链接题目大意题目给定一个无向图,节点上放置有机器人,要求每一个回合机器人都要往相邻的节点走一步,问是否存在有一个节点,使得所有机器人在某一步中能够在此节点相会思路分析对于一个无向图而言,如果我们能在第kkk到达节点nnn,那么我们可以在他和相邻节点来回穿梭,即k+2,k+4,k+6,...k+2,k+4,k+6,...k+2,k+4,k+6,...这些时刻我们都可以到达这个节点。也就是说,在这道题中,我们在意的其实不是走多少步,而是步长的奇偶性。需要注意的是,有些节点不管是奇数还是偶数都能到达

2020-07-04 10:53:18

高等数学|微积分(上)知识点总结

2020-07-03 23:24:58

POJ 1661 Help Jimmy【题解报告|DFS|DP】

题目大意场景中包括多个长度和高度各不相同的平台。地面是最低的平台,高度为零,长度无限。Jimmy老鼠在时刻0从高于所有平台的某处开始下落,它的下落速度始终为1米/秒。当Jimmy落到某个平台上时,游戏者选择让它向左还是向右跑,它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时,开始继续下落。Jimmy每次下落的高度不能超过MAX米,不然就会摔死,游戏也会结束。设计一个程序,计算Jimmy到底地面时可能的最早时间。DFS这道题,爆搜显然是能找到正确答案的,我们从上往下跳,落到一个平台上的时候,

2020-07-03 16:13:20

POJ 2046 Gap【题解报告|BFS&hash判重】

题目链接题目大意4*8的方格有28个数字,按照给定的规则移动,现在要你从初始状态移动到终结状态,问你最少几步.思路分析依然是BFS,且每个状态需要的元素很多。所以用dist[][][][][]…[]这种形式空间不足,所以需要用hash判重且保存所有出现过的状态。首先我们每个状态要用一个32位的char数组s保存32个方格中的每个数字,然后我们用e[4]数组保存32个方格中(有4个0)4个0的位置分别是多少,并且用p[48]保存XY(11<=XY<=47)这个数字在s数组中的位置.用di

2020-07-03 09:17:10

POJ 2078 Matrix【题解报告|策略枚举】

题目大意:一个n*n的数字矩阵,每次操作可以对任意一行或者一列进行循环移动,操作次数任意。求每种情况每一列的最大值的最小值。思路分析最大值最小化。n最多只有7,所以想着暴力试试,枚举任意行所有的状态求最大值再求最小值。不过这样算的复杂度7^14,竟然也过了。。...

2020-07-02 17:44:41

POJ-1847 Tram【题解报告|Dijstra】

题目链接题目大意有一个火车站,里面有n条轨道,然后有n个轨道切换点。问最多切换几次,能从A轨道切换到B轨道。每个轨道切换点能切换至m条轨道上,其中第一条可以切换的轨道不算切换次数,因为本来就是往那条轨道上运行过去。如果不能从A轨道切换到B轨道,则输出-1。思路分析这道题算是比较裸的dijkstra算法,当然还有其他算法。问题的关键是如何建边,其实很简单,这道题的边的权值只有1和0两种情况,0是切换点后面的第一条轨道,1是切换点后面剩下的其他轨道。这样建好边后就可以直接用很裸的dijkstra算法

2020-07-02 16:24:49

POJ 3026 Borg Maze【解题报告|DFS+PRIM】

题目链接题目描述在一个 y行 x列 的迷宫中,有可行走的通路空格  ,不可行走的墙 #,还有两种英文字母 A 和 S ,现在从 S 出发,要求用最短的路径 L 连接所有字母,输出这条路径 L 的总长度。思路分析BFS + Prim一格的长度为1,而且移动的方法只有上、下、左、右,所以在无任何墙的情况下(但“墙#”是必须考虑的,这里只是为了说明)任意两个字母之间的距离就是直接把 横坐标之差 加上 纵坐标之差注意的是:① 可行的路为 字母 和 空格② 不可行的路为 # 和 矩阵范围之外根据

2020-07-02 15:49:05

POJ 3020 Antenna Placement【题解报告|二分图匹配】

题目大意一个矩形中,有N个城市’*’,现在这n个城市都要覆盖无线,若放置一个基站,那么它至多可以覆盖相邻的两个城市。问至少放置多少个基站才能使得所有的城市都覆盖无线?思路分析在这道题上卡了很久,才接触二分图也没什么好的思路。这道题需要用到一个定理:二分图最小边覆盖 = 两边顶点数 - 最大匹配数无向图的最小边覆盖 = (二分图两边顶点数 - 二分图的最大匹配数)/2下面列举几个二分图问题的常用定理:定理1:最大匹配数 = 最小点覆盖数(这是 Konig 定理)定理2:二分图最小边覆

2020-07-02 11:57:45

POJ 1789 Truck History【题解报告|最小生成树】

题目大意用一个7位的string代表一个编号,两个编号之间的distance代表这两个编号之间不同字母的个数。一个编号只能由另一个编号“衍生”出来,代价是这两个编号之间相应的distance,现在要找出一个“衍生”方案,使得总代价最小,也就是distance之和最小。例如有如下4个编号:aaaaaaabaaaaaaabaaaaaaabaaaa显然的,第二,第三和第四编号分别从第一编号衍生出来的代价最小,因为第二,第三和第四编号分别与第一编号只有一个字母是不同的,相应的distance都是1

2020-07-02 09:11:49

操作系统常见考点与知识点汇总

文章目录1. 进程的有哪几种状态,状态转换图,及导致转换的事件。2:进程与线程的区别。3:进程通信的几种方式4:临界区/关键段5:事件1. 进程的有哪几种状态,状态转换图,及导致转换的事件。运行态:进程占用CPU,并在CPU上运行;就绪态:进程已经具备运行条件,但是CPU还没有分配过来;阻塞态:进程因等待某件事发生而暂时不能运行;当然理论上上述三种状态之间转换分为六种情况; 运行——>就绪:1,主要是进程占用CPU的时间过长,而系统分配给该进程占用CPU的时间是有限的

2020-07-01 08:44:20

查看更多

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