SDUT 3568 Rock Paper Scissors 状压统计

就是改成把一个字符串改成三进制状压，然后分成前5位，后5位统计，

然后直接统计 f[i][j][k]代表，后5局状压为k的，前5局比和j状态比输了5局的有多少个人

复杂度是O（T*30000*25*m）m比较小，也就最多几十吧，将将过

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <vector>

#include <cmath>

#include <queue>

#include <map>

#include <string>

using namespace std;

typedef long long LL;

const int N=3e4+;

const int M=;

const int INF=0x3f3f3f3f;

int get(int x,int y){

  int ret=;

  for(int k=;k<;++k){

    int dig0=x%,dig1=y%;

    if(dig0==(dig1+)%)++ret;

    x/=,y/=;

  }

  return ret;

}

vector<int> win[][M],lose[][M];

int T,cas,n,a[N][],ret[N][],f[][M][M];

char ch[];

int main(){

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

    for(int j=;j<M;++j){

      win[get(i,j)][i].push_back(j);

      lose[get(i,j)][j].push_back(i);

    }

   }

   scanf("%d",&T);

   while(T--)

   {

    scanf("%d",&n);

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

    {

      scanf("%s",ch);

      for(int j=;j<;++j)

      {

        if(ch[j]=='R')a[i][j]=;

        else if(ch[j]=='P')a[i][j]=;

        else a[i][j]=;

      }

    }

    memset(f,,sizeof(f));

    memset(ret,,sizeof(ret));

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

    {

       int mask0=,mask1=;

       for(int j=;j<;++j)mask0=mask0*+a[i][j];

       for(int j=;j<;++j)mask1=mask1*+a[i][j];

       for(int j=;j<=;++j)

       {

          for(int k=;k<lose[j][mask0].size();++k)

          {

              int t=lose[j][mask0][k];

              ++f[j][t][mask1];

          }

       }

    }

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

       int mask0=,mask1=;

       for(int j=;j<;++j)mask0=mask0*+a[i][j];

       for(int j=;j<;++j)mask1=mask1*+a[i][j];

       for(int s0=;s0<=;++s0)

         for(int s1=;s1<=;++s1){

           for(int k=;k<win[s1][mask1].size();++k){

             int t=win[s1][mask1][k];

             ret[i][s0+s1]+=f[s0][mask0][t];

           }

         }

      --ret[i][];

    }

    printf("Case #%d:\n",++cas);

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

      for(int j=;j<;++j)

        printf("%d ",ret[i][j]);

      printf("%d\n",ret[i][]);

    }

   }

   return ;

}