牛客算法周周练6
A，青蛙过河
题目描述
这个题目的篇幅很长，我这里就简要的描述几个要点，首先是和汉诺塔问题很像，很多人第一眼看到就以为是汉诺塔，我也是，讲一讲和汉诺塔不同的地方，首先这个是青蛙过河，河里有石墩和荷叶两种，同样两岸也是一个石墩，石墩上面只能是小的的青蛙叠在上面，大的青蛙叠在下面，荷叶上只能坐一个青蛙，还有一个很关键的地方让这个题目完全偏离了汉诺塔，就是在两岸的石墩，离开了这边或者到达了对面就不能再回去。解析
因为离开了这边或者到达了对面就不能再回去，由此可以推断出，最大的一只青蛙一定是从对岸的这边直接跳到对岸去，然后我们分析一下荷叶的作用，不难想到，荷叶上之只能坐一个，那么我们直接将一只最小的放在荷叶上，这么这个荷叶和荷叶上的青蛙都可以不用管了（因为它可以随时直接跳到对面），同样有多片荷叶我们就将最小的，其次小的依次放上去，然后我们再看石墩的作用，这里假设我们有n片荷叶，如果我们中间没有石墩，那么能跳到对面的青蛙就是n+1只，如果我们有1个石墩，这样我们怎么看？我们可以将中间这个石墩先看作河对岸的石墩，然后我们能跳过来的青蛙就有n+1只，然后我们再把n+1只直接从这边跳到河对岸，然后再把河中间的n+1只跳到对岸，这么看我们每多出一个石墩（假设总共为k个），就可以将k-1个石墩时的青蛙叠在这个新的石墩上，由此，我们可以推断出递推式：当有n片荷叶，k个石墩时，能够跳过去的青蛙个数有：代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
ll n,k;
cin>>n>>k;
cout<<(k+1)*2*n<<endl;
return 0;
}
B，华华对月月的忠诚
题意
大概就是月月为了防止华华找别的妹子，给他整了一个活，给出一个类似斐波那契数列然后求
(呵，恋爱的酸臭味）
解析
首先题目中给出的N非常大，甚至还不取模，很明显这个题和N没什么关系，既然和N没有关系，就要观察那个的特点，首先我们要知道辗转相除法之外的辗转相减法。gcd(a,b)如果a>b那么会等于gcd(a-b,b)。如果b>a那么会等于gcd(a,b-a)，如果a，b相等此时就是gcd。还有一个结论就是 gcd(2a,2b) = 2gcd(a,b)。一般用于高精度，代替取模的运算，这个是演算过程：
这么看这个题目就很简单了，贴上代码。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int gcd(ll a,ll b){
if(b==0)
return a;
else
return gcd(b,a%b);
}
int main(void){
ll a,b,n;
ios::sync_with_stdio(false);
cin>>a>>b>>n;
cout<<gcd(a,b)<<endl;
return 0;
}C，Game
题意
有一个数，Johnson和Nancy轮流对他操作，将这个数进行分解，分解成两个非1的因数，当谁不能进行分解的时候，就是算谁数。解析
做法很简单，对这个数进行质因数分解就好了，没有啥好博弈的，（这个才是真正的签到题，下面那个签到题是虚假的代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void){
ios::sync_with_stdio(false);
ll n,n1;
cin>>n;
n1=n;
ll flag=0;
for(ll i=2;i<n;++i){
while(n1%i==0&&n1!=i){
n1/=i;
flag++;
}
}
if(flag&1)cout<<"Johnson"<<endl;
else cout<<"Nancy"<<endl;
return 0;
}
D，挖沟
题意
清清楚楚明明白白这是一个板子题解析
这是一个最小生成树kruskal算法的板子题（主要是我自己还没学明白我就不多说了，代码
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline int read() {
int s = 0, w = 1; char ch = getchar();
while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return s * w;
}
const int N = 1e5 + 7; //节点
const int M = 5e5 + 7; //路径数
int n, m;
struct Edge {
int u, v, w;
bool operator <(const Edge tmp) const {
return w < tmp.w;
}
}edge[M];
int father[N];
ll ans = 0; //最小生成树的花费和
int find(int root) {
int son = root;
while (root != father[root])
root = father[root];
while (son != root) { //路径压缩
int temp = father[son];
father[son] = root;
son = temp;
}
return root;
}
void kruskal() {
for (int i = 1; i <= m; i++) {
int u = edge[i].u, v = edge[i].v;
int x = find(u), y = find(v);
if (x != y) {
father[x] = y;
ans += edge[i].w;
}
}
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; ++i)
father[i] = i;
for (int i = 1; i <= m; ++i)
edge[i].u = read(), edge[i].v = read(), edge[i].w = read();
sort(edge + 1, edge + 1 + m);
kruskal();
printf("%lld\n", ans);
return 0;
}E，签到题
题意
表面上说是签到题，还给出了一大段代码，只要我们补充，仔细一看，这是线段树哒。题意大概就是给出N个区间，然后算出N个区间覆盖的总范围。解析
线段树哒，线段树我不会哒，那么不会我们就不做了吗，不，我们仔细看下这个题目，这个题目并不难，不用线段树也能做，在题目给出的代码上进行略微的修改，我们采取用模拟的方式同样也能过，如果我学会了线段树我还记得这个题目的话我会回来补充线段树的做法。代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;
int a[maxn];
int opt, x, y;
set<pair<int, int> >P;
int main(){
int n, L;
cin >> n >> L;
int ans = 0;
while (n--){
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;
}
