可用分押宝游戏火热进行中...	专题改版：Java Web 专题

Google编程中国挑战赛第一轮Room18

楼主xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）2005-12-19 22:34:00 在 C/C++ / C++ 语言提问

第一题 [250分]
Problem Statement

You want to buy two neighboring tickets in the first row of the theater so that one of the tickets is as far from the aisles as possible.
You will be given a String describing the first row of the theater where '.' represents an empty seat and 'X' represents an occupied seat. Your task is to return the index (from 0) of the empty seat that is furthest from the aisles (the two ends of the String) and is also next to an empty seat. If there are multiple possible seats, return the one with the smallest index. Return -1 if there are no seats that satisfy your requirements.
Definition

Class:
TheaterVisit
Method:
chooseSeat
Parameters:
string
Returns:
int
Method signature:
int chooseSeat(string row)
(be sure your method is public)

Constraints
-
row will contain between 1 and 50 characters, inclusive.
-
Each character in row will be either '.' or 'X'.
Examples
0)

"....."
Returns: 2
You can buy either tickets with indexes 1 and 2 or tickets with indexes 2 and 3.
1)

"......"
Returns: 2

2)

"..X..."
Returns: 3
You should buy tickets with indexes 3 and 4.
3)

".X.X..."
Returns: 4

4)

"X.XX.X"
Returns: -1

5)

".."
Returns: 0 问题点数：1、回复次数：33Top

1 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-12-19 22:34:58 得分 0

第二题[500分]

Problem Statement

A group of vertical blocks are placed densely one after another on the ground. The blocks each have a width of 1, but their heights may vary. For example, if the heights of the vertical blocks are given as {1,5,5,1,6,1}, the configuration would look like the following picture:

Your task is to reproduce the exact shape of this structure using some number of non-intersecting rectangles. You will be given a vector <int> heights representing the heights of the vertical blocks from left to right. Return the minimal number of rectangles necessary to perform this task with the given configuration of blocks.
Definition

Class:
BlockStructure
Method:
cover
Parameters:
vector <int>
Returns:
int
Method signature:
int cover(vector <int> heights)
(be sure your method is public)

Constraints
-
heights will have between 1 and 50 elements, inclusive.
-
Each element of heights will be between 1 and 1000, inclusive.
Examples
0)

{1,5,5,1,6,1}
Returns: 3

We can use rectangles with sizes 6x1, 2x4 and 1x5.
1)

{2,2,2,4,4}
Returns: 2

We can use a 3x2 rectangle and a 2x4 rectangle.
2)

{6,6,6,6,6,6}
Returns: 1
The structure is a rectangle.
3)

{71,44,95,16,10,80,12,17,98,61}
Returns: 10
It's impossible to use less than 10 rectangles.
4)

{100,100,97,100,100,100,97,98,99,99}
Returns: 5Top

2 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-12-19 22:35:41 得分 0

第三题[1000分]
Problem Statement

We have a sequence of integers, and we would like to remove all duplicate elements from this sequence. There may be multiple ways to perform this task. For example, given the sequence { 1, 2, 1, 3 }, we could end up with either { 1, 2, 3 } or { 2, 1, 3 } as the remaining sequence, depending on which duplicate 1 we remove from the original sequence. For this problem, we want to return the lexicographically first of of all possible remaining sequences. A sequence S1 comes before sequence S2 lexicographically if and only if S1 has a smaller value than S2 at the lowest index at which the two sequences differ (so, for example, { 1, 2, 3 } comes before { 2, 3, 1 }).
You will be given a int[] sequence. Return a int[] containing the sequence after all the duplicates are removed. See the examples for further clarification.
Definition

Class:
HardDuplicateRemover
Method:
process
Parameters:
int[]
Returns:
int[]
Method signature:
int[] process(int[] sequence)
(be sure your method is public)

Constraints
-
sequence will have between 1 and 50 elements, inclusive.
-
Each element of sequence will be between 1 and 1000, inclusive.
Examples
0)

{5, 6, 5, 1, 6, 5}
Returns: {1, 6, 5 }
There are six different ways to remove duplicates (remaining numbers are marked by '*'):
{ *5, *6, 5, *1, 6, 5},
{ *5, 6, 5, *1, *6, 5},
{ 5, *6, *5, *1, 6, 5},
{ 5, 6, *5, *1, *6, 5},
{ 5, *6, 5, *1, 6, *5},
{ 5, 6, 5, *1, *6, *5}.

