算法竞赛入门【码蹄集进阶塔335题】(MT2286-2290)

这篇具有很好参考价值的文章主要介绍了算法竞赛入门【码蹄集进阶塔335题】(MT2286-2290)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法竞赛入门【码蹄集进阶塔335题】(MT2286-2290)



前言

算法竞赛入门【码蹄集进阶塔335题】(MT2286-2290),云曦算法,算法,c++,开发语言,码蹄集

为什么突然想学算法了?

> 用较为“官方”的语言讲,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言,是因为当下快到了考研和找工作的年纪(ಥ_ಥ),无论走哪一条路,都不免需要一些相对丰富的算法知识,是故,便产生了一个暑假速成算法的计划,可能对于像我这种算法竞赛小白而言,几乎很难,但我仍然还是想尝试一下,毕竟,梦想还是要有的,万一实现了呢?~( ̄▽ ̄~)~

算法竞赛入门【码蹄集进阶塔335题】(MT2286-2290),云曦算法,算法,c++,开发语言,码蹄集


为什么选择码蹄集作为刷题软件?

码蹄集,是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的,其依托全国各大名校计算机系和清华大学出版社等单位的强大资源,旨在为计算机学习爱好者提供全面和权威的计算机习题。
算法竞赛入门【码蹄集进阶塔335题】(MT2286-2290),云曦算法,算法,c++,开发语言,码蹄集


目录

1. MT2286 小码哥的抽卡之旅1

(1)题目描述
小码哥最近迷上了一款抽卡游戏。单抽出金的概率是0.6%,如果前89发都不出金,则90发必出金。小天目前存了一些抽数,想要你帮他算算他出金的概率。

格式

输入格式: 一个整数n,表示小码哥的抽数
.
输出格式: 一个百分数p,表示出金的概率,保留六位小数(按所给样例)

样例1

输入: 1
.
输出: 0.600000%

(2)参考代码

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
int main() {
    int n;
    double get = 0, notget = 1 - get;
    cin >> n;
    for (int i = 0; i < n; i++) {
        get += notget * 0.006;
        notget = 1 - get;
    }
    printf("%.6lf%\n", get * 100);
    return 0;
}


2. MT2287 抽奖概率

(1)题目描述

小码哥正在进行抽奖,箱子里有一红一白两小球,每次摸出一个球,摸到红球中奖,如果中奖,就不再继续抽奖;

如果未中奖(摸到白球),则往箱子里补充一个白球(摸出的白球不放回),继续抽奖,直到中奖,或者达到最大抽奖次数。

假设至多能抽奖M次,求当停止抽奖时,(中奖球数/摸出总球数)的期望。

格式

输入格式: 第一行,一个整数M。
.
输出格式: 保留到小数后六位。

样例1

输入: 4
.
输出: 0.682292

(2)参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int i,j,k,n,m,t;
double res;
int main() {
    cin>>n;
    for(i=1;i<=n;i++){
        res+=1.0/i/pow(2,i);
    }
    printf("%.6lf",res);
}

3. MT2288 石子游戏

(1)题目描述
小码哥与小码妹正在玩石子游戏,游戏规则是这样的:桌上放有两堆石子,双方轮流取石子,轮到的一方只能从数量较多的一堆里取走另一堆的数量的正整数倍,把一堆石子取完的玩家获胜(如果两堆石子一样多,可以任选一堆来取)。现在告诉你初始状态下两堆石子的数目,请你判断若双方采取最优策略,先手是否必胜。


格式

输入格式: 一行,两个正整数a, b 表示两堆石子的数量,0<a,b ≤1×105。
.
输出格式: 输出一行,若先手必胜输出YEs,否则输出NO

样例1

输入格式: 13 10
.
输出格式: NO

(2)参考代码

