企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P2540 [NOIP 2015 提高组] 斗地主 加强版 - 洛谷

【题目描述】

牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的A AA到K KK加上大小王的共54 5454张牌来进行的扑克牌游戏。在斗地主中，牌的大小关系根据牌的数码表示如下：3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A < 2 < 小王 < 大王 3<4<5<6<7<8<9<10<J<Q<K<A<2<\text{小王}<\text{大王}3<4<5<6<7<8<9<10<J<Q<K<A<2<小王<大王，而花色并不对牌的大小产生影响。每一局游戏中，一副手牌由n nn张牌组成。游戏者每次可以根据规定的牌型进行出牌，首先打光自己的手牌一方取得游戏的胜利。

现在，牛牛只想知道，对于自己的若干组手牌，分别最少需要多少次出牌可以将它们打光。请你帮他解决这个问题。

需要注意的是，本题中游戏者每次可以出手的牌型与一般的斗地主相似而略有不同。具体规则如下：

在此题中认为两个王不能组成对子牌。

【输入】

第一行包含用空格隔开的2 22个正整数T , n T,nT,n，表示手牌的组数以及每组手牌的张数。

接下来T TT组数据，每组数据n nn行，每行一个非负整数对a i , b i a_i,b_iai​,bi​，表示一张牌，其中a i a_iai​表示牌的数码，b i b_ibi​表示牌的花色，中间用空格隔开。特别的，我们用1 11来表示数码A AA，11 1111表示数码J JJ，12 1212表示数码Q QQ，13 1313表示数码K KK；黑桃、红心、梅花、方片分别用1 − 4 1-41−4来表示；小王的表示方法为0 1，大王的表示方法为0 2。

【输出】

共T TT行，每行一个整数，表示打光第i ii手牌的最少次数。

【输入样例】

1 8 7 4 8 4 9 1 10 4 11 1 5 1 1 4 1 1

【输出样例】

3

【算法标签】

#省选# #IDA*#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=30;// 牌面值种类数量intt,n;// t: 测试用例数量, n: 每手牌的数量intf[N][N][N][N];// 记忆化数组，f[s][t][j][z]表示在给定牌型下的最小出牌次数intwasd[4]={0,5,3,2};// 不同牌型的最小连续长度：单顺5张，双顺3对，飞机2个三张inta[N];// 统计每种牌的数量，a[i]表示牌面值为i的牌有多少张intb[N];// 牌型转换数组，b[1]单牌数，b[2]对子数，b[3]三张数，b[4]炸弹数// 辅助函数，返回两个整数中的较小值intcmp(inta,intb){returna<b?a:b;}// 深度优先搜索函数，计算在给定基本牌型下的最小出牌次数// 参数说明：// s: 单牌的数量// t: 对子的数量// j: 三张的数量// z: 炸弹的数量intdfs(ints,intt,intj,intz){// 如果这个状态已经计算过，直接返回结果if(~f[s][t][j][z]){returnf[s][t][j][z];}intans=1e9;// 初始化为一个很大的数// 策略1：拆分对子为两个单牌if(t){ans=cmp(ans,dfs(s+2,t-1,j,z));}// 策略2：拆分三张为一个对子和一个单牌if(j){ans=cmp(ans,dfs(s+1,t+1,j-1,z));}// 策略3：拆分炸弹为一个三张和一个单牌if(z){ans=cmp(ans,dfs(s+1,t,j+1,z-1));}// 策略4：拆分炸弹为两个对子if(z){ans=cmp(ans,dfs(s,t+2,j,z-1));}// 策略5：三带一（用三张带一个单牌）if(j&&s){ans=cmp(ans,dfs(s-1,t,j-1,z)+1);}// 策略6：三带二（用三张带一个对子）if(j&&t){ans=cmp(ans,dfs(s,t-1,j-1,z)+1);}// 策略7：四带二单（用炸弹带两个单牌）if(z&&s>1){ans=cmp(ans,dfs(s-2,t,j,z-1)+1);}// 策略8：四带二对（用炸弹带两个对子）if(z&&t>1){ans=cmp(ans,dfs(s,t-2,j,z-1)+1);}// 策略9：一手出完所有牌（每个单牌、对子、三张、炸弹都单独出）returnf[s][t][j][z]=cmp(ans,s+t+j+z);}// 处理顺子、连对、飞机等特殊牌型// 参数说明：step - 当前已经出的次数intchupai(intstep){intans=1e9;// 初始化为一个很大的数inttot;// 用于统计连续牌的数量// 处理三种特殊牌型：k=1单顺，k=2双顺，k=3飞机for(intk=1;k<=3;k++){// 从3开始遍历，因为顺子从3开始（3,4,5,...）for(inti=3;i<=14;i++){tot=0;// 统计从i开始最多有多少张连续的牌for(intj=i;j<=14;j++){if(a[j]>=k)// 如果当前牌有至少k张{tot++;}else{break;// 不连续了，停止统计}}// 枚举所有可能的顺子长度for(intj=i+wasd[k]-1;j<=i+tot-1;j++){// 移除这个顺子for(intl=i;l<=j;l++){a[l]-=k;}// 递归处理剩下的牌ans=cmp(ans,chupai(step+1));// 恢复这个顺子，进行回溯for(intl=i;l<=j;l++){a[l]+=k;}}}}// 统计剩余的牌型b[1]=b[2]=b[3]=b[4]=0;// 初始化牌型数组for(inti=2;i<=14;i++)// 从2到A（14）统计{b[a[i]]++;// 根据牌的数量统计牌型}// 处理大小王if(a[0]==2)// 如果有两张王（大小王）{// 可以当作一对王炸ans=cmp(ans,step+1+dfs(b[1],b[2],b[3],b[4]));}// 将王当作单牌处理b[1]+=a[0];ans=cmp(ans,step+dfs(b[1],b[2],b[3],b[4]));returnans;}intmain(){// 输入测试用例数量和每手牌的数量cin>>t>>n;// 初始化记忆化数组memset(f,-1,sizeof(f));f[0][0][0][0]=0;// 基础情况：没有牌，需要0次出牌// 处理每个测试用例while(t--){intu,v;// u: 牌面值, v: 花色memset(a,0,sizeof(a));// 清空牌数统计// 输入n张牌for(inti=1;i<=n;i++){cin>>u>>v;a[u]++;// 统计该牌面值的数量}// 将A（1）映射到14，便于处理顺子a[14]=a[1];// 计算最少出牌次数并输出cout<<chupai(0)<<endl;}return0;}

【运行结果】

1 8 7 4 8 4 9 1 10 4 11 1 5 1 1 4 1 1 3