The last variant is the lexicographically first.
1)

{3, 2, 4, 2, 4, 4}
Returns: {3, 2, 4 }

2)

{6, 6, 6, 6, 6, 6}
Returns: {6 }

3)

{1, 3, 2, 4, 2, 3}
Returns: {1, 2, 4, 3 }

4)

{5, 4, 1, 5}
Returns: {4, 1, 5 }Top

3 楼csucdl（csucdl）回复于 2005-12-19 22:36:21 得分 0

关注Top

4 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-12-19 22:42:16 得分 0

时间太紧了, 没有做完, 提交的两题, 还有一题被别人找出毛病了.

没时间玩了, 回去睡觉, 大家可以看看题, 不太难.Top

5 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-12-20 08:53:52 得分 0

惨淡, 今天早上去看system test, 结果第一题也被kill了, 最后得分 0.00

汗~~~Top

6 楼cxyol（C++,VC 学习中......）回复于 2005-12-20 09:40:27 得分 0

同情，斑竹努力呀！Top

7 楼oo（为了名副其实，努力学习oo技术ing）回复于 2005-12-20 10:50:01 得分 0

markTop

8 楼wshcdr（dd）回复于 2005-12-20 10:53:54 得分 0

mkTop

9 楼wzjall（风）回复于 2005-12-20 12:27:55 得分 0

题目不错!也不算太难!只是一个小时我还真做不完更别说写的有多好了Top

10 楼0000000009（）回复于 2005-12-20 20:44:07 得分 1

我试着做了第一题:
int TheaterVisit::ChoosSeat(string row)
{
int i = row.length();

int pf = 0;
int pb = 0;

if(i%2)
pf = pb = i/2 + 1;
else
{
pf = i/2;
pb = i/2 + 1;

if( row.at(pf) == '.'
&& row.at(pb) == '.' )
return pf;

};

while(pf>0)
{
if( row.at(pf--) == '.'
&&row.at(pf) == '.' )
return pf;

if( row.at(pb++) == '.'
&&row.at(pb) == '.' )
return pb-1;
}
return -1;
}Top

11 楼0000000009（）回复于 2005-12-20 21:00:02 得分 0

第二题什么意思?
本来我就不会english,再看不到题中的图我真无法理解题意。Top

12 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-12-20 22:14:29 得分 0

CSDN不能发图, 想看详细的题目, 请查看我的Blog

http://blog.csdn.net/xiaocai0001/archive/2005/12/20/557650.aspxTop

13 楼lisypro（）回复于 2005-12-21 08:20:39 得分 0

upTop

14 楼0000000009（）回复于 2005-12-21 10:25:30 得分 0

我的第一题你看看Top

15 楼Aaron_ia（︿疯继续吹|一春一景|小小菜︿）回复于 2005-12-21 12:08:30 得分 0

pf = pb = i/2 + 1;
不能是加1吧？Top

16 楼ugvihc（maybe good good study, hope day day up!）回复于 2005-12-21 15:02:57 得分 0

试了下第一题.
#include<iostream>
#include<string>
using namespace std;

class TheaterVisit
{
public:
int chooseSeat(string row);
};

int TheaterVisit::chooseSeat(string row)
{
int location;
int first,end;
int len;
bool firstFlag;
bool endFlag;
len=row.length();

location=-1;
firstFlag=endFlag=false;

for(first=len/2,end=len/2;(end<len-1)||(first>0);)
{
// cout<<"first:"<<first<<" end:"<<end<<endl;

if(firstFlag==true||endFlag==true)
{
break;
}

if(firstFlag==false)
{
if(row[first]=='.')
{
if(row[first-1]=='.')
{
location=first-1;
firstFlag=true;
}
}
}

if(endFlag==false)
{
if(row[end]=='.')
{
if(row[end+1]=='.')
{
location=end;
endFlag=true;
}
}
}
end++;
first--;

}
return location;
}

void main()
{
TheaterVisit tv;
string str=".....";
cout<<str<<" \n"<<tv.chooseSeat(str)<<endl;;
}Top

17 楼0000000009（）回复于 2005-12-21 15:25:14 得分 0

pf = pb = i/2 + 1;
不能是加1吧？
-----------------------------------
为什么Top

