poj1321 DFS水

2011年6月03日 22:09

 

棋盘问题
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 11335   Accepted: 5563

Description

在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

Input

输入含有多组测试数据。 
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 
当为-1 -1时表示输入结束。 
随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。 

Output

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

Sample Input

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

Sample Output

2
1

 

#include<cstdio>
#include<cstring>
int n,k;
int i;
int j;
char board[12][12];
int pos[12];
int cnt;
void DFS(int row,int num)
{
    if(num==0)
    {
        cnt++;
        return;
    }
    if(row>=n) return;
    for(int l=0; l<n; l++)
    {
        if(pos[l]!=1&&board[row][l]=='#')
        {
            pos[l]=1;
            DFS(row+1,num-1);
            pos[l]=0;
        }
    }
    DFS(row+1,num);
}
int main()
{
    scanf("%d%d",&n,&k);
    while(n!=-1&&k!=-1)
    {
        for(i=0; i<n; i++)
            scanf("%s",board[i]);
        cnt=0;
        memset(pos,0,sizeof(pos));
        DFS(0,k);
        printf("%d\n",cnt);
        scanf("%d%d",&n,&k);
    }
    return 0;
}

 

Posted by WARush Filed in poj的挣扎 Tagged by DFS poj acm 水 Comments[4]

poj1611 并查集基础题

2010年6月28日 09:08

Description

 

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others. 
In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP). 
Once a member in a group is a suspect, all members in the group are suspects. 
However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.

Input

The input file contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every student is numbered by a unique integer between 0 and n−1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space. 
A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.

Output

For each case, output the number of suspects in one line.

Sample Input

100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0

Sample Output

4
1 

 

 

 

并查集较为简单，注意路径压缩！~~

 

#include<iostream>
using namespace std;
int n,m;
int i,j;
int t;
int a,b;
int zero;//remember the set where zero is
int f[30001];//set mark
int c[30001];//set count
int Find(int x)
{
    if(f[x]==x)return x;
    else
        f[x]=Find(f[x]);
    return f[x];
}
void Union(int x1,int y1)
{
    int x=Find(x1);
    int y=Find(y1);
    if(x!=y)
    {
        if(c[x]>=c[y])
        {
            f[y]=x;
            c[x]=c[x]+c[y];
            if(y==zero)
             zero=x;
        }
        else
        {
            f[x]=y;
            c[y]=c[x]+c[y];
            if(x==zero)
             zero=y;
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)&&(n||m))
    {
        zero=0;
        for(i=0;i<n;i++)
            {
               f[i]=i;
               c[i]=1;
            }

        for(i=0;i<m;i++)
        {
            scanf("%d",&t);
            scanf("%d",&a);
            for(j=0;j<t-1;j++)
            {
                scanf("%d",&b);
                Union(a,b);
            }
        }
        printf("%d\n",c[zero]);

    }
    return 0;
}

 

 

 

 

Posted by WARush Filed in poj的挣扎 Tagged by 并查集 路径压缩 Comments[61]

poj1067

2010年6月28日 01:14

Description

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一 是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到 你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

Input

输 入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数 目，a和b都不大于1,000,000,000。

Output

输 出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。

Sample Input

2 1
8 4
4 7

Sample Output

0
1
0




在数论中，贝亚蒂定理（英文：Beatty sequence）指：若 p,q \in \mathbb{R^+} ,p,q \not\in \mathbb{Q} 使 得\frac{1}{p} + \frac{1}{q} = 1。 定义集（贝亚蒂列）P = \{\lfloor np \rfloor : n \in Z^+ \}, Q=\{\lfloor nq \rfloor : n \in Z^+\}， 则P 和 Q 构成正整数集的一个分划： P \cap Q = \emptyset，P \cup Q = Z^+。

即是说：若两个正无理数的倒数之和是1，则任何正整数都可 刚好以一种形式表示为不大于其中一个无理数的正整数倍的最大整数。

 

#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    int n;
    double alpha=(1.0+sqrt(5.0))/2.0;
    double beta=(3.0+sqrt(5.0))/2.0;
    int num1,num2;
    int temp1,temp2;
    while(scanf("%d%d",&num1,&num2))
    {
        if(num1<num2)swap(num1,num2);
        n=(int)(ceil(num1/beta));
        temp1=(int)(beta*n);
        temp2=(int)(alpha*n);
        if((num1==temp1)&&(num2==temp2))
         printf("0\n");
         else printf("1\n");
    }
    return 0;
}

Posted by WARush Filed in poj的挣扎 Tagged by 博弈 Beatty定理 库佐夫博弈 Comments[2]