直接写个合集吧, 单独写可能300字都不够(迫真

A. 青蛙过河

题目太长了, 去看了下别人解释的题意
简单来说就是在石墩上青蛙可以类似Hanoi问题(汉诺塔)地叠着
我们想叠得越多越好，显然我们既然有办法把它叠起来，用叠的逆过程就可以把它们全部合法的放到河对岸

• , 每个荷叶一只青蛙，一只青蛙直接跳到对岸，有 只
• , 在石墩上放 只青蛙, 问题被分解为

于是很容易得到每多一个石墩, 都可以把原来 个石墩的青蛙转移到上面来, 数量翻倍
得到答案

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll mod = 1e9 + 7;
const int N = 2e5 + 5;

int main() {
  ll n, m;
  cin >> n >> m;
  cout << (m + 1) * (1LL << n) << "\n";
  return 0;
}

B. 华华对月月的忠诚

Solution

直接手推几项,
不难看出 , 我们要求
因为 与 , 与 互为斐波那契数列的相邻两项, 显然互质
所以, 前面的系数 不用看, 显然答案为

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  ll a, b;
  string s;
  cin >> a >> b >> s;
  cout << __gcd(a, b) << "\n";
  return 0;
}

C. Game

Solution

对 进行质因数分解, 判断质因子奇偶性即可

Code

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef unsigned long long ll;
static auto faster_iostream = []() {
    std::ios::sync_with_stdio(false);  // turn off sync
    std::cin.tie(nullptr);             // untie in/out streams
    return 0;
}();
const int N = 2e5 + 5;
const int mod = 20010905;
int main(){
    int n;
    while(cin >> n){
        int flag = 0;
        int cnt = 0;
        for(int i = 2; i * i <= n; i++){
            if(n % i == 0){
                flag = 1;
                while(n % i == 0){
                    n /= i;
                    cnt++;
                }
            }
        }
        if(n > 1){
            cnt++;
        }
        //cout << cnt << endl;
        if(!flag){
            cout << "Nancy" << endl;
        }
        else if((cnt - 1) % 2 == 1){
            cout << "Johnson" << endl;
        }
        else cout << "Nancy" << endl;
    }
}

D. 挖沟

Solution

读题的时候注意一些关键字
由于需要在任意两个点之间传递信息，两个坑之间必须挖出至少一条通路, 希望挖出数量尽可能少的沟，使得任意两个据点之间有至少一条通路
显然就是求一个无向图最小生成树

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;

struct Edge {
  int u, v;
  ll w;
  bool operator < (const Edge &s) const {
    return w < s.w;
  }
}edge[N << 1];

int F[N], tot;
int findz(int x) {
  return F[x] = F[x] == x ? x : findz(F[x]);
}
void Union(int x, int y) {
  int fx = findz(x), fy = findz(y);
  if(fx != fy) {
    F[fx] = fy;
  }
}
ll Kruscal(int n) {
  ll ans = 0;
  for(int i = 1; i <= n; i++) F[i] = i;
  sort(edge, edge + tot);
  for(int i = 0; i < tot; i++) {
    int u = edge[i].u, v = edge[i].v;
    if(findz(u) != findz(v)) {
      Union(u, v);
      ans += edge[i].w;
    }
  }
  return ans;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int u, v;
    ll w;
    cin >> u >> v >> w;
    edge[tot].u = u, edge[tot].v = v, edge[tot].w = w;
    tot++;
  }
  cout << Kruscal(n) << "\n";
  return 0;
}

E. 签到题

Solution

看了题意后感觉是个珂朵莉树裸题(就是那个 序列操作)
然后就抄了个模板叫上去(区间赋 , 区间赋 )
最后查询区间 里面 的个数
然后 了, 不知道是什么原因(我题目理解错了
然后看了下大家的题解, 暴力就能做了
感觉还有线段树的做法, 但是好像跟珂朵莉树一样 了(那就写暴力吧)
update
我懂了, 不是区间赋值为 , 而是区间加(线段树搞搞就行)

Code1

#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 vis[MAXN];
int main(){
     scanf("%d%d",&N,&maxL);
     int res=0;
     while(N--){
         int opt,x,y;
         scanf("%d%d%d",&opt,&x,&y);++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){
                 ++vis[i];
                 res+=(vis[i]==1);
             }
         }
         if(opt == 2){
             if(L.find(MP(x,y)) == L.end()) continue;
             L.erase(MP(x,y));
             for(int i=x;i<=y;++i){
                 --vis[i];
                 res-=(vis[i]==0);
             }
         }
         if(opt == 3){
             printf("%d\n",res);
         }
     }
     return 0;
}

Code2(线段树)

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 1e6 + 5;
std::set < pair<int, int> > L;

struct node {
  int l, r;
  ll val;
  ll ans;
}t[N << 2];

void push_up(int rt) {
  if(t[rt].val) {
    t[rt].ans = t[rt].r - t[rt].l + 1;
  } else if(t[rt].l != t[rt].r) {
    t[rt].ans = t[rt << 1].ans + t[rt << 1 | 1].ans;
  } else {
    t[rt].ans = 0;
  }
}
void build(int rt, int l, int r) {
  t[rt].l = l, t[rt].r = r;
  if(l == r) {
    return ;
  }
  int mid = l + r >> 1;
  build(rt << 1, l, mid);
  build(rt << 1 | 1, mid + 1, r);
}
void update(int rt, int ql, int qr, int x) {
  if(t[rt].l >= ql && t[rt].r <= qr) {
    t[rt].val += x;
    push_up(rt);
    return ;
  }
  int mid = t[rt].l + t[rt].r >> 1;
  if(qr <= mid) {
    update(rt << 1, ql, qr, x);
  }
  else if(ql > mid) {
    update(rt << 1 | 1, ql, qr, x);
  }
  else {
    update(rt << 1, ql, mid, x);
    update(rt << 1 | 1, mid + 1, qr, x);
  }
  push_up(rt);
}
int main() {
  //ios::sync_with_stdio(false), cin.tie(nullptr);
  int m, n;
  cin >> m >> n;
  build(1, 1, n);
  while(m--) {  
    int op, l, r;
    cin >> op >> l >> r;
    if(op == 1) {
      if(L.find({l, r}) != L.end()) continue;
      L.insert({l, r});
      update(1, l, r, 1);
    }
    else if(op == 2) {
      if(L.find({l, r}) == L.end()) continue;
      L.erase({l, r});
      update(1, l, r, -1);
    }
    else {
      push_up(1);
      cout << t[1].ans << "\n";
    }
  }
}