A 等差数列

给出两个等差数列 \(a,b\)，求区间 \([l,r]\) 中同时出现在两个等差数列的数的个数。

\(a_1,b_1\le 100, r\le 10^{18}\)。

数论。

设 \(a,b\) 的等差数列公差 \(d_1,d_2\)，每 \(\operatorname{lcm}(d_1,d_2)\) 就会出现一个符合条件的数，这个循环长度只有 \(10^4\) 级别，暴力找即可。

然后 \([1,n]\) 的答案就是最小的符合条件的数到 \(n\) 之间的循环机个数，上取整。

最后答案差分一下。

const int N = 1e5 + 9;

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

LL a, aa, d1, b, bb, d2, l, r, fir, cc;
LL sum[N];

LL solve(LL n) {
    if (n < fir) return 0;
    return (LL)ceil((double)(n - fir + 1) / (double)cc);
}

inline void main() {
    read(a), read(aa), read(b), read(bb), read(l), read(r);
    if (a < b) swap(a, b), swap(aa, bb);
    d1 = aa - a, d2 = bb - b;
    for (int i = a; i <= 1e5; ++i) {
        if ((i - a) % d1 == 0 && (i - b) % d2 == 0) {
            if (!fir) fir = i;
            else {
                cc = i - fir;
                break;
            }
        }
    }
    printf("%lld\n", solve(r) - solve(l-1));
}

B 玩具

\(n\le 10^6\)。

模拟题题目好长就不概括了。

就是类似队列的思想预处理每个点到其之前 \(L\) 个可行位置的长度，贪心地跳即可。

const int N = 3e6 + 9;

int n, B, L;
LL ans;
LL g[N];
char str[N];

inline bool check() {
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (i > B) sum -= str[i - B] == '1';
        sum += str[i] == '1';
        if (i >= B && sum < L) return false;
    }
    return true;
}

inline void main() {
    read(L), read(B), read(n);
    scanf("%s", str+1);
    if (!check()) return puts("IMPOSSIBLE"), void();

    int l = 1, r = L;
    g[L] = 1;
    for (int i = L + 1; i <= n; ++i) {
        if (str[i] == '1') {
            r = i, l++;
            while (str[l] == '0') l++;
        }
        g[i] = l;
    }
    l = L, r = B;
    while (r < n) {
        ans += L;
        l = r, r = g[r] + B - 1;
    }
    if (l < n) ans += L;
    printf("%lld\n", ans + n - B);
}

C 整除

给定 \(k,m\)，求一个最小的能被 \(m\) 整除的 \(n\)，保证 \(n\) 的每一位数字都属于 \([0,k)\)。

\(k\le 10,m\le 10^6\)。

图论。

设 \(f_i\) 表示 \(n \bmod m = i\) 的最小的 \(n\)，\(f_i\) 可以向 \(f_i\times10+j\quad(j\in[0,k))\) 连边。

对每个点的出边从小到大 bfs，即可保证答案最小。

\(f_i\) 存不下，只存最低位的前驱点即可，最后从 \(0\) 点往回倒推。

const int N = 1e6 + 5;

int K, m;
int dis[N], ans[N], pre[N], q[N];
vector<int> e[N];
vector<char> output;

inline void main() {
    read(K), read(m);
    for (int u = 0; u < m; ++u) {
        for (int j = 0; j < K; ++j) {
            int v = (u * 10 + j) % m;
            e[u].push_back(v);
        }
        pre[u] = -1;
    }
    memset(dis, 0x3f, sizeof dis);
    int ql = 1, qr = 0;
    for (int u = 1; u < K; ++u) {
        ans[u] = u;
        dis[u] = 0;
        q[++qr] = u;
    }
    while (ql <= qr) {
        int u = q[ql++];
        for (int i = 0; i < e[u].size(); ++i) {
            int v = e[u][i];
            if (dis[v] > dis[u] + 1) {
                ans[v] = i;
                dis[v] = dis[u] + 1;
                pre[v] = u;
                q[++qr] = v;
            }
        }
    }
    for (int u = 0; u != -1; u = pre[u]) {
        output.push_back(ans[u] + '0');
    }
    for (int i = output.size() - 1; ~i; --i)
        putchar(output[i]);
    puts("");
}

D 集合

类似 CF571D Campus。

可以看这道题的题解（没用带权并查集）。

RenaMoe's Blog

20年11月22日「启智树」模拟赛

A 等差数列

B 玩具

C 整除

D 集合