250810 模拟赛

T1 石子游戏

好像有一些更强的性质，\(f(n)\) 直接从 \(f(\lfloor \frac nk\rfloor)\) 转移即可。

T2 乘法计数

查询区间 \([1,n]\) 内所有整数的数位乘积共有多少种不同的取值。

\(n\le 10^{18},\ T\le 5\)

注意到由于是前缀查询，因此对每个乘积只需考虑最小的一个数字即可。由此我们有两种做法：第一种是枚举质因子的次数，然后贪心得到最小值；第二种是直接钦定数位单调不降，然后离线扫询问即可。

T4 环形工厂

先贴个 std。

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <tuple>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#define ll long long
#define pa pair<ll,ll>
#define fi first
#define se second
#define int ll
using namespace std;

const int N = 10004;

int L, n, m;
int st[N], ps[N];
char dr[N];
int du[N];
bool vis[N], occ[N];
int tp[N];
int ans_tp[N], ans_tm[N];

priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> ev;

inline int dist(int x, int y) {
    return (y - x + L) % L;
}

inline int rev_id(int x) {
    if (x > m) return x - m;
    return x + m;
}

inline int ori_id(int x) {
    if (x > m) return x - m;
    return x;
}

void add_ev(tuple<int,int,int> e) {
    ev.push(e);
}

struct Tracker {
    multiset<pa> car;
    multiset<pa> fac;

    void add_car(int i, int t) {
        int r = (ps[i] - t % L + L) % L;
        auto it = fac.lower_bound({ps[i], -1e6});
        if (it == fac.end()) it = fac.begin();
        if (it != fac.end()) {
            int tm = t + dist(ps[i], (*it).fi);
            add_ev({tm, i, (*it).se});
        }
        car.insert({r, -i});
    }

    void add_fac(int i, int t, int ins = 0) {
        auto it = car.lower_bound({(tp[i] - t % L + L) % L + 1, -1e6});
        if (!car.empty()) {
            if (it == car.begin()) it = car.end();
            --it;
            if (it != car.end()) {
                int cp = ((it->fi + t) % L);
                int tm = t + dist(cp, tp[i]);
                add_ev({tm, -it->se, i});
            }
        }
        if (ins) fac.insert({tp[i], i});
    }

    void rem_fac(int i, int t) {
        fac.erase({tp[i], i});
        auto it = fac.lower_bound({tp[i], i});
        if (it == fac.end()) it = fac.begin();
        if (it != fac.end()) {
            add_fac(it->se, t);
        }
    }

    void car_arr(int i, int j, int t) {
        car.erase({(tp[j] - t % L + L) % L, -i});
        fac.erase({tp[j], j});
        auto it = fac.lower_bound({tp[j], j});
        if (it == fac.end()) it = fac.begin();
        if (it != fac.end()) {
            add_fac(it->se, t);
        }
        add_ev({t + du[i], -1, ori_id(j)});
    }
};

Tracker cw, ccw;

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    freopen("factory.in", "r", stdin);
    freopen("factory.out", "w", stdout);

    cin >> n >> m >> L;

    for (int i = 1; i <= m; i++) {
        cin >> tp[i];
        add_ev({0, -1, i});
        tp[m + i] = (L - tp[i]) % L;
    }

    for (int i = 1; i <= n; i++) {
        cin >> st[i] >> ps[i] >> dr[i] >> du[i];
        add_ev({st[i], i, -1});
        if (dr[i] == '-') {
            ps[i] = (L - ps[i]) % L;
        }
    }

    while (!ev.empty()) {
        auto [t, i, j] = ev.top(); ev.pop();

        if (j == -1) {
            if (dr[i] == '+') cw.add_car(i, t);
            else ccw.add_car(i, t);
            continue;
        }

        if (i == -1) {
            occ[j] = false;
            cw.add_fac(j, t, 1);
            ccw.add_fac(j + m, t, 1);
            continue;
        }

        int j0 = j;
        if (j0 > m) j0 -= m;

        if (vis[i] || occ[j0]) continue;

        ans_tp[i] = tp[j0];
        ans_tm[i] = t;
        vis[i] = true;
        occ[j0] = true;

        if (dr[i] == '+') {
            cw.car_arr(i, j, t);
            ccw.rem_fac(rev_id(j), t);
        } else {
            ccw.car_arr(i, j, t);
            cw.rem_fac(rev_id(j), t);
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans_tp[i] << " " << ans_tm[i] << '\n';
    }

    return 0;
}