1.百度语言翻译机(解答)
////////////////////////////////////////////////////////
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
int n;
map<string,string> data;
string k,w;
string s;
cin>>n;
while(n--)
{
cin>>k>>w;
data[k]=w;
}
cin>>s;
basic_string<char>::iterator ib,ie;
ie=ib=s.begin();
string temp;
for(;ie!=s.end();ie++)
{
if(*ie>='A'&&*ie<='Z')
{
temp+=*ie;
if(*ib<='A'||*ib>='Z') ib=ie;
}
else
{
if(*ib>='A'&&*ib<='Z')
{
s.replace(ib,ie,data[temp]);
ib=ie=s.begin();
temp.erase();
}
else
ib=ie;
}
}
cout<<s<<endl;
return 0;
}
//////////////////////////////////////////////////////////////////////
2.饭团的烦恼
2006百度之星程序设计大赛预赛题目之饭团的烦恼 参考解答
#include <string>
#include <vector>
#include <fstream>
#include <iostream>
#include <stdio.h>
#include "math.h"
using namespace std;
struct food
{
string name;
int price;
bool isHun;
bool isXinla;
};
static int nFoodMenu; //菜单上菜的数目
static int nFoodNeed; //饭团需要点的菜的数目
static int nPeople; //就餐的人数
//荤菜，素菜，辛辣，清淡菜
static int nHunFood;
static int nSuFood;
static int nXinFood;
static int nQindanFood;
vector<food> menu;
vector< vector<food> > chosenMenus;
vector<food> bestMenu;
double Distance15yuan(const vector<food>& chosenMenu)
{ //所选菜与15元相差多少
// test price
int totalPrice = 0;
for(vector<food>::const_iterator iter = chosenMenu.begin(); iter != chosenMenu.end(); ++iter)
{
totalPrice += (*iter).price;
}
return abs(totalPrice/nPeople - 15); //8折
}
void GetBestMenu()
{
double priceDistance = 1e+308;
double thisDistance = 0.0;
for(vector< vector<food> >::iterator iter = chosenMenus.begin(); iter != chosenMenus.end(); ++iter)
{
thisDistance = Distance15yuan(*iter);
if(thisDistance < priceDistance)
{
priceDistance = thisDistance;
bestMenu = *iter;
}
}
}
bool TestCondition(vector<food> chosenFood)
{ //是否符合荤菜，素菜，辛辣，清淡菜数量要求
int nTestHunFood = 0;
int nTestSuFood = 0;
int nTestXinFood = 0;
int nTestQindanFood = 0;
for(vector<food>::iterator iter = chosenFood.begin(); iter != chosenFood.end(); ++iter)
{
if((*iter).isHun == true)
{
++nTestHunFood;
}
else
{
++nTestSuFood;
}
}
if(nTestHunFood != nHunFood)
{
return false;
}
if(nTestSuFood != nSuFood)
{
return false;
}
for(vector<food>::iterator iter = chosenFood.begin(); iter != chosenFood.end(); ++iter)
{
if((*iter).isXinla == true)
{
++nTestXinFood;
}
else
{
++nTestQindanFood;
}
}
if(nTestXinFood != nXinFood)
{
return false;
}
if(nTestQindanFood != nQindanFood)
{
return false;
}
return true;
}
void CreateChosenMenus(vector<food>leftFood, vector<food> rightFood)
{
if(leftFood.size() == nFoodNeed)
{
if(TestCondition(leftFood) == true)
{
chosenMenus.push_back(leftFood);
}
return;
}
for(vector<food>::iterator iter = rightFood.begin(); iter != rightFood.end(); ++iter)
{
vector<food> newLeftFood(leftFood);
newLeftFood.push_back(*iter);
vector<food> newRightFood;
for(vector<food>::iterator i = iter+1; i != rightFood.end(); ++i)
{
newRightFood.push_back(*i);
}
CreateChosenMenus(newLeftFood, newRightFood);
}
}
void TryToSolove()
{
vector<food> left;
CreateChosenMenus(left, menu);
GetBestMenu();
}
int main(int argc, char* argv[])
{
ifstream is(argv[1], ios::in | ios::binary);
is >> nFoodMenu;
is >> nFoodNeed;
is >> nPeople;
food temp;
for(int i = 0; i < nFoodMenu; ++i)
{
is >> temp.name;
is >> temp.price;
is >> temp.isHun ;
is >> temp.isXinla;
menu.push_back(temp);
}
is >> nHunFood;
is >> nSuFood;
is >> nXinFood;
is >> nQindanFood;
TryToSolove();
double averagePrice = 0.0;
for(vector<food>::iterator iter = bestMenu.begin(); iter != bestMenu.end(); ++iter)
{
cout << (*iter).name << endl;
averagePrice += (*iter).price;
}
printf("%0.2f\n", averagePrice/nPeople*0.8);
return 0;
}
//////////////////////////////////////////////////////////////////////////
题目扫述：
N个小孩正在和你玩一种剪刀石头布游戏（剪刀赢布，布赢石头，石头赢剪刀）。N个小孩中有一个是裁判，其余小孩分成三组（不排除某些组没有任何成员的可能性），但是你不知道谁是裁判，也不知道小孩们的分组情况。然后，小孩们开始玩剪刀石头布游戏，一共玩M次，每次任意选择两个小孩进行一轮，你会被告知结果，即两个小孩的胜负情况，然而你不会得知小孩具体出的是剪刀、石头还是布。已知各组的小孩分别只会出一种手势（因而同一组的两个小孩总会是和局），而裁判则每次都会随便选择出一种手势，因此没有人会知道裁判到底会出什么。请你在M次剪刀石头布游戏结束后，猜猜谁是裁判。如果你能猜出谁是裁判，请说明最早在第几次游戏结束后你就能够确定谁是裁判。
输入要求：
输入文件包含多组测试数据，每组测试数据第一行为两个整数N和M(1<=N<=500，0”和“<”，分别表示和局、第一个小孩胜和第二个小孩胜三种情况。例：
3 3
0<1
1<2
2<0
3 5
0<1
0>1
1<2
1>2
0<2
4 4
0<1
0>1
2<3
2>3
1 0
输出要求：
1．每组测试数据输出一行，若能猜出谁是裁判，则输出裁判的编号，并输出在第几次游戏结束后就能够确定谁是裁判，小孩的编号和游戏次数以一个空格隔开；
2．如果无法确定谁是裁判，输出-2；如果发现剪刀石头布游戏的胜负情况不合理（即无论谁是裁判都会出现矛盾），则输出-1。例：
-2
1 4
-1
0 0
解题方法：
这个题其实是个并查集的题，如果做过食物链的那个题的话，这个题一定是没有问题的，并查集是这个题的基础.
思路是这样的，轮流把这N个小孩看成是裁判，当设i为裁判时，如果对剩余小孩进行并查集归类成功，则小孩i则有可能是裁判。
如果有多于一个小孩或小于一个小孩可能为裁判，很简单，按要求输出既可.
如果只有一个可能为裁判，则这个小孩就为裁判。
如何判断出裁判，那么到第几条才能知道他是裁判呢？其实很简单，只要排除了其余小孩做为裁判的可能性，就知道他是裁判了（排除法，并且这个小孩当裁判并不导致矛盾），所以记录所有小孩当裁判时其余小孩归类错误时的行号，取最大行号的既可。
/////////////////////////////////////////////////////////////////////////
4.蝈蝈计分
#include<stdio.h>
#include<assert.h>
#define MaxNumber 1000
static int nNumber;
static int Numbers[MaxNumber];
enum SIDE{A=0, B=1, AB=1};
enum Result{Failed=0, Success=1, Finished=2};
static int unknown;
static int a,b;
static int aWin,bWin;
static int nMatch;
static int ScoreTab[5][2];
static int hasOldAnswer;
static int Old_nMatch;
static int Old_ScoreTab[5][2];
int Win(int x, int y)
{
if( x>=21 && x-y>1 )
return 1;
else
return 0;
}
enum Result AddScore(enum SIDE side, int score)
{
if( side == A )
{
a += score;
if( Win(a,b) )
{
if( Win(a-1,b) )
return Failed;
else
{
++aWin;
ScoreTab[nMatch][A] = a;
ScoreTab[nMatch][B] = b;
++nMatch;
a = b = 0;
if( aWin == 3 )
return Finished;
else
return Success;
}
}
}
else
{
b += score;
if( Win(b,a) )
{
if( Win(b-1,a) )
return Failed;
else
{
++bWin;
ScoreTab[nMatch][A] = a;
ScoreTab[nMatch][B] = b;
++nMatch;
a = b = 0;
if( bWin == 3 )
return Finished;
else
return Success;
}
}
}
return Success;
}
void Solve(int start, enum SIDE side)
{
if( unknown )
return;
if( start == nNumber )
{
if( a!=0 || b!=0 )
return;
if( !hasOldAnswer )
{
int i;
hasOldAnswer = 1;
Old_nMatch = nMatch;
for(i=0; i<nMatch; ++i)
{
Old_ScoreTab[i][A] = ScoreTab[i][A];
Old_ScoreTab[i][B] = ScoreTab[i][B];
}
}
else
{
if( Old_nMatch != nMatch )
unknown = 1;
else
{
int i;
for(i=0; i<nMatch; ++i)
{
if( Old_ScoreTab[i][A] != ScoreTab[i][A] )
{ unknown = 1; break; }
else if( Old_ScoreTab[i][B] != ScoreTab[i][B] )
{ unknown = 1; break; }
}
}
}
return;
}
if( Numbers[start] != 10 )
{
enum Result tmp = AddScore(side, Numbers[start]);
if( tmp == Failed )
return;
else if( tmp==Finished && nNumber-start!=1 )
return;
else /* Success || Finished */
Solve(start+1, (enum SIDE)(AB-side));
}
else
{
enum Result tmp;
int ta,tb,taWin,tbWin,tnMatch;
ta = a;
tb = b;
taWin = aWin;
tbWin = bWin;
tnMatch = nMatch;
tmp = AddScore(side,10);
if( tmp == Failed )
return;
else if( tmp==Finished && nNumber-start!=1 )
return;
else
Solve(start+1, (enum SIDE)(AB-side));
a = ta;
b = tb;
aWin = taWin;
bWin = tbWin;
nMatch = tnMatch;
tmp = AddScore(side,10+Numbers[start+1]);
if( tmp == Failed )
return;
else if( tmp==Finished && nNumber-start!=2 )
return;
else
Solve(start+2, (enum SIDE)(AB-side));
}
}
int main(int argc, char *argv[])
{
int nCase;
FILE *fin;
fin = fopen(argv[1], "r");
if( !fin )
{
printf("Error: cannot open input file.\n");
return 1;
}
fscanf(fin, "%d", &nCase);
while( nCase-- )
{
int i;
fscanf(fin, "%d", &nNumber);
for(i=0; i<nNumber; ++i)
{
char tmp[2];
fscanf(fin, "%s", tmp);
if( *tmp == 'X' )
Numbers[i] = 10;
else
Numbers[i] = (*tmp-'0');
}
hasOldAnswer = 0;
a = b = aWin = bWin = nMatch = 0;
unknown = 0;
Solve(0,A);
assert( hasOldAnswer );
if( unknown )
printf("UNKNOWN\n");
else
{
for(i=0; i<Old_nMatch; ++i)
printf("%d:%d\n", Old_ScoreTab[i][A], Old_ScoreTab[i][B]);
}
if( nCase != 0 )
printf("\n");
}
fclose(fin);
return 0;
}
/////////////////////////////////////////////////////////////////////
3.变态比赛规则
/*
算法分析：
1。用数组total[]存储可能存在的比赛场数。
2。顺序分析把n个人分成2-（n-1）个组的情况，即顺序分析k= 2-（n-1）
A 用数组fenfa[]存储分成k组时各种不同组合的比赛场数，用数组part[]存储存储具体的组合情况，
即每组有多少人 。
B 将问题“求把n个人分成k组时各种不同组合的情况”转化为：
将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)，
例如:n=7,k=3,下面三种分法被认为是相同的。
1，1，5； 1，5，1； 5，1，1；
求各种不同分法的组合。
C 把求得的各种不同分法的组合存储到数组part[]中。再根据数组part[]计算每种组合的比赛场数。
D 把每种组合的比赛场数存储到数组fenfa[]中。
3。按照上面的分析方法，可以产生n-1个一维数组fenfa[]，把每个数组fenfa[]的值存储到数组total[]。
4。根据输入数据，在数组total[]中进行分析判断。
*/
#include <iostream>
#include<fstream>
#include <time.h>
using namespace std;
const int MAX = 100;
void Readata(const char *filename);
void SplitNumber(int n, int k, int step, int part[], int fenFa[], int &top);
int NumGame(const int part[], int low, int high);
int main()
{
time_t startTime;
time_t endTime;
time(&startTime);
Readata("in.txt");
time(&endTime);
cout << difftime(endTime, startTime) << endl;
getchar();
return 0;
}
void Readata(const char *filename)
{
fstream in(filename);
if (!in)
return ; //结束程序执行
while (!in.eof())
{
int data[2];
in >> data[0];
in >> data[1];
//cout << data[0] << ' ' << data[1] << endl;
int *total = new int[data[0]*data[0]*data[0]];//存储可能存在的比赛场数
total[0] = 0;
int t = 1;
for (int k=2; k<=data[0]; k++)//分析各种分组可能产生的比赛场数
{
int *fenFa = new int[k*data[0]];//存储分成k组时各种不同组合的比赛场数
int *part = new int[k+1];//存储具体的组合情况，即每组有多少人
part[0] = 1;//为处理方便，不考虑下标0，并使part[0] = 1
int top = 0;//累积各种不同组合的数量
SplitNumber(data[0], k, 0, part, fenFa, top);//处理各种不同组合的分法
//for (int i=0; i<top; i++)
// cout << fenFa[i] << ' ';
// cout << endl;
for (int i=0; i<top; i++)//存储可能存在的比赛场数
total[t++] = fenFa[i];
delete []part;
delete []fenFa;
}
int i;
for (i=0; i<t; i++) //判断是否可能存在data[1]场比赛
if (data[1] == total[i])
{
cout << "YES" << endl;
break;
}
if (i == t)
cout << "NO" << endl;
delete []total;
}
in.close(); //关闭文件
}
void SplitNumber(int n, int k, int step, int part[], int fenFa[], int &top)
{
if (k == 2)
{
for (int i=part[step]; i<=n/2; i++)
{
if (n-i >= i)
{
part[step+1] = i;
part[step+2] = n-i;
//for (int j=1; j<=step+2; j++)
// cout << part[j] << ' ';
// cout << endl;
fenFa[top++] = NumGame(part, 1, step+2); //存储每种组合的比赛场数
}
}
}
else
{
for (int i=part[step]; i<=n/2; i++)
{
part[step+1] = i;
SplitNumber(n-i, k-1, step+1, part, fenFa, top);
}
}
}
int NumGame(const int part[], int low, int high)//计算每种组合的比赛场数
{
int sum;
if (low == high) //如果只有1个组，比赛场数为0
sum = 0;
else if (low == high-1)//如果有2个组，比赛场数为两组人数的乘积
sum = part[low] * part[high];
else //如果多于2个组，先把多个组合并成两个大组，再递归处理每个大组
{
int mid = (low + high) / 2 ;
int sum1 = 0;
for (int i=low; i<=mid; i++)
sum1 += part[i];
int sum2 = 0;
for (int i=mid+1; i<=high; i++)
sum2 += part[i];
sum = sum1 * sum2;
sum += NumGame(part, low, mid) + NumGame(part, mid+1, high);
}
return sum;
}