11 2008 档案
URAL 1080. Map Colouring
摘要: BFS,确定每个结点的颜色,发生冲突时输出-1
阅读全文
posted @
2008-11-12 11:52 Joseph 阅读(213) |
评论 (0) 编辑
URAL 1078. Segments
摘要: 预处理所有包含关系,记忆化搜索。
阅读全文
posted @
2008-11-12 11:50 Joseph 阅读(258) |
评论 (0) 编辑
URAL 1095. Nikifor 3
摘要: 因为给出的数字中一定包含1,2,3,4,而且1234是7的同余系。在所有的数字中挑出一组1234,以及所有的0,判断剩下的数字除7的余数,在数的末尾添加相应的由1234组成的四位数,再添上0,就AC了。
阅读全文
posted @
2008-11-11 17:17 Joseph 阅读(346) |
评论 (0) 编辑
URAL 1028. Stars
摘要: 又一道树状数组的题。注意坐标值有可能为0,会导致死循环,都加1就可以了。
阅读全文
posted @
2008-11-10 20:38 Joseph 阅读(311) |
评论 (0) 编辑
URAL 1090. In the army now
摘要: 用了树状数组,尽管还不太理解。归并排序统计逆序对个数也可以。
阅读全文
posted @
2008-11-10 20:12 Joseph 阅读(925) |
评论 (0) 编辑
URAL 1085. Meeting
摘要: 将线路和车站都抽象为结点,bfs计算最短路,注意有月票的人携带的钱看作无穷多
阅读全文
posted @
2008-11-09 17:27 Joseph 阅读(270) |
评论 (0) 编辑
URAL 1060. Flip Game
摘要: 枚举对第一行的操作,根据操作后的状态确定之后每一行如何操作,记录最小的操作次数即为答案
阅读全文
posted @
2008-11-07 19:21 Joseph 阅读(194) |
评论 (0) 编辑
URAL 1056. Computer net
摘要: 首先以1号结点为根建树,计算出每个结点的最大深度,再计算每个结点经过父结点路径的最长距离g[i],g[i]=max(g[father],deep[brother]+2)
阅读全文
posted @
2008-11-07 17:38 Joseph 阅读(257) |
评论 (0) 编辑
URAL 1053. Pinocchio
摘要: 传说中欧几里德发明的求最大公约数的方法
阅读全文
posted @
2008-11-06 20:31 Joseph 阅读(136) |
评论 (0) 编辑
URAL 1049. Brave balloonists
摘要: 先用筛法求出1到10000的所有素数,建立素数表。依次对ai分解质因数,统计所有质因数出现的次数ti,最后的约数个数为 (t1+1)*(t2+1)*(t3+1)*...*(tn+1)
阅读全文
posted @
2008-11-06 18:36 Joseph 阅读(103) |
评论 (0) 编辑
URAL 1045. A funny game
摘要: 要注意数据保证了图是一棵树,树形DP。f[i]表示走到i是否必胜,如果f[j]=true (j是i的孩子) f[i]=false,否则f[i]=true。当f[start]=false时第一个恐怖分子必胜。
阅读全文
posted @
2008-11-06 17:17 Joseph 阅读(194) |
评论 (0) 编辑
URAL 1040. Airline company
摘要: 题目要求与每个顶点相连的所有边编号最大公约数为1,其实只要其中的两条边编号互质,所有边编号的最大公约数一定为1。我们知道相邻的数字一定互质,那么只要与一个顶点相连的所有边中有两条编号相邻,这个顶点就可以符合条件。DFS序列,对边进行编号刚好可以构造出满足要求的解,并且无解的情况是不存在的。
阅读全文
posted @
2008-11-06 16:34 Joseph 阅读(175) |
评论 (0) 编辑
URAL 1039. Anniversary party
摘要: 树形DP,用数组邻接表空间不够,于是将树转化为二叉树AC
阅读全文
posted @
2008-11-05 20:34 Joseph 阅读(138) |
评论 (0) 编辑
URAL 1037 Memory management
摘要: 维护两个堆,一个记录空闲内存,一个记录使用中的内存
阅读全文
posted @
2008-11-05 19:16 Joseph 阅读(143) |
评论 (0) 编辑
URAL 1034 Queens in peaceful positions
摘要: 枚举三个需要调整位置的皇后,调整后只有两种情况,分别判断是否符合要求
阅读全文
posted @
2008-11-05 17:16 Joseph 阅读(124) |
评论 (0) 编辑
URAL 1036 Lucky tickets
摘要: 简单的DP,要注意细节的处理,s为奇数,s最大值为1000(n=50 s=1000,answer=0)
阅读全文
posted @
2008-11-04 17:52 Joseph 阅读(426) |
评论 (0) 编辑
URAL 1031 Railway tickets
摘要: DP,利用很好的优化,在O(n)时间复杂度内解决
s1,s2,s3分别记录距离在l1,l2,l3内的最远点编号,dp时只需根据这三个点更新
阅读全文
posted @
2008-11-04 16:46 Joseph 阅读(197) |
评论 (0) 编辑
URAL 1030 Titanic
摘要: 以地球球心为坐标原点,建立三维坐标系,求出两点坐标,计算直线距离,求出夹角,再乘以半径。
阅读全文
posted @
2008-11-04 16:05 Joseph 阅读(247) |
评论 (0) 编辑
URAL 1029 Ministry
摘要: DP,对每一层扫描两遍
阅读全文
posted @
2008-11-04 14:33 Joseph 阅读(186) |
评论 (0) 编辑
URAL 1024 Permutations
摘要: 找出所有的循环,计算循环长度的最小公倍数
阅读全文
posted @
2008-11-04 11:23 Joseph 阅读(332) |
评论 (2) 编辑