AcWing 1801:蹄子剪刀布 ← 模拟题

2024-06-22 06:12

本文主要是介绍AcWing 1801:蹄子剪刀布 ← 模拟题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【题目来源】
https://www.acwing.com/problem/content/1803/

【题目描述】
你可能听说过“石头剪刀布”的游戏。
这个游戏在牛当中同样流行,它们称之为“蹄子剪刀布”。
游戏的规则非常简单,两头牛相互对抗,数到三之后各出一个表示蹄子,剪刀或布的手势。

蹄子赢剪刀,剪刀赢布,布赢蹄子
例如,第一头牛出“蹄子”手势,第二头牛出“布”手势,则第二头牛获胜。
如果两头牛出相同的手势,则算平局。
农夫约翰的两头奶牛正在进行 N 轮“蹄子剪刀布”对抗,他看的十分入迷。
不幸的是,虽然他可以看到奶牛正在做出三种不同类型的手势,但他却
无法分辨出哪一个代表“蹄子”,哪一个代表“布”以及哪一个代表“剪刀”
不知道这三种手势的具体含义的情况下,农夫约翰给这三种手势分配了编号 1,2,3
手势 1 可能代表“蹄子”,可能代表“剪刀”,也可能代表“布”,反正他傻傻分不清楚。
给出两头奶牛在 N 场比赛中所做出的具体手势对应的编号,请你判断第一头奶牛最多可能赢多少盘对抗。

【输入格式】
第一行包含整数 N。
接下来 N 行,每行包含两个整数(1 或 2 或 3),表示两头奶牛在一轮对抗中所出的手势对应的编号。

【输出格式】
输出第一头奶牛可能获胜的最大场次数。

【数据范围】
1≤N≤100

【输入样例】
5
1 2
2 2
1 3
1 1
3 2

【输出样例】
2

【样例解释】
此样例的一种解决方案是,1 表示剪刀,2 表示蹄子,3 表示布。
这样,第一头奶牛可以赢得 (1,3) 和 (3,2) 两场比赛。

【算法分析】
● 蹄子?剪刀?布?确实傻傻
分不清 ^_^

● 依据游戏规则,蹄子赢剪刀,剪刀赢布,布赢蹄子。据此,不失一般性,约定用编号1、编号2、编号3对游戏规则进行编码。由于编号1可能代表“蹄子”,可能代表“剪刀”,也可能代表“布”,编号2及编号3亦如此。故:
若用编号1表示“蹄子”,编号2表示“剪刀”,编号3表示“布”,则游戏规则编码为 1 2 3;
若用编号1表示“蹄子”,编号3表示“剪刀”,编号2表示“布”,则游戏规则编码为 1 3 2;
若用编号2表示“蹄子”,编号1表示“剪刀”,编号3表示“布”,则游戏规则编码为 2 1 3;
若用编号2表示“蹄子”,编号3表示“剪刀”,编号1表示“布”,则游戏规则编码为 2 3 1;
若用编号3表示“蹄子”,编号1表示“剪刀”,编号2表示“布”,则游戏规则编码为 3 1 2;
若用编号3表示“蹄子”,编号2表示“剪刀”,编号1表示“布”,则游戏规则编码为 3 2 1;
总上,可得6种游戏规则编码,即 1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1。

● 显然,上述6种游戏规则编码,对应以下6种赢的陈述:
1 2 3 → 1 赢 2,2 赢 3,3 赢 1
1 3 2 → 1 赢 3,3 赢 2,2 赢 1
2 1 3 → 2 赢 1,1 赢 3,3 赢 2

2 3 1 → 2 赢 3,3 赢 1,1 赢 2
3 1 2 → 3 赢 1,1 赢 2,2 赢 3

3 2 1 → 3 赢 2,2 赢 1,1 赢 3
不过,在利用下图可视化后,发现6种赢的陈述有同构的情形,本质上对应两种情况。

● 两种情况
对于上图左上而言,对应
1 3 2、2 1 3、3 2 1,即 1 赢 3,2 赢 1,3 赢 2。
也就是
第一头牛出的手势编号值与第二头牛出的手势编号值之差为 -2 和 1 时获胜
对于上图左下而言,对应
1 2 3、2 3 1、3 1 2,即 1 赢 2,2 赢 3,3 赢 1。
也就是
第一头牛出的手势编号值与第二头牛出的手势编号值之差为 -1 和 2 时获胜
显然,比较两种情况,较大的就是第一头牛赢的最大次数。若二牛出的手势编号值相同,则平局,无需考虑。

【算法代码】

#include <bits/stdc++.h>
using namespace std;int fi,se;int main() {int n;cin>>n;for(int i=1; i<=n; i++) {int x,y;cin>>x>>y;if((x-y)==-2 || (x-y)==1) fi++;if((x-y)==-1 || (x-y)==2) se++;}cout<<max(fi,se)<<endl;return 0;
}/*
in:
40
1 3
3 1
3 2
3 3
1 2
3 3
3 1
1 1
3 2
1 2
3 1
2 3
1 3
3 2
2 3
3 3
3 2
2 2
2 3
2 1
3 3
1 1
2 3
2 1
3 2
2 3
3 3
2 1
2 3
2 3
2 1
3 3
1 1
1 1
2 3
2 2
3 3
2 3
2 2
1 1out:
14
*/




【参考文献】
https://blog.csdn.net/qq_50677040/article/details/122737418
https://www.acwing.com/solution/content/88041/
https://www.acwing.com/problem/content/solution/1803/1/
https://www.acwing.com/solution/content/87164/
https://www.acwing.com/video/3693/






 

这篇关于AcWing 1801:蹄子剪刀布 ← 模拟题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1083511

相关文章

机试算法模拟题 服务中心选址

题目描述 一个快递公司希望在一条街道建立新的服务中心。公司统计了该街道中所有区域在地图上的位置,并希望能够以此为依据为新的服务中心选址:使服务中心到所有区域的距离的总和最小。 给你一个数组positions,其中positions[i] = [left, right] 表示第 i 个区域在街道上的位置,其中left代表区域的左侧的起点,right代表区域的右侧终点,假设服务中心的位置为loca

【AcWing】851. 求最短路

spfa算法其实是对贝尔曼福特算法做一个优化。 贝尔曼福特算法会遍历所有边来更新,但是每一次迭代的话我不一定每条边都会更新,SPFA是对这个做优化。 如果说dist[b]在当前这次迭代想变小的话,那么一定是dist[a]变小了,只有a变小了,a的后继(b)才会变小。 用宽搜来做优化,用一个队列,队列里边存的就是所有变小了的结点(队列里存的是待更新的点)。 基本思路就是我更新过谁,我再拿

【AcWing】852. spfa判断负环

#include<iostream>#include<algorithm>#include<cstring>#include<queue>using namespace std;const int N= 1e5+10;int n,m;int h[N],w[N],e[N],ne[N],idx;int dist[N],cnt[N];//cnt存最短路径的边数bool st[N];v

AcWing 282. 石子合并

必看的视频讲解↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 【E28【模板】区间DP 石子合并——信息学竞赛算法】 合并过程总开销等于红色数字总和,可以理解为花费的总体力! f数组的含义是f【i】【j】是从第i堆石子开始到第j堆石子的花费体力最小值 如何理解三层for呢? 第一层for是控制区间长度len,第二层for是控制区间起点位置i,第三层for是控制区间

HDU 1332(模拟题,电子数字)

#include <iostream>#include <cstring>using namespace std;#define MAXLENGTH 8void lcd_display (long size, long number){// 将number拆分为单个的数字。int digits[MAXLENGTH];memset (digits, -1, sizeof (

AcWing 897. 最长公共子序列

动态规划就是多见识应用题就完事儿了,也没有什么好说的。 讲解参考: 【E05 线性DP 最长公共子序列】 #include<iostream>#include<algorithm>#define N 1010using namespace std;char a[N],b[N];int n,m;int f[N][N];int main(){cin >> n >> m >> a

AcWing 2. 01背包问题

一定要看的视频讲解:↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 【E08【模板】背包DP 01背包——信息学竞赛算法】 i表示放入i个物品,j表示第j个物品,用于访问体积v【j】 #include <iostream>#include <algorithm>using namespace std;const int N = 1010;int n, m;int v[N]

携程编程大赛 (预赛第二场)第一题【剪刀石头布】

Problem Description 现有M个人一起玩剪刀石头布,以1-M编号,每人出一种,出过不再改变,但是我们并不知道它到底是哪一种。 (其中石头赢剪刀,剪刀赢布,布赢石头,一样则平) 裁判用两种说法对这M个人所构成的输赢关系进行描述:  一:"1 A B",表示第A个人和第B个人出的一样。  二:"2 A B",表示第A个人赢第B个人。  裁判对M个人,用以上两种说法,连说

AcWing-算法提高课(第一章)-下

区间DP 环形石子合并 状态表示:f[i,j](f[i,j]表示,在,由,将第i堆石子到第j堆石子合并成一堆石子的每个合并方式的代价,组成的集合,中,的最小值)状态计算:f[i,j]=min(f[i,k]+f[k+1,j]+s[j]-s[i-1])(s[j]表示第1堆石子到第j堆石子的总重量,s[i-1]表示第1堆石子到第i-1堆石子的总重量,s[j]-s[i-1]表示第i堆石子到第j堆石子的

贪心推公式——AcWing 125. 耍杂技的牛

贪心推公式 定义 贪心算法是一种在每一步选择中都采取在当前状态下最优的选择,希望通过局部的最优选择来得到全局最优解的算法策略。 运用情况 问题具有最优子结构,即一个问题的最优解包含其子问题的最优解。可以通过局部最优决策逐步推导到全局最优。问题的选择策略相对明确且易于计算。 注意事项 贪心算法并不总是能得到全局最优解,可能会陷入局部最优。对于一些复杂问题,需要谨慎验证其正确性。可能需要对