做过一道类似的题 因为是问最短，很容易想到是bfs 对于点x，可以到达点x-1,和点2*x 需要注意的是上界限。 并不是max(m,n) 因为可能先达到比m大，之后再减回来的情况是更优的。 max(2m,2n)肯定是足够的 /************************************************************************* > File Name: code/cf/#295/B.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年08月17日 星期一 04时16分51 …

给一个字符串，问这个字符串中是否26个字母都出现过（大小写只出现一个就算出现过） 开个布尔数组，扫一遍即可。 嘛，做两道水题放松下== 反正也是要清的。 /************************************************************************* > File Name: code/cf/#295/A.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年08月17日 星期一 04时05分12 …

将博客搬至CSDN

题意是说，给定一个有向图，对于每一条边，问是否是s到t的最短路上一定会经过的边． 如果是就输出yes 如果不是，问能否通过减少这条边的权值（减少的权值就是修理费用），使得这条边成为新的最短路上的边． 对于一条边是否一定是最短路上的边，我们可以从s做一遍最短路，然后反响建边，从t再做一遍最短路． 得到两个d1,d2数组 如果一条边d1[u] + d2[v] + w(u, v) = 最短路，那这条边在最短路上的边．但是未必不能缺少． 我们还要判断这条边是否是不能缺少的． 不能缺少的意思是说，如果没有这条边，就不能构成最短路． 那么这条边一定是桥． 我们可以用tarjan算法求桥． 据说是水题，不过图论还没怎么刷，所以对我来说还是很有难度 …

很容易看出来是dp 我们左右一起，一对一对放． 对于每一对，有三种方法，分别是两左，一左一右，两右． 初始区间长度为２n，每次放完后缩小区间长度 ，最后一定是放２个n，这个时候区间长度缩小为２，表明一种满足题意的情况． 状态转移的时候需要分别判断三个状态是否满足题目中给出的k组限制条件． 细节见注释． /************************************************************************* > File Name: code/cf/#314/F.cpp > Author: 111qqz > Email: rkz2013@126.com > …

基础的搜索BFS和DFS,自己找题切吧... 高级搜索的题集就在下面,自己看着办吧... 努力爆搜,努力剪枝吧~~~ 【Level 1】 HDOJ-1429 胜利大逃亡(续)　HDOJ-1885 Key Task HDOJ-1226 超级密码 HDOJ-1664 Different Digits HDOJ-2821 Pusher HDOJ-2128 Tempter of the Bone II HDOJ-3533 Escape HDOJ-4101 Ali and Baba HDOJ-3839 Ancient Messages HDOJ-1685 Booksort HDOJ-2614 Beat HDOJ-3309 Roll The …

＿＿＿＿＿＿ 好蠢，竟然没看出来这道题的不同之处，以为就是个搜 然后样例什么的都过了．．． 结果显然wa... 然后才发现，这道题应该是tsp问题． 解法是先跑一遍bfs, 对于所有的脏点和起点，得到没两个点之间的距离． 然后跑一遍dfs，枚举出所有的组合，同时更新答案． 晚安． /************************************************************************* > File Name: code/poj/rr2688.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: …

比赛的时候没搞出来，really sad. 其实这题很容易啊．．．． 首先，对于lie 的判断应该基于能放的船的个数． 能放的船的个数是随着射的点数的增加而减少的． 射完每个点后更新能放的船的个数，如果这个时候已经无法放下k条船了，说明lie了． 如果所有都射完也没发生，那么就-1. 由于船与串不能相邻，除了最后一条船，每条船实际占的size 应该为a+1 那么很容易知道对于长度为l的区间，能放的船的个数为（l+1）/(a+1) 这是初始能放的船的个数，为最大值． 当射了点b之后，破坏的是b所在的一段最大的没有被射过点的区间的连续性． 做法是找到距离b点最近的左端和右端的被射过的点． 可以用set 搞，找的时候upper_bound …

/************************************************************************* > File Name: code/cf/#315/E.cpp > Author: 111qqz > Email: rkz2013@126.com > Created Time: 2015年08月15日 星期六 13时48分36秒 ************************************************************************/ #include<iostream> …

【2-SAT问题】 现有一个由N个布尔值组成的序列A，给出一些限制关系，比如A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等，要确定A[0..N-1]的值，使得其满足所有限制关系。这个称为SAT问题，特别的，若每种限制关系中最多只对两个元素进行限制，则称为2-SAT问题。 由于在2-SAT问题中，最多只对两个元素进行限制，所以可能的限制关系共有11种： A[x] NOT A[x] A[x] AND A[y] A[x] AND NOT A[y] A[x] OR A[y] A[x] OR NOT A[y] NOT (A[x] AND A[y]) NOT (A[x] OR A[y]) A[x] XOR …