注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

ctsc2012 showhand  

2014-02-28 20:57:19|  分类: ctsc |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本来想把CTSC的题像WC那样做下的
不过似乎现在的话还是早点开始补NOI吧
那就把CTSC2012,2013的可做传统题搞一下就去补NOI去了

先吐槽下出题人名字跟某个曾经狂虐我的初中同学缩写一样……
然后感谢这题让我知道了怎么打梭哈
这题刚开始的时候是想枚举我的牌……然后各种组合计数之类的搞搞的
看起来应该分开写一定能写出来
事实证明我错了……

那种做法可写?????????

中间穿插了CF、学校的考试……
结果一直拖到昨天晚上还有30分……
然后立了个奇怪的flag,调不出来就不睡觉
凌晨的时候终于查出了各种bug,然后90分
又裸眼检查了一个小时……发现什么都没检查出来
发现凌晨一点了,有种明天(今天)就不用去上课了的不祥预感
最后还是滚回去睡觉了……
然后早上被检查迟到的抓住登记名字了呵呵

翘了两节数(自)学(习)课……偷跑去机房检查
经过各种这里改一下那里动一下的实验总算找出错误了……
然后用时rank1……觉得很是惊讶。表示我只是为了方便hash所以选了个二进制数来左移什么的,没想到竟然rank1了
希望早点停课吧……那样我就不会立些乱七八糟的flag了
虽然那样的话某种意义上而言也是心态上的退步

看起来能跑得过复杂度的算法显然……
能写的出来的算法?其实应该还是能想的只是想到一个很好想的想法之后就很难冷静下来用信息的思维思考他了
我们来说正解吧

