#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010, M = 1010;

int n;
int w[6][6] = {
    {1, 0, 1, 1, 0, 0},
    {0, 1, 0, 0, 1, 0},
    {0, 1, 0, 0, 1, 0},
    {0, 1, 0, 0, 1, 0},
    {1, 0, 1, 1, 0, 1},
    {0, 0, 0, 0, 1, 0},
};
int f[N][6][M];

void add(int a[], int b[])
{
    for (int i = 0, t = 0; i < M; i ++ )
    {
        t += a[i] + b[i];
        a[i] = t % 10;
        t /= 10;
    }
}

int main()
{
    cin >> n;
    f[1][1][0] = f[1][4][0] = 1;
    for (int i = 2; i < n; i ++ )
        for (int j = 0; j < 6; j ++ )
            for (int k = 0; k < 6; k ++ )
                if (w[k][j])
                    add(f[i][j], f[i - 1][k]);
    int res[M] = {0};
    add(res, f[n - 1][0]), add(res,f[n - 1][4]);
    add(res, res);

    int k = M - 1;
    while (k > 0 && !res[k]) k -- ;
    for (int i = k; i >= 0; i -- ) cout << res[i];
    cout << endl;

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 500010, M = N * 2;

int n, root;
int h[N], e[M], w[M], ne[M], idx;
LL d[N], ans;

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

void dfs(int u, int father)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        dfs(j, u);
        d[u] = max(d[u], d[j] + w[i]);
    }

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        ans += d[u] - (d[j] + w[i]);
    }
}

int main()
{
    scanf("%d%d", &n, &root);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    dfs(root, -1);
    printf("%lld\n", ans);

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 40;

int n;
int a[N][N];

int main()
{
    cin >> n;
    int x = 1, y = n / 2 + 1;
    for (int i = 1; i <= n * n; i ++ )
    {
        a[x][y] = i;
        if (x == 1 && y == n) x ++ ;
        else if (x == 1) x = n, y ++ ;
        else if (y == n) x --, y = 1;
        else if (a[x - 1][y + 1]) x ++ ;
        else x --, y ++ ;
    }

    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= n; j ++ )
            cout << a[i][j] << ' ';
        cout << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2000010;

int n;
char a[N], b[N];

int get_min(char s[])
{
    int i = 0, j = 1;
    while (i < n && j < n)
    {
        int k = 0;
        while (k < n && s[i + k] == s[j + k]) k ++ ;
        if (k == n) break;
        if (s[i + k] > s[j + k]) i += k + 1;
        else j += k + 1;
        if (i == j) j ++ ;
    }
    int k = min(i, j);
    s[k + n] = 0;
    return k;
}

int main()
{
    scanf("%s%s", a, b);
    n = strlen(a);
    memcpy(a + n, a, n);
    memcpy(b + n, b, n);

    int x = get_min(a), y = get_min(b);
    if (strcmp(a + x, b + y)) puts("No");
    else
    {
        puts("Yes");
        puts(a + x);
    }

    return 0;
}

扩展题

1. AcWing 1343. 挤牛奶

区间合并 $O(nlogn)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int m, n;
struct Segment
{
    int l, r;
    bool operator< (const Segment& t) const
    {
        return l < t.l;
    }
}seg[N];

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ ) cin >> seg[i].l >> seg[i].r;
    sort(seg, seg + n);

    int sum = 0;
    int L = seg[0].l, R = seg[0].r;
    for (int i = 1; i < n; i ++ )
        if (seg[i].l <= R) R = max(R, seg[i].r);
        else
        {
            sum += R - L + 1;
            L = seg[i].l, R = seg[i].r;
        }
    sum += R - L + 1;
    cout << m + 1 - sum << endl;

    return 0;
}

朴素算法 $O(ML)$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int L, n;
bool st[N];

int main()
{
    cin >> L >> n;
    for (int i = 0; i <= L; i ++ ) st[i] = true;
    while (n -- )
    {
        int a, b;
        cin >> a >> b;
        for (int i = a; i <= b; i ++ ) st[i] = false;
    }

    int res = 0;
    for (int i = 0; i <= L; i ++ ) res += st[i];
    cout << res << endl;

    return 0;
}

