杂项模版

模拟退火：

// SA算法伪代码：
// T：当前剩余时间
// T_min：日落时分，因为乘法永远无法使得T变为0，所以需要一个极小的数来代替0
// r：时间流逝速率
// dE：高度差
// now：当前所处位置
// next：随机选取的位置
// H(a)：a处的高度
// ans：当前最优解
//  while(T>T_min)
//  {
//      next=randow();//随机选取一个位置
//      dE=H(now)-H(next);//求取高度差
//      if(dE<0) now=next;//如果更高，直接前往
//      else
//      {
//          if(exp(-dE/T)>random(0,1)) now=next;
//      }//否则看概率
//      ans=max(ans,H(now));
//      T*=r;//时间流逝
//  }

#include <iostream>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <stdio.h>
using namespace std;
const int maxn = 1e3 + 10;
struct node
{
    double x, y;
} p[maxn];
int n;
double ans;
double sumx, sumy;
double mx, my;
double dis(double x, double y)
{
    double ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += sqrt((x - p[i].x) * (x - p[i].x) + (y - p[i].y) * (y - p[i].y));
    }
    return ans;
}
void SA()
{
    double nowx = mx, nowy = my;
    double T = 100000;
    double T_min = 1e-12;
    double r = 0.996;
    while (T > T_min)
    {
        for (int i = -1; i <= 1; i++)
        {
            for (int j = -1; j <= 1; j++)
            {
                double nextx = nowx + i * T;
                double nexty = nowy + j * T;
                double nextans = dis(nextx, nexty);
                double delta = nextans - ans;
                if (delta < 0)
                {
                    ans = nextans;
                    nowx = nextx;
                    nowy = nexty;
                    mx = nextx;
                    my = nexty;
                }
                else if (exp(delta / T) * RAND_MAX > rand())
                 {
                     nowx = nextx;
                     nowy = nexty;
                 }
            }
        }
        T *= r;
    }
}
void solve()
{
    ans = dis(mx, my);
    // cout << (double)clock() / CLOCKS_PER_SEC << endl;
    // while ((double)clock() / CLOCKS_PER_SEC < 0.8)
    //     SA();
    SA();
    SA();
}
signed main()
{
    srand(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].x >> p[i].y;
        sumx += p[i].x;
        sumy += p[i].y;
    }
    mx = sumx / n;
    my = sumy / n;
    solve();
    printf("%.0lf\n", ans);
    return 0;
}

莫队：

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;
#define int long long
const int maxn = 3e4 + 10;
int sq;
struct query
{
    int l, r, id;
    bool operator<(const query &other) const
    {
        if (l / sq != other.l / sq)
            return l < other.l;
        if (l / sq & 1)
            return r < other.r;
        return r > other.r;
    }
} q[maxn * 10];
int a[maxn], ans[maxn * 10], cnt[maxn * 100];
int l = 1, r = 0;
int cur = 0;
void add(int p)
{
    if (cnt[a[p]] == 0)
    {
        cur++;
    }
    cnt[a[p]]++;
}
void del(int p)
{
    cnt[a[p]]--;
    if (cnt[a[p]] == 0)
    {
        cur--;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    sq = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++)
    {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q, q + Q);
    for (int i = 0; i < Q; i++)
    {
        while (l > q[i].l)
            add(--l);
        while (r < q[i].r)
            add(++r);
        while (l < q[i].l)
            del(l++);
        while (r > q[i].r)
            del(r--);
        ans[q[i].id] = cur;
    }
    for (int i = 0; i < Q; i++)
    {
        cout << ans[i] << endl;
    }
    return 0;
}

最小最大（二分）：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int n, c;
bool judge(int d)
{
    int last = 1, k = 1;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] - a[last] >= d)
        {
            k++;
            last = i;
        }
    }
    if (k >= c)
        return true;
    else
        return false;
}
int main()
{
    cin >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    int left = 0;
    int right = a[n];
    int mid = left + (right - left) / 2;
    while (left <= right)
    {
        if (judge(mid))
        {
            left = mid + 1;
        }
        else
            right = mid - 1;
        mid = left + (right - left) / 2;
    }
    cout << right << endl;
    return 0;
}

波利亚计数：

#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
using namespace std;
#define ll long long
ll qp(ll a, ll x, ll mod)
{
    ll ans = 1;
    while (x)
    {
        if (x & 1)
        {
            ans = (ans * a) % mod;
        }
        a = (a * a) % mod;
        x >>= 1;
    }
    return ans;
}
int euler_phi(int n)
{
    int ans = n;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0)
        {
            ans = ans / i * (i - 1);
            while (n % i == 0)
                n /= i;
        }
    if (n > 1)
        ans = ans / n * (n - 1);
    return ans;
}

signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, mod;
        cin >> n >> mod;
        int ans = 0;
        if (n == 0)
        {
            cout << 0 << endl;
            continue;
        }
        for (int i = 1; i * i <= n; i++)
        {
            if (n % i == 0)
            {
                if (i * i != n)
                    ans = (ans + (euler_phi(n / i) % mod * qp(n, i - 1, mod)) % mod + euler_phi(i) % mod * qp(n, n / i - 1, mod) % mod) % mod;
                else
                    ans = (ans + (euler_phi(n / i) % mod * qp(n, i - 1, mod)) % mod) % mod;
            }
        }
        cout << ans << endl;
    }
    return 0;
}