我们枚举所有牌的组合……是C(52,5)的
重载一个<,排序
重载<是最容易写错的地方,我检查的时候基本上都是在检查这里……当然也是因为ydc太弱了的原因
排序之后,我们要统计的就是:
对于每一个我可能抽得到的牌面A,
统计有几个对方可能抽得到的牌面B,
使得B<A
而且B与A没有相同牌
前三个是普及组难度的约束条件……
sort一下之后扫过去,开个变量累加能是B的,遇上能是A的就加上那个变量
所以真正麻烦的是“B与A没有相同牌”
当然这也只是提高组难度
由于牌数=5,所以可以2^5的容斥
于是问题就解决了……常数的话没怎么在意,一不小心就rank1了
其实问题本身不是很难
但是出题人把简单地模型隐藏在了让人晕头转向的梭哈下(像我这种不会打麻将不会打梭哈的都被某些题给教会一点了)
模拟题、代码题的可怕外表下,就很难想到那些平常总能想到的技巧性东西了
果然叫这个名字的都是大神……
先去改今天的考试题了……不改完就……算了不敢再立flag了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#define maxn 12
#define maxm 3000000
#define mod 7812521
#define lowbit(x) (x&-x)
#define TONGHUASHUN 9
#define SITIAO 8
#define MANTANGHONG 7
#define TONGHUA 6
#define SHUNZI 5
#define SANTIAO 4
#define LIANGDUI 3
#define YIDUI 2
#define WUDUI 1
using namespace std;
typedef long long LL;
struct Node
{
int state1,state2,S,type;
bool in(int *a,int n)
{
int i=0;
for(int j=S;i<n&&j;++i,j>>=6)
{
while((j&63)<a[i]&&j)
j>>=6;
if((j&63)!=a[i])
return false;
}
return i==n;
}
int which()
{
static int num[maxn],col[maxn],a[maxn];
bool tong=false,shun=false;
int n=0;
for(int i=S;i;i>>=6)
a[++n]=i&63,num[n]=(a[n]>>2)+1,col[n]=a[n]&3;
if(num[1]==num[2]-1&&num[2]==num[3]-1&&num[3]==num[4]-1&&num[4]==num[5]-1)
shun=true;
if(num[1]==1&&num[2]==10&&num[3]==11&&num[4]==12&&num[5]==13)
shun=true;
if(count(col+1,col+6,col[1])==5)
tong=true;
if(shun==false||num[2]!=2)
{
int st;
for(st=1;num[st]==1;++st)
++n,a[n]=52+a[st],num[n]=14,col[n]=col[st];
for(int i=st;i<=n;++i)
a[i-st+1]=a[i],num[i-st+1]=num[i],col[i-st+1]=col[i];
n=5;
}
for(int i=n;i>=1;--i)
state1=state1<<6|num[i];
state2=col[n];
if(tong&&shun)
{
state1=num[n],state2=col[n];
return TONGHUASHUN;
}
if(num[1]==num[4])
{
state1=num[4],state2=col[4];
return SITIAO;
}
if(num[2]==num[5])
{
state1=num[5],state2=col[5];
return SITIAO;
}
if(num[1]==num[3]&&num[4]==num[5])
{
state1=num[3],state2=col[3];
return MANTANGHONG;
}
if(num[3]==num[5]&&num[1]==num[2])
{
state1=num[5],state2=col[5];
return MANTANGHONG;
}
if(tong)
return TONGHUA;
if(shun)
return SHUNZI;
if(num[1]==num[3])
{
state1=num[3],state2=col[3];
return SANTIAO;
}
if(num[2]==num[4])
{
state1=num[4],state2=col[4];
return SANTIAO;
}
if(num[3]==num[5])
{
state1=num[5],state2=col[5];
return SANTIAO;
}
if(num[1]==num[2]&&num[3]==num[4])
{
state1=(num[4]<<6|num[2])<<6|num[5],state2=col[4];
return LIANGDUI;
}
if(num[1]==num[2]&&num[4]==num[5])
{
state1=(num[5]<<6|num[2])<<6|num[3],state2=col[5];
return LIANGDUI;
}
if(num[2]==num[3]&&num[4]==num[5])
{
state1=(num[5]<<6|num[3])<<6|num[1],state2=col[5];
return LIANGDUI;
}
for(int i=2;i<=n;++i)
if(num[i]==num[i-1])
{
state1=num[i],state2=col[i];
for(int j=n;j>=1;--j)
if(num[j]!=num[i])
state1=state1<<6|num[j];
return YIDUI;
}
return WUDUI;
}
friend bool operator < (const Node &a,const Node &b)
{
if(a.type!=b.type)
return a.type<b.type;
if(a.state1!=b.state1)
return a.state1<b.state1;
return a.state2<b.state2;
}
}st[maxm];
int n,tot,play1[maxn],play2[maxn];
int F[maxn]={52};
LL ans1,ans2;
int nEdge=1,start[mod+10],to[mod],next[mod],dp[mod];
int get(int p)
{
int x=p%mod;
for(int i=start[x];i;i=next[i])
if(to[i]==p)
return i;
++nEdge,to[nEdge]=p,next[nEdge]=start[x],start[x]=nEdge;
return nEdge;
}
void read()
{
scanf("%d",&n);
for(int i=0,a,b;i<n;++i)
{
scanf("%d %d",&a,&b);
play1[i]=a*4-b;
}
for(int i=0,a,b;i<n-1;++i)
{
scanf("%d %d",&a,&b);
play2[i]=a*4-b;
}
sort(play1,play1+n),sort(play2,play2+n-1);
}
void addstate()
{
++tot;
int &s1=st[tot].S;
for(int i=1;i<=5;++i)
s1=s1<<6|F[i];
st[tot].type=st[tot].which();
}
void DFS(int p)
{
if(p>5)
{
addstate();
return ;
}
for(int i=F[p-1]-1;i>=0;--i)
{
F[p]=i;
DFS(p+1);
}
}
void work()
{
static int num[maxn];
sort(st+1,st+tot+1);
int sumB=0;
for(int i=1;i<=tot;++i)
{
if(st[i].in(play1,n))
{
int cnt=0;
for(int j=st[i].S;j;j>>=6)
num[cnt++]=j&63;
reverse(num,num+cnt);
ans1+=sumB;
for(int i=1;i<=31;++i)
{
int sign=1,state=0;
for(int j=0;j<=4;++j)
if(i>>j&1)
sign*=-1,state=state<<6|num[j];
ans1=ans1+sign*dp[get(state)];
}
}
if(st[i].in(play2,n-1))
{
++sumB;
int cnt=0;
for(int j=st[i].S;j;j>>=6)
num[cnt++]=j&63;
reverse(num,num+cnt);
for(int i=1;i<=31;++i)
{
int state=0;
for(int j=0;j<=4;++j)
if(i>>j&1)
state=state<<6|num[j];
++dp[get(state)];
}
}
}
static LL comb[60][10];
comb[0][0]=1;
for(int i=1;i<=52;++i)
{
comb[i][0]=1;
for(int j=1;j<=5;++j)
comb[i][j]=comb[i-1][j]+comb[i-1][j-1];
}
ans2=comb[52-2*n+1][5-n]*comb[52-4-n][6-n];
}
void print()
{
LL d=__gcd(ans1,ans2);
ans1/=d,ans2/=d;
printf("%lld/%lld\n",ans1,ans2);
}
int main()
{
read();
DFS(1);
work();
print();
return 0;
}


  评论这张
 
阅读(659)| 评论(3)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017