第一题:
Oil Deposits
--------------------------------------------------------------------------------
Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 1412 Accepted Submit: 780
--------------------------------------------------------------------------------
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.
Input
The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 <= m <= 100 and 1 <= n <= 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*', representing the absence of oil, or `@', representing an oil pocket.
Output
For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.
Sample Input
1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0
Sample Output
0
1
2
2
翻译一下,上面的那个矩阵表示的是一块土地,@代表的是油,你的任务是找出土地上有多少快油,比如第一个例子只有一块是:
@ @
@
@ @ 要是翻译的不是很清楚,大家自己用金山,
提交地址:http://acm.zju.edu.cn/show_problem.php?pid=1709
第二
Sorting by Swapping
Time Limit:1000MS Memory Limit:10000K
Total Submit:2753 Accepted:1471
Description
Given a permutation of numbers from 1 to n, we can always get the sequence 1, 2, 3, ..., n by swapping pairs of numbers. For example, if the initial sequence is 2, 3, 5, 4, 1, we can sort them in the following way:
2 3 5 4 1
1 3 5 4 2
1 3 2 4 5
1 2 3 4 5
Here three swaps have been used. The problem is, given a specific permutation, how many swaps we needs to take at least.
Input
The first line contains a single integer t (1 <= t <= 20) that indicates the number of test cases. Then follow the t cases. Each case contains two lines. The first line contains the integer n (1 <= n <= 10000), and the second line gives the initial permutation.
Output
For each test case, the output will be only one integer, which is the least number of swaps needed to get the sequence 1, 2, 3, ..., n from the initial permutation.
Sample Input
2
3
1 2 3
5
2 3 5 4 1
Sample Output
0
3
翻译:求选择排序的时候交换的次数.注意排序的元素很特殊,他们是从1开始的连续的自然数序列!!!
提交地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1674
两个题目都不是很难,只要大家多动动脑筋一定都能做出来
[此贴子已经被作者于2007-6-9 9:52:02编辑过]
----------------解决方案--------------------------------------------------------
支持一下,落个沙发先.
大家做做吧.
----------------解决方案--------------------------------------------------------
好久没有来了,沙发都没有占到,
大家注意第一个题目我可能翻译的不是很准确,
[此贴子已经被作者于2007-6-9 21:09:05编辑过]
----------------解决方案--------------------------------------------------------
//2007-06-09 13:51:32 Accepted 1709 C++ 00:00.00 880K lecoo
#include <iostream>
#include <assert.h>
using namespace std;
int adj_M[102][102];
int dx[]={0,0,1,-1,1,1,-1,-1};
int dy[]={1,-1,0,0,1,-1,1,-1};
void dfs(int x,int y)
{
for(int i=0;i<8;i++){
if(adj_M[x+dx[i]][y+dy[i]]=='@'){
adj_M[x+dx[i]][y+dy[i]]='*';
dfs(x+dx[i],y+dy[i]);
}
}
}
int main()
{
int m,n;
while(scanf(\"%d %d\",&m,&n)!=EOF && (m||n)){
assert(getchar()=='\n');
for(int i=0;i<=m+1;i++){
adj_M[i][0]='*';
}
for(int j=0;j<=n+1;j++){
adj_M[0][j]='*';
}
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
adj_M[i][j]=getchar();
}
assert(getchar()=='\n');
}
int cnt=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(adj_M[i][j]=='@'){
cnt++;
adj_M[i][j]='*';
dfs(i,j);
}
}
}
printf(\"%d\n\",cnt);
}
}
//1674 Accepted 164K 62MS G++ 396B 2007-06-09 13:50:28
#include <iostream>
#include <algorithm>
using namespace std;
int arr[10001];
int main()
{
int N;
scanf(\"%d\",&N);
while(N--){
int n;
scanf(\"%d\",&n);
for(int i=1;i<=n;i++){
scanf(\"%d\",&arr[i]);
}
int cnt=0;
for(int i=1;i<=n;i++){
while(arr[i]!=i){
swap(arr[i],arr[arr[i]]);
cnt++;
}
}
printf(\"%d\n\",cnt);
}
}
----------------解决方案--------------------------------------------------------
看看.......
----------------解决方案--------------------------------------------------------
哎呀 第一题 我只想出了 现用二维数组 然后在进行判断
不过这个方法感觉有点烂 还有人有更好的方法来做第一题吗？ 把算法发出来看看啊
----------------解决方案--------------------------------------------------------
第一个题目我和leeco的算法一样.都是DFS,时间都是0MS,空间多点400多K.
第二个有点不一样:
#include<stdio.h>
int main()
{
int t,n,a[10005],b[10005],sum,i,j,min,temp;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a[i]),b[a[i]]=i;
sum=0;
for(i=1;i<=n;i++)
{
if(b[i]==i) continue;
else
{
b[a[i]]=b[i];
a[b[i]]=a[i];
sum++;
}
}
printf("%d\n",sum);
}
return 0;
}
----------------解决方案--------------------------------------------------------
下期出题的任务.继续交给leeco
----------------解决方案--------------------------------------------------------
现在做题的人越来越少了，可能大家都很忙吧，抽空先做了一下第二题，第一题回头来做。
#include <stdio.h>
#include <stdlib.h>
void main()
{
int cyclenum, length;
int i, j, k, temp, count;
int *str;
printf( "Input the cycle number:" );
scanf( "%d", &cyclenum );
for( i = 0; i < cyclenum; i ++ )
{
printf( "Input the length of array:" );
scanf( "%d", &length );
printf( "Input the elements of array:" );
str = ( int * )malloc( sizeof( int ) * length );
for( j = 0; j < length; j ++ )
scanf( "%d", str + j );
count = 0;
for( j = 1; j <= length; j ++ )
{
k = j - 1;
if( str[k] == j )
continue;
else
{
for( k = j; k < length; k ++ )
{
if( str[k] == j )
{
temp = str[j - 1];
str[j - 1] = str[k];
str[k] = temp;
count++;
break;
}
}
}
}
free(str);
printf( "The least number of swaps is:%d.\n", count );
}
}
----------------解决方案--------------------------------------------------------
学习学习
----------------解决方案--------------------------------------------------------