【牛客算法周周练6】
A-青蛙过河
这道题其实不难，这个叠罗汉看着是有点像汉诺塔对吧，但是有一个条件直接把这道题压死了：
- 每个青蛙只能站在比自己大一级的青蛙背上，而且只能在石墩上踩背。
讲解：
- 既然如此，我们就能明白，如果要把青蛙完全移动到某一个石墩上，那一定是青蛙全部排开了（也就是平铺了一层）。
- 那么，因为我们有m篇荷叶，那么我们先平铺m只青蛙到荷叶上，然后加上起始石墩上的青蛙，就可以在一个中间石墩上放上m+1只青蛙了。
- 而在每多一个石墩的情况下，我们就可以比原来多一倍的青蛙，所以可以简单的得到公式了，ans = （m + 1）* 2n。
- 这个公式的幂次是怎么来的呢？其实是有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;
}
//函数区比赛 文章被收录于专栏
憨憨的专栏
