【牛客算法周周练6】

A-青蛙过河

这道题其实不难，这个叠罗汉看着是有点像汉诺塔对吧，但是有一个条件直接把这道题压死了：

每个青蛙只能站在比自己大一级的青蛙背上，而且只能在石墩上踩背。

讲解：

既然如此，我们就能明白，如果要把青蛙完全移动到某一个石墩上，那一定是青蛙全部排开了（也就是平铺了一层）。
那么，因为我们有m篇荷叶，那么我们先平铺m只青蛙到荷叶上，然后加上起始石墩上的青蛙，就可以在一个中间石墩上放上m+1只青蛙了。
而在每多一个石墩的情况下，我们就可以比原来多一倍的青蛙，所以可以简单的得到公式了，ans = （m + 1）* 2ⁿ。
这个公式的幂次是怎么来的呢？其实是有1个石墩就是石墩上放一批，起点有一批；2个石墩就是，河中石墩：2,1，加上起点的；三个就是，河中石墩4,2,1，加上起点的。所以就是一个幂次关系。

打代码：

简单操作，2的n次方用位运算就好了。
直接出答案，看代码吧

AC代码

#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main() {
    IOS;
    int n, m; cin >> n >> m;
    cout << (m + 1) * (1 << n) << endl;
    return 0;
}

B-华华对月月的忠诚

不瞒你说，我觉得这道题在考验我的忠诚。

我最开始还是很忠诚的，看到数据范围，我觉得我没有这个信心了。

但是看到这个范围，我们就能明白，这道题一定有可以取巧的办法。

就比如这道题，任意两个相邻的gcd就都是一样的呀。

打代码：

直接算gcd（a，b）就好了。
看代码咯~

AC代码

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false);
//代码预处理区
 
ll gcd(ll x, ll y) {
    return y == 0 ? x : gcd(y, x % y);
}
//函数预定义区
 
int main() {
    IOS;
    ll a, b; string n;
    cin >> a >> b >> n;
    cout << gcd(a, b) << endl;
    return 0;
}
//函数区

C-Game

这道题非常简单，我们知道这两个人就是在把一个数一直拆成因子对，拆不下去的人算输了。

博弈思想：

既然我们每个人拆一次数，也就是说，每进行一次操作，我们的数就会多一个。如此反复，最后就会变成我们这个数的所有素因子。
那么我们的重心自然就放到素因子上来了。上面的一句话十分重要，就是我们操作一次，数就多一个。
所以我们自然而然的就明白了，我们的输家就和这个数的奇偶性有关。
所以，我们就明白了了，素因子个数是奇数，先手必败。素因子是偶数，后手必败（这里的玩家不需要聪明的一批，俩傻X结果也是一样的）。

所以呢，我们这里知道了博弈是咋肥事，打代码就好了：

我们先筛出素因子，求出个数。详情看代码。
然后奇数出先手，偶数出后手。
看代码趴~

AC代码

#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(false);
 
int main() {
    IOS;
    int n; cin >> n;
    int cnt = 0;
    for (int i = 2; i * i <= n; i++)
        for (; n % i == 0; n /= i)
            cnt++;
    if (n > 1) cnt++;
    if (cnt & 1) cout << "Nancy" << endl;
    else cout << "Johnson" << endl;
    return 0;
}
//函数区

D-挖沟

难得啊，难得有个名字叫挖沟的题不给我挖沟嘞。

这道题就是简简单单，明明白白，清清楚楚的最小生成树的板子题（kruskal简单，可以看一下链接里的最小生成树专栏讲解）。

上面既然已经给了专栏链接，我就直接来这道题啦：

按照kruskal思想，我们要从小到大选边，所以我们排个序。（题目的边可以重复，这样顺便就使重复的权值大的边拍在后面，不会影响答案了）
接下来就是连接这条边：要注意判断这条边能不能连接，也就是判断两头的点是否在同一棵树里面，这里我们可以用并查集简单实现。
听说查并集进行路径压缩就会变得更快哦。
不在同一棵树里面就连起来，然后加上这里的边权。

打代码：

我们先用一个结构体边数组（内置边的端点与边权），储存所有的边信息。
然后按照我们上面讲的kruskal思想来遍历所有边就好了。
看我代码趴~

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int N = 1e5 + 7; //节点
const int M = 5e5 + 7; //路径数
struct Edge {
	int u, v, w;
	bool operator <(const Edge tmp) const {
		return w < tmp.w;
	}
} edge[M];
int n, m, fa[N];
int ans = 0;
//全局变量区

int find(int x);//查找+路径压缩
void kruskal();//最小生成树算法
//函数预定义区

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; ++i) fa[i] = i;
	for (int i = 0; i < m; ++i)
		cin >> edge[i].u >> edge[i].v >> edge[i].w;
	sort(edge, edge + m);
	kruskal();
	cout << ans << endl;
	return 0;
}
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void kruskal() {
	for (int i = 0; i <= m; i++) {
		int u = edge[i].u, v = edge[i].v;
		int x = find(u), y = find(v);
		if (x != y) {
			fa[x] = y;
			ans += edge[i].w;
		}
	}
}
//函数区

E-签到题

我信里个鬼嘞签到题。

这道题可以用线段树，但是也可以用模拟，因为题目控制没有那么严格_{（线段树我不会）}。

怎么模拟呢？

简单来说就是用pair键值对模拟数组的两边，然后用一个真实的数组模拟出每个位置上重叠的区间数量（真的是人沙雕了才会去套题目的模板，超时了QAQ）。
这告诉了我们不要定向思维，不要出题人给个套就钻。
然后根据题目意思，我们要注意，重复的区间不叠加，直接删除。

打代码：

题目没给啥题目，我们先按题目代码看出来要输入啥就好了。
然后按照我说的模拟过程，详情看我代码就好啦~

AC代码

#include <iostream>
#include <set>
using namespace std;
//代码预处理区

const int maxn = 1e5 + 5;
int a[maxn];
set<pair<int, int> >P;
//全局变量区

int main(){
    int n, L; cin >> n >> L;
    int ans = 0;
    while (n--){
        int opt, x, y; cin >> opt >> x >> y;
        if (opt == 1){
            if (P.find(make_pair(x, y)) != P.end()) continue;
            P.insert(make_pair(x, y));
            for (int i = x; i <= y; i++){
                a[i]++;
                if (a[i] == 1) ans++;
            }
        }
        else if (opt == 2){
            if (P.find(make_pair(x, y)) == P.end()) continue;
            P.erase(make_pair(x, y));
            for (int i = x; i <= y; i++){
                a[i]--;
                if (a[i] == 0) ans--;
            }
        }
        else cout << ans << endl;
    }
    return 0;
}
//函数区