2 卯足劲过样例

尚未进行身份认证

暂无相关描述

等级
博文 181
排名 3w+

字符串比较

#include<bits/stdc++.h>usingnamespacestd;intcom(char*A,char*B){if(A==B)returnstrlen(B);int*a,*b;char*a1,*b1;a=(int*)A,b=(int*)B;while(*a++==*b++);///I...

2019-07-14 19:07:39

二分查找总结

不同情形下的二分查找策略:https://segmentfault.com/a/1190000016825704

2019-03-24 14:59:06

八数码 IDA* A *比较总结 HDU1043 POJ1077

这是一个经典的搜索题,做法很多可以详见此题的八境界做法,这里只阐述A*与IDA*算法。A*算法:简单来说是带估值函数的广搜。不同之处在于:对每个放入队列(opentable)的节点计算估值函数h(x),然后进行排序。这样出队时的顺序就不是自然顺序,而是有导向性的一个顺序,这样可以比直接搜索能更快的到达目标节点。缺点:A*算法与bfs一样,都是搜索当前节点下...

2019-03-17 23:41:33

leetcode128 最长连续序列

此题难就难在数组为排序且时间复杂度在o(n)注意此题目中如果数列[2,2,3]这样的数组,连续的数为[2,3]思路:1、如果给我们一个数组我们可能会这样做:先取第一个元素,假如是k。然后查找数组是否有k-1和k+1这两个数,然后递归查找。查找完后把当前数以及找到的其他连续的数删除。重复下去,可知每个数最多遍历一次,所以时间复杂度为o(n),判断数组众是否存在某个数可借助hash_m...

2019-02-17 17:20:02

和至少为 K 的最短子数组(双端队列实现单调栈)leetcode862

思路::1、首先求数列的前缀和S[n] 则任意一段的子序列和S[a,b]=s[b]-s[a-1] 2、用双端队列维护这样一个单调栈 假设i<j<k,且s[i]>s[j]则 a.ifs[k]-s[i]>=K→s[k]-s[j]>=k,因此此时的s[i]可以被丢弃  b.有贪心思想可知这个序列不可能以负数或0开头或者结尾所以如果存在s...

2019-02-17 16:50:10

北大算法考题(思维)

#include<bits/stdc++.h>usingnamespacestd;intn;intfindKnown(boolrelation[][10]){ //relation代表了n个人的关系,为一个NxN的方阵 //relation[i][j]代表从i到j是否有边,有边为true,无边为false inti; //第一阶段 int...

2019-01-07 20:06:36

scrapy爬去知乎用户+代理池实现

spider:#-*-coding:utf-8-*-importjsonfromscrapyimportSpider,Requestfromzhihuuser.itemsimportUserItem#https://www.cnblogs.com/lei0213/p/7904994.htmlclassZhihuSpider(Spider):...

2018-10-22 17:08:11

hdu4281 状态压缩dp(mtsp)+树状数组

#include<bits/stdc++.h>#defineinf0x3f3f3f3fusingnamespacestd;constintmaxn=17;/*这里参考大佬的代码,去掉初始位进行二进制枚举*/intn,m,maxs,lim,cnt;intx[maxn],y[maxn],c[maxn];intdp[1<<maxn];///某状态...

2018-10-10 22:31:35

求给定区间外有多少个不同的数(区间倍增+主席树)

思路:求区间不同个数自然很容易想到主席树/莫队,但是这里是区间外,怎么处理呢?求区间内不同的个数给定的是连续的范围,而区间外的则是一个断开的,所以应该要想到把两个区间拼接在一起。怎么拼接呢,令a[i+n]=a[i],即多保存一份副本在区间外,这样恰当,当求区间(1,L)和区间(R,,n)时实际上转化成求区间(R,L+n),这样就把断开的区间变成连续的区间,用主席树或莫队解决。#include...

2018-07-23 21:37:13

骑士周游 贪心优化

思路:在原本直接回溯版本的基础上,走下一步的时候考虑下一步的下一步可行解的数量,按可行解的数量从小到大的顺序选择下一步。优化出来的效率高很多,再次感受到算法的魅力。/*输入n*n的棋盘,输出从给定位置出发的马踏棋盘的路径*/#include#defineinf0x3f3f3f3f#definedebugcout<<"debug___________"<<endlusingna

2018-05-10 13:56:07

负值01背包