18 楼lj197912（从零开始）回复于 2005-12-21 16:12:37 得分 0

第二题，大家看对不，欢迎提意见
int cover(vector <int> heights)
{
vector <int> tempheight = heights;
int count = 0;
for(int i = 0; i < tempheight.size(); i++)
{
for(int j = i + 1; j < tempheight.size(); j++)
{
if(tempheight[i] > tempheight[j])
{
int temp;
temp = tempheight[i];
tempheight[i] = tempheight[j];
tempheight[j] = temp;
}

}
int aa = tempheight[i];
int t = 0;
}

int height = 0;
for(int k = 0; k < tempheight.size(); k++)
{
if(k == 0)
{
height = tempheight[k];
count++;
}
else
{
if( height == tempheight[k])
continue;
else
height = tempheight[k];

bool flag = false;
for(int l = 0; l < heights.size(); l++)
{

if(height == heights[l])
{

flag = true;
}
if(flag && (heights[l] != height || l == (heights.size() - 1)))
{
count++;
flag = false;

}

}

}

}
return count;
}Top

19 楼khyang（天佑）回复于 2005-12-21 21:09:23 得分 0

学习Top

20 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-12-21 21:15:16 得分 0

第一题没有通过系统测试, 让我感觉挺纳闷的.
第二题到现在也没什么有什么好的思路
第三题现在做好了, 但不知道对不对.Top

21 楼0000000009（）回复于 2005-12-23 14:36:04 得分 0

lj197912(从零开始) 第二题思路非常好
我原来觉得必须用递归Top

22 楼jianlirong（简）回复于 2005-12-24 02:28:57 得分 0

第一题：
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class TheaterVisit
{
public:
int chooseSeat(string s)
{
vector<int> list;
int position=0;
while(s[position]!=0)
{
if(s[position]=='.'&&s[position+1]=='.') list.push_back(position);
position++;
}
if(list.size()==0) return -1;
int size=list.size();
if(size==1) return list[0];

int max=0;int keep=0;

for(int i=0;i<size;i++)
{
int min=list[i]<position-list[i]-2 ? list[i]:position-list[i]-2;
if(min>max)
{
keep=i;
max=min;
}
}

return list[keep];

}

};

第二题：
#include <iostream>
#include <vector>

using namespace std;

class BlockStructure
{
public:
int cover(vector<int>& list)
{
int size=list.size();
if(size==0) return 0;

return cover(list,0,size-1);
}

private:
int cover(vector<int>& list,int begin,int end)
{
if(begin==end)
{
list[begin]=0;
return 1;
}

int min=list[begin];
for(int i=begin+1;i<=end;i++) if(list[i]<min) min=list[i];
for(i=begin;i<=end;i++) list[i]-=min;

i=begin;
int sum=1;
while(i<=end)
{
int a=list[i];
if(list[i]==0)
{
i++;
continue;
}
int first=i;int last=begin;
while(i<=end&&list[i]!=0) i++;
if(i>end) last=end;
else last=i-1;
sum+=cover(list,first,last);
}

return sum;
}
};

第三题，明天晚上再做，今天晚上太累了！！随便写了一下，还没认真调试过，大家帮看一下！！！本人学编程不久，希望大家能对我的编程风格提点建议的。谢谢！！Top

23 楼wzjall（风）回复于 2005-12-24 13:42:12 得分 0

我也做了下第一题,代码很少,我测试是没问题! 看看对吗?
#include<iostream>
#include<string>
using namespace std;

void main()
{
int i,index=-1;
string s;
cin>>s;
int n=s.size();

for(i=0;i<n-1;i++)
{
if(s[i]=='.'&&s[i+1]=='.')
{
if(n-1-i>index)//千万不要用 if(s.size()-1-i>index);//.否则有可能出错，原因不详！！！！
{
index=i;
}
}
}

cout<<index;
}
还有我注释的那个不知道什么原因,真奇怪,有是有问题,有时没有Top

24 楼wzjall（风）回复于 2005-12-24 13:43:56 得分 0

第二题没看懂,那为可以解释一下吗?Top

25 楼newpuple（开始新的学程）回复于 2005-12-24 14:46:30 得分 0

markTop

26 楼wzjall（风）回复于 2005-12-24 16:39:08 得分 0

