2020-05-13

牛客算法周周练6

字数统计: 2.5k字 | 阅读时长: 11分

A题

大小各不相同的一队青蛙站在河左岸的石墩（记为A）上，要过到对岸的石墩(记为D)上去。河心有几片菏叶(分别记为Y1…Ym)和几个石墩(分别记为S1…Sn)。图示如下：

tupian

青蛙的站队和移动方法规则如下：

1．每只青蛙只能站在荷叶、石墩，或者仅比它大一号的青蛙背上（统称为合法的落脚点）；

2．一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另一个落脚点；

3．青蛙允许从左岸A直接跳到河心的石墩、荷叶和右岸的石墩D上，允许从河心的石墩和荷叶跳到右岸的石墩D上；

4．青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回跳动；

5．青蛙在离开左岸石墩后，不能再返回左岸；到达右岸后，不能再跳回；

6．假定石墩承重能力很大，允许无论多少只青蛙都可呆在上面。但是，由于石墩的面积不大，至多只能有一只青蛙直接站在上面，而其他的青蛙只能依规则1落在比它大一号的青蛙的背上。
7．荷叶不仅面积不大，而且负重能力也有限，至多只能有一只青蛙站在上面。

8．每一步只能移动一只青蛙，并且移动后需要满足站队规则；

9．在一开始的时候，青蛙均站在A上，最大的一只青蛙直接站在石墩上，而其它的青蛙依规则6站在比其大一号的青蛙的背上。

青蛙希望最终能够全部移动到D上，并完成站队。

设河心有m片荷叶和n个石墩，请求出这队青蛙至多有多少只，在满足站队和移动规则的前提下，能从A过到D。

例如，在m=1且n=1时，河心有一片荷叶（Y1）和一个石墩（S1），此时至多有4只青蛙能够过河（由小到大称为1、2、3、4），过河的一种方法为：

tupian2

输入描述:
仅有两行，每一行仅包含一个整数和一个换行/回车符。第一行的数字为河心的石墩数n(0 ≤ N ≤ 25)，第二行为荷叶数m(0 ≤ M ≤ 25)。

输出描述:
仅包含一个数字和一个换行/回车符。该数字为在河心有n个石墩和m片荷叶时，最多能够过河的青蛙的只数。

输入

输出

题意：
中文题，不过多叙述题意。

思路：
这道题的话，看起来像汉诺塔，但是汉诺塔可以随意移动，虽然也有一定前提。但是对这个题目来说最要命的约束条件就是到了对面就不能动了。所以我们可以知道一定是重的青蛙先跳去对面。所以我们从几个极端来看。
如果给出莲叶数是m，石头数目是n。

如果n是0，那么最多可以允许m+1个青蛙，m个青蛙填满莲叶，最后一个青蛙跳过去。
如果n是1，那么最多允许m+1个青蛙先填满莲叶，在去石头上面过渡，另外的m+1个青蛙根据m=0的情况跳。所以一共（m + 1）*2。所以我们得出结论：

$ans=2^{n}*(m+1)$

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int main()
{
    int n, m;
    cin >> n >> m;
    cout << (1 << n) * (m + 1) << endl;
    return 0;
}

B题

题意：
月月给华华出了一道题，先给你一个式子：$F_{1}=A,F_{2}=B,F_{i}=F_{i-1}+F_{i-2}(i>2)$，然后求$gcd(F_{N},F_{N+1})$。

思路：
这道题的话，考察裴蜀定理,裴蜀定理具体如下：裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且$gcd(a,b)=d$，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使$ax+by=d$成立。由裴蜀定理可知，要求$gcd(F_{N},F_{N+1})$,只要求出$gcd(A,B)$就可以了，这两者是相等的。并且C++函数库中已经封装了_$gcd(a,b)$用来求a与b之间的最大公约数，我们只需要套用就可以了。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int main()
{
    ll a, b, n;
    cin >> a >> b >> n;
    cout << __gcd(a, b) << endl;
    return 0;
}

C题

题意：
Nancy喜欢博弈！
Johnson和Nancy得到了一个神奇的多重集合，仅包含一个正整数n，两个人轮流进行操作。
一次操作可以将集合中一个数字分解为它的任意两个非1的因数，并加入集合中。
他们想知道，在Johnson和Nancy绝顶聪明的情况下，如果Nancy先手进行操作，最后谁没有办法继续操作了呢？

