洛谷P2668 斗地主 [NOIP2015]
2024-09-05 07:09:43
题目描述
牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A到K加上大小王的共54张牌来进行的扑克牌游戏。在斗地主中,牌的大小关系根据牌的数码表示如下:3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王,而花色并不对牌的大小产生影响。每一局游戏中,一副手牌由n张牌组成。游戏者每次可以根据规定的牌型进行出牌,首先打光自己的手牌一方取得游戏的胜利。
现在,牛牛只想知道,对于自己的若干组手牌,分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。
需要注意的是,本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。
具体规则如下:
输入输出格式
输入格式:
第一行包含用空格隔开的2个正整数Tn,表示手牌的组数以及每组手牌的张数。
接下来T组数据,每组数据n行,每行一个非负整数对aibi表示一张牌,其中ai示牌的数码,bi表示牌的花色,中间用空格隔开。特别的,我们用1来表示数码A,11表示数码J,12表示数码Q,13表示数码K;黑桃、红心、梅花、方片分别用1-4来表示;小王的表示方法为01,大王的表示方法为02。
输出格式:
共T行,每行一个整数,表示打光第i手牌的最少次数。
输入输出样例
输入样例#1:
1 8
7 4
8 4
9 1
10 4
11 1
5 1
1 4
1 1
输出样例#1:
3
输入样例#2:
1 17
12 3
4 3
2 3
5 4
10 2
3 3
12 2
0 1
1 3
10 1
6 2
12 1
11 3
5 2
12 4
2 2
7 2
输出样例#2:
6
说明
样例1说明
共有1组手牌,包含8张牌:方片7,方片8,黑桃9,方片10,黑桃J,黑桃5,方片A以及黑桃A。可以通过打单顺子(方片7,方片8,黑桃9,方片10,黑桃J),单张牌(黑桃5)以及对子牌(黑桃A以及方片A)在3次内打光。
对于不同的测试点, 我们约定手牌组数T与张数n的规模如下:
数据保证:所有的手牌都是随机生成的。
简直可怕的搜索。
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
int T;
int n;
int cnt[mxn];
int ans;
int tot=;
void dfs(int time){
tot++;
if(tot>)return;
if(time>=ans)return;
int i,j;
bool flag=;
for(i=;i<=;i++)
if(cnt[i]){flag=;break;}
if(!flag){ans=time;return;}
//三顺子
for(i=;i<=;i++){
if(cnt[i]<)continue;
int ed=i;
while(ed<){
if(cnt[ed]<)break;
cnt[ed++]-=;
if(ed-i<)continue;
dfs(time+);
}
for(j=i;j<ed;j++)cnt[j]+=;
}
//双顺子
for(i=;i<=;i++){
if(cnt[i]<)continue;
int ed=i;
while(ed<){
if(cnt[ed]<)break;
cnt[ed++]-=;
if(ed-i<)continue;
dfs(time+);
}
for(j=i;j<ed;j++)cnt[j]+=;
}
//单顺子
for(i=;i<=;i++){
if(!cnt[i])continue;
int ed=i;
while(ed<){
if(!cnt[ed])break;
cnt[ed++]--;
if(ed-i<)continue;
dfs(time+);
}
for(j=i;j<ed;j++)cnt[j]++;
}
//四带
for(i=;i<=;i++)
if(cnt[i]>=){
cnt[i]-=;
for(j=;j<=;j++){
if(i==j)continue;
if(cnt[j]>=){
cnt[j]-=;
dfs(time+);
cnt[j]+=;
}
}
cnt[i]+=;
} //三带
for(i=;i<=;i++)
if(cnt[i]>=){
cnt[i]-=;
for(j=;j<=n;j++)
if(i!=j)
for(int k=;k<=;k++){
if(cnt[j]>=k){
cnt[j]-=k;
dfs(time+);
cnt[j]+=k;
}
}
cnt[i]+=;
}
//火箭 /对子 /炸弹 /单张
for(j=;j;j--)
for(i=;i<=;i++)
if(cnt[i]>=j){
cnt[i]-=j;
dfs(time+);
cnt[i]+=j;
}
return;
}
int main(){
scanf("%d%d",&T,&n);
int i,j;
while(T--){
memset(cnt,,sizeof cnt);
ans=n;
for(i=;i<=n;i++){
int a;
scanf("%d%*d",&a);
if(a==)a=;
else if(a==)a=;
else a-=;
cnt[a]++;
}
dfs();
printf("%d\n",ans);
}
return ;
}
敲了个暴搜果断WAWAWA
然后默默抄了题解
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
int cnt[mxn],r[mxn];
int ans;
int T,n;
int query(){//r存储剩余[i]张的牌的数量
int tot=;
memset(r,,sizeof r);
for(int i=;i<=;i++)
r[cnt[i]]++;
while(r[] && r[]>=)r[]--,r[]-=,tot++;
while(r[] && r[]>=)r[]--,r[]-=,tot++;
while(r[] && r[])r[]--,r[]--,tot++;
while(r[] && r[])r[]--,r[]--,tot++;
while(r[] && r[])r[]--,r[]--,tot++;
return tot+r[]+r[]+r[]+r[];
}
void dfs(int time){
if(time>=ans) return;
int tmp=query();
if(time+tmp<ans)ans=tmp+time;
int i,j,x;
for(i=;i;i--)
for(j=;j<=;j++){
x=j;
while(cnt[x]>=i){
x++;
if((i== && x-j>=)||(i== && x-j>=)||(i== && x-j>=)){
for(int k=j;k<x;k++) cnt[k]-=i;
dfs(time+);
for(int k=j;k<x;k++) cnt[k]+=i;
}
}
}
}
int main(){
scanf("%d%d",&T,&n);
int i,j;
while(T--){
memset(cnt,,sizeof cnt);
ans=n;
for(i=;i<=n;i++){
int a;
scanf("%d%*d",&a);
if(a==)a=;
else if(a)a--;
cnt[a]++;
}
dfs();
printf("%d\n",ans);
}
return ;
}
最新文章
- javascript命名规范
- Java多线程系列--“JUC锁”02之 互斥锁ReentrantLock
- Spring的jdbcTemplate查询执行原生sql
- tar命令的详细解释
- HTML CSS——margin和padding的学习
- 161021、spring异步调用,完美解决!
- POJ 3278 经典BFS
- Retrofit入门
- [置顶] 【玩转cocos2d-x之七】场景类CCScene和布景类CCLayer
- Android开发之bindService()通信
- Java中OutOfMemoryError(内存溢出)的情况及解决办法
- bzoj2809
- 病毒侵袭 - HDU 2896(AC自动机)
- 天天乐宝APP开发
- 数据库 -->; SQL 和 NoSQL 的区别
- 精进之路之volatile
- linux shell cut 命令
- myEclips 中的项目复制重命名
- 【Vue实战之路】一、Vue-cli入门及Vue工程目录全解。
- npm出错的解决方案
热门文章
- 项目实战8.1—tomcat企业级Web应用服务器配置与会话保持
- 一道JS面试题所引发的";血案";,透过现象寻本质,再从本质看现象
- 【Ecshop】修改处理用户购物车的行为
- python3.7 time模块
- 2017 United Kingdom and Ireland Programming(Gym - 101606)
- 查询语句为“%string_”的情况
- HDFS上传文件
- datagrid的修改和删除功能的实现
- 使用 Dom4j 将 XML 转换为 MAP
- vue/vux编译时出现 unexpected token <;11:0-485>;