最大公约数模板题

#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int n;
    cin >> n;

    while (n -- )
    {
        int a, b;
        cin >> a >> b;
        cout << gcd(a, b) << endl;
    }

    return 0;
}

约数之和模板题

#include <iostream>
#include <algorithm>
#include <unordered_map> 
#include <vector>

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, x;

    unordered_map<int, int> primes;

    cin >> n;

    while (n -- )
    {
        cin >> x;

        for (int i = 2; i <= x / i; i ++ )
        {
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }
        }

        if (x > 1) primes[x] ++ ;
    }

    LL res = 1;

    for (auto prime : primes)
    {
        int p = prime.first, a = prime.second;
        LL t = 1;

        while (a -- ) t = (t * p + 1) % mod;

        res = res * t % mod;
    }

    cout << res << endl;

    return 0;
}

约数个数模板题

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 110, mod = 1e9 + 7;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    unordered_map<int, int> primes;

    int n, x;
    cin >> n;

    while (n -- )
    {
        cin >> x;

        for (int i = 2; i <= x / i; i ++ )
        {
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }
        }

        if (x > 1) primes[x] ++ ;
    }

    LL res = 1;

    for (auto t : primes)
        res = res * (t.second + 1) % mod;

    cout << res << endl;

    return 0;
}

试除法求约数模板题

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> get_divisors(int n)
{
    vector<int> res;

    for (int i = 1; i <= n / i; i ++ )
    {
        if (n % i == 0)
        {
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }
    }

    sort(res.begin(), res.end());

    return res;
}

int main()
{

    int n;
    cin >> n;

    while (n -- )
    {
        int a;
        cin >> a;

        auto res = get_divisors(a);

        for (auto t : res)  cout << t << ' ';

        cout << endl;
    }

    return 0;
}

1.Searching Local Mininum

推荐博客

题目类型

神奇二分 + 递增递减的数学知识 这是一道交互型题目 感觉挺有趣的

题目大意

• 有n个数字，数字范围为1~n且不重复。
• 有数字流传输过来，你预先不知道其位置，但是你可以在接收数字之前给其定下位置。
• 问：你能否在确定小于等于100个数字位置之前找到一个数字，这个数字 idx 满足 a[idx] 为波谷位置

题目思路

数据范围大 肯定不能暴力 用二分来找
如果 [l, n] 左边递减右边递增 那么在 [l, n] 一定存在波谷
因为a[0] 和 a[n] 为正无穷 故二分找 a[mid] 使得 a[mid] < a[mid - 1] && a[mid] < a[mid + 1]

代码实现

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

void get(int x)
{
    if (x < 1 || x > n || a[x]) return;
    cout << "? " << x << endl;
    fflush(stdout);
    cin >> a[x]; 
}

signed main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    cin >> n;

    a[0] = a[n + 1] = N;

    int l = 1, r = n;

    while (l < r)
    {
        int mid = l + r >> 1;
        get(mid), get(mid + 1);
        if (a[mid] < a[mid + 1]) r = mid;
        else l = mid + 1;
    }

    cout << "! " << r << endl;

    return 0;
} 

2.滑雪与时间胶囊

题目类型

最小生成树 + 图的遍历

题目思路

因为只能由高到低 所以需要遍历出从1能到达那些点 不能盲目的进行Kruskal()
要先用dfs把从1能到的点筛选出来, 加边的时候不要else if 因为当H[a] == H[b]的时候, 是双向边
然后用Kruskal算法求解

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10, M = 3e6 + 10;

int e[M], ne[M], h[N], idx;
int p[N], H[N];
int n, m; 
LL cnt, res;
bool vis[N];

struct Edge
{
    int u, v, w;
    bool operator < (const Edge &W)const
    {
        if (H[v] != H[W.v]) return H[v] > H[W.v];
        return w < W.w;
    }
}edge[M];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int find(int a)
{
    if (p[a] != a) p[a] = find(p[a]);
    return p[a];
}

void dfs(int nu)
{
    vis[nu] = 1;
    cnt ++;
    for (int i = h[nu]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (vis[j]) continue;
        dfs(j);
    }
}

void Kruskal()
{
    sort(edge, edge + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    for (int i = 0; i < m; i ++ )
    {
        auto e = edge[i];

        if (!vis[e.u] || !vis[e.v]) continue;

        int pu = find(e.u), pv = find(e.v);

        if (pu != pv)
        {
            p[pu] = pv;
            res += (LL)e.w;
        }
    }
}

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    memset(h, -1, sizeof h);

    cin >> n >> m;

    for (int i = 1; i <= n; i ++ ) cin >> H[i];

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (H[a] >= H[b]) edge[i] = {a, b, c}, add(a, b);
        if (H[a] <= H[b]) edge[i] = {b, a, c}, add(b, a);
    }

    dfs(1);

    Kruskal();

    cout << cnt << ' ' << res << endl;

    return 0;
}

3.Painting the Array I

推荐博客

题目类型

贪心 + 二分查找

题目思路

