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;
}