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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1028][JSOI2007]麻将  

2014-11-03 15:16:16|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1028: [JSOI2007]麻将

时限只有1s……以为会T然后又过了=。=
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
const int N = 400+10;
const int M = 3000+100;
int scan(){int i=0;scanf("%d",&i);return i;}
int n,m;
int num[N],list[N];
//从小开始优先让相同的牌组到一起
bool check(){
list[0] = 0;
int i,tmp[N];
bool ok = 1;
for(i=1;i<=n;i++)tmp[i] = num[i];
for(i=1;i<=n;i++)
if(tmp[i]){
while(tmp[i] >= 3)tmp[i]-=3;
while(tmp[i]){
if(tmp[i+1]==0||tmp[i+2]==0 || i+2 > n){ok=0;break;}
tmp[i]--;tmp[i+1]--;tmp[i+2]--;
}
if(!ok)break;
}
return ok;
}
int main(){
int i,j,a,b,ans[N]={};
//freopen("in.txt","r",stdin);
n = scan();m = scan();
for(i=1;i<=m*3+1;i++){
a = scan();
num[a]++;
}
for(i=1;i<=n;i++){
num[i]++;
bool ok = 0;
for(j=1;j<=n&&!ok;j++)
if(num[j] >= 2){
num[j]-=2;
if(check())ok=1;
num[j]+=2;
}
num[i]--;
if(ok){ans[++ans[0]] = i;}
}
if(ans[0]==0)printf("NO\n");
for(i=1;i<=ans[0];i++)
if(i < ans[0]) printf("%d ",ans[i]);
else printf("%d",ans[i]);
return 0;
}

题解:
贪心+暴力
牌又有两张一组的又有三张一组的,并且还缺了一张,好混乱……
考虑只有正好全部由三张一组的组成的情况
发现如果从小到大,每次优先把三张组到一起,一定是最优的方法。
如果这样都不行,那么一定不存在合法方案。
所以暴力枚举添上的一张牌是什么,再枚举两张一组的情况,就可以在O(N^2 * M)的时间里解决这个问题了。
没有TLE大概是因为数据弱(。??)ノ?
  评论这张
 
阅读(26)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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