题意:n头牛,每头牛有一个幽默值和聪明值(有负数),问如何从中选择k头牛,使得幽默值和聪明值的和非负且最大。思路:把问题看成01背包,背包的总容量为幽默值的和,每一头牛的幽默值和聪明值分别看成是物品的价值和体积。因为幽默值有可能为负数,不能做数组的下标,所以要先移位。#include#include#include#include#defineinf0x3f3f3f3fus

2018-04-15 16:31:02

hdu1495 隐式图bfs

题意:中文思路:这道题思路还是比较明显的,不过有几个地方可以剪枝,降低复杂度。初始状态(s,0,0)目标状态(1/2s,1/2s,0)。每次操作其实无非(s-&amp;gt;a,s-&amp;gt;b,a-&amp;gt;b,a-&amp;gt;s,b-&amp;gt;s,b-&amp;gt;a) 虽然如此,自己做的时候还是卡在了自己捉急的编程技巧上。下面附上自己tle的代码和别人的ac代码。tle:#include&amp;lt;cstdio&amp;gt;...

2018-03-29 13:35:38

poj2917 构造+因子个数

链接:https://www.nowcoder.com/acm/contest/90/F来源:牛客网#include#include#include#include#defineMAX40005intprime[MAX];intvis[MAX];intidx;intcal(intn){intret=1;intsyz[MAX];

2018-03-24 20:52:39

逆向思维题

链接:https://www.nowcoder.com/acm/contest/90/J来源:牛客网题目描述牛客网是IT求职神器,提供海量C++、JAVA、前端等职业笔试题库,在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的编程。作为acmer的小A,牛客网是他首选的题库。小A是一个中度强迫症患者,每次做数组有关的题目都

2018-03-24 19:49:48

hysbz1296 三维dp+01背包

题意:中文思路:定义dp[i][j][w]为第i个位置涂w颜色,并且往左涂j次后的最大正确颜色。则dp[i][j][w]=max(dp[i-1][j][w],dp[i-1][j-1])+1,dp[i][j][!w]=max(dp[i-1][j-1][w],dp[i-1][j][!w]).(这里注意因为相连两个如果涂同样的颜色,只需涂一次。然后再背包一下就好了。不过背包要注意的是,因为每次进行的

2018-03-22 16:30:56

goj 1462 思维+并查集

思路:首先,如果按照正着走某一条桥拆了的话,其对应着的是反着走某一条桥被新建了。所以可以把题目想象成一开始都没有桥连通。先把每条桥能使用的时间从大到小排序(因为最后拆的桥对应逆向思维的第一条建的桥),然后用并查集判断一下接下来要建桥的两个点是否已经连通。若之前没有连通,建桥后连通,说明这是关键的一条桥,学生会起义。#include#include#include#include

2018-03-20 17:30:10

goj1461 思维

思路:首先计算出任意一个位置的'1'最长可以向左延伸的距离。然后遍历每一列,按延伸值从小到大排序一次,则下面的始终可以覆盖上面。从最下面开始往上走求最大的面积。/*记录每个点能够向左延展的距离,定义状态dp[j][i]代表第j列的第i行的元素向左延展的最远距离,(之所以把列写在前面是为了后面的排序)然后我们对这个距离排序,从大到小,每个上面的都可以被下面的拓展,那么枚举每个右下角,取最大

2018-03-20 17:23:37

goj 1460 dag的最小路径覆盖

思路:直接把每一个相邻的植物都用边连起来,然后求一次最小路径覆盖就可以了。注意:匈牙利算法返回1代表找到一条增广路,对应一个匹配。最小路径覆盖=最大独立集=节点数-最大匹配数。#include#include#include#includeusingnamespacestd;constintmaxn=100;chars[maxn][maxn];inth,w,

2018-03-20 17:18:33

hdu2376 最小区间覆盖(水题)

题意:vj上有中文版思路:见代码;注意剪枝就行了这题。#include#include#include#includeusingnamespacestd;constintmaxn=1e6+50;intt,n,st,ed,cnt,maxr;structCOW{ intl,r;}c[maxn];boolcmp(COWa,COWb){ if(a.

2018-03-18 00:49:41

hihocoder1705 用set排序

题目:中文思路上这题不难想到:首先从左边扫一遍位置,记录每个空位置左边连续的空位置,然后再从右扫一遍,记录每个空位置右边的连续空位置.(注意把这些空位置放入set中去).然后把set内的首元素拿出来就是满足条件的一个座位。然后把这个座位标记为坐上,在set中删掉,更新以这个位置为分界的左边的椅子和右边的椅子,重复操作。比较难想到的是用set自带的排序来做,开始我用优先队列来做,发现删除

2018-03-18 00:45:08
奖章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!