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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1306][CQOI2009]match循环赛  

2014-11-20 20:58:31|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1306: [CQOI2009]match循环赛

做法不是很好……跑了7s
要是考场上写肯定T出翔
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<map>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 9;
int n,m;
int scan(){int i=0;scanf("%d",&i);return i;}
struct Node{
short dis,d[N];
Node(){d[0] = 0;}
void print(){
printf("dis: %d\nd: ",dis);
for(int i=0;i<=n;i++)printf("%d ",d[i]);
printf("\n");
}
};
bool operator < (Node a,Node b){
if(a.dis%2!=b.dis%2)return a.dis%2 < b.dis%2;
for(int i=0;i<=n;i++)
if(a.d[i]!=b.d[i])return a.d[i] < b.d[i];
return 1<1;
}
typedef unsigned int ll;
queue<Node>dui;
map<Node,short>v;
map<Node,ll>f;
int from[70],to[70];
void update(Node next,ll val){
if(v[next]!=(next.dis+1)){
dui.push(next);
v[next] = next.dis+1;
f[next] = val;
}else f[next] += val;
}
int main(){
//freopen("in.txt","r",stdin);
int i,j;
ll ans=0;
Node now,next,end;
n = scan();
for(i=1;i<=n;i++)
now.d[0] += (now.d[i] = scan());
now.dis = n*(n-1)/2;
now.d[0] -= now.dis*2;
dui.push(now);
v[now] = now.dis+1;
f[now] = 1;
from[now.dis] = 1;
to[now.dis] = 2;
from[0] = n+1;

for(i=now.dis-1;i;i--){
to[i] = to[i+1] + 1;
from[i] = from[i+1];
if(to[i] > n)to[i]=(++from[i])+1;
}
int T=0;
while(!dui.empty()){
T++;
now = dui.front();dui.pop();
//now.print();
int fr,t;ll val;
fr = from[now.dis];t = to[now.dis];
val = f[now];
//printf("times:%d val:%d\n----------\n",T,val);
//check!
if(fr > 1 && now.d[fr-1] > 0)continue;
if(!now.dis && !now.d[0]){
ans = val;
break;
}
//win
if(now.d[fr] >= 3 && now.d[0]){
//printf("win \n");
next = now;
next.d[0]--;
next.d[fr]-=3;
next.dis--;
//next.print();
update(next,val);
}
//draw
if(now.d[fr] >= 1 && now.d[t] >=1 && now.dis > now.d[0]){
next = now;
next.d[fr]--;
next.d[t] --;
next.dis--;
update(next,val);
}
//lose
if(now.d[t] >= 3 && now.d[0]){
next = now;
next.d[0]--;
next.d[t]-=3;
next.dis--;
update(next,val);
}
}
//printf("%d\n",ans);
cout << ans << endl;
return 0;
}

题解:
状压DP(递推计数)
其实不太能算是DP,因为实在是有点暴力
首先由于得分的特点,我们可以很容易得到分出胜负的比赛数目 = Σai - n*(n-1)/2
然后状态是现在进行完第dis场,每队的分数d[i]以及分出胜负的场数d[0]
初始状态就是输入状态,最终状态是所有值都=0
然后要DP的时候要保证顺序是已经确定的。
也就是说第k场是哪两队比是确定的,因为不太好算出来,所以可以提前预处理出来。
因为状态巨大,但是合法状态可能并不多,所以需要进行剪枝:
1.如果一个队伍在之前都一定不会再进行比赛那么它的分数必须是0
2.如果剩下的场数和分出胜负的场数一样就不枚举平局的情况
然后一开始跑了9s..
到网上搜了下标解似乎是hash判重+dfs搜索,最快的所有数据能达到10+s..
然后我把
int->short 
long long -> unsigned int
变成了7s,如果把map改成hash的话可能会更快0.0
另:
一开始怕爆int全用的long long,结果后来一看有中间变量是int
这么粗心考场上肯定要跪啊……
  评论这张
 
阅读(17)| 评论(3)
推荐 转载

历史上的今天

评论

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

页脚

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