原题数据后3个点有误，现已修正。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2e7 + 10;

int n;
char a[N], b[N];
int p[N];

void init()
{
    int k = 0;
    b[k ++ ] = '$', b[k ++ ] = '#';
    for (int i = 0; i < n; i ++ ) b[k ++ ] = a[i], b[k ++ ] = '#';
    b[k ++ ] = '^';
    n = k;
}

void manacher()
{
    int mr = 0, mid;
    for (int i = 1; i < n; i ++ )
    {
        if (i < mr) p[i] = min(p[mid * 2 - i], mr - i);
        else p[i] = 1;
        while (b[i - p[i]] == b[i + p[i]]) p[i] ++ ;
        if (i + p[i] > mr)
        {
            mr = i + p[i];
            mid = i;
        }
    }
}

int main()
{
    scanf("%s", a);
    n = strlen(a);

    init();
    manacher();

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, p[i]);
    printf("%d\n", res - 1);

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 100010, M =  N * 2;

int n;
int h[N], e[M], ne[M], idx;
int color[N], cnt[N], sz[N], son[N];
LL ans[N], sum;
int mx;

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

int dfs_son(int u, int father)
{
    sz[u] = 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father) continue;
        sz[u] += dfs_son(j, u);
        if (sz[j] > sz[son[u]]) son[u] = j;
    }
    return sz[u];
}

void update(int u, int father, int sign, int pson)
{
    int c = color[u];
    cnt[c] += sign;
    if (cnt[c] > mx) mx = cnt[c], sum = c;
    else if (cnt[c] == mx) sum += c;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father || j == pson) continue;
        update(j, u, sign, pson);
    }
}

void dfs(int u, int father, int op)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father || j == son[u]) continue;
        dfs(j, u, 0);
    }

    if (son[u]) dfs(son[u], u, 1);
    update(u, father, 1, son[u]);

    ans[u] = sum;

    if (!op) update(u, father, -1, 0), sum = mx = 0;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &color[i]);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    dfs_son(1, -1);
    dfs(1, -1, 1);

    for (int i = 1; i <= n; i ++ ) printf("%lld ", ans[i]);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int h[M], e[N], ne[N], idx;
int color[N], sz[M], p[M];
int ans;

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

void merge(int& x, int& y)
{
    if (x == y) return;
    if (sz[x] > sz[y]) swap(x, y);
    for (int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        ans -= (color[j - 1] == y) + (color[j + 1] == y);
    }
    for (int i = h[x]; ~i; i = ne[i])
    {
        int j = e[i];
        color[j] = y;
        if (ne[i] == -1)
        {
            ne[i] = h[y], h[y] = h[x];
            break;
        }
    }
    h[x] = -1;
    sz[y] += sz[x], sz[x] = 0;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &color[i]);
        if (color[i] != color[i - 1]) ans ++ ;
        add(color[i], i);
    }

    for (int i = 0; i < M; i ++ ) p[i] = i;

    while (m -- )
    {
        int op;
        scanf("%d", &op);
        if (op == 2) printf("%d\n", ans);
        else
        {
            int x, y;
            scanf("%d%d", &x, &y);
            merge(p[x], p[y]);
        }
    }

    return 0;
}

考点

整数二分

扩展题

1. AcWing 789. 数的范围
2. AcWing 22. 旋转数组的最小数字，不具有单调性，但具有二段性
3. AcWing 113. 特殊排序，没有单调性，但可以二分

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 100010;

int n, m;
int h[N], w[N];

bool check(int mid)
{
    LL res = 0;
    for (int i = 0; i < n; i ++ )
    {
        res += (LL)h[i] / mid * (w[i] / mid);
        if (res >= m) return true;
    }
    return false;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &h[i], &w[i]);

    int l = 1, r = 1e5;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    printf("%d\n", r);
    return 0;
}