题意是说,给定一个有向图,对于每一条边,问是否是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 …
阅读更多