【题解】HNOI2013比赛-白红宇

【题解】HNOI2013比赛

阅读量：5021 次

发布时间：2019-06-12

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

【题解】[P3230

将得分的序列化成样例给的那种表格，发现一行和一列是同时确定的。这个表格之前是正方形的，后来长宽都减去一，还是正方形。问题形式是递归的。这就启示我们可以把这个正方形$hash$起来，直接搜索。

平局和胜场可以很显然地算出来，

$draws=\frac{(n)(n-1)}{2} \times 3-sum$

$wins=\frac{n(n-1)}{2}-draws$

靠这个剪枝。

注意

if(rac[now]+(n-to+1)*3

不能是

if(rac[now]+(win)*3

也不能是

if(rac[now]+(win)*3+drs

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   using namespace std;#define RP(t,a,b) for(register int (t)=(a),edd_=(b);t<=edd_;++t)#define DRP(t,a,b) for(register int (t)=(a),edd_=(b);t>=edd_;--t)#define ERP(t,a) for(int t=head[a];t;t=e[t].nx)#define Max(a,b) ((a)<(b)?(b):(a))#define Min(a,b) ((a)<(b)?(a):(b))#define TMP template
                   
                    #define lef L,R,l,mid,pos<<1#define rgt L,R,mid+1,r,pos<<1|1#define midd register int mid=(l+r)>>1#define chek if(R
                    
                     
                      57) q=c==45?-1:q,c=getchar(); while(c>=48&&c<=57) x=x*10+c-48,c=getchar(); if(q==-1) x=-x; return x;}const int maxn=17;ll data[maxn];ll rac[maxn];ll n;ll temp[maxn];map < ll , ll > mp;const ll mod=1e9+7;int f=1;int drs,win;inline ll ha(int x){ int cnt=0; RP(t,x+1,n) temp[++cnt]=data[t]-rac[t]; sort(temp+1,temp+cnt+1); ll ret=0; RP(t,1,cnt) ret=ret*28+temp[t]; //ret=ret*46+dr; //ret=ret*46+win; return ret;}inline void com(int x,int y,int k){ if(k==1) drs--,rac[x]++,rac[y]++; if(k==3) win--,rac[x]+=3; if(k==0) win--,rac[y]+=3;}inline void back(int x,int y,int k){ if(k==1) drs++,rac[x]--,rac[y]--; if(k==3) win++,rac[x]-=3; if(k==0) win++,rac[y]-=3;}inline bool jde(int x,int y,int k){ com(x,y,k); if(rac[x]<0||rac[y]<0||rac[x]>data[x]||rac[y]>data[y]||drs<0||win<0) return 0; return 1;}int dx[]={0,1,3,0};ll dfs(int now,int to){ if(rac[now]+(n-to+1)*3
                      
                       n){ //return dfs(now+1,now+2); ret=ha(now); if(mp.find(ret)!=mp.end()) return mp[ret]; else return mp[ret]=dfs(now+1,now+2); } RP(t,1,3){ if(jde(now,to,dx[t])) ret+=dfs(now,to+1); back(now,to,dx[t]);ret%=mod; }return ret;}int main(){#ifndef ONLINE_JUDGE freopen("in.in","r",stdin); freopen("out.out","w",stdout);#endif n=qr(1); win=(n*(n-1))>>1; drs=0; RP(t,1,n) drs+=(data[t]=qr(1)); drs=win*3-drs; win-=drs; sort(data+1,data+n+1); printf("%lld\n",dfs(1,2)); return 0;}

转载于:https://www.cnblogs.com/winlere/p/10333220.html

你可能感兴趣的文章