荒废好久了。。。。 $wa$ $wa$ $wa$

与很久之前打过的一场 $cf$ 题目类似 Codeforces Round 829 (Div. 2)D. Factorial Divisibility

对于 $x >= k$， 则 $x!$ 一定可以被 $k!$ 整除，因为 $x!$ 展开为$k! * (k + 1) * (k + 2) * …… * x$。

反之， $x < k$， $x!$ 就不能被 $k!$ 整除。

题目要求 $k$ 尽可能大， 那么应该尽可能消掉比 $k$ 小的 $x$，消去的方法就是凑阶乘。

例如， $4$ 个 $3!$ 之和等于 $3! * 4$ = $4!$.

从 $1$ 开始凑， 如果发现 $i$ 在凑的过程中留有余数，就除不尽了，最大数就是 $i!$ 。

题目元素个数不会超过 $1e5$， 所以最大可以被凑出来的阶乘是 $100000!$。

若所有数都大于 $1e5$， 能整除的就只能是其中最小的数。

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

using namespace std;

const int N = 1e5 + 10;

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

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) {
        scanf("%d", &a[i]);
        if (a[i] <= 1e5) s[a[i]] ++ ;
    }

    for (int i = 1; i <= 1e5; i ++ ) {
        if (s[i] % (i + 1)) {
            printf("%d\n", i);
            return 0;
        }
        s[i + 1] += s[i] / (i + 1);
    }

    int ans = 1e9;
    for (int i = 1; i <= n; i ++ ) ans = min(ans, a[i]);

    printf("%d\n", ans);

    return 0;
}

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

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];
int f[N], g[10];

string _to_string(int x) {
    string res = "";
    while (x) res = char(x % 10 + '0') + res, x /= 10;
    return res;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    int res = 0;
    for (int i = 1; i <= n; i ++ ) {
        string t = _to_string(a[i]);
        int head = t[0] - '0', tail = t[t.size() - 1] - '0';
        f[i] = 1;
        f[i] = max(f[i], g[head] + 1);
        g[tail] = max(g[tail], f[i]);
        res = max(res, f[i]);
    }

    cout << n - res;

    return 0;
}

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

using namespace std;

const int N = 500010;

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

int main() {
    cin >> k >> s + 1 >> a >> b;

    n = strlen(s + 1);
    long long ans = 0;
    int cnt = 0;
    for (int i = k; i <= n; i ++ ) {
        if (s[i - k + 1] == a) cnt ++ ;
        if (s[i] == b) ans += cnt;
    }

    cout << ans;

    return 0;
}

预处理前缀异或和， 再按位拆分。

则求区间 $[i, j]$ 的异或和为 $s_j$ ^ $s_{i - 1}$

枚举所有区间的右端点，若右端点的第 $j$ 位是 $1$, 则该数会与前面每个第 $j$ 位是 $0$ 的左端点 异或后 第 $j$ 位仍然是 $1$, 就会产生 $2^j$ 的贡献。

反之 右端点的第 $j$ 位是 $0$ 同理

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

using namespace std;

typedef long long i64;

const int N = 1e5 + 10;

int n;
int s[N];
int cnt[30][2];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);
    for (int i = 1; i <= n; i ++ ) s[i] ^= s[i - 1];

    for (int i = 0; i < 30; i ++ ) cnt[i][0] = 1;

    i64 ans = 0;
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 0; j < 30; j ++ ) {
            int v = s[i] >> j & 1;
            ans += cnt[j][v ^ 1] * (1ll << j);
            cnt[j][v] ++ ;
        }
    } 

    printf("%lld\n", ans);

    return 0;
}

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

using namespace std;

const int N = 1e6 + 10;

int n;
char s[N], t[N];

void solve() {
    scanf("%s%s", t + 1, s + 1);
    n = strlen(s + 1);

    int ans = 0;
    for (int i = 2; i < n; i ++ ) 
        if (s[i] != t[i] && s[i - 1] == s[i + 1] && s[i - 1] != s[i]) 
            ans ++ , s[i] ^= 1;

    if (strcmp(s + 1, t + 1)) ans = -1;
    printf("%d\n", ans);
}

int main() {
    int _; scanf("%d", &_);
    while (_ -- ) solve();
    return 0;
}

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

using namespace std;

const int N = 1e6 + 10;

char str[N];
bool st[N];

int main() {
    cin >> str + 1;
    int ans = 0;
    for (int i = 2; str[i]; i ++ ) {
        if (st[i - 1]) continue;
        if ((str[i] == str[i - 1]) || (str[i] == '?') || (str[i - 1] == '?')) {
            ans ++ ;
            st[i] = true;
        }
    }

    cout << ans;

    return 0;
}

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

using namespace std;

typedef long long i64;

const int N = 1510, M = 1210, MOD = 1e9 + 7;

int n, m;
char str[N], nums[M];
int tr[N][10], idx;
bool dar[N];
int q[N], ne[N];
int f[M][N];

