吴凡的题库——快快编程1101-1400

  1. 斗地主
题目描述
比赛真题 请勿抄答案，违反者封号（已有若干人因此被封）

     牛牛最近迷上了一种叫斗地主的扑克游戏。斗地主是一种使用黑桃、红心、梅花、方片的AA到KK加上大小王的共5454张牌来进行的 扑克牌游戏。在斗地主中，牌的大小关 系根据牌的数码表示如下：3<4<5<6<7<8<9<10
输入输出样例
输入样例#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

#include
#define gc() getchar()
#define isd isdigit
using namespace std;
int n,t,ans;
int pai[20];
int san_pai();
void feiji(int step);
void shunzi(int step);
void liandui(int step);
int read() {
    int x=0;
    char ch=gc();
    while(!isd(ch))ch=gc();
    while(isd(ch))x=x*10+ch-'0',ch=gc();
    return x;
}
void chupai(int step) {      //开始出牌 
    if(step>=ans)return ;   //最优性剪枝 
    int tmp=san_pai();      //打散牌 
    ans=min(tmp+step,ans); //更新最优解 
    feiji(step);  //飞机 
    shunzi(step); //顺子 
    liandui(step);//连对 
}
void feiji(int step){//出飞机 
    int l,end;
    for(int st=3; st<=13; ++st) {//枚举连续牌起始点 
        l=0;
        while(pai[st+l]>=3)l++;//找出最大长度 
        for(int j=l; j>=2; --j) {//枚举出牌长度 
            end=st+j-1;             
            for(int k=st; k<=end; k++)pai[k]-=3;//出飞机 
            chupai(step+1);//继续出牌 
            for(int k=st; k<=end; k++)pai[k]+=3;//搜索回溯 
        }
    }
    return;
}
void liandui(int step) {//连对 
    int l,end;
    for(int st=3; st<=12; ++st) {//枚举连续牌起始点 
        l=0;
        while(pai[st+l]>=2)l++;//找出最大长度 
        for(int j=l; j>=3; --j) {//枚举出牌长度
            end=st+j-1;
            for(int k=st; k<=end; k++)pai[k]-=2;//出连对 
            chupai(step+1);//继续出牌
            for(int k=st; k<=end; k++)pai[k]+=2;//搜索回溯
        }
    }
    return;
}
void shunzi(int step) {//顺子 
    int l,end;
    for(int st=3; st<=10; ++st) {//枚举连续牌起始点 
        l=0;
        while(pai[st+l]>=1)l++;//找出最大长度 
        for(int j=l; j>=5; --j) {
            end=st+j-1;
            for(int k=st; k<=end; k++)pai[k]-=1;//出顺子 
            chupai(step+1);//继续出牌
            for(int k=st; k<=end; k++)pai[k]+=1;//搜索回溯
        }
    }
    return;
}
int san_pai() {//贪心打散牌 
    int zs[5],num=0;
    memset(zs,0,sizeof(zs));
    bool wangzha=false;        
    if(pai[1]==2)wangzha=true;//是否有王炸 
    zs[1]+=pai[1];            //王算单牌 
    for(int i=2; i<=14; ++i)zs[pai[i]]++;//统计个数 
    /******  暴力出奇迹  ******/
    while(!zs[3]&&zs[1]==1&&zs[2]==1&&zs[4]>1)zs[4]-=2,zs[1]--,zs[2]--,num+=2;//神特判 
    //把一个炸拆成3张和单牌,再出一组四带二单和三带一 
    while(!zs[2]&&zs[1]==1&&zs[4]==1&&zs[3]>1)zs[3]-=2,zs[1]--,zs[4]--,num+=2;//神特判 
    //把一组三张拆成一对和一单,再出一组四带二单和三带二 
    if(zs[3]+zs[4]>zs[1]+zs[2])//三四张的比单牌和对牌多,拆着打 
        while(zs[4]&&zs[2]&&zs[3])zs[2]--,zs[3]--,zs[1]++,zs[4]--,num++;//拆三张,4带两对余一单 
    if(zs[3]+zs[4]>zs[1]+zs[2])//还多继续拆 
        while(zs[4]&&zs[1]&&zs[3])zs[1]--,zs[3]--,zs[2]++,zs[4]--,num++;//拆三张,4带两单余一对 
    while(zs[4]&&zs[1]>1)zs[4]--,zs[1]-=2,num++;//四带两单 
    while(zs[4]&&zs[2]>1)zs[4]--,zs[2]-=2,num++;//四带两对 
    while(zs[4]&&zs[2]  )zs[4]-- ,zs[2]--,num++;//对看成两单再四带 
    if(zs[3]%3==0&&zs[1]+zs[2]<=1)                //三张的太多了拆三张 
        while(zs[3]>2)zs[3]-=3,num+=2;//把一组三张拆成单和对,再出三带一和三带二 
    while(zs[3]&&zs[1]  )zs[3]-- ,zs[1]--,num++;//三带一 
    while(zs[3]&&zs[2]  )zs[3]-- ,zs[2]--,num++;//三带二 
    //还剩三张和炸,组合出 
    while(zs[4]>1&&zs[3])zs[3]--,zs[4]-=2,num+=2;//把一个炸拆成一对和两单,再出三带二和四带两单 
    while(zs[3]>1&&zs[4])zs[4]--,zs[3]-=2,num+=2;//把一个炸拆成两对,再出两组三带一对 
    while(zs[3]>2)zs[3]-=3,num+=2;                //同上,把一组三张拆成单和对,再出三带一和三带二
    while(zs[4]>1)zs[4]-=2,num++;                //把一个炸拆成两对,再出一组四带两对 
    if(wangzha&&zs[1]>=2)
        return num+zs[2]+zs[3]+zs[4]+zs[1]-1;
    else
        return num+zs[1]+zs[2]+zs[3]+zs[4];
}
int main() {
    t=read();
    n=read();
    int a,b;
    while(t--){
        ans=0x7f7f7f7f;
        memset(pai,0,sizeof(pai));
        for(int i=1; i<=n; ++i) {
            a=read();b=read();
            if(a==1)pai[14]++;
            else if(a==0)pai[1]++;
            else pai[a]++;
        }
        chupai(0);
        printf("%d\n",ans);
    }
    return 0;
}

  1. 时间复杂度（同468）

  2. 愚公移山

