ACM竞赛第十题.docx

10-20-30有一种称为102030的用52张不考虑花色的纸牌游戏。人头牌(K、Q、J)的值是10，A的值是1，任何其他牌的值是它们的面值(如2、3、4等)。牌从牌堆的顶端发起。你先发7张牌，从左至右形成7组。当给最右边一组发了一张牌后，下一张牌就应发最左边的一组。每给一组发一张牌时，查看这组牌的以下三张牌的组合的总和是否为10、20或30： 前两张和最后一张， 第一张和最后二张，或 最后三张。如果是这样，就抽出这三张牌并将其放在牌堆的底部。对于这个问题，总是按上面给出的顺序查看牌。按牌在组中出现的顺序将它们取出并放在牌堆的底部。当抽出三张牌时，又有可能出现三张可以抽出的牌。如果是这样，再将它们抽出。如此重复直至再也不能从这组牌抽出符合条件的牌为止。举例来说，假设有组牌含5、9、7、3，5是第一张牌，然后发出6。前两张牌加最后一张牌(5+9+6)等于20。抽出这三张牌后这组牌成为7、3。而牌堆的最底部变成6，6上面的一张牌是9，9上面的一张牌是5(如图6.2-1)。图6.2-1如果发的不是6而是Q，那么5+9+10=24，5+3+10=18，但7+3+10=20，因此最后三张牌可以抽走，剩下5、9(如图6.2-2)。图6.2-2如果有一组只含有三张牌且这组牌的和为10、20或30，那么这组牌被抽走后就“消失”了。这就是说，随后的发牌将跳过现在成为空的这组牌的位置。当所有牌组都消失，你就获胜。当你无牌可发时，你游戏失败。当前两种情况都不发生时，出现平局。编写一个程序，将初始的牌堆作为输入，完成102030游戏。输入每组输入由52个整数组成，由空格和或行结束(end 0f line)分开。整数表示初始牌堆的面值。第一个整数是牌堆的最顶端的牌。在最后一张牌后输入0标志输入结束。输出对每组输入，输出游戏结果是胜、负还是平局，并输出游戏结果决定前所发的牌数。(假如游戏状态发生重复，意味着平局)使用“输出范例”部分中表明的格式。输入范例输出范例2 6 5 10 10 4 10 10 10 4 5 10 4 5 10 9 7 6 1 7 6 9 5 3 10 10 4 10 9 2 110 1 10 10 10 3 10 9 8 10 8 7 1 2 8 6 7 3 3 8 2 4 3 2 10 8 10 6 8 9 5 8 10 5 3 5 4 6 9 9 1 7 6 3 5 10 10 8 10 9 10 10 72 6 10 10 4 10 1 3 10 1 1 10 2 2 10 4 10 7 7 1010 5 4 3 5 7 10 8 2 3 9 10 8 4 5 1 7 6 7 2 6 9 10 2 3 10 3 4 4 9 10 1 110 5 10 10 1 8 10 7 8 10 6 10 10 10 9 6 2 10 10 0 Win：66Loss：82Draw：73试题来源：ACM 1996总决赛在线测试地址：UVA 246试题解析 我们将游戏过程中手中牌和各堆牌的状况用字符串s表述 分隔定位每堆牌的区间 我们将7堆牌和手中的牌转化为字串s，并通过大写字母”ABCDEFGH”分割的办法定位每堆牌的位置。例如，初始时输入52张牌的面值a1.52，则s=”Aa1Ba2Ca3Da4Ea5Fa6Ga7Ha8.52”。a1.7为最先放入牌堆1牌堆7的七张牌，手中的牌为a8.52，并将之定义为牌堆8。为了定位每堆牌在s中的首尾位置设signi为第i堆的标志（sign1=A, , sign7=G，sign8=H），该堆牌在s中的首尾指针为li和ri。显然，li为s中字符signi的位置+1；ri为s中字符signi+1的位置-1。使用哈希技术判别重合情况我们将字串s设为状态。显然，当前状态若与先前状态重合，则说明继续玩下去是不可能有输赢的，应视为平局。为此，我们使用哈希技术存储当前状态。状态s的哈希函数设为hash(s)=若不考虑花色的话，纸牌共有13个不同种类，我们将s中的每一位数码看作是一个13进制数。hash(s)取s对应的13进制数对素数（小于哈希表长的最大素数）的余数。但这个哈希函数并不完全可靠，因为不能保证哈希值与状态一一对应。为此，我们采用开放寻址法消除冲突：将hash(s)设为哈希表中搜索状态s的首址；另外再设状态s的判重函数hash2(s)，该函数值取s对应的13进制数对素数的余数，即hash2(s)=只有当hash(s1)=hash(s2)，hash2(s1)=hash2(s2)时，才可确定状态s1和s2相同。哈希表为h和key，其中hf为状态存储标志。若hf=1，则keyf存储状态的判重函数值。我们将对应同一哈希函数值的所有状态存放在一个连续的存储空间，即从单元f1(f1=hash(s)开始，设置一个连续的存储空间f1, f1+1,，其中hf1=1, keyf1!=f2, hf1+1=1, keyf1+1!=f2, （f2=hash2(s)），即这些状态的判重函数值各不相同，都是非同一状态。若想要存储状态s，则先计算s的哈希值f1和判重函数值f2；然后从f1单元开始，逐个单元搜索：若发现状态s已在哈希表中（hf=1，keyf=f2，f1f），则放弃存储；若发现状态s未在哈希表中出现（hf=0，f1f），则设hf=1，并将s的判重函数值存储在keyf中(keyf=f2)。模拟发一张牌给第i堆牌的过程首先取手中的第1张牌（取出s中第l(8)位置的字符t，从s中删除该字符），放入第i堆牌尾(t插入s的r(i)+1位置)。然后在第i堆牌中反复进行3种组合的处理，直至第i堆不少于3张牌（r(i)-l(i)2）或者无法组合为止。 若第i堆牌被取完（r(i)<l(i)），则标志该堆牌消失（vi=true）。模拟游戏过程 首先读入52张牌，计算初始状态s； 计算f=hashs，将s置入哈希表（hf=1, keyf=hash2s）； 堆序号i初始化为1，发牌数step设为7； 进入循环，直至结果产生为止： 累计所发牌数（step+）；手中的首张牌发给第i堆，进行组合处理： 若状态s在哈希表存在，则输出“Draw”和发牌数step，并退出程序； 若无牌可发（l(8)s.size()），则输出“Loss”和发牌数step，并退出程序； 若所有牌堆消失，则输出“Win”和发牌数step，并退出程序； 寻找未消失的下一个牌堆i（i=(i%7)+1; while(vi) i=(i%7)+1），继续循环；参考程序：#include<iostream> /预编译命令#include<cstdio>#include<fstream>#include<algorithm>#include<cmath>#include<vector>#include<map>#include<cstring>#include<math.h>#include<string>#include<set>using namespace std; /使用 C标准程序库中的所有标识符const int p=; /哈希函数1的模const int p2=; /哈希函数2的模bool h; /hf标志哈希值1为f的状态已经出现int key; /标志哈希值1为f的状态，其对应的哈希值2为keyfstring s; /用于储存当前状态 int a60,n; /纸牌的面值序列为achar sign10; /牌堆标志，用于在字符串中定位 bool v10; /牌堆是否被拿完的标志，vi=true标志第i组牌已消失 int num(char c) /将牌符转化为面值（人头牌的面值为10，其它牌的面值对应牌符） if (c='0') return 10; else return c-'0'int ch(int x) /将牌的面值转化为牌符（人头牌的牌符为0，其它牌的牌符对应面值） if (x=10) return '0' else return char('0'+x);int l(int i) /计算s中第i个牌堆的首指针 return s.find(signi)+1;int r(int i) /计算s中第i个牌堆的尾指针 return s.find(signi+1)-1;int hash(string s) /计算状态s的哈希值：hash(s)= int f=0; for (int i=0;i<=s.size()-1;i+) f=(f*13+si-'0')%p; return f;int hash2(string s) /计算状态s的判重函数值 ：hash2(s)= int f=0; for (int i=0;i<=s.size()-1;i+) f=(f*31+si-'0')%p2; return f;bool have(string s) /若状态s未曾出现，则加入哈希表中并返回0；否则返回1 int f=hash(s),f2=hash2(s); /计算状态s的哈希值f和判重函数值f2 while (hf&&(keyf!=f2) f+; if (!hf) /若s未在哈希表中出现，则加入哈希表，存储对应的判重函数值并返回0 hf=1; keyf=f2; return 0; else return 1; /否则状态s在哈希表中存在void initialize() /初始化 s.clear(); /状态初始化为空 char c='A' for (int i=1;i<=n;i+) /计算定位数组sign1.8=”ABCDEFGH”, 状态s=”Aa1Ba2Ca3Da4Ea5Fa6Ga7Ha8.52” if (i<=8) s+=c; signi=c; c+; s+=ch(ai); memset(v,0,sizeof(v); /初始时所有牌堆未消失 memset(h,0,sizeof(h); /哈希表初始化为空 memset(key,0,sizeof(key); have(s); /构造状态s的哈希表void remove1(int i) /处理第i堆牌的第1种组合： string t=s.substr(l(i),2);/将第i堆牌的前2张牌和最后1张牌的数和插入状态s t+=s.substr(r(i),1); s+=t; s.erase(l(i),2); /释放这三张牌 s.erase(r(i),1);bool case1(int i) /判断第i堆牌是否出现第1种组合：若前2张牌和最后1张牌的数和不等于10、20、30，则返回0；否则将数和插入s，释放这三张牌并返回1 int sum=num(sl(i)+num(sl(i)+1)+num(sr(i); if (sum=10|sum=20|sum=30) remove1(i); return 1; return 0;void remove2(int i) /处理第i堆牌的第2种组合 string t=s.substr(l(i),1);/将第i堆牌的第1张牌和最后2张牌的数和插入s t+=s.substr(r(i)-1,2); s+=t; s.erase(l(i),1); /释放这三张牌 s.erase(r(i)-1,2);bool case2(int i) /判断第i堆牌是否出现第2种组合：若第1张牌和最后2张牌的数和不等于10、20、30，则返回0；否则将数和插入s，释放这三张牌并返回1 int sum=num(sl(i)+num(sr(i)-1)+num(sr(i); if (sum=10|sum=20|sum=30) remove2(i); return 1; return 0;void remove3(int i) /处理第i堆牌的第3种组合 string t=s.substr(r(i)-2,3); / 将第i堆牌的最后3张牌的数和插入状态s s+=t; s.erase(r(i)-2,3); / 释放这三张牌bool case3(int i) /判断第i堆牌是否出现第3种组合：若最后3张牌的数和不等于10、20、30，则返回0；否则将数和插入状态s，释放这三张牌并返回1 int sum=num(sr(i)-2)+num(sr(i)-1)+num(sr(i); if (sum=10|sum=20|sum=30) remove3(i); return 1; return 0;void deliver(int i) /将手中的首张牌发给第i堆，进行组合处理 string t=s.substr(l(8),1);/取手中的第1张牌，放入第i堆牌尾，该牌从手中释放 s.insert(r(i)+1,t); s.erase(l(8),1); if (r(i)-l(i)>=2) /若第i堆不少于3张牌，则反复处理3种组合，直到无法组合为止 while (r(i)-l(i)>=2) bool flag=0; if (case1(i) continue; else if (case2(i) continue; else if (case3(i) continue; else flag=1; if (flag) break; /若未出现任何一种组合，则退出循环 if (r(i)<l(i) vi=1; /若第i堆牌拿完，则标志该堆牌消失int over() /判断游戏是否结束 if (have(s) return 3; else /若状态s在哈希表存在，则返回平局标志 if (l(8)>=s.size() return 2; else /若无牌可发，返回输标志 for (int i=1;i<=7;i+) /若存在未消失的牌堆，则返回继续游戏标志if (!vi) return 0; return 1; /否则返回赢标志void game() /模拟游戏过程 int i=1; /从第1堆开始，先发7张牌 int step=7; int res; /结果标志 while (1) deliver(i); /将手中的首张牌发给第i堆，进行组合处理 step+; /累计所发的牌数 res=over(); /计算和返回当前状态的结果值 if (res) break; /若结果产生，则退出while循环 i=(i%7)+1; /继续寻找未消失的下一组牌 while (vi) i=(i%7)+1; /根据结果标志，输出输赢或平局信息 if (res=1) cout<<"Win : " else if (res=2) cout<<"Loss: " else if (res=3) cout<<"Draw: " cout<<step<<endl; /输出所发牌数int main() /读入过程和主过程 n=52; /牌数 cin>>a1; /读第1组测试用例的首张牌 while (a1) /若当前测试用例的首张牌非零，则读余下的51张牌 for (int i=2;i<=n;i+) cin>>ai; initialize(); /初始化 game(); /模拟游戏过程 cin>>a1; /读下1组测试用例的首张牌