- 题意是说,给定一个有向图,对于每一条边,问是否是s到t的最短路上一定会经过的边. - 如果是就输出yes - 如果不是,问能否通过减少这条边的权值(减少的权值就是修理费用),使得这条边成为新的最短路上的边. 
 阅读更多
- 很容易看出来是dp - 我们左右一起,一对一对放. - 对于每一对,有三种方法,分别是两左,一左一右,两右. - 初始区间长度为2n,每次放完后缩小区间长度 ,最后一定是放2个n,这个时候区间长度缩小为2,表明一种满足题意的情况. 
 阅读更多
- 比赛的时候没搞出来,really sad. 其实这题很容易啊.... 首先,对于lie 的判断应该基于能放的船的个数. 能放的船的个数是随着射的点数的增加而减少的. 射完每个点后更新能放的船的个数,如果这个时候已经无法放下k条船了,说明lie了. 如果所有都射完也没发生,那么就-1. 
 阅读更多
- 1/************************************************************************* 2 > File Name: code/cf/#315/E.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月15日 星期六 13时48分36秒 6 ************************************************************************/ 7 …
 阅读更多
- 【2-SAT问题】(转自kuangbin的博客)2015-08-15 · 5 min read- 【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问题。
 阅读更多
- D. Symmetric and Transitive - time limit per test - 1.5 seconds - memory limit per test - 256 megabytes - input - standard input - output - standard output - Little Johnny has recently learned about set theory. Now he is studying binary relations. You've probably heard the term "equivalence relation". These relations are very … 
 阅读更多