WOJ 1619-白红宇

WOJ 1619

阅读量：5154 次

发布时间：2019-06-13

本文共 2557 字，大约阅读时间需要 8 分钟。

武大校赛的一个题目，先简单总结一下比赛，第一次出去去现场赛，难免遇到一些问题。。这次主要问题就两个吧，2h挂机以后发现了模板题结果没带模板。。看到模拟题迟迟没有动手试图用奇淫技巧去过模板题。。。其实老老实实写模拟说不定还好一些呢。。。时间分配感觉不是很好，和平常用三个机器确实差很多，以后继续努力吧！来年再战。

这个就是当时的麻将题，题意是化简的麻将规则，然后给你一副牌看看能不能胡，这题一张一张搜应该也可以，毕竟每种的合法接临牌就那么几个，有时间试一下似乎更快。。后来听群里说可以枚举子集，于是自己写了个状压的记忆化来枚举，每次拿出三个看看可以不可以就行了，不过复杂度还是不太会计算，这里优化的技巧是预处理出来每个状态的1的个数。。。题比较长，代码能力有待提升。

#include 
    
     #include 
     #include 
      
       #include 
       
        #include 
        
         using namespace std;int lim=0;int dp[1<<12];int has[1<<12];vector
         
           v;string vv[12];map
          
            mp;string ans[3];int ccc;int p3(int x){ ccc=0; for(int i=0;i<12;i++){ if((x>>i)&1) ans[ccc++]=vv[i]; } if(ans[0]==ans[1]&&ans[1]==ans[2]) return 1; if(ans[0][1]!=ans[1][1]||ans[1][1]!=ans[2][1]||ans[0][1]!=ans[2][1]) return 0; ans[0][0]+=2; ans[1][0]+=1; if(ans[0]==ans[1]&&ans[1]==ans[2]) return 1; return 0;}int man=0;int ncnt(int x){ int ret=0; while(x){ x=x&(x-1); ret++; } return ret;}int k;int DP(int sit){ if(dp[sit]!=-1) return dp[sit]; if(has[sit]==3){ dp[sit]=p3(sit); return dp[sit]; } for(int i=(sit&(sit-1));i;i=((i-1)&sit)){ if(has[i]%3==0) dp[sit]=max(DP(i)+DP(sit-i),dp[sit]); } return dp[sit];}int p(){ map
           
            ::iterator it=mp.begin(); string s1; string s2; int i,ii,cnt,cc; vector
            
             ::iterator st; for(;it!=mp.end();it++){ if(it->second>=2){ memset(dp,-1,sizeof(dp)); cnt=0; ii=0; st=v.begin(); for(;st!=v.end();st++){ if(*st==it->first&&cnt<2){ cnt++; continue; } vv[ii++]=*st; } cc=1; for(int i=0;i<12;i++){ if(vv[i].size()==1){ if(mp[vv[i]]<3){ cc=0; break; } } else{ s1=vv[i]; s2=vv[i]; s1[0]+=1; s2[0]-=1; if(mp[vv[i]]<3&&mp.find(s1)==mp.end()&&mp.find(s2)==mp.end()){ cc=0; break; } } } sort(vv,vv+12); if(cc&&DP(man)==4){ return 1; } } } return 0;}int p13(){ if(mp.size()==13&& mp.find("1w")!=mp.end()&&mp.find("9w")!=mp.end()&& mp.find("1t")!=mp.end()&&mp.find("9t")!=mp.end()&& mp.find("1b")!=mp.end()&&mp.find("9b")!=mp.end()&& mp.find("w")!=mp.end()&&mp.find("e")!=mp.end()&&mp.find("s")!=mp.end()&&mp.find("n")!=mp.end()&& mp.find("f")!=mp.end()&&mp.find("z")!=mp.end()&&mp.find("b")!=mp.end()) return 1; else return 0;}int p7(){ if(mp.size()==7){ map
             
              ::iterator it=mp.begin(); for(;it!=mp.end();it++){ if(it->second!=2) return 0; } return 1; } return 0;}int main(){ int t; cin>>t; for(int i=0;i<12;i++){ man+=(1<
              
               >s; mp[s]++; v.push_back(s); } int bo=0; bo=p13(); if(bo==1){ cout<<"Yes\n"; continue; } bo=p7(); if(bo==1){ cout<<"Yes\n"; continue; } bo=p(); if(bo==1){ cout<<"Yes\n"; } else cout<<"No\n"; } return 0;}

转载于:https://www.cnblogs.com/zhangxianlong/p/10672579.html

你可能感兴趣的文章