void insert() {
    cin >> str;
    int p = 0;
    for (int i = 0; str[i]; i ++ ) {
        int v = str[i] - '0';
        if (!tr[p][v]) tr[p][v] = ++ idx;
        p = tr[p][v];
    }
    dar[p] = true;
}

void build() {
    int hh = 0, tt = -1;
    for (int i = 0; i <= 9; i ++ ) 
        if (tr[0][i]) q[ ++ tt] = tr[0][i];

    while (hh <= tt) {
        int t = q[hh ++ ];
        for (int i = 0; i <= 9; i ++ ) {
            int &p = tr[t][i];
            if (!p) p = tr[ne[t]][i];
            else {
                ne[p] = tr[ne[t]][i];
                dar[p] |= dar[ne[p]];
                q[ ++ tt] = p;
            }
        }
    }
}

i64 dfs(int pos, int u, int lead, int limit) {
    if (!pos || dar[u]) return !dar[u];
    if (!limit && !lead && ~f[pos][u]) return f[pos][u];
    int up = limit ? nums[pos] - '0' : 9; i64 res = 0;
    for (int i = 0; i <= up; i ++ ) 
        res = (res + dfs(pos - 1, (lead && !i) ? 0 : tr[u][i], lead && !i, limit && i == up)) % MOD;
    return limit ? res : (lead ? res : f[pos][u] = res);
}

int main() {
    cin >> nums + 1 >> m;
    while (m -- ) insert();
    build();
    int len = strlen(nums + 1);
    reverse(nums + 1, nums + len + 1);
    memset(f, -1, sizeof f);
    cout << dfs(len, 0, 1, 1) - 1;
    return 0;
}

数位

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

using namespace std;

typedef long long i64;

int len;
int nums[20];
i64 f[20][10];

i64 dfs(int pos, int mod, int limit) {
    if (!pos) return !!mod;
    if (!limit && ~f[pos][mod]) return f[pos][mod];
    int up = limit ? nums[pos] : 9; i64 res = 0;
    for (int i = 0; i <= up; i ++ ) 
        if (i != 9) res += dfs(pos - 1, (mod + i) % 9, limit && i == up);
    return limit ? res : f[pos][mod] = res;
}

i64 calc(i64 x) {
    len = 0;
    memset(f, -1, sizeof f);
    while (x) nums[ ++ len] = x % 10, x /= 10;
    return dfs(len, 0, 1);
}

void solve(int C) {
    i64 l, r;
    scanf("%lld%lld", &l, &r);
    printf("Case #%d: %lld\n", C, calc(r) - calc(l - 1));
}

int main() {
    int _, C = 0; scanf("%d", &_);
    while (_ -- ) solve( ++ C);
    return 0;
}

最小值是最快变成 $0$ 的，如果第一个元素是最小值则先手必败，否则后手必败

若第一个元素是最小值且不是 $0$ (是 $0$ 直接输了，没必要讨论)：

• 则先手 $Alice$ 减 $1$ 后，不管与谁交换值，交换后都比之前大， 由于第一个元素不是 $0$ , 所以交换后轮到 $Bob$ 也必然不是 $0$。而 $Bob$ 只需要做一件事，不断将最小值扔回给 $Alice$ ， 则 $Alice$ 必然最先达到 $0$， 必败。

若第一个元素不是最小值

• 则 $Alice$ 在减 $1$ 后， 直接选择最小值扔给 $Bob$，转变为 $Bob$ 先手拿到最小值，则转变上面那种情况，必败。

#include <cstring>
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

void solve() {
    scanf("%d", &n);
    int minv = 2e9;
    for (int i = 1; i <= n; i ++ ) {
        scanf("%d", &a[i]);
        if (a[i] < minv) minv = a[i];
    }
    puts(a[1] == minv ? "Bob" : "Alice");
}

int main() {
    int _; scanf("%d", &_);
    while (_ -- ) solve();
    return 0;
}

树上二分

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

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];
int tr[N], ans[N];

int add(int x, int v) {
    for (; x <= n; x += x & -x) tr[x] += v;
}

int query(int x) {
    int res = 0;
    for (; x; x -= x & -x) res += tr[x];
    return res;
}

int kth(int l, int r, int k) {
    if (l == r) return r;
    int mid = l + r >> 1;
    int cnt = query(mid) - query(l - 1);
    if (cnt >= k) return kth(l, mid, k);
    return kth(mid + 1, r, k - cnt);
}

int main() {
    cin >> n;
    for (int i = 2; i <= n; i ++ ) cin >> a[i];

    for (int i = 1; i <= n; i ++ ) add(i, 1);

    for (int i = n; i > 1; i -- ) {
        a[i] ++ ;
        ans[i] = kth(1, n, a[i]);
        add(ans[i], -1);
    }

    ans[1] = kth(1, n, 1);

    for (int i = 1; i <= n; i ++ ) cout << ans[i] << endl;

    return 0;
}