文章列表
这道题也是我拿来测板子的
题意：给定一个r*c(r<=100,c<=100)的矩阵，每个元素表示该点高度，给定初始速度v，当从一点移动到另一点后，速度变为原先的2^(该点高度-移动到的点的高度)，花费时间是1/原先高度，求从1,1到r,c的最短时间
题解：可以推出，每个点速度是一样的，这样就直接最短路了
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
using names ...
- 2012-10-23 22:41
- 浏览 487
- 评论(0)
又是一道最小生成树,拿来测模板;
题意:N个点,坐标给出,然后有M条路已经修好了,给出这M条路的起始点和终点,求需要再修多远的路才能得到最小生成树
题解:把已经修好的路长度算0,然后最小生成树就好了;话说我wa了一次,题目说了全部用64位的运算,我没看到,把坐标改成longlong就过了
好水啊;
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace s ...
- 2012-10-22 13:17
- 浏览 463
- 评论(0)
想比赛前吧模板整理好,就做了一道这个题看看模板
题意:有P个点,用坐标给出,有两种联系方式:1每个点可以和距离在D以内的点相互联系,2有S个专门的卫星通道,两个点直接联系;
求D最小多少可以把这个图连起来
题解:首先不考虑S个卫星通道,先求最小生成树,用卫星通道把最小生成树中最大的S-1个边代替掉,然后剩下的最大的那条边的值
就是能把整个图连起来的D的最小值
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include < ...
- 2012-10-22 12:09
- 浏览 593
- 评论(0)
本来想下午做完了周末好好玩,结果尼玛做了一晚上...
题意:
亚瑟王要在圆桌上召开骑士会议，为了不引发骑士之间的冲突，并且能够让会议的议题有令人满意的结果，每次开会前都必须对出席会议的骑士有如下要求：
1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置；
2、 出席会议的骑士数必须是奇数，这是为了让投票表决议题时都能有结果。
如果出现有某些骑士无法出席所有会议（例如这个骑士憎恨所有的其他骑士），则亚瑟王为了世界和平会强制把他剔除出骑士团。
现在给定准备去开会的骑士数n，再给出m对憎恨对（表示某2个骑士之间使互相憎恨的），问亚瑟王至少要剔除多少个骑士才能顺利召开会议
( 我找网 ...
- 2012-10-19 17:21
- 浏览 949
- 评论(0)
题意：给出一个无向图，要求找出每个割点，以及除去割点之后能把图分成几个连通块
题解：点的双联通，统计割点属于多少个连通块
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;
const int MAXN = 1005 ;
struct type
{
int end , next ;
} ;
type edge[MAXN*MAXN] ;
int head[MAXN] , Count , top ; ...
- 2012-10-18 15:07
- 浏览 638
- 评论(0)
题意:有一些奶牛,他们之间有互相崇拜的关系,并且这个关系是有传递性的,求被所有奶牛崇拜的奶牛数量;
题解:先用强连通缩点,把强连通分量缩成一个点,强连通中的点必然是互相崇拜的,然后再缩点后的图中找
到出度为零的点,如果这些点的数量大于一,那么必然没有解,因为这些点直接没有互相崇拜关系,如果只有
一个点,那么求出这个点对应的强连通分量里面的点的个数就是答案了;
代码搓了点:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;
const ...
- 2012-10-18 10:45
- 浏览 489
- 评论(0)
这道题我比赛的时候懵了，那么简单一道题，我还想成了网络流相关。。。sb了，，，#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdio>
using namespace std ;
ifstream fin ( "input.txt" ) ;
ofstream fout ( "output.txt" ) ;
int n ;
char student[105] ;
int map[ ...
- 2012-10-17 14:31
- 浏览 500
- 评论(0)
这道题是长春的E题,我是看了别人才会做的,这道题是一个并查集的题,将边按从大到小排序,然后依次合并,
这样每次都是按边的权值来计算合并后的值,接下来就是讨论这两个集合谁并入谁,应该是合并后所得值小的
并入值大的,这样就要记录每个集合当前元素个数sum和当前值rank
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std ;
const int MAXN = 200005 ;
int ...
- 2012-10-17 11:22
- 浏览 513
- 评论(0)
我在poj写了175题，都是以前写的，都木有写解题报告==！
我今天才想起来写解题报告，写了几篇发现太多了。。。。
我就把代码打包上传到资源页去了，以后就只写刚做的题的报告了
- 2012-10-16 22:27
- 浏览 473
- 评论(0)
我第一次做codeforces的比赛，以前都在半夜，太懒了就不做，终于有rating了，1421
第一题想懵了，不想做了，看了下第二题，大水题，就是排一下序，找前几的序号，
由于不熟悉它的输入输出re了一次wa了一次，我太水了
#include <iostream>
#include <cstring>
#include <algorithm>
#include <fstream>
using namespace std ;
ifstream fin ( "input.txt" ) ;
ofstream f ...
- 2012-10-16 21:30
- 浏览 583
- 评论(0)
这道题其实就是求割点数量
用点双联通
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
using namespace std ;
const int MAXN = 1001 ;
const int MAXM = 2*MAXN * MAXN ;
const int INF = 99999999 ;
struct type
{
int end , next ;
} ;
type edge[MAXM] ...
- 2012-10-16 13:09
- 浏览 564
- 评论(0)
题意就是要求割点
用tarjan求强连通
#include <iostream>
#include <cstring>
using namespace std ;
const int MAXN = 1100 ;
const int MAXM = MAXN * MAXN ;
struct type
{
int to , next ;
} ;
type edge[MAXM] ;
int head[MAXN] , Count , low[MAXN] , dfn[MAXN] , stack[MAXN] , top , ans ...
- 2012-10-16 13:04
- 浏览 458
- 评论(0)
这是一个全局最小割的题：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std ;
const int INF = 999999999 ;
const int MAXN = 505 ;
int map[MAXN][MAXN] , low[MAXN] , vis[MAXN] , last , pre , N , flag ;
bool bfs() ;
void prim( i ...
- 2012-10-16 12:05
- 浏览 760
- 评论(0)
经典网络流
sap：
#include <iostream>
#include <cstring>
#include <queue>
#include <stack>
using namespace std ;
const int MAXN = 500 ;
const int MAXM = 25000 ;
const int INF = 9999999 ;
int map[MAXN+10][MAXN+10] ;
int dis[MAXN+10] , gap[MAXN+10] , pre[MAXN+10] ;
i ...
- 2012-10-16 12:02
- 浏览 408
- 评论(0)
题意：最长上升子序列
题解：虽然是经典dp，但我用网络流做啊，dp我一点不懂啊怎么办
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std ;
const int INF = 99999999 ;
const int MAXN = 1505 ;
const int MAXM = MAXN * 100 ;
struct type
{
int end , next , w ;
...
- 2012-10-16 11:59
- 浏览 382
- 评论(0)