D - Laser Marking

问题可以转换为不同组端点之间的移动的最小代价
由于 $n$ 最大6,考虑暴力
全排列 + 二进制枚举方向

void solve(){
    cin >> n >> S >> T;
    double sr = 0;
    for (int i = 0; i < n; i ++ ){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        tr[i] = {a, b, c, d};
        double D = sqrt(1.0 * (c - a) * (c - a) + (d - b) * (d - b));
        sr += D / T;
    }
    //线段移动T, 不同线段端点间移取S
    vector<int> v(n);
    for (int i = 0; i < n; i ++ ) v[i] = i;
    double ans = 1e9;
    do{
        for (int i = 0; i < (2 << n); i ++ ){ //枚举方向
            vector<pair<int, int>> p, q; //
            p.push_back({0, 0});
            for (int j = 0; j < n; j ++ ){
                if (i >> j & 1){ //正向
                    q.push_back({tr[v[j]].a, tr[v[j]].b});
                    p.push_back({tr[v[j]].c, tr[v[j]].d});
                }else{//反向
                    p.push_back({tr[v[j]].a, tr[v[j]].b});
                    q.push_back({tr[v[j]].c, tr[v[j]].d});
                }
            }
            double res = 0;
            //p->q
            for (int j = 0; j < n; j ++ ){ 
                double D = sqrt(1.0 * (p[j].x - q[j].x) * (p[j].x - q[j].x) + (p[j].y - q[j].y) * (p[j].y - q[j].y));
                res += D / S;
            }
            ans = min(ans, res);
        }
    }while (next_permutation(v.begin(), v.end()));
    ans += sr;
    cout << fixed << setprecision(7) << ans << '\n';
}

E - Sensor Optimization Dilemma 2

看到最小值最大——经典二分
难点在于给定指标，求完成每道工序的最小代价
其中每道工序给定2种工具，各有代价和产出。
又是一个经典问题，这类问题的特征是产出的数据范围较小。

新问题如下：
道具A的代价是p,产出是a
道具B的代价是q,产出是b
问至少产出n的最小代价

做法如下：
我们可以把n缩小到 $n % (a * b)$ 的范围然后暴力
其中 $n / (a * b) * a * b$ 的产出一定有最优的 $O(1)$ 结论
设置 $t = n / (a * b)$ ，那么一定可以只有A或者B完成恰好的产出，代价就是 $t * b * p 或 t * a * q$,取小
然后考虑 n % (a * b),暴力即可
一个通用的码法是
设置 A 优 B,枚举B的数量
现在来计算时间复杂度：
设置B选k次, k * b <= x % (a * b) <= a * b -> k <= a
同理 k <= max(a, b)
时间复杂度为 $O(max(a, b) + 1)$

if (p * b > q * a){
        swap(a, b);
        swap(p, q);
    }
    ll ans = 1e18;
    //枚举q
    for (int i = 0; i <= q; i ++ ){
        ll v = i * q;
        int ned = n - i * b;
        if (ned > 0){
            v += ((ll)ned + a - 1) / a * p;
        }
        ans = min(ans, v);
    }
    cout << ans;

然后用如上方法可以在有限时间解决 check 问题

#define int long long
const int N = 100 + 10;

int n, X; //金钱
int a[N], b[N], p[N], q[N];

bool check(int x){
    int res = 0;
    for (int i = 1; i <= n; i ++ ){
        int r = 1e18; 
        for (int j = 0; j <= 100; j ++ ){ 
            int v = j * q[i];
            int ned = x - j * b[i];
            if (ned > 0)
                v += (ned + a[i] - 1) / a[i] * p[i];
            r = min(r, v);
        }
        res += r;
        if (res > X) return false;
    }
    return true;
}

void solve(){
    cin >> n >> X;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i] >> p[i] >> b[i] >> q[i];
        if (a[i] * q[i] < b[i] * p[i]){
            swap(a[i], b[i]);
            swap(p[i], q[i]);
        }
    }
    int l = 0, r = 1e9;
    while (l < r){
        int mid = (l + r + 1) / 2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l;
}

F - Shipping

二维优化DP
$dp_{i, j}$ 代表前i件物品,第i件j天寄出的最小代价
但是j很大，时间超限
所以考虑优化，注意到j只可能是 T * k + X的形式
map离散存j即可

ll n, K, X, T[N], sum[N];

map<ll, ll> mp[N], f[N];
vector<ll> v[N];

void solve(){
    cin >> n >> K >> X;
    for (int i = 1; i <= n; i ++ ) cin >> T[i], sum[i] = sum[i-1] + T[i];

    mp[0][0] = 1, f[0][0] = 0;
    v[0].push_back(0);
    for (int i = 1; i <= n; i ++ )
        for (int j = max(1ll, i - K + 1); j <= i; j ++ )
            for (int k = 0; k < v[j-1].size(); k ++ ){
                ll now = v[j-1][k], NT = max(T[i], (j == 1) ? now : now + X);
                if (mp[i][NT] == 0){
                    v[i].push_back(NT);
                    mp[i][NT] = 1;
                    f[i][NT] = 1e18;
                }
                f[i][NT] = min(f[i][NT], f[j-1][now] + (i - j + 1) * NT - (sum[i] - sum[j-1]));
            }
    ll ans = 1e18;
    for (auto t : v[n]){
        ans = min(ans, f[n][t]);
    }
    cout << ans;
}