• 当 p == q 时 a[i] 加到哪都行
• 当 p == a[i] q != a[i] 时 要加在a2 中 同理知 p != a[i] q == a[i] 时 加在 a1 中
• 当都不相同时候 要找一下 我们可以求出p和q在a[i]之后出现的离i最近的位置f[p][pp]和f[q][qq]，如果f[p][pp]<f[q][qq]，那么就将a[i]放入a1中，否则放入a2中。
  这里只需要举一个简单的小例子：
  假设p=1，q=2，a中还有[3,2,2,1]这三个元素，如果将3放入a1中，那么答案只能再加3。但是如果将3放入a2中，答案可以再加4。

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int a[N], n, num[N];
vector<int> f[N];

int main()
{
    cin.tie(0); cout.tie(0);
    ios::sync_with_stdio(false);

    int res = 0;

    cin >> n;

    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        f[a[i]].push_back(i);
    }

    int p = 0, q = 0;

    for (int i = 1; i <= n; i ++ )
    {   
        if (p == a[i] && q == a[i]) continue;

        else if (p != a[i] && q == a[i])
        {
            p = a[i];
            res ++ ;
        }

        else if (p == a[i] && q != a[i])
        {
            q = a[i];
            res ++ ;
        }

        else
        {
            int pp = lower_bound(f[p].begin(), f[p].end(), i) - f[p].begin();
            int qq = lower_bound(f[q].begin(), f[q].end(), i) - f[q].begin();

            if (pp >= f[p].size()) q = a[i];
            else if (qq >= f[q].size()) p = a[i];
            else if (f[p][pp] > f[q][qq]) q = a[i];
            else p = a[i];

            res ++ ;
        }
    }

    cout << res << endl;

    return 0;
} 

筛质数模板题

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, cnt;
int prime[N];
bool st[N];

// 埃式筛法
void get_prime1()
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            prime[cnt ++ ] = i;
            for (int j = i + i; j <= n; j += i) st[j] = true;
        }
    }
}

// 欧拉筛法
void get_prime2()
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) prime[cnt ++ ] = i;
        for (int j = 0; prime[j] <= n / i; j ++ )
        {
            st[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
            // 欧拉筛核心是筛掉最小质因数 j后面的 prime[m] * i 变成了 prime[m] * k * prime[j] 
            // prime[j] 才是最小质因数 故要break 
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n;

    get_prime2();

    cout << cnt << endl;

    return 0;
}

分解质因数模板题

#include <bits/stdc++.h>

#define int long long
#define endl '\n'

using namespace std;

int a, n;

void divide(int u)
{
    for (int i = 2; i <= u / i; i ++ )
    {
        if (u % i == 0)
        {
            int s = 0;
            while (u % i == 0)
            {
                s ++ ;
                u /= i;
            }

            cout << i << ' ' << s << endl;
        }
    }

    if (u > 1) cout << u << ' ' << 1 << endl;

    cout << endl;
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> n;

    while (n -- )
    {
        cin >> a;
        divide(a);
    }

    return 0;
}

试除法判断质数

#include <iostream>

using namespace std;

int n;

bool is_Prime(int x)
{
    if (x < 2) return false;

    for (int i = 2; i <= x / i; i ++ )
    {
        if (x % i == 0) return false;
    }
    return true;
}

int main()
{
    cin >> n;

    while (n -- )
    {
        int a;
        cin >> a;
        if (is_Prime(a)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

匈牙利算法模板题

#include <bits/stdc++.h>

using namespace std;

const int N = 510, M = 1e5 + 10;

int h[N], ne[M], e[M], idx;
int n1, n2, m, res;
int match[N];
bool st[N];

void add(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx ++ ;
}

bool find(int u)
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];

        if (!st[j])
        {
            st[j] = true;

            if (!match[j] || find(match[j]))
            {
                match[j] = u;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    memset(h, -1, sizeof h);

    cin >> n1 >> n2 >> m;

    while (m -- )
    {
        int u, v;
        cin >> u >> v;
        add(u, v);
    }

    for (int i = 1; i <= n1; i ++ )
    {
        memset(st, false, sizeof st);
        if (find(i)) res ++ ;
    }

    cout << res << endl;

    return 0;
}

染色法模板题

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 2e5 + 10;

int h[N], ne[M], e[M], idx;
int color[N]; // color数组中只有 0 1 2 三个数字
int n, m;

void add(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx ++ ;
}

bool dfs(int u, int c) // 染色
{
    color[u] = c;

    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];

        if (!color[j])
            if (!dfs(j, 3 - c)) return false;
        if (color[j] == c) return false;
    }
    return true;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    memset(h, -1, sizeof h);

    cin >> n >> m;

    while (m -- )
    {
        int u, v;
        cin >> u >> v;
        add(u, v), add(v, u);
    }

    bool flag = true;
    for (int i = 1; i <= n; i ++ )
    {
        if (!color[i])
        {
            if (!dfs(i, 1))
            {
                flag = false;
                break;
            }
        }
    }

    if (!flag) cout << "No" << endl;
    else cout << "Yes" << endl;

    return 0;
}