思路：
这道题的话，每次操作可以将集合中的一个数字分解为它的任意两个非1的因数, 集合中的数字个数+1。因为质因数是无法再被分解的,所以最后集合中的数全为 n 的质因数。因此只需要看题目给定的n有多少个质因数。假设n有p个质因数，那么这场游戏将进行p-1次操作（每次操作后集合中的数字个数+1），如果p-1为奇数那么后手便无法再进行操作，如果p-1为偶数则先手再无法进行操作。所以我们只要筛一下素数就行了。最后$n==1$的情况要判断一下。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int main()
{
    int n;
    cin >> n;
    if (n == 1)
    {
        cout << "Nancy" << endl;
        return 0;
    }
    int ans = 0;
    for (int i = 2; i <= n; i++)
    {
        while (n % i == 0)
        {
            n /= i;
            ans++;
        }
    }
    if (ans % 2 != 0)
        cout << "Nancy" << endl;
    else
        cout << "Johnson" << endl;
    return 0;
}

D题

题意：
胡队长带领HA实验的战士们玩真人CS，真人CS的地图由一些据点组成，现在胡队长已经占领了n个据点，为了方便，将他们编号为1~n，为了隐蔽，胡队长命令战士们在每个据点出挖一个坑，让战士们躲在坑里。由于需要在任意两个点之间传递信息，两个坑之间必须挖出至少一条通路，而挖沟是一件很麻烦的差事，所以胡队长希望挖出数量尽可能少的沟，使得任意两个据点之间有至少一条通路，顺便，尽可能的$\sum d[i][j]$使最小（其中$d[i][j]$为据点i到j的距离）。

思路：
这道题的话，就是一道裸的最小生成树，直接做就可以了。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
struct node
{
    int s;
    int e;
    int v;
} edge[maxx*5];
bool cmp(node a, node b)
{
    return a.v < b.v;
}
int pre[maxx];
int n, m;
void init()
{
    for (int i = 0; i <= n; i++)
        pre[i] = i;
}
int getf(int a)
{
    if (pre[a] == a)
        return a;
    int tmp = getf(pre[a]);
    return pre[a] = tmp;
}
int Kruskal(int a, int b)
{
    int fa = getf(a);
    int fb = getf(b);
    if (fa != fb)
    {
        pre[fa] = fb;
        return 1;
    }
    else
        return 0;
}
int main()
{
    while (cin >> n >> m)
    {
        init();
        for (int i = 1; i <= m; i++)
            cin >> edge[i].s >> edge[i].e >> edge[i].v;
        sort(edge + 1, edge + m + 1, cmp);
        int ans = 0;
        for (int i = 1; i <= m; i++)
        {
            if (Kruskal(edge[i].s, edge[i].e))
                ans += edge[i].v;
        }
        cout << ans << endl;
    }
    return 0;
}

E题

题意：
这道题给你了一些代码，让你补全。

思路：
这道题的话，看完代码后不难看出是求的线段树，所以我们按要求补全即可。

AC代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define fi first
#define lc (x << 1)
#define se second
#define U unsigned
#define rc (x << 1 | 1)
#define Re register
#define LL long long
#define MP std::make_pair
#define CLR(i, a) memset(i, a, sizeof(i))
#define FOR(i, a, b) for (Re int i = a; i <= b; ++i)
#define ROF(i, a, b) for (Re int i = a; i >= b; --i)
#define SFOR(i, a, b, c) for (Re int i = a; i <= b; i += c)
#define SROF(i, a, b, c) for (Re int i = a; i >= b; i -= c)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 1000000 + 5;
int N, maxL;
std::set<std::pair<int, int>> L;
int a[MAXN];
inline int calc()
{
    // 返回 set 中所有线段的并长度。(每个 pair 表示一个线段[first,second]
    int ans = 0;
    for (int i = 1; i <= maxL; i++)
    {
        if (a[i])
            ans++;
    }
    return ans;
}
int main()
{
    scanf("%d%d", &N, &maxL);
    while (N--)
    {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 1)
        {
            if (L.find(MP(x, y)) != L.end())
                continue;
            L.insert(MP(x, y));
            for (int i = x; i <= y; i++)
                a[i]++;
        }
        if (opt == 2)
        {
            if (L.find(MP(x, y)) == L.end())
                continue;
            L.erase(MP(x, y));
            for (int i = x; i <= y; i++)
                a[i]--;
        }
        if (opt == 3)
        {
            printf("%d\n", calc());
        }
    }
    return 0;
}