第三题:
大体思路:
如果 a[i]>=a[m]( a[m]为a[i]后面的第一个没被删除的数据),
则a[i]=k--( 这样就可以表示a[i]被删除掉了,k初始值为0), i--(回溯)

如果 a[i]<a[m] ,则删除a[i]后面的所有等于a[i]的数据.i++

#include <iostream>
using namespace std;

void f(int a[],int n)
{
int i=0,j=0,k=0;
while(i<n)
{
if(a[i]>0)
{
j=i+1;
while (j<n)
{

if (a[i]==a[j])
{
for(int m=i+1;m<j;m++)
{
if (a[m]>0)
{
break;
}
}

if (a[i]>=a[m])
{
a[i]=k--;
if (i>0)
{
i--;
}
break;
}
else
{
a[j]=k--;
for (int w=j+1;w<n;w++)
{
if (a[w]==a[i])
{
a[w]=k--;
}
}
i++;
break;
}
}
j++;
}

if (j==n)
{
i++;
}
}
else
{
i++;
}
}
}
void main()
{
int a[]={5, 4, 1, 5,3,23,1,3,4,2,3,43,2,2,32,30,23,2,3,34,5,2,3,5,32,3,5,3,23,5};
int n=sizeof(a)/sizeof(int);
f(a,n);

for (int i=0;i<n;i++)
{
if (a[i]>0)
{
cout<<a[i]<<endl;
}
}
}
第二题还是没看懂题(看了图片,英语能看懂,就是不能理解题意),懂的能讲讲吗? Top

27 楼wzjall（风）回复于 2005-12-24 17:42:27 得分 0

上面的思路估计不太好理解,再来个简单点的,好理解,效率也高一些.

#include<iostream>
using namespace std;

void main()
{
int i,j,l,k,m,n;
int str[]={1,2,3,4,3,23,2,2,4,32,4,3,7,9,42,1,2,43,43,1,4};
l=sizeof(str)/sizeof(int);

for(i=0;i<l;i++)
{
//find the last of the element which is equal to str[i]
for (k=l;k>i;k--)
{
if (str[k]==str[i])
{
break;
}
}

if(k>=0)
{
//如果 i 以后, k 以前的数据有大于str[i]的，则删除str[i]
for(m=i+1;m<k;m++)
{
if(str[m]<str[i]&&str[m]!=0)
{
str[i]=0;

break;

}
}
//否则删除i以后，k+1以前的所有等于str[i]的数据。
if(m==k)
{
for(m=i+1;m<=k;m++)
{
if(str[m]==str[i])
{
str[m]=0;
}
}
}
}
}

for(i=0;i<l;i++)
if(str[i]!=0)
cout<<str[i]<<'\t';
cout<<endl;
}
Top

28 楼wzjall（风）回复于 2005-12-24 18:00:37 得分 0

第二题总算理解了,先想想看!(首先怎么就没理解呢?我!其实解释的很清楚了.谢谢小雨了.)Top

29 楼iamcaicainiao（老菜，长征）回复于 2005-12-24 18:07:23 得分 0

/* 第一题，我的思路 */
int chooseSeat(string row)
{
int i;/* 空位 */
int j;/* 紧挨着j的空位，即i＋1 */

/* 扫描string，搜索所有连续挨着的两个空位 */
/* 将每一个i保存起来，可以保存到二维数组A中，第一维 */

/* 扫描数组A中的元素值，求出每个元素距离走廊的长度，保留小的那个
保存到二维数组A中的第二维 */

/* 扫描数组A中的第二维值最大者 */

}Top

30 楼iamcaicainiao（老菜，长征）回复于 2005-12-24 18:10:15 得分 0

/* 第二题就不懂了 */Top

31 楼iamcaicainiao（老菜，长征）回复于 2005-12-24 18:15:45 得分 0

/* 第三题愣是没看懂。 lexicographically first什么意思啊。唉，可怜我的菜菜的英语啊 */Top

32 楼xiaocai0001（高楼目尽欲黄昏/梧桐叶上萧萧雨）回复于 2005-12-24 18:45:49 得分 0

>> lexicographically first

字典顺序排序Top

33 楼wzjall（风）回复于 2005-12-24 20:43:41 得分 0

第二题还是没思路!今天写第三题就用了我三个小时(写了两个,思路不一样).真是太菜了.Top