题目描述
《愚公移山》是战国时期思想家列子创作的一篇寓言。



愚公门前有太行，王屋两座大山。在山的正对面居住的愚公苦于山区北部的阻塞，出来进去都要绕道，于是愚公决定要移去这两座山。邻居智叟说不能 完成，嘲笑愚公顽固愚蠢，愚公说：“我移不完还有我的子孙后代，一代一代的移。”



已知第一代愚公移走了x[1]吨，第二代移走了x[2]吨，…，第n代移走了x[n]吨。请输出n个数字，代表

截止到第一代一共移走几吨？

截止到第二代一共移走几吨？

截止到第三代一共移走几吨？

……

截止到第n代一共移走几吨？

输入输出格式
输入格式
输入第一行是正整数n，n<=100000。第二行共n个正整数x[i]，代表每一代移走几吨，均不超过1000000。
输出格式
输出共一行包含n各正整数。

输入输出样例
输入样例#1:
4
1 2 3 4
输出样例#1:
1 3 6 10
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无

#include
using namespace std;
int main(){
	long long n,t,d[100009];
	cin>>n;
	for(int i=1;i<=n;i++)cin>>d[i];
	t=0;
	for(int i=1;i<=n;i++){
		t+=d[i];
		cout<
  1. 黑白染色1
题目描述
你有一串黑白珠子，从左到右依次用B或W表示颜色。你希望将珠子重新染色，共有m种染色方案，第i种方案要将珠子中第ai个到第bi个全部变成白色W。请问：对每一种方案需要至少染几个珠子？


输入输出格式
输入格式
输入第一行为字符串，只包含B或W，长度在2到200000个字符。第二行为正整数m，代表方案数量，不超过100000。接着有m行，每行2个正整数ai,bi。保证1<=ai<=bi<=珠子串总长度
输出格式
输出共一行包含m个整数。

输入输出样例
输入样例#1:
WBWWBW
3
1 6
4 5
3 4
输出样例#1:
2 1 0
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无

#include
using namespace std;
int main(){
	string s;
	int n,b[200009],t[200009];
	cin>>s>>n;
	b[0]=0;
	for(int i=0;i>x>>y;
		cout<
  1. 倒背如流1
题目描述
请你输入10个数，每行一个，“倒背如流”程序会反向输出这10个数，每行一个。
输入共十行，每行一个非负整数，均不超过100。输出十行共十个整数。

输入输出格式
输入格式
输入共十行，每行一个非负整数，均不超过100。
输出格式
输出十行共十个整数。

输入输出样例
输入样例#1:
0
1
2
3
4
5
6
7
8
9
输出样例#1:
9
8
7
6
5
4
3
2
1
0
输入样例#2:

输出样例#2:

输入样例#3:

输出样例#3:


#include
using namespace std;
int main(){
	int s[15]; 
	for(int i = 0;i<10;i++){
		cin>>s[i];
	}
	for(int i = 10 - 1;i>=0;i--){
		cout<
  1. 倒背如流2
题目描述
请你输入n个数，“倒背如流”程序会反向输出这n个数。

输入输出格式
输入格式
输入第一行为正整数n，n<=1000。第二行包含n个非负整数，均不超过100。
输出格式
输出共一行，包含n个整数，由空格隔开。

输入输出样例
输入样例#1:
9
0 1 2 3 4 5 6 7 8
输出样例#1:
8 7 6 5 4 3 2 1 0
输入样例#2:

输出样例#2:

输入样例#3:

输出样例#3:


#include
using namespace std;
int main(){
	int n,i,s[1009];
	cin>>n;
	for(i=0;i<=n-1;i++){
		cin>>s[i];
	}
	for(i=n-1;i>=0;i--){
		cout<
  1. 成绩前3名
题目描述
期末考试结束了，全班n个同学的成绩都已经公布，成绩已经按照从小到大的顺序排好，老师想要打印一个前3名的成绩排名榜，成绩要求从大到小输出 。

输入输出格式
输入格式
输入格式：输入的第1行为1个整数n，n表示班级人数，n<=10000.输入的第2行为n个整数，表示学生成绩，已经从小到大排好序
输出格式
输出格式：输出共1行包含3个整数，表示前3名的成绩，从大到小排列，由空格隔开

输入输出样例
输入样例#1:
3
98 99 100
输出样例#1:
100 99 98
输入样例#2:
5
50 70 70 70 100
输出样例#2:
100 70 70
解释说明：共5个学生成绩需要输出前3名，正好是100分,70分和70分，也就是最后3个数
输入样例#3:
5
1 2 3 4 5
输出样例#3:
5 4 3

#include
using namespace std;
int main(){
	int n;
	int s[10009];
	cin>>n;
	for(int i = 0;i>s[i];
	}
	for(int i = n-1;i>=n-3;i--){
		cout<
  1. 蚁人装置
题目描述
蚁人装备的制作需要10项尺寸：身高，臂展，肩宽，腿长，胸围，等等共10个浮点数。当蚁人缩小x倍后，其装备尺寸会等比例缩小，输 入正整数x后，请输出缩小后的10项尺寸。

输入输出格式
输入格式
输入10个正的浮点数，均不超过1000。
输出格式
输出十个浮点数，保留4位小数，由空格隔开。

输入输出样例
输入样例#1:
15 14 5 9 8 1 2 3 4 5
10
输出样例#1:
1.5000 1.4000 0.5000 0.9000 0.8000 0.1000 0.2000 0.3000 0.4000 0.5000
输入样例#2:

输出样例#2:

输入样例#3:

输出样例#3:


#include
#include
using namespace std;
int main(){
	double s[15],x;					
	for(int i = 0;i < 10;i ++){			
		cin>>s[i];
	}
	cin>>x;
	for(int i = 0;i < 10;i ++){
		cout<
  1. 找到根分左右1
题目描述
给出一棵二叉树的前序遍历与中序遍历的排列。求出它的根结点是哪个？再求出左子树有几个结点？右子树有几个结点？
（约定树结点用不同的大写字母表示，长度≤8）。

输入输出格式
输入格式
输入一行包含两个字符串，代表一棵二叉树的前序与中序排序,中间用一个空格隔开。
输出格式
输出第一行包含一个字符代表根结点。第二行包含两个整数，左右子树各有几个结点。

输入输出样例
输入样例#1:
ABC BAC
输出样例#1:
A
1 1
输入样例#2:
ABC CBA
输出样例#2:
A
2 0
输入样例#3:
XBCD BXDC
输出样例#3:
X
1 2

#include
using namespace std;
int main(){
	string pre,mid;
	cin>>pre>>mid;
	char root=pre[0];
	int p=mid.find(root);
	int len=mid.size();
	int L=p;
	int R=len-L-1;
	cout<
  1. 找到根分左右2
题目描述
给出一棵二叉树的中序遍历与后序遍历的排列。求出它的根结点是哪个？再求出左子树有几个结点？右子树有几个结点？
（约定树结点用不同的大写字母表示，长度≤8）。

输入输出格式
输入格式
输入一行包含两个字符串，代表一棵二叉树的中序遍历与后序遍历,中间用一个空格隔开。
输出格式
输出第一行包含一个字符代表根结点。第二行包含两个整数，左右子树各有几个结点。

输入输出样例
输入样例#1:
BAC BCA
输出样例#1:
A
1 1
输入样例#2:
BXDC BDCX
输出样例#2:
X
1 2
输入样例#3:

输出样例#3:


#include
using namespace std;
int main(){
	string post,mid;
	cin>>mid>>post;
	int len=post.size();
	char root=post[len-1];
	int p=mid.find(root);
	int L=p;
	int R=len-L-1;
	cout<
  1. 迟到的暑期福利2
题目描述
学校发暑期福利啦，给了你总共能容纳V大小的背包，最大承重量为W。

允许你到超市里任意选购商品，学校报销哦。

现在超市有n种物品。每种物品无限件。

每种物品有其大小bi，价值vi，重量wi。

现需要你计算出你能得到的最大价值是多少？

输入输出格式
输入格式
第一行，3个整数，n，V，W。
第二行，n个整数，bi。
第三行，n个整数，vi。
第四行，n个整数，wi。
输出格式
一个整数表示价值。

输入输出样例
输入样例#1:
1 464 387
19
80
38
输出样例#1:
800
输入样例#2:
无
输出样例#2:
无
输入样例#3:
无
输出样例#3:
无

#include
using namespace std;
typedef long long ll;
const ll MAXC=2009;
ll n,V,W,w[MAXC],v[MAXC],p[MAXC],f[MAXC][MAXC];
int main(){
	cin>>n>>V>>W;
	for(ll i=1;i<=n;i++)cin>>v[i];
	for(ll i=1;i<=n;i++)cin>>p[i];
	for(ll i=1;i<=n;i++)cin>>w[i];
	for(ll i=1;i<=n;i++)
	    for(ll j=v[i];j<=V;j++)
	        for(ll k=w[i];k<=W;k++)
	            f[j][k]=max(f[j][k],f[j-v[i]][k-w[i]]+p[i]);
	cout<
  1. 数儿子
题目描述
在一棵二叉树里，从根节点开始，每个节点最多可以分成两个分叉。通俗地讲，每个节点最多有两个儿子节点。对于一颗完全二叉树，它的节点排列方 式必须是一层一层完全紧凑的排列，不可以跳过任何位置，除了最后一层可以不满，其他每层都必须排满，最后一层节点必须都靠左排列。
已知一棵完全二叉树有n个节点，这棵树的所有节点位置都是确定的，请问：
有多少节点是叶节点（没有儿子）？
有多少节点拥有1个儿子节点？
有多少节点拥有2个儿子节点？

输入输出格式
输入格式
输入文件sons.in  输入正整数n。n<=10000
输出格式
输出文件sons.out  输出三个整数，由空格隔开。

输入输出样例
输入样例#1:
4
输出样例#1:
2 1 1
输入样例#2:
5
输出样例#2:
3 0 2
输入样例#3:
无
输出样例#3:
无

#include
using namespace std;
int main(){
	freopen("sons.in", "r", stdin);
	freopen("sons.out", "w", stdout);
	int n,ans0,ans1,ans2;
	cin>>n;
	if(n%2==0)ans1=1;
	else ans1=0;
	ans2=(n-ans1)/2;
	ans0=ans2+1;
	cout<
  1. 曼哈顿距离1
题目描述
纽约曼哈顿的街道横平竖直，街道名字由编号组成，类似坐标系统。
南北方向的路编号为第1大道，第2大道，第3大道，…
东西方向的路编号为第1大街，第2大街，第3大街，…
“曼哈顿距离”就是一个人从某个路口走向另一个路口的最短行走距离。
例如：从第1大道第1大街路口，走到第1大道第2大街路口，距离为1。
例如：从第1大道第1大街路口，走到第2大道第2大街路口，距离为2。
例如：从第1大道第1大街路口，走到第3大道第2大街路口，距离为2+1=3。
例如：从第1大道第1大街路口，走到第3大道第4大街路口，距离为2+3=5。
注意“曼哈顿距离”不同于直线距离，因为街道间有建筑物会挡住直线路线。
如图，绿色代表直线距离，不是曼哈顿距离。而红色，蓝色，黄色，都代表曼哈顿距离，长度为12。已知你想从第a大道第b大街路口，走到第c大道第d 大街路口，距离多少?

输入输出格式
输入格式
输入4个正整数a,b,c,d,均不超过500。
输出格式
输出一个整数。

输入输出样例
输入样例#1:
1 1 4 3
输出样例#1:
5
样例解释：第1大道第1大街路口，走到第4大道第3大街路口，距离|4-1|+|3-1|=5
输入样例#2:
1 9 5 1
输出样例#2:
12
样例解释：第1大道第9大街路口，走到第5大道第1大街路口，距离|5-1|+|1-9|=12
输入样例#3:
无
输出样例#3:
无

#include
#include
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	cout<
  1. 曼哈顿距离2
题目描述
输入两个浮点数坐标点(a,b),(c,d)，输出它们之间的曼哈顿距离
|a-c|+|b-d|
即它们横坐标差的绝对值加上纵坐标差的绝对值

输入输出格式
输入格式
输入4个浮点数a,b,c,d。输入数值范围-100到100之间。
输出格式
输出一个浮点数。输出保留1位小数。

输入输出样例
输入样例#1:
1.1 0 3.1 3
输出样例#1:
5.0
输入样例#2:
0 0 3 4.5
输出样例#2:
7.5
输入样例#3:

输出样例#3:


#include
#include
#include
using namespace std;
int main(){
	float a,b,c,d;
	cin>>a>>b>>c>>d;
	float e=fabs(a-c)+fabs(b-d);
	cout<
  1. 字符类型
题目描述
输入一个字符x，请判断x是什么类型的。
如果x是小写字母，输出lowercase
否则，如果x是大写字母，输出UPPERCASE
否则，如果x是阿拉伯数字，输出digit
否则，输出other

输入输出格式
输入格式
输入文件type.in  输入一个字符。
输出格式
输出文件type.out 输出一行字符串。

输入输出样例
输入样例#1:
m
输出样例#1:
lowercase
输入样例#2:
0
输出样例#2:
digit
输入样例#3:
Z
输出样例#3:
UPPERCASE

#include
using namespace std;
int main(){
	freopen("type.in", "r", stdin);
	freopen("type.out", "w", stdout);
	char c;
	cin>>c;
	if (c <='Z' && c >= 'A')
	    cout<<"UPPERCASE";
	else if (c <= 'z' && c >= 'a')
		cout<<"lowercase";
	else if (c <= '9' && c >= '0')
	    cout<<"digit";
	else
		cout<<"other";
	return 0;
}

相关

标签

一品网 冀ICP备14022925号-6