HDU 5229 博弈思维 - c++编程基础

TOP

HDU 5229 博弈思维

2015-11-21 01:01:41 来源: 作者: 【大中小】浏览:2次

题意：总共有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); } }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 2495 Incomplete chess board..	下一篇：c/c++中空指针，空指针常量，NULL

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: