2025年斗牛游戏

科技前沿 • 2025-03-25 13:27 • 阅读 79

大家好，我是讯享网，很高兴认识大家。

题目背景
又是一年过去了。小 Z 在春节期间可以好好的放松放松，于是小 Z 和小伙伴们玩起了牛哄哄（斗牛）。
游戏规则是这样的：
给定 5 张牌，分别从 1∼10。你需要挑选其中的三张牌加起来是10 的倍数，另外两张牌的和的个位数则为你最后获得的点数，特别的，如果这两张牌的和是 10 的倍数，则点数为 10，也叫做牛哄哄。如果不能构成 10 的倍数，则点数为 0，也叫做牛不拢。如 5 3 2 3 4 的点数是 7，又叫做牛七。
小 Z 觉得玩的不过瘾，于是对上述规则进行了一些改变。
给定 n 张牌，牌的大小为 1∼10。你需要挑选其中的 n−2 张牌加起来是 10 的倍数，另外两张牌和的个位数即为你所获得的点数。特别地，如果这两张牌的和是 10 的倍数，则点数为 10，也叫做牛哄哄。如果任意 n−2 张牌不能构成 10 的倍数，则点数为 0，也叫做牛不拢。由于小 Z 想要更开心的玩耍，所以需要你来完成这个程序来帮助小 Z 在 1 秒内知道点数。

输入格式
第一行一个整数 n，表示一共有 n 张牌。
第二行 n 个整数，表示这 n 张牌的大小。

第一次看题只想到了最基础的搜索就是枚举所有可选的两张牌，用所有牌的总和减去这两张牌如果是10的倍数，那么剩下两个牌的和mod10就是牛数，在枚举过程中不断更新即可。
复杂度n²可以拿到80分
程序如下

讯享网

#include<bits/stdc++.h> using namespace std; int a[10005]={ 
   0}; int main() { 
   int w,n,max=0; cin>>n; long long int sum=0; for(int i=1;i<=n;i++) { 
   scanf("%d",&a[i]); sum+=a[i]; } for(int i=1;i<n;i++) { 
    for(int j=i+1;j<=n;j++) { 
    if((sum-a[i]-a[j])%10==0&&a[i]+a[j]==10)max=10; if((sum-a[i]-a[j])%10==0&&(a[i]+a[j])%10>max) max=(a[i]+a[j])%10; } } printf("%d",max); return 0; }

讯享网

只能处理相当有限的数据

之后进一步对这个思想进行优化，因为最大牛数一定是总和mod10，，想到了如果summod10等于两个值mod10就可以说明一定存在两个数，使sum减掉这两个数后为10的倍数，sum%10即为牛数
在读入数据时，存储所有的数出现的次数，只要存在这两个数的和mod10等于总和mod10就说明牛数有解，这个算法的优点体现在判断只用进行常数次（最多10次）只在读入数据时消耗了o（n）的复杂度
总复杂度只有读入时的o（n）
代码如下

讯享网#include <bits/stdc++.h> using namespace std; int n,w[11],ans,sum; int a[]; int main(){ 
    scanf("%d",&n); for(int i=1;i<=n;i++){ 
    scanf("%d",&a[i]); w[a[i]]++; sum+=a[i]; } ans=sum%10; if(ans==0)ans=10; for(int i=1;i<=10;i++){ 
    if(w[i]&&w[(ans+10-i)%10]){ 
    if(i==(ans+10-i)%10&&w[i]<2)continue; cout<<ans<<endl; return 0; } }cout<<0<<endl; return 0; }

2025年斗牛游戏

相关推荐