2 KGV093

尚未进行身份认证

Looking back I see a setting sun, and watch my shadow fade into the floor. I am left standing on the edge, wondering how we got this far.

等级
博文 346
排名 1w+

poj 1208(链表)

传送门题意:(转自https://www.cnblogs.com/zhurb/p/5839701.html)给定一个长度n,有0~n-1编号的箱子和位置,起始个编号的箱子放在相同编号的位置。有一系列操作:moveaontob,将a,b上面的箱子放回初始位置,并将a放到b箱上。moveaoverb,将a上面的箱子放回初始位置,并将a放到b箱最上方。pilea...

2018-11-08 22:24:12

Luogu 3952(NOIP2017 D1T2 时间复杂度)(模拟+栈)

传送门题意:给你T组简化代码,每组L行,给一个复杂度。模拟循环,计算复杂度,判断语法是否有误以及给定复杂度是否正确。 题解:略(用栈模拟整个过程),方法基本就这一个,具体实现方法千变万化(代码中有注释) 本题大概有两大难点:①同一层中可能有若干个平行的循环(如样例第五个程序),实际复杂度应取其中最大复杂度②对于没有进入的循环不能直接跳过不处理(因为后面出现的语法...

2018-11-05 22:12:07

Luogu 4779(dijkstra+线段树优化)(dijkstra+堆优化)

传送门题意:模板题,求有向非负权图的单源最短路题解:明说了要卡SPFA,所以只能dijkstra+数据结构优化,不管用堆还是线段树,只有能到O(nlogn)就OK。实测线段树略快。注意:每次“出队”时将当前点赋值为INF(如果硬要做删除操作就只有上平衡树了233),线段树在判断“队列为空”的边界时直接判断全局最小值是否等于INF即可。线段树优化dijkstra:#in...

2018-08-20 20:57:18

浅谈字符串哈希

一.分类1.单模哈希g(s)=f(s)%mod注意:①MOD要是质数(使模的结果等概率分布在0~mod-1)②1e9左右不等于1e9+7或1e9+92.双模哈希3.自然溢出(unsignedlonglong) 二.比较  速度 正确率 自然溢出(国内不会卡)(不建议用于POI) 1 2 单模哈希 2 3 双模哈希(绝对...

2018-08-20 16:40:48

Luogu 1967(货车运输)(最大生成森林+LCA)

传送门题意:有 nn 座城市,编号从 11 到 nn ,城市之间有 mm 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 qq 辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。题解:由于要装尽量多的货物,所以先用kruskal跑一个最大生成森林,然后再因为存在短板效应,所以在这些生成的树上跑倍增(可参考倍增求LCA),求出每条询问的路径上的最...

2018-08-19 18:41:55

Luogu 1395(树形dp)

传送门题意:树上选一个点使所有点到它的距离之和最小,输出其编号和最小距离之和,如有多个,输出编号最小的一个题解:设dp[i]位选i点时所有点到它的距离之和,考虑父子关系可得转移方程dp[now]=dp[father]+(n-size[now])-size[now],问题就在于从哪里开始转移?可以求得dp[1],然后向下转移,至于dp[1]怎么求:dp[1]=Σsize[i](i≠1)。...

2018-08-16 21:03:25

bzoj 2208(tarjan+拓扑排序+bitset)

传送门题意:求一个有向图中可达顶点对数(每个点可达其自身)题解:听说可以直接用floyd传递闭包+bitset,但是为了提高效率顺便复习算法,还是采用tarjan先缩点然后反向建图在DAG上一边拓扑排序一边用bitset传递可达点集。去年的bitset今年终于会用了......#include<cstdio>#include<cstring>#incl...

2018-08-16 14:39:55

Luogu 1631(优先队列)

传送门题意:有两个长度都是N的序列A和B,在A和B中各取一个数相加可以得到个和,求这个和中最小的N个题解:先排序得到两个递增的数列a和b,然后用小根堆维护a+b,每次取队首,如果这次取出的是a[i]+b[j],则往队列中插入a[i]+b[j+1],所以需要另开一个数组p[i]来记录每一个a[i]应该匹配的b。正确性显然:取前k小值等价于取k次当前最小值,如果a[i]+b[j]都没被取到...

2018-08-15 19:56:00

数论基本性质证明(欧拉函数、莫比乌斯反演)

一年前学的数论、半年前补的证明,今日附一句歌词:Lightswillguideyouhome,andigniteyourbones,andIwilltrytofixyou.一起送给OI~

2018-05-23 17:19:58

hdu 1576(扩展欧几里得)

A/BTimeLimit:1000/1000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):7677    AcceptedSubmission(s):6112ProblemDescription要求(A/B)%9973,但由于A很大,我们只给出n(n=A%9973)(我...

2018-05-04 21:28:21

Luogu 1279 字串距离(dp)

题目描述设有字符串X,我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串,如字符串X为”abcbcd”,则字符串“abcb□cd”,“□a□bcbcd□”和“abcb□cd□”都是X的扩展串,这里“□”代表空格字符。如果A1是字符串A的扩展串,B1是字符串B的扩展串,A1与B1具有相同的长度,那么我扪定义字符串A1与B1的距离为相应位置上的字符的距离总和,而两个非空格字符的距离定义...

2018-03-30 16:57:29

Luogu 1160(双向链表)

三个月不见,本蒟蒻阴魂不散死灰复燃,先来点水题找找感觉。题意:一个学校里老师要将班上N个同学排成一列,同学被编号为1~N,他采取如下的方法:1.先将1号同学安排进队列,这时队列中只有他一个人;2.2~N号同学依次入列,编号为i的同学入列方式为:老师指定编号为i的同学站在编号为1~i-1中某位同学(即之前已经入列的同学)的左边或右边;3.从队列中去掉

2018-02-01 22:01:39

NOIP 2017题解(更新ing)

D1T1:小凯的疑惑题目:求一个最大的正整数c,使得ax+by=c(其中a,b为互质的两个正整数)没有非负正整数解。正解:(想要直接数学推导的就去找数竞大佬吧。。。下面说说考试时怎么办——“一猜想+两验证”)①打表找规律(不急,后面有严格证明)观察不为-1的所有元素可不完全归纳所求最大的c即ab-a-b。下面是赛后打表验证的代码:#include#include

2017-12-07 23:20:17

NOIP 2017总结

NOIP一周以后CDQZ_GXOI队再一次重聚在机房,也许这是最后一次在机房看见大部分昔日的战友。与往日不同的是,大多数身旁的人都是省一,而本人并不是。 官方成绩是30+190=220分,也许历史上很少有人考出类似的分数(估计去年来考第一天都有100多分),就连hfu老师都又气又笑地问我:“你介(这)个第一天整(怎)么连山(三)~~~十分都考出来啦?!”。第二天破釜沉舟拼来一个正常的分数,...

2017-11-21 21:48:55

codevs 2178(中缀表达式求值)

中缀表达式a+b*c+(d*e+f)*g,其转换成后缀表达式则为abc*+de*f+g*+。转换过程需要用到栈,具体过程如下:1)如果遇到操作数,我们就直接将其输出。2)如果遇到操作符,则我们将其放入到栈中,遇到左括号时我们也将其放入栈中。3)如果遇到一个右括号,则将栈元素弹出,将弹出的操作符输出直到遇到左括号为止。注意,左括号只弹出并不

