文章列表
这题也是并查集，最近并查集写的有点多
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;
int father[50005] ;
int find( int x )
{
if( father[x] != x ) father[x] = find( father[x] ) ;
return father[x] ;
}
void Union( int a , int b )
{
int f ...
- 2012-10-16 11:53
- 浏览 287
- 评论(0)
题意：有N个点；多条路；事先每个点都被摧毁；输入两个数字A,B代表这两个点有一条路，字符O和数字A，代表修复这个点；若输入S，A，B代表询问A，B是否连通；
题解：并查集
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;
const int MAXN = 1005 ;
struct type
{
int x , y ;
} ;
type Point[MAXN] ;
int father[MAXN] ; ...
- 2012-10-16 11:49
- 浏览 352
- 评论(0)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std ;
const int MAXN = 30005 ;
int father[MAXN] ;
int find( int x )
{
if( father[x] != x ) father[x] = find( father[x] ) ;
return father[x] ;
}
void U ...
- 2012-10-16 11:44
- 浏览 551
- 评论(0)
题意：T代表case数量，N代表N个人，M代表将要输入M组关系，每组关系有一个字符和两个整数ch，A，B，如果ch是‘A’，代表询问A,B是否是同一集合，‘D’代表A和B是同一集合
题解：并查集
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;
const int INF = 99999999 ;
const int MAXN = 100005 ;
int father[MAXN] ;
int rank[MAXN] ...
- 2012-10-16 11:41
- 浏览 460
- 评论(0)
题意：中文题，自己读吧
题解：并查集，只不过增加了一个当前点到与根节点的关系
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;
const int MAXN = 50005 ;
int N ;
int father[MAXN] ;
int rank[MAXN*2] ;
int change( int X )
{
switch( X )
{
case 0 : retur ...
- 2012-10-16 11:35
- 浏览 478
- 评论(0)
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;
int num[6] ;
bool vis[6] ;
int n , Max ;
void dfs( int depth )
{
int i , j ;
if( depth == 4 )
{
int flag = 0 , FLAG = 0 ;
int sum = 0 ;
fo ...
- 2012-10-16 11:24
- 浏览 504
- 评论(0)
这道题是长春赛区的K题；
题意：(K^r)+(K^(r-1))+....+K+1=N，或：(K^r)+(K^(r-1))+....+K=N；给出N，求K和R的值，如果有多个答案，输出R*K最小的那个；k>=2;N<=10^12;
题解：R一定是小于40的（K大于等于2），枚举R的值，R的值一定的情况下，N相对于K是单调递增的，故用二分求答案
#include <iostream>
#include <cstring>
#include <cstdio>
#include <fstream>
using namespace ...
- 2012-10-16 11:22
- 浏览 487
- 评论(0)
题意：还是最近公共祖先
题解：这个题只能用tarjan离线算
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std ;
const int MAXN = 40005 ;
struct type
{
int end , next ;
int w ;
} ;
type edge[MAXN*2] , qedge[MAXN*2] ;
int M , N , K ...
- 2012-10-16 11:14
- 浏览 534
- 评论(0)
题意：最近公共祖先
题解：最近公共祖先
代码：
1，裸地在线算法
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;
const int MAXN = 1000 ;
int N , M ;
int father[MAXN] ;
int count[MAXN] ;
bool vis[MAXN] ;
int main()
{
int i , j , a , b ;
int ...
- 2012-10-16 11:08
- 浏览 577
- 评论(0)
题意：最近公共祖先
题解：就是最近公共祖先吧。。
代码：用裸的在线算法，就想写tarjan了
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;
const int MAXN = 10005 ;
int father[MAXN] ;
int N ;
bool vis[MAXN] ;
int main()
{
int T ;
int i , j ;
int a , b ...
- 2012-10-16 11:03
- 浏览 539
- 评论(0)
题意：给一个100以内的整数，如果能分成两个偶数输出YES，否则输出NO
题解：水题
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std ;
int main()
{
int n , i , j , flag = 0 ;
scanf( "%d" , & n ) ;
for( i = 2 ; i < n ; i += 2 )
for( j = 2 ; j & ...
- 2012-10-16 10:56
- 浏览 447
- 评论(0)