HDU 5229 ZCC loves strings 博弈

题目链接：

hdu:http://acm.hdu.edu.cn/showproblem.php?pid=5229

bc:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=582&pid=1002

题解：

设字符串a，b;

结论：先手胜的充分必要条件是|a|+|b|为奇数或a==b。

证明：

数学归纳法：

|a|+|b|=0；时，先手败，结论成立

假设|a|+|b|<p时结论成立，现在分类讨论|a|+|b|的情况：

p为偶数：

如果a=b，则先手直接采取方案b取胜，否则，先手只能执行方案A必败。

p为奇数：

先手只要用方案a取走一个，且保证取走之后a！=b（取较短的那个，当较短为0时，去另一个），那么就能保证必胜。

综上所述，结论成立。

---------------------------------我是分割线----------------------------------

对于当前输入串，统计它之前与它相等的串的个数x和长度与它不同奇偶的串的个数y，累加它对答案的贡献x+y，线性扫一遍就好了。

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<map>

 using namespace std;

 const int maxn=1e5+;

 int odd[];

 char str[maxn];

 int n;

 map<string,int> mymap;

 void init(){

     mymap.clear();

     memset(odd,,sizeof(odd));

 }

 int gcd(int a,int b){ return b==?a:gcd(b,a%b); }

 int main(){

     int tc;

     scanf("%d",&tc);

     while(tc--){

         init();

         int ans=;

         scanf("%d",&n);

         for(int i=;i<n;i++){

             scanf("%s",str);

             int o=strlen(str)&;

             ans+=odd[!o];

             odd[o]++; 

             //str不需要是string类型！

             ans+=mymap[str];

             mymap[str]++;

         }

         int demo=n*(n-)/;

         int g=gcd(ans,demo);

         if(ans==) printf("0/1\n");

         else printf("%d/%d\n",ans/g,demo/g);

     }

     return ;

 }

 /*

 2

 ab

 bc

 */

巴特西

HDU 5229 ZCC loves strings 博弈

题目链接：

题解：

代码：

最新文章

热门文章