4 KIJamesQi

尚未进行身份认证

暂无相关简介

等级
TA的排名 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]为最大元素 */typedef struct { /*自底向上调整每一个元素

2017-07-23 12:17:35

LightOJ 1062 Crossed Ladders(二分)

int main(int argc, const char * argv[]){ int kase;cin >> kase; while(kase--) { double x, y, c;cin >> x >> y >> c; double l = 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-th permutation of the string.0<n<2310 < n < 2^{31} 思路 先排序,求出当前串有K种组合,如果n大于k,显然impossible; 然后就是每个位置枚举字符,判断下合理性就行了;char s[30];long long f[22];typedef struct item { 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的格子图,上面有空地、障碍物、三个出口和三个小人;每次一条指令让他们往四个方向移动一格,不能动的原地不动,动的就移动一格;一个格子上最多同时只有一个人思路 暴力bfsconst int dx[] = {0, -1, 0, 1};const int dy[] = {1, 0, -1, 0};bool mark[11][11][11][11][11][11];char

2017-02-14 15:16:35

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

题目 求nmn^m所有约数的和在mod 1e9+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 \leq N \leq 10^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 \leq N \leq 100;思路 先求出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 :2016File Name :*****************************************///

2017-02-05 23:29:20

Lightoj1028 欧拉函数

题意 一个十进制数1≤n≤10121 \leq n \leq 10^{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来模拟,一个大的优先,一个小的优先,同时删除、同时加入。struct item1 { int k, p; item1() {} item1(int k, int p) : k(k), p(p) {} bool operator < (const item1& rhs) const { return p <

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>#define min(x, y

2016-10-04 23:16:15

hdu 4822 Tri-war(LCA倍增)

题目链接 给出一棵树,n,3≤n≤105个点n,3 \leq n \leq 10^5个点,然后m次讯问,1≤m≤105m次讯问,1 \leq m \leq 10^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] && v is a

2016-09-24 22:13:50

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

题目链接 给出n个数字,和最小间隔d。从i能走到j的充要条件就是|ai−aj|≥d\vert a_i - a_j \vert \ge d ,求最长的路径长度并输出路径,有多解输出任意一组路径。 思路就是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 \leq l_j &&rj≤ri r_j \leq r_i 。 那么按照l进行排序,l相同的r大的排在前面,然后从后往前扫。const int maxn = 2e5 + 10;struct seg

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博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!