杭电多校3补题记录

1007: Tokitsukaze and Rescue (HDU 6797)

比赛的时候想的是随机删除最短路的一条边，结果题解比我想象中的更暴力。

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const ll inf = 0x3f3f3f3f;
const int maxn = 60;

int G[maxn][maxn];
int ans;

int dist[maxn], fa[6][maxn];
bool vis[maxn];

void dfs(int n, int k){
    memset(dist, 0x3f, sizeof dist);
    memset(vis, 0, sizeof vis);
    dist[1] = 0;
    for(int i=0; i<n; i++){
        int sel = 0;
        for(int j=1; j<=n; j++) {
            if(vis[j]) continue;
            if(sel == 0 || dist[sel] > dist[j]) sel = j;
        }
        vis[sel] = true;
        for(int j=1; j<=n; j++){
            if(dist[j] > dist[sel] + G[sel][j]){
                fa[k][j] = sel;
                dist[j] = dist[sel] + G[sel][j];
            }
        }
    }
    if(k == 0){
        ans = max(ans, dist[n]);
        return;
    }
    for(int u=n, f; u!=1; u=f){
        f = fa[k][u];
        int tmp = G[u][f];
        G[u][f] = G[f][u] = inf;
        dfs(n, k - 1);
        G[u][f] = G[f][u] = tmp;
    }
}

void solve(){
    ans = -1;
    memset(G, 0x3f, sizeof G);
    int n, k;
    cin >> n >> k;
    for(int i=0; i<=n; i++) G[i][i] = 0;
    for(int i=0, u, v, w; i<(n - 1) * n / 2; i++){
        cin >> u >> v >> w;
        G[u][v] = G[v][u] = w;
    }
    dfs(n, k);
    cout << ans << '\n';
}

signed main(){
    Android;
    int tk; cin >> tk;
    while(tk--)
    solve();
}

1006: X Number (HDU 6796)

毒瘤的数位dp增加了

---

子问题1：已知"1"有1个，"2"有3个，还有6位可为[0,9]任意数字，求x为众数的方法数

解：遍历i=[0,6]，代表6位中有多少$i$位为x

然后dp求解

---

数位dp空间优化小技巧：通过回溯维护状态

基本照抄标程，加入了一点小小的个人理解

本题开O(fast)有害，慢300ms左右

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r==0?' ':'\n')
#define pii pair<int, int>
#define sqr(x) ((x)*(x))
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;

ll comb[20][20];

ll C(int n, int m){ // C(3, 1) = 3
    if(n - m < m) m = n - m;
    if(comb[n][m] != -1) return comb[n][m];
    ll & ans = comb[n][m];
    ans = 1;
    for(int i = n; i > n - m; i--) ans *= i;
    for(int i = 1; i <= m; i++) ans /= i;
    return ans;
}

ll a[20], l, r, x;
map<array<int, 10>, ll> dp[20];
array<int, 10> state = {0};

ll dpx[20];
ll dfs(int len, bool lim, bool leading_zero){
    auto ptr = dp[len].find(state);
    if(ptr != dp[len].end() && !lim) return ptr->second;

    if(len == 0){
        for(int i=0; i<10; i++){
            if(i != x && state[i] >= state[x]) return dp[len][state] = 0;
        }
        return dp[len][state] = 1;
    }

    ll ans = 0;

    if(!lim && !leading_zero){ // 子问题1
        for(int sel = 0; sel <= len; sel++){
            for(int i=0; i < len - sel; i++) dpx[i] = 0;
            dpx[len - sel] = C(len, sel);
            for(int i=0; i<10; i++){
                if(i == x) continue;
                if(state[x] + sel <= state[i]){
                    dpx[0] = 0;
                    break;
                }
                for(int j=1; j<=len-sel; j++){
                    for(int k=1; k<=min(j, state[x]+sel-state[i]-1); k++){
                        dpx[j - k] += dpx[j] * C(j, k);
                    }
                }
            }
            ans += dpx[0];
        }
        return dp[len][state] = ans;
    }

    if(leading_zero) ans += dfs(len - 1, lim && a[len]==0, 1);

    int begin = leading_zero?1:0, end = lim?a[len]:9;
    for(int i=begin; i<=end; i++){
        if(i == x || state[i] + 1 <= state[x] + len) {
            state[i]++;
            ans += dfs(len - 1, lim && i == a[len], 0);
            state[i]--;
        }
    }
    return lim ? ans:dp[len][state] = ans;
}

ll solve(ll val){
    int p = 0;
    while(val){
        a[++p] = val % 10;
        val /= 10;
    }
    return dfs(p, 1, 1);
}

signed main(){
    memset(comb, -1, sizeof comb);
    Android;
    int tk; cin >> tk;
    while(tk--){
        for(int i=0; i<20; i++)
            dp[i].clear();
        cin >> l >> r >> x;
        cout << solve(r) - solve(l - 1) << '\n';
    }
}

1008: Triangle Collision (HDU 6798)

题解原文：

灵感来自用激光笔往镜子中射入激光被多次反射。 人眼从激光笔的视角来看，光束并没有被“反射”，而是穿入了“镜子中的世界”。