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

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

---

---

前言

为什么突然想学算法了？

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

---

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

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

---

目录

1. MT2291 饿饿!饭饭!

（1）题目描述
嗯哼，小码哥在新的一年里不会忘记身为干饭人的初心!

众所周知，小码哥非常不喜欢一直吃同样的东西，但由于理想与现实的差距，食堂在这n天里只会供应k种餐食。

在一天吃3餐的情况下，前w天一共wx3顿饭小码哥不希望有任何一顿重复。现在请问食堂有多少种方案可以满足超级可爱乖巧的小码哥的需要。

格式

输入格式:
第一行，三个整数n，k，w表示n天内食堂只会供应k种餐室，小码哥的意义详见题面。
.
输出格式: 输出一行一个数，表示满足小码哥需要的方案数。

样例1

输入: 5 4 1
.
输出格式: 24

备注：

数据范围: 1≤n, w, k≤ 12

（2）参考代码

#include 

using namespace std;
typedef long long ll;
ll ans = 1;
int main( )
{
    int n,k,w;
    cin>>n>>k>>w;
    w*=3;
    if(w>k) ans=0;
    for(int i =k-w+1; i<=k;i++) ans*=i;
    cout<<ans<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

2. MT2292 甜甜花的研究

（1）题目描述

小码哥酷爱研究植物，他对甜甜花的研究无人能及，可他仍然在不断研究着。现在小码哥有n粒甜甜花的种子，每一粒种子都能长出不同的甜甜花，由于种子实在太多，小码哥一个人实在无法照料，于是他雇佣了m位种植能手，第i个人能照料a株甜甜花，请问小码哥有多少种分配方式将这些种子分配出去?

格式

输入格式:
输入共两行:
第一行输入用空格隔开的两个正整数n、m ,
第二行输入m个正整数，分别代表ai。
.
输出格式:
输出一个整数表示方法个数
由于结果可能很大，须将结果对12520取模

样例1

输入:
5 2
3 1
.
输出:
20

备注：

其中: n≤104,m ≤100,ai ≤100数据保证种子有剩余

（2）参考代码

#include 

using namespace std;
typedef long long int ll;
const int mod=12520,N=10010;

ll C(ll n,ll m){
    ll ans = 1;
    for(ll i=1;i<=n;i++) ans*=i;
    for(ll i=1;i<=m;i++) ans/=i;
    for(ll i=1;i<=n-m;i++) ans/=i;
    return ans;
}

int main( )
{
    int n,m,a1,a2;
    cin>>n>>m>>a1>>a2;
    ll num1 = C(n,a1)%12520;
    ll num2 = C(m,a2)%12520;
    ll result = num1*num2;
    cout<<result<<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
24

---

3. MT2293 赌石

（1）题目描述
富饶的璃月街道上有一家石料店，店主小码哥是个精明的商人，为了使他的赌石生意更加红火，他根据赌徒的心理设计了一个有趣的买卖规则:他在店铺的两边放了个小桶，一个桶里有n个红球，另一个有n个蓝球。每一批2n个璞石与这些球一—对应，对每个来买璞石的客户石头都会让他们在原地闭眼旋转数圈后走向一个小桶，若拿到蓝球则可免费获得一块石头，但若拿到红球则需要付出两倍的价钱。

假设每个人每次拿到蓝球和红球的概率相同，现在请你求出一个桶里没球而另一个桶里还剩两个球的概率，精确到小数点后四位。

---

格式

输入格式: 输入一个正整数代表这批璞石的个数。
.
输出格式: 输出一个四位小数代表所求答案。

样例1

输入格式: 256
.
输出格式: 0.9500

（2）参考代码

#include 
#include 
#include 
#include 
 
using namespace std;
 
typedef long double LD;
 
LD C_div(int k, int n)
{
    LD res = 1;
    
    for (int i = n, j = 1; j <= k; i -- , j ++ )
        res = res * i / j;
    
    for (int i = 1; i <= k; i ++ ) res /= (LD)4.0;
    return res;
}
 
int main()
{
    int n;
    cin >> n;
    
    n /= 2;
    
    printf("%.4llf", 1 - C_div(n - 1, 2 * n - 2));
    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
28
29
30

---

4. MT2294 square

（1）题目描述
猩猩，骆驼，还有泡泡经常喜欢在饭后到操场上散步，由于猩猩的走路姿势最突出最显眼，理所应当的成为他们中的主角，所以我的题目就说猩猩散步了。(骆驼和泡泡别有意见哈，和猩猩争啥…)

当然，话说回来，猩猩在OI上的能力也是不容低估的，你看，散步时还会想一道与此相关的问题，这是道经典的不能再经典的问题了。

在一个mxn的矩阵上，猩猩在左下角的顶点出现了，他只能沿着路径向上或者向右走，他的目标是“蠕动”到右上角的顶点，问他有多少路径可以选择。嗯，这个、这个、这个似乎地球人都知道怎么做，但是请注意，我有个条件没给呢! m和n现在的最大范围是50000，这可怎么办?仔细想想吧。

---

格式

输入格式:
只有一行，包含两个整数m和n，其均不小于4，上限均为50000。
.
输出格式: 由于最后的答案数目过大，所以只检查后100位，输出时每行十个数字，没空格间隔，共十行，如果答案位数没超过100位，则需要在空位上补0。

样例1：

输入： 7 4
.
输出：
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000330

（2）参考代码

#include 
using namespace std;
const int N = 1e6 + 7;
int ans[110];
int cnt[N];
int b[110];
void multi(int x)
{
    memcpy(b, ans, sizeof b);
    memset(ans, 0, sizeof ans);
    int j = 0;
    while (x) {
        int z = x % 10;
        x /= 10;
        for (int i = 1; i <= 100; i++) {
            if (i + j <= 100)
                ans[i + j] += z * b[i];
        }
        j++;
    }
    for (int i = 1; i <= 100; i++) {
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
    }
}
int main()
{
    int m, n;
    cin >> m >> n;
    if (m > n)
        swap(m, n);
    for (int i = 0; i < m; i++) {
        int x = m + n - i;
        for (int j = 2; j <= x / j; j++) {
            while (x % j == 0) {
                x /= j;
                cnt[j]++;
            }
        }
        if (x != 1)
            cnt[x]++;
    }
    for (int i = 1; i <= m; i++) {
        int x = i;
        for (int j = 2; j <= x / j; j++) {
            while (x % j == 0) {
                x /= j;
                cnt[j]--;
            }
        }
        if (x != 1)
            cnt[x]--;
    }
    ans[1] = 1;
    for (int i = 1; i < N; i++) {
        while (cnt[i]) {
            multi(i);
            cnt[i]--;
        }
    }
    for (int i = 100; i >= 1; i--) {
        cout << ans[i];
        if (i % 10 == 1)
            cout << 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
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

---

5. MT2295 越狱

（1）题目描述
监狱有n个房间，每个房间关押一个犯人，有m种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

答案对1007取模。

---

格式

输入格式: 输入只有一行两个整数，分别代表宗教数m 和房间数n。
.
输出格式: 输出一行一个整数代表答案。

样例1

输入格式: 2 3
.
输出格式: 6

备注：

其中: 1≤m ≤le8,1 ≤n ≤1e10

（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，供大家更好的进行学习与刷题～(￣▽￣～)~

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