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

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

---

---

前言

为什么突然想学算法了？

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

---

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

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。

---

目录

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

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

格式

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

样例1

输入: 1
.
输出: 0.600000%

（2）参考代码

#include 
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

2. MT2287 抽奖概率

（1）题目描述

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

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

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

格式

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

样例1

输入: 4
.
输出: 0.682292

（2）参考代码

#include 
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);
}
1
2
3
4
5
6
7
8
9
10
11
12

---

3. MT2288 石子游戏

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

---

格式

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

样例1

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

（2）参考代码

#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

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();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

---

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 
/*
思路：不越狱的状态好计算所以：越狱数=总的状态数-不越狱的状态数
其中 总的状态数为：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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

---

结语

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

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

愿你的结局，配得上你一路的颠沛流离。