主题：第74次编程比赛题目
天边蓝 [专家分：1810] 发布于 2008-10-13 09:40:00
1.找单数（30%）
给定一个含有n个数的序列，这个序列中恰好有两个数出现一次，请你找出这两数。（假定其他的数都有两个）
函数原型如下：
// array[] -- n个数的序列，数的取值范围（-1e9，1e9）
// n -- 数的个数，2<=n<=10^8
// reslut[]-- 返回数组，长度为2
void findSingle(int array[], int n，int reslut[])
{
}
2.炮兵阵地（70%）
Description
司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也
可能是平原（用"P"表示）。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地
图上的攻击范围沿横向左右各两格，沿纵向上下各两格。其它位置均攻击不到。另外炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他
支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
Input
第一行包含两个由空格分割开的正整数，分别表示N和M；
接下来的N行，每一行含有连续的M个字符('P'或者'H')，中间没有空格。按顺序表示地图中每一行的数据。N <= 100；M <= 10。
Output
仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。
Source
POJ1185 http://acm.pku.edu.cn/JudgeOnline/problem?id=1185
比赛截止时间
2008年10月18号18：00
提问请到http://bbs.pfan.cn/post-286940.html
回复列表 （共22个回复）
11 楼
red999 [专家分：20] 发布于 2008-10-16 11:14:00
#include<iostream>
using namespace std;
int total;
int PNum;
int m;
int n;
void setFlat(char *map[])
{
PNum = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(*(map[i]+j) != 'H')
{
*(map[i]+j) = 0;
PNum ++;
}
}
}
}
void setMap(char *map[])
{
for(int i=0; i<n; i++)
{
for(int j=0; j<m-1; j++)
{
if(*(map[i]+j) != 'H')
{
if(*(map[i]+j+1) != 'H')
{
(*(map[i]+j))++;
(*(map[i]+j+1))++;
}
if(j<m-2 && *(map[i]+j+2) != 'H')
{
(*(map[i]+j))++;
(*(map[i]+j+2))++;
}
}
}
}
for(int i=0; i<m; i++)
{
for(int j=0; j<n-1; j++)
{
if(*(map[j]+i) != 'H')
{
if(*(map[j+1]+i) != 'H')
{
(*(map[j]+i))++;
(*(map[j+1]+i))++;
}
if(j<n-2 && *(map[j+2]+i) != 'H')
{
(*(map[j]+i))++;
(*(map[j+2]+i))++;
}
}
}
}
}
void setPosition(char *map[])
{
int min = *map[0];
int x = 0;
int y = 0;
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if( min > *(map[i]+j))
{
min = *(map[i]+j);
x = i;
y = j;
}
}
}
*(map[x]+y) = 'H';
total ++;
if(y+2<m)
*(map[x]+y+2) = 'H';
if(y+1<m)
*(map[x]+y+1) = 'H';
if(y-2>0)
*(map[x]+y-2) = 'H';
if(y-1>0)
*(map[x]+y-1) = 'H';
if(x+2<n)
*(map[x+2]+y) = 'H';
if(x+1<n)
*(map[x+1]+y) = 'H';
if(x-2>0)
*(map[x-2]+y) = 'H';
if(x-1>0)
*(map[x-1]+y) = 'H';
}
int main()
{
char* map[10];
cout<<"Input n&m:"<<endl;
cin>>n>>m;
while(n > 100 || m > 10 || n < 0 || m < 0)
{
cout<< "Input error. "<< endl;
cout<<"Input n & m:"<<endl;
cin>>n>>m;
}
cout<<"Input map:"<<endl;
for(int i=0; i<n; i++)
{
map[i] = new char[m];
cin>>map[i];
for(int j=0; j<m; j++)
{
if(*(map[i]+j) == 'P')
*(map[i]+j) = 0;
}
}
PNum = 1;
while(PNum != 0)
{
setMap(map);
setPosition(map);
setFlat(map);
}
cout<<total<<endl;
for(int i=0; i<n; i++)
delete []map[i];
system("pause");
return 0;
}
12 楼
goal00001111 [专家分：4030] 发布于 2008-10-16 12:41:00
/*
找单数（30%）
给定一个含有n个数的序列，这个序列中恰好有两个数出现一次，请你找出这两数。（假定其他的数都有两个）
函数原型如下：
// array[] -- n个数的序列，数的取值范围（-1e9，1e9）
// n -- 数的个数，2<=n<=10^8
// result[]-- 返回数组，长度为2
void findSingle(int array[], int n，int result[])
{
}
*/
#include<iostream>
using namespace std;
void findSingle(int array[], int n, int result[]);
int main()
{
int a[10] = {1,2,2,4,5,3,1,6,4,5};
int r[2];
findSingle(a, 10, r);
for (int i=0; i<2; i++)
{
cout << r[i] << endl;
}
system("pause");
return 0;
}
// array[] -- n个数的序列，数的取值范围（-1e9，1e9）
// n -- 数的个数，2<=n<=10^8
// result[]-- 返回数组，长度为2
//复杂度最高为n*(n-1)/2
void findSingle(int array[], int n, int result[])
{
int *tempArray = new int(n);
for (int i=0; i<n; i++)
{
tempArray[i] = array[i];
}
int i, j, top = 0;
bool flag;
for (i=0; i<n; i++)
{
result[top] = tempArray[i];
flag = true;
for (j=i+1; j<n; j++)
{
if (tempArray[i] == tempArray[j])//找到相同的数则用最后一个数代替相同数
{
tempArray[j] = tempArray[--n];
flag = false;
break;
}
}
if (flag)//没有找到相同的数，则存入数组
{
top++;
if (top > 1) //只有两个数满足条件
{
break;
}
}
}
delete tempArray;
}
13 楼
toto996 [专家分：0] 发布于 2008-10-16 18:49:00
我想看看！
14 楼
toto996 [专家分：0] 发布于 2008-10-16 19:41:00
我看看！
15 楼
zhangyuke [专家分：0] 发布于 2008-10-16 21:56:00
第一题
[code=c]
#include <iostream.h>
void findSingle(int array[],int n,int result[])
{
int m=0;
for ( int i =0;i<n-1;i++)
{
for (int j=0;j<n;j++)
{
if(i==j)
continue;
if(array[i]==array[j])
break;
}
if(j=n-1&&array[i]!=array[j])
{
result[m]=array[i];
m+=1;
}
}
}
void main()
{
int array[]={1,1,2,3,3,4,5,5};
int result[2]={0,0};
findSingle(array,8,result);
cout<<result[0]<<" "<<result[1]<<endl;
}
第二题
#include <iostream.h>
//输入P和H
void inputChar(char *ph,int m,int n)
{
int i,j;
cout<<"Please input the char of 'P' or 'H'."<<endl;
for (i=0;i<n;i++)
{
cout<<i<<"line:"<<endl;
for (j=0;j<m;j++)
{
cin>>ph[i*n+j];
}
}
}
//获得K的值
int getValueofK(char *ph,int m,int n)
{
int i,j;
int k=0;
for(j=0;j<m;j++) //设置第一行的第一个炮兵点
{
if (j==0&&ph[j]=='P')
{
ph[j]='*'; //将第一行的第一个p点设为炮兵
k=k+1;
}
if (ph[j]=='P'&&ph[j-1]!='*')
{
ph[j]='*';
k+=1;
}
}
for(i=1;j<n;i++) //设置第一列的炮兵点
{
if (ph[i*m]=='P'&&ph[(i-1)*m]!='*')
{
ph[i*m]='*';
k+=1;
}
}
for (i=1;i<n;i++)
{
for (j=1;j<m;j++)
{
if (ph[i*m+j]=='P'&&ph[i*m+j-1]!='*'&&ph[(i-1)*m+j]!='*')
{
ph[i*m+j]='*';
k+=1;
}
}
}
return k;
}
void main()
{
int M,N;
int k=0;
cout<<"Please input the value of M and N:"<<endl;
cin>>M>>N;
char * ph = new char[N*M];
inputChar(ph,N,M);
k=getValueofK(ph,M,N);
cout<<"THE VALUE OF K IS:"<<k<<endl;
delete ph;
}
[/code]
16 楼
toto996 [专家分：0] 发布于 2008-10-17 09:52:00
先交第一题，第二题太ACM了！
[code]
#include <iostream>
using namespace std;
void findSingle(int array[], int n,int result[])
{
int nK = 0;//result的索引
bool bSingle = true;//是否只出现一次
for (int nI = 0; nI < n; ++nI)
{
bSingle = true;
if (2 == nK)//如果result已存满，就结束搜索
{
break;
}
for (int nJ = 0; nJ < n; ++nJ )//搜索数组里是否还有同样的元素
{
if (array[nI] == array[nJ] && nI != nJ)
{
bSingle = false;
break;
}
}
if (bSingle)//如果只出现一次，就保存
{
result[nK++] = array[nI];
}
}
}
int main()
{
int array[] = {1,4,1,4,2,3,1,4};
int result[2];
findSingle(array, 8, result);
cout << result[0] << result[1];
return 0;
}[/code]
17 楼
fan888 [专家分：0] 发布于 2008-10-17 16:48:00
学习！！
18 楼
fan888 [专家分：0] 发布于 2008-10-17 16:49:00
学习
19 楼
gangmae [专家分：0] 发布于 2008-10-17 19:55:00
#include<stdio.h>
#define ARR_SIZE 10
#define RES_SIZE 2
void findSingle(int array[], int n, int reslut[]);
main()
{
int array[ARR_SIZE] = {1,1,2,3,3,2,10,9,5,5};
static int result[RES_SIZE];
findSingle(array,ARR_SIZE,result);
}
void findSingle(int array[], int n, int result[])
{
int find = 0;
int i, j, res = 0;
for(i = 0; i < n-1; i++)
{
for(j = 0; j < n; j++)
{
if(i == j)
j++;
if(array[i] == array[j])
break;
if(j == n-1)
{
result[res++] = array[i];
find++;
}
}
if(find == 2)
break;
}
printf("%d %d\n",result[0],result[1]);
}
20 楼
gangmae [专家分：0] 发布于 2008-10-17 20:03:00
#include<stdio.h>
#define ARR_SIZE 10
#define RES_SIZE 2
void findSingle(int array[], int n, int reslut[]);
main()
{
int array[ARR_SIZE] = {1,1,2,3,3,2,10,9,5,5};
static int result[RES_SIZE];
findSingle(array,ARR_SIZE,result);
}
void findSingle(int array[], int n, int result[])
{
int find = 0;
int i, j, res = 0;
for(i = 0; i < n-1; i++)
{
for(j = 0; j < n; j++)
{
if(i == j)
j++;
if(array[i] == array[j])
break;
if(j == n-1)
{
result[res++] = array[i];
find++;
}
}
if(find == 2)
break;
}
printf("%d %d\n",result[0],result[1]);
}
我来回复
您所在位置：