程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 5229 博弈思維

HDU 5229 博弈思維

編輯：C++入門知識

HDU 5229 博弈思維

題意：總共有N 個串，從中拿出2個串來，兩人輪流進行兩種操作

操作1：將兩個串中隨機拿出一個非空串，刪掉其末尾字母

操作2：如果兩個串相同且非空才能執行該操作，清空兩個串；

誰面臨無法執行操作時，判為輸，兩人足夠機靈

題解：明顯如果兩個串相同則必定先生贏，兩個人為了避免對手拿到必勝狀態一定會盡量使兩個串差距大。策略為拿兩個串中最小的串，既能使對家面臨兩個串都為空的狀態或者是兩個串不相等的非必勝狀態。兩人同時采取最優策略，那麼很明顯最終的輸贏只和取的A和B 串長有關， A的長度加上B的長度為奇數，先手勝，否則後手贏。還有一種情況就是初始狀態A串和B串相等，那麼先手勝。所以只需要跑一遍循環記錄之前出現的奇數串和偶數串數目和與之相同串的數目，便可以求出勝率

太久沒動腦子了，題目想不出來，看了官方題解才明白該如何做，加油吧

代碼：

#include
#include
#include
#include
using namespace std;
map<string, int> mymap;
int gcd(int a, int b)
{
    if(b == 0)  return a;
    return gcd(b, a%b);    
}
int main()
{
     int T, n;
     char s1[210005];
     scanf("%d", &T);
     
     while(T--)
     {
       scanf("%d", &n);
       int sum = 0, ou , ji;
       ou = ji = 0, sum = 0;
       mymap.clear();
       for(int i = 1; i <= n; i++)
       {
          scanf("%s", s1);
          if(mymap[s1]) sum += mymap[s1];
          mymap[s1] ++;
          int len = strlen(s1);
          if(len & 1)  sum += ou, ji++;
          else sum += ji, ou++;        
       }     
       int kk = (n*(n-1))/2;  
       int k = gcd(sum, kk);
       printf("%d/%d\n", sum/k, kk/k);     
     }    
}