astar2006百度之星参考源程序.txt

06百度之星题目和解答!

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)
{