4 KIJamesQi

尚未进行身份认证

暂无相关描述

等级
博文 305
排名 1w+

AOE关键路径

时间发生的先后顺序存在一定时间上的限制,时间A必须在其前驱活动发生完之后才能发生;边:表示活动的持续时间,两个事件之间必须先进行相应的活动时间;点:表示事件四个关键属性Ve[i]:表示事件i发生的最早时间;Vl[i]:表示事件i最晚发生的时间e[i]:表示活动i最早发生的时间;l[i]:表示活动i最晚发生的时间;

2017-12-06 21:39:14

考研数据结构----MaxHeap

原理这里我们建立的是最大堆,用完全二叉树来表示这个堆;1.堆顶比两棵子树中的任何元素都要大;2.每棵子树同样满足这个条件;即根是树中最大值,没课子树的根是子树中的最大值所以我们在构造的时候要先从最小的子树开始构造,这样才能构造更大的子树/**建立大顶堆,a[1]为最大元素*/typedefstruct{/*自底向上调整每一个元素

2017-07-23 12:17:35

LightOJ 1062 Crossed Ladders(二分)

intmain(intargc,constchar*argv[]){intkase;cin>>kase;while(kase--){doublex,y,c;cin>>x>>y>>c;doublel=0,r=min(x,y);Rep(i,1,100){

2017-02-17 19:05:43

LightOJ 1061 N Queen Again(搜索+状压DP)

题目给出一张8*8的图,上面有8个皇后,现在每次只能移动一个皇后往同一个方向走任意步,总共有8个方向;问最少需要多少步使得所有皇后相互不会攻击对方?思路单纯的暴搜是不行的,时空都会炸。假如我们知道最终每个皇后应该在的位置,然后再来计算最少步数就会简单不少,这里可以用状压来做;因为最终的情况是每行有一个皇后,所以我没需要记录每行皇后所在的列,然后枚举哪个皇后移动到这个位置

2017-02-17 19:02:29

LightOJ 1060 nth Permutation(组合数--k大字典序)

题目给一串长度不超过20的字符串,求n-thpermutationofthestring.0<n<2310<n<2^{31}思路先排序,求出当前串有K种组合,如果n大于k,显然impossible;然后就是每个位置枚举字符,判断下合理性就行了;chars[30];longlongf[22];typedefstructitem{cha

2017-02-17 18:43:53

LightOJ 1057 Collecting Gold(状压DP)

题目n∗m,(n,m)<(20,20)n*m,(n,m)<(20,20)的格子图上有一个人,和不超过15个的金矿;求这个人从当前位置出发获取所有金矿然后再回到这个位置需要走的最少路程?每次只能往邻近的四个方向走;思路因为没有障碍物,所以算两个格子间的距离很方便;开始用的穷举所有的获取金矿的先后顺序,然后TLE了;最后就状压过了,dp[sta][i]表示达到状态sta

2017-02-14 15:25:21

LightOJ 1055 Going Together (暴力搜索……繁琐)

题目一张n*n的格子图,上面有空地、障碍物、三个出口和三个小人;每次一条指令让他们往四个方向移动一格,不能动的原地不动,动的就移动一格;一个格子上最多同时只有一个人思路暴力bfsconstintdx[]={0,-1,0,1};constintdy[]={1,0,-1,0};boolmark[11][11][11][11][11][11];char

2017-02-14 15:16:35

lightoj1054 Efficient Pseudo Code(欧拉函数+Divisor function)

题目求nmn^m所有约数的和在mod1e9+71e9+7的结果;思路数学知识点n可以写成n=px11∗px22∗...n=p_1^{x1}*p_2^{x2}*...,那么nm=pm∗x11∗pm∗x22...n^m=p_1^{m*x1}*p_2^{m*x2}...这样就可以用下面这个公式求解了,具体数学看上面的链接,这里x取1;σx(n)=∏ri

2017-02-14 15:07:04

lightoj1052 String Growth (矩阵求解Fibonacci)

题意给出一个只含有{a,b}两种字符的串,每次扩展就用ab把串中的b给替换掉,同时用b把a给替换掉;然后给出第n次扩展后的串长为x,第m次扩展后的串长为y,求第k次扩展后的串长为多少?思路首先简单的扩展几个串可以发现,a的个数和b的个数都是fibonacci数,且按照fibonacci数数增长;这样我们假设一开始由p个a,q个b;然后求出第n次和第m次的fibonacci数,

2017-02-14 14:52:57

lightoj1038 - Race to 1 Again(期望DP)

题意给出一个1≤N≤1051\leqN\leq10^5,每次选其一个约数相除,知道得到结果为1为止,求期望次数;思路期望dp,求x平均除多少次得到1;假设x有c个因子(含1和本身),E[x]表示结果;那么E[x]=(E[1]+E[a1]+E[a2]+…+E[x]+c)/c;加c是因为每次要多走一步才能得到ai,每次选者的概率为1/c;

2017-02-05 23:41:25

lightoj1035 欧拉函数(暴力)

题意用表达式x=px11px22...x=p_1^{x_1}p_2^{x_2}...的形式表示N!,1≤N≤1001\leqN\leq100;思路先求出100以内的素数,然后暴力分解,记录每个素数出现的次数;/*****************************************Author:Crazy_AC(JamesQi)Time

2017-02-05 23:35:13

lightoj1037 状压DP(入门级)

题意简单思路dp[sta]表示状态为sta时需要打的最少次数,dp[0]=0;/*****************************************Author:Crazy_AC(JamesQi)Time:2016FileName:*****************************************///

2017-02-05 23:29:20

Lightoj1028 欧拉函数

题意一个十进制数1≤n≤10121\leqn\leq10^{12},现在用base进制来表示,问有多少种表示方法使得最后一位上的数为0?等同于求出n有多少种约数,即n%base==0n\%base==0;思路开始想的是枚举sqrt内的数,TLE了,因为有10000组数据。。。。有一个表达式x=px11∗px22∗px33...x=p_{1}^{x

2017-02-05 14:59:55

poj3481 Double Queue(set模拟or splay)

题目链接题目意思明确。可以用两个set来模拟,一个大的优先,一个小的优先,同时删除、同时加入。structitem1{intk,p;item1(){}item1(intk,intp):k(k),p(p){}booloperator<(constitem1&rhs)const{returnp<

2016-10-24 16:45:24

hdu5919 Sequence II(主席树求区间数种数和k大查找)

题目链接给你一个含有n个数的数列,m次查询。每次查询给出l和r两个数,表示子序列a[l]…a[r],然后子序列中有k种数(需要自己求出k值),p[j]表示第j种数从左到右第一次出现的位置,那么会得到p[1]…p[k]&&p[1]<p[2]<…<p[k]。然后倒着建立主席树,然后就类似区间k小的查找。#include<stdio.h>#definemin(x,y

2016-10-04 23:16:15

hdu 4822 Tri-war(LCA倍增)

题目链接给出一棵树,n,3≤n≤105个点n,3\leqn\leq10^5个点,然后m次讯问,1≤m≤105m次讯问,1\leqm\leq10^5,时限是10000ms,显然每次讯问要控制在log级。每次讯问给出a,b,c三个不同的点,对于每个点求出树上的点到它的距离严格小于到其他两个点的距离的个数。如果是两个点,可以找到两个点的路径中点,把树分成分别包含a,b

2016-09-28 21:23:04

Gym 100543A Parades

题目链接一颗有n个点的树,然后上面有m条关系链[u,v](就是u到v的路径),选出x条链,相互没有边重合,但是点是可以重合的。求x的最大值。思路:树形dp+状压dp。对于以u为根的子树,dp[u]表示这棵子树能有的最大x的值(也就是被选中的x条链满足题目条件且每条链的所有边都在子树中,不经过[fa,u])。第一部分就是dp[u]=∑dp[v]&&visa

2016-09-24 22:13:50

CodeForces 474E Pillars(线断树区间最大)

题目链接给出n个数字,和最小间隔d。从i能走到j的充要条件就是|ai−aj|≥d\verta_i-a_j\vert\ged,求最长的路径长度并输出路径,有多解输出任意一组路径。思路就是dp[i]表示以i结尾的最长路径长度,dp[i]<-{pre{dp[j]}里面满足条件且最长的长度}+1,这里查找的就可以是区间最大值的查找,因为要记录路径,所以里面还需要最大值

2016-09-19 19:59:56

Codeforces 652D(一维树状数组)

题目链接有n根木棍,每根的范围是[li,ri][l_i,r_i],没有两个的rir_i是想通的,问每根棍子完全覆盖多少根棍子。第i根棍子覆盖第j根棍子,必要条件就是li≤ljl_i\leql_j&&rj≤rir_j\leqr_i。那么按照l进行排序,l相同的r大的排在前面,然后从后往前扫。constintmaxn=2e5+10;structseg

2016-09-19 16:40:46

csu1808 地铁(最短路)

一个城市中有n个站m条线路(指直接相连接u-v),也就是和城市地铁一样,在某个站换线需要花额外的时间,求1号站到n号站的最短时间消耗。猛的一看就是普通的最短路问题,但是实际需要改变很多,不能单纯的按照原来的方式求解dis[v]表示到v的最小时间花费。因为你无法知道这个最小值是由哪条线路过来的,会直接影响后面的换线时间消耗。所以我们纪录走i号线到v的最小时间,这样就能明白起最小

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