#include <bits/stdc++.h>
using namespace std;
int dfs(int a,int b){
    if(a<b){
        int t=a;
        a=b;
        b=t;
    }
    int t=a%b;
    if(t==0) return 1;
    int ans=dfs(b,t);
    if(ans==0) return 1;
    if(t+b<a) ans=dfs(t+b,b);
    if(ans==0) return 1;
    return 0;
}
int main() {
    int a,b;
    cin>>a>>b;
    if(dfs(a,b)==1) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

4. MT2289 谁会赢呢?

(1)题目描述
小码哥和小码弟正在玩游戏,他们都绝顶聪明。

开始时有一个整数n,二者轮流行动,每次行动可以在当前的n上减去其一个非1非n的因子。

若某一方无法进行操作则判其输,小码哥先手,谁会赢呢?


格式

输入格式:
第一行一个正整数t表示数据组数。接下来t行,每行一个整数表示n
.
输出格式: t行,每行输出获胜者

样例1:

输入
4
1
4
12
69
.
输出
xiaomadi
xiaomage
xiaomage
xiaomadi

(2)参考代码

import time
from typing import List, Tuple
from collections import deque, Counter
from queue import PriorityQueue
import math
from functools import lru_cache
#from sortedcontainers import SortedDict, SortedSet
import random
import copy
import sys
sys.setrecursionlimit(999999999)
MOD = 10**9 + 7
def get_prime(N):
    prime_vals = []
    flag = [True] * (N+1)
    for val in range(2, N+1):
        if flag[val]:
            prime_vals.append(val)
        for p_val in prime_vals:
            if val * p_val > N:
                break
            flag[val * p_val] = False
            if val % p_val == 0:
                break
    return prime_vals
primes = get_prime(100000)
def devide_prime(val):
    ans = []
    for i in primes:
        if i*i > val:
            break
        if val % i == 0:
            cnt = 0
            while val % i == 0:
                val //= i
                cnt += 1
            ans.append((i, cnt))
        if val == 1:
            break
    if val != 1:
        ans.append((val, 1))
    return ans
# 统计不等于1或者x自身的因子
def get_div(x):
    ret = devide_prime(x)
    ans = []
    def dfs(ii, val):
        nonlocal ans
        if ii == len(ret):
            if 1 < val < x:
                ans.append(val)
            return
        for i in range(ret[ii][1] + 1):
            dfs(ii + 1, val * (ret[ii][0] ** i))
    dfs(0, 1); return ans
def is_prime(x):
    if x <= 1:
        return False
    if x <= 3:
        return True
    i = 2
    while True:
        if i * i > x:
            break
        if i * i == x:
            return False
        if x % i == 0:
            return False
        i += 1
    return True
# 获取2的次幂数
def get_2_cnt(x):
    cnt = 0
    while x > 0 and x & 1 == 0:
        cnt += 1
        x >>= 1
    return cnt
def main():
    # 先手是否必赢
    def dp(x):
        if x == 1 or is_prime(x):
            return False
        div = get_div(x)
        for v in div:
            if not dp(x - v):
                return True
        return False
    T = int(input())
    for _ in range(T):
        n = int(input())
        if n <= 10:
            ret = dp(n)
        else:
            # 规律:n是偶数且不是2的奇数次幂,则先手必胜
            cnt2 = get_2_cnt(n)
            ret = False
            if n % 2 == 0:
                if not (cnt2 & 1 == 1 and n == (1 << cnt2)):
                    ret = True
        print("Honcy" if ret else "Tak")
if __name__ == '__main__':
    main();


5. MT2290 Game

(1)题目描述
小码哥和小码妹准备玩一个游戏。有n堆石头,每堆石头个数为ai。小码哥先手,每一回合玩家可以从n堆石头中任选一堆移除。

胜负判定规则:

如果玩家移除一堆石头之后,导致所有移除的石头数量之和是3的倍数,那么该玩家输。如果不满足上一条,且移除后没有剩余的石头,那么小码妹胜。(不关心于该回合是谁的)

保证两者都是最聪明的。如果小码哥胜则输出1,否则输出0。

请构造一个函数Game,然后传入数组a,然后进行胜负的判断。


格式

输入格式: 第一行一个整数n(1≤n ≤105)第二行有n个整数a(1 ≤ai ≤104 )
.
输出格式: 输出1或者0

样例1

输入格式:
5
5 1 2 4 3
.
输出格式: 0

(2)参考代码

#include<bits/stdc++.h> 
/*
思路:不越狱的状态好计算所以:越狱数=总的状态数-不越狱的状态数
其中 总的状态数为:m^n
    不越狱的状态数: m*(m-1)^(n-1) :只有第一个可以选择m个宗教,其他的只能选和前一个不同的宗教所以是m-1种情况
这里计算用了快速幂的方法。
*/
using namespace std;
long long p=1007;
long long qpow(long long x, long long y){
    if(y==0)
        return 1;
    if(y%2==1){
        return qpow(x, y - 1) * x % p;
    }else{
        long long t = qpow(x, y/2) % p;
        return t*t % p;
    }
}
int main( )
{
    long long m,n;
    cin>>m>>n;
    long long ans = qpow(m,n)-(m*qpow(m-1,n-1)%p);
    cout<<(ans+p)%p<<endl;//注意需要+p之后再取 %p,防止有负数
    return 0;
}

结语

感谢大家一直以来的不断支持与鼓励,码题集题库中的进阶塔350题正在逐步更新,之后会逐步跟进星耀,王者的题,尽请期待!!!
同时,也希望这些题能帮助到大家,一起进步,祝愿每一个算法道路上的“苦行僧”们,都能够历经磨难,终成正果,既然选择了这条路,走到了这里,中途放弃,岂不是太过可惜?

另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0,供大家更好的进行学习与刷题~( ̄▽ ̄~)~

愿你的结局,配得上你一路的颠沛流离。文章来源地址https://www.toymoban.com/news/detail-738762.html

到了这里,关于算法竞赛入门【码蹄集进阶塔335题】(MT2286-2290)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法竞赛入门【码蹄集进阶塔335题】(MT2226-2250)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月11日
    浏览(37)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2281-2285)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月07日
    浏览(40)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2176-2200)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月09日
    浏览(42)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2301-2305)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月06日
    浏览(52)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2076-2100)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2023年04月19日
    浏览(47)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2201-2225)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月08日
    浏览(37)
  • 算法竞赛入门【码蹄集进阶塔335题】(MT2271-2275)

    为什么突然想学算法了? 用较为“官方”的语言讲 ,是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中,要想完成任何实质性的工作,理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。 但从实际而言 ,是因为当

    2024年02月07日
    浏览(36)
  • 算法竞赛入门【码蹄集新手村600题】(MT1020-1040)

    码蹄集网站地址:https://www.matiji.net/exam/ojquestionlist (1)题目 输入一个实数,第一次按实型输出;第二次保留2位小数输出;第三次保留3位小数但最小列宽8列输出,空格分隔。 格式 样例1 (2)参考代码 (1)题目 输出3.1415926、12345678.123456789的小数、指数形式。 格式 样例1 (

    2024年02月16日
    浏览(44)
  • 算法竞赛入门【码蹄集新手村600题】(MT1280-1300)C语言

    码蹄集网站地址:https://www.matiji.net/exam/ojquestionlist (1)题目 输入正整数N(1500),首先计算其逆序数M(比如12逆序后是21)。然后输出N的M次方的最后3位数。 格式 样例1 (2)参考代码 (1)题目 一个自然数,如果每一位数的位数次幂之和等于该自然数,则称之为Disarium数。 比如

    2024年02月07日
    浏览(44)
  • 供水管线 码蹄集

    首先,题目要求我们去掉一些管道,使得总的管道管理费用最小。在去掉部分管道的情况下,城市之间不再形成一个回路,即城市之间构成了一棵树。因此,我们需要找到一棵生成树,使得所有管道管理费用之和最小。 接下来,我们需要选择合适的算法来寻找最小生成树。常

    2024年02月06日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包