HDOJ1232:畅通工程——并查集简单应用

Problem Description
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?

Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( #include #include int father[1001]; int FindGF(int a)//找祖父节点 { while (father[a] != a) a = father[a]; return a; } void Branch(int a, int b)//合并不同的祖父节点 { int fx, fy; fx = FindGF(a); fy = FindGF(b); if (fx != fy) father[fx] = fy; } int main() { int n, m, i, x, y, ans; while (scanf(“%d”, &n) && n != 0) { for (i = 1; i

HDOJ3926:Hand in hand——并查集、同构图应用

Problem Description
In order to get rid of Conan, Kaitou KID disguises himself as a teacher in the kindergarten. He knows kids love games and works out a new game called “hand in hand”.

Initially kids run on the playground randomly. When Kid says “stop”, kids catch others’ hands immediately. One hand can catch any other hand randomly. It’s weird to have more than two hands get together so one hand grabs at most one other hand. After kids stop moving they form a graph.

Everybody takes a look at the graph and repeat the above steps again to form another graph. Now Kid has a question for his kids: “Are the two graph isomorphism?”

Input
The first line contains a single positive integer T( T D_Double同学的。
首先考虑到每个节点的度数最多只能是2(每人两只手)。最终这些学生可能会被分成多组,每组是一个环形圆圈,或者是一条链。

题目要判断两个已经连好的图是否是”同构图”,。这里所谓的同构图是指两个图组成的不同的圆圈,链条,他们各个所对应的数量都是相等的。

那么我们只需要用并查集把连这的都合并起来,如果发现有环,就进行标识。然后把两个图的并查集按照每颗树的节点个数大小排序,如果个数相同,那么有环的都放在前面。 然后,只要一一比较两个已排序的数组,只要发现有一个是不同的,就不是同构图。

代码:

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxN = 10001;

int n, m, n2, m2;
int father[maxN], PT[maxN], isCircle[maxN];
//memset(0, isCircle, sizeof(isCircle));
struct node
{
    int num, isCircle;
    friend bool operator b.num;
        return a.isCircle>b.isCircle;
    }
}an[maxN], bn[maxN];

int findset(int x)
{
    if (x == father[x]) return x;
    return father[x] = findset(father[x]);
}
void Union(int x, int y)
{
    x = findset(x); y = findset(y);
    if (x == y)
    {
        isCircle[x] = 1;
        return;
    }
    if (PT[x]>PT[y])
    {
        father[y] = x;
        PT[x] += PT[y];
    }
    else
    {
        father[x] = y;
        PT[y] += PT[x];
    }
}

int main()
{
    int t, ncase = 1;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        memset(isCircle, 0, sizeof(isCircle));
        for (int i = 1; i 

参考了一部分代码。心急火燎的赶去看谷歌IO了~

HDOJ2045:不容易系列之(3)—— LELE的RPG难题——递推求解

Problem Description
人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉,这可急坏了众多“Cole”(LELE的粉丝,即”可乐”),经过多方打探,某资深Cole终于知道了原因,原来,LELE最近研究起了著名的RPG难题:

有排成一行的n个方格,用红(Red)、粉(Pink)、绿(Green)三色涂每个格子,每格涂一色,要求任何相邻的方格不能同色,且首尾两格也不同色.求全部的满足要求的涂法.

以上就是著名的RPG难题.

如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?

Input
输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成,(0=4是才能用。
f[1]=k; f[2]=k*(k-1); f[3]=k*(k-1)*(k-2);
如果n很大的会话,可以利用矩阵乘法快速幂进行加速。
可以参考Matrix67的博客

代码:

#include
int main()
{
	_int64 i, t = 1, j, n[52];
	n[1] = 3;
	n[2] = n[3] = 1;
	for (i = 4; i
	

HDOJ2044:一只小蜜蜂…——递推求解

Problem Description
有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房,不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中,蜂房的结构如下所示。

Input
输入数据的第一行是一个整数N,表示测试实例的个数,然后是N 行数据,每行包含两个整数a和b(0<a<b<50)。

Output
对于每个测试实例,请输出蜜蜂从蜂房a爬到蜂房b的可能路线数,每个实例的输出占一行。

Sample Input
2
1 2
3 6

Sample Output
1
3

递推求解,注意_int64。

代码:

#include
int main()
{
    int a, b, n, i;
    _int64 cell[52] = { 1, 1, 2 };
    for (i = 3; i
	

HDOJ1465:不容易系列之一——递推求解

Problem Description
大家常常感慨,要做好一件事情真的不容易,确实,失败比成功容易多了!
做好“一件”事情尚且不易,若想永远成功而总从不失败,那更是难上加难了,就像花钱总是比挣钱容易的道理一样。
话虽这样说,我还是要告诉大家,要想失败到一定程度也是不容易的。比如,我高中的时候,就有一个神奇的女生,在英语考试的时候,竟然把40个单项选择题全部做错了!大家都学过概率论,应该知道出现这种情况的概率,所以至今我都觉得这是一件神奇的事情。如果套用一句经典的评语,我们可以这样总结:一个人做错一道选择题并不难,难的是全部做错,一个不对。

不幸的是,这种小概率事件又发生了,而且就在我们身边:
事情是这样的——HDU有个网名叫做8006的男性同学,结交网友无数,最近该同学玩起了浪漫,同时给n个网友每人写了一封信,这都没什么,要命的是,他竟然把所有的信都装错了信封!注意了,是全部装错哟!

现在的问题是:请大家帮可怜的8006同学计算一下,一共有多少种可能的错误方式呢?

Input
输入数据包含多个多个测试实例,每个测试实例占用一行,每行包含一个正整数n(1<n<=20),n表示8006的网友的人数。

Output
对于每行输入请输出可能的错误方式的数量,每个实例的输出占用一行。

Sample Input
2
3

Sample Output
1
2

思路:
错排序列问题。难点在于找到递归式;初始状态F(1)=0,F(2)=1和状态转移式F(n)=(n-1)*F(n-2)

代码:

#include
int main()
{
    __int64 n, i, a[21] = { 1, 2 };
    for (i = 2; i
	

HDOJ1297:Children’s Queue——递推求解、大数运算

Problem Description
There are many students in PHT School. One day, the headmaster whose name is PigHeader wanted all students stand in a line. He prescribed that girl can not be in single. In other words, either no girl in the queue or more than one girl stands side by side. The case n=4 (n is the number of children) is like
FFFF, FFFM, MFFF, FFMM, MFFM, MMFF, MMMM
Here F stands for a girl and M stands for a boy. The total number of queue satisfied the headmaster’s needs is 7. Can you make a program to find the total number of queue with n children?

Input
There are multiple cases in this problem and ended by the EOF. In each case, there is only one integer n means the number of children (11、如果n个人的合法队列的最后一个人是男,则对前面n-1个人的队列没有任何限制,他只要站在最后即可,所以,这种情况一共有F(n-1);

  • 2、如果n个人的合法队列的最后一个人是女,则要求队列的第n-1个人务必也是女生,这就是说,限定了最后两个人必须都是女生,这又可以分两种情况:
  • 2.1、如果队列的前n-2个人是合法的队列,则显然后面再加两个女生,也一定是合法的,这种情况有F(n-2);
  • 2.2、但是,难点在于,即使前面n-2个人不是合法的队列,加上两个女生也有可能是合法的,当然,这种长度为n-2的不合法队列,不合法的地方必须是尾巴,就是说,这里说的长度是n-2的不合法串的形式必须是“F(n-4)+男+女”,这种情况一共有F(n-4).
  • 所以F(n)=F(n-1)+F(n-2)+F(n-4)。因为题目要求n取值在1000以内,超过了_int64的大小。所以要用大数运算来做。但是大数运算至今没搞懂,就直接从网上找了大数的模板了……

    代码:

    #include
    #include
    #include
    using namespace std;
    long long s[1010][1005];
    int main()
    {
        int i,j,n;
        memset(s,0,sizeof(s));
        s[1][0]=1;s[2][0]=2;s[3][0]=4;s[4][0]=7;
        for(i=5;i=10){
                    s[i][j+1]+=s[i][j]/10;
                    s[i][j]%=10;
                }
           }
        }
    
        while(cin>>n){
            i=1000;
            while(i--){
                if(s[n][i]!=0)
                    break;
            }
            cout=0;i--)
                printf("%d",s[n][i]);
            cout