当前位置: 代码迷 >> 综合
 解决方案列表
  • [综合] 二进制反码求和

    在看TCP/IP时,看到IP协议中有个首部检验和是用的二进制反码求和。不太理解,上网搜到了一个答案,记载下面。 以4bit(计算方便一点,和16bit是一样的)做检验和来验证。 假设原始数据为1100,1010,0000(校验位)那么把他们按照4bit一组进行按位取反相加。1100取反0011,1...

    47
    热度
  • [综合] PAT1003 Emergency (25)(dijkstra多条路径权重处理)

    题意: n个城市m条路,每个城市有救援小组,所有的边的边权已知。给定起点和终点,求从起点到终点的最短路径条数以及最短路径上的救援小组数目之和。如果有多条就输出点权(城市救援小组数目)最大的那个 思路: 这种题用dijkstra+回溯可以保证一定做的出来。 #include<bits/stdc+...

    54
    热度
  • [综合] PAT1007 Maximum Subsequence Sum (25)(最大连续和)

    这题没什么好说的就是一个最大连续和的裸题,只要掌握dp[i]=max(dp[i-1],0)+num[i]即可,记录一下主要是因为我自己写的时候边界条件没处理好,也就是dp[i-1]这里对于0的处理,所以尽量少用dp[i-1]这种形式,用一个变量存就可以了。 /*自己写的不太好*/ #include&...

    70
    热度
  • [综合] PAT1010 Radix (25)(模拟)

    这题的题意极难懂,给两个数a,b和a的进制x,问b在哪个进制下和x进制的a相等,一开始我以为就是简单的最高进制单字符为z=36就行了,后来发现不对,这题的基数可以非常大,比如9999991110这种情况,b的基数就可以取999999,可以看出基数最大的可能也就是a的十进制表示,还要注意用longlo...

    72
    热度
  • [综合] PAT1014 Waiting in Line (30)(模拟)

    这题思路倒是不难,比较容易想到是用queue进行模拟,主要是要想到对每个队列维护一个当前顾客进入的时间,我的模拟不咋样啊,这种题就感觉难度不小了。 #include<string> #include<cstdlib> #include<vector> #inclu...

    47
    热度
  • [综合] PAT1018 Public Bike Management (30)(最短路径+DFS)

    题意: 每个自行车车站的最大容量为一个偶数cmax,如果一个车站里面自行车的数量恰好为cmax/2,那么称处于完美状态。如果一个车展容量是满的或者空的,控制中心(处于结点0处)就会携带或者从路上手机一定数量的自行车前往该车站,一路上会让所有的车展沿途都达到完美。现在给出cmax,车站的数量n,问题车...

    97
    热度
  • [综合] PAT1020 Tree Traversals (25)(中序后序遍历生成树)

    题目很简单,就是给出树的中序和后序遍历,要求输出层序遍历,记录一下主要是因为之前这块一直懒得写,一直没写过 #include<bits/stdc++.h> #defineINF0x6ffff usingnamespacestd;structnode{intdata;node*left,*...

    86
    热度
  • [综合] PAT1021 Deepest Root (25)(树的最深节点)

    题意: 给出n-1条边,要求判断能否生成一棵树,并求树中所有以它为根时深度最大的节点。 思路: 我一开始做的时候就很莽的直接用dfs搜索,就有一个节点超时,其实简单的思考就是如果以1为根,那么就是当前最深的几个点,他们之间的距离也就是树最大的深度。可以这么理解:从1到i距离最远,那么以i为根,到1的...

    62
    热度
  • [综合] PAT1022 Digital Library (30)(map的使用)

    很简单的题,就是考察一个map的使用,不过这题有个陷阱就是最后输出的id必须是7位的,我做这题的时候用到了string的分割,其实不需要,直接用getchar()就可以判断结束条件,注意使用getline时要吃掉\n #include<string> #include<cstdli...

    34
    热度
  • [综合] PAT1026 Table Tennis (30)(排队模拟)

    又是排队模拟,PAT很喜欢出排队模拟题,这题巨复杂,反正我是没想出来,基本的思路就是分为桌子为VIP和选手为VIP一共4种情况讨论,太复杂。抄了一下别人的代码,其中的几个难点写了注释。 #include<iostream> #include<vector> #includ...

    13
    热度
  • [综合] PAT1033 To Fill or Not to Fill (25)(贪心)

    题意: 开车从起点出发,到终点的路上有一些加油站,不同的加油站油价不同,要求输出到终点时最少花费的钱 思路: 贪心,在加满油可以走的最大距离内分情况讨论: 在范围内存在加油站油价比当前加油站小,就加油加到刚好可以到那个加油站 在范围内不存在加油站油价比当前加油站小,说明当前加油站油价最小,所以在...

    49
    热度
  • [综合] PAT1034 Head of a Gang (30)(并查集)

    题意: 给出n次通话记录,当通话的人数超过2人并且通话总时长超过k时,这些人就是犯罪团伙,其中通话时间最大的人是头目,要求按字母序输出头目和团伙人数 思路: 就是并查集,将两两通话的人关联在一起,因为通话的人的姓名是按三位字母给出的,所以要离散化,并且对应要用一些STL保存映射。我自己写的时候有两个...

    20
    热度
  • [综合] PAT1038 Recover the Smallest Number (30)(贪心)

    题意: 给出一些字符串,把他们拼接起来获得最小数字 要点: 就是贪心,比较字符串大小,如果其中一个是另一个的子串就比较一下它和另一个除去相同子串剩下的部分即可。我一开始想复杂了,一直在考虑前导0的问题,觉得如果前导0放在中间可能会更小,但其实是不可能的,因为放在前面总位数变少了,所以压根不用考虑这么...

    49
    热度
  • [综合] PAT1039 Course List for Student (25)(hash)

    这题一点都不难,但是会有一个点超时,我原本是用map直接写,最后一个点超时,这是因为处理字符串类型的速度是相当慢的,这题学生姓名非常规则,所以hash一下转化为数字速度就会快很多。记录一下这种情况。 #include<iostream> #include<string> #i...

    74
    热度
  • [综合] PAT1040. Longest Symmetric String (25)(回文串:dp)

    题意: 给出一个字符串,求出其中最大的回文串字数 要点: 这题比较好的办法是用dp做: dp[i][j]表示从s[i]到s[j]是否为回文串,用0、1区分 s[i]=s[j]时,dp[i][j]=dp[i+1][j-1];s[i]!=s[j]时,dp[i][j]=0 边界:dp[i][i]=1,...

    67
    热度
  • [综合] PAT1043. Is It a Binary Search Tree (25)(BST)

    题意: 给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果,并输出后序遍历 思路: 这题判断是否为BJT很简单和输出后序遍历都很简单,递归一下即可。我做的时候主要是没想到怎么处理镜像。就按照第一个点和第二个点判断大小来做了一下果然有几个点过不去。后来看了一下...

    87
    热度
  • [综合] PAT1044. Shopping in Mars (25)(二分)

    题意: 给出一系列数字,要求输出子序列使其和等于m,如果没有等于m的子序列就输出和减去m的差最小的子序列 要点: 这题的时间要求是100ms,n的量级是10^5,O(n^2)是肯定不行了,但我一开始算了一下O(nlogn)觉得不大行,就一直在想O(n)的方法,实际上O(nlogn)=10^5*17=...

    16
    热度
  • [综合] PAT1045. Favorite Color Stripe (30)(dp)

    题意: 给出m中颜色作为喜欢的颜色(同时也给出顺序),然后给出一串长度为L的颜色序列,现在要去掉这个序列中的不喜欢的颜色,然后求剩下序列的一个子序列,使得这个子序列表示的颜色顺序符合自己喜欢的颜色的顺序,不一定要所有喜欢的颜色都出现 思路: 就是个简单的dp,一遍过,不过我dp不怎么样所以记录一下:...

    82
    热度
  • [综合] PAT1049. Counting Ones (30)(数学)

    题意: 给出一个n,求从0到n一共出现几个1 思路: 这题还是有点复杂的,看了一下别人的代码,基本思路是一位一位考虑,也就是计算这一位为1的数有几个,用now表示当前位的值,left为左边的数字,right为右边的数字,a为当前位的位数,以3105为例: 当now>=2时,比如分为3105...

    57
    热度
  • [综合] PAT1051. Pop Sequence (25)(栈模拟)

    题意: 有个容量限制为m的栈,分别把1,2,3,…,n入栈,给出一个系列出栈顺序,问这些出栈顺序是否可能. 思路: 我的思路是将出栈顺序一个个入栈,如果当前栈顶等于此时入栈的元素说明正确,如果小于就继续入栈到该元素为止,如果小于说明出栈顺序有错,其中判断一下栈的元素个数是否大于m。过是过了但是感觉写...

    81
    热度