2017-11-10 21:58:55

Luogu 3371(dijkstra堆优化)

传送门模板题。再说一遍:dijkstra不能用入队标记。不是“不要”,是“不能”!!!#include#include#include#include#includeusingnamespacestd;constintN=10004,M=500004;intn,m,S;inthead[N],etot=0,dis[N];structEDGE{ intv,

2017-11-09 21:27:31

hihocoder 1043(完全背包)

传送门模板题,正着for。#include#include#include#includeusingnamespacestd;intc[502],v[502];intn,m;intf[100004];inlineintread(){ intx=0;charc=getchar(); while(c'9')c=getchar(); while(c

2017-11-09 20:40:32

hihocoder 1038(01背包)

传送门模板题,倒着for,复杂度O(n*maxV)。#include#include#include#includeusingnamespacestd;intc[502],v[502];intn,m;intf[100004];inlineintread(){ intx=0;charc=getchar(); while(c'9')c=getch

2017-11-09 20:36:39

hihocoder 1098(kruskal)

传送门模板题,原计划觉得kruskal稳如狗根本不用管,但是保险起见还是敲一遍,如果忘了就吃键盘。#include#include#include#includeusingnamespacestd;constintN=1e5+4,M=1e6+4;intn,m,fa[N];structEDGE{ intu,v,w; friendbooloperator

2017-11-09 19:57:18

hihocoder 1032(manacher)

传送门模板题。关键:记一个最远延伸的起点id。#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;constintN=1e6+4;chars[N];intp[N<<1];in...

2017-11-09 19:46:07
奖章
    暂无奖章