模板总结

寄搜模板

ll dp[N][state];        // 状态根据题目性质改变, 例子记录数位中 非零 数位的个数
// 从高位向低位递归
ll dfs(int pos, int cnt, bool lead, bool limit){    // (当前数位, 根据题目需要记录状态, 是否有前导零, 前面的数位是否填满)
	if(pos == -1) return 1;	    // 递归出口, 可能需要判断是否符合题目条件
	if(!limit && !lead && dp[pos][cnt] != -1) return dp[pos][cnt];  // 记忆化, 具体看题目,一般需要 !limit 与 !lead
	int up = limit ? a[pos] : 9;    // 根据前面是否填满, 设立枚举上界
    /*
        灵活修改
        if(cnt == k) up = 0;
    */
	ll res = 0;
	for(int i = 0; i <= up; i++){
        /*
            灵活修改, 进行递归
		    int t = (i != 0);
            res += dfs(pos - 1, cnt + t, lead && i == 0, limit && i == a[pos]); // 注意lead和limit的传递
        */
	}
	if(!limit && !lead) dp[pos][cnt] = res;     // 根据需要, 进行记忆化存储
	return res;
}

例题

dls动态规划中级课

数数3

dls数位DP中级课

• 求满足 存在 3 个连续数位单调递增的数字个数

ll dp[20][2][10][5];

ll dfs(int rem, int exist, int last, int inc) {
    ll& ans = dp[rem][exist][last][inc];
    if (ans != -1) return ans;
    if (!rem) return exist;
    ans = 0;
    for (int i = 0; i <= 9; i ++) {
        int new_inc = (i > last) ? min(3, inc + 1) : 1;
        ans += dfs(rem - 1, exist | (new_inc == 3), i, new_inc);
    }
    return ans;
}

ll solve(ll x) {
    x ++;
    vector<int> d;
    while (x) {
        d.pb(x % 10);
        x /= 10;
    }
    reverse(ALL(d));
    int m = d.size();
    ll ans = 0;
    // 处理前导零
    for (int i = 1; i <= m - 1; i ++) {
        for (int j = 1; j <= 9; j++)
            ans += dfs(i - 1, 0, j, 1);
    }
    int rem = 0, exist = 0, inc = 0, last = 0;
    for (int i = 0; i < m; i++) {
        for (int j = (i == 0) ? 1 : 0; j < d[i]; j++) {
            int new_inc = (j > last) ? min(3, inc + 1) : 1;
            ans += dfs(m - i - 1, exist | (new_inc == 3), j, new_inc);
        }
        inc = (d[i] > last) ? min(3, inc + 1) : 1;
        last = d[i];
        exist |= (inc == 3);
    }
    return ans;
}

CF1560F2. Nearest Beautiful Number (hard version)

Codeforces Round #739 (Div. 3)

• 定义 k-美丽数 为数位中不同数位最多为 \(k\) 的数字。
• 求大于等于 \(n\) 的最小 k-美丽数。

这类问题核心：快速判断剩下的位是否能满足要求(new_cnt <= k)

vector<int> d;
int n, k;
int vis[11];        // 多组数据清空 vis[]，直接返回dfs不一定回溯
bool dfs(int x, bool larger, int cnt, int num) {
    if (x == (int)d.size()) {
        printf("%d\n", num);
        return true;
    }
    else {
        for (int i = larger ? 0 : d[x]; i <= 9; i ++) {
            vis[i]++;
            int new_cnt = cnt;
            if (vis[i] == 1) new_cnt++;
            if (new_cnt <= k && dfs(x + 1, larger | (i > d[x]), new_cnt, num * 10 + i))
                return true;
            vis[i]--;
        }
    }
    return false;
}

void solve(int x) {
    d.clear();
    while (x) {
        d.pb(x % 10);
        x /= 10;
    }
    reverse(ALL(d));
    dfs(0, 0, 0, 0);
}

不同位大于等于 \(k\) 最小数字求法

这里的核心代码就是 new_cnt + (int)d.size() - x - 1 >= k ，还要减 1 是因为当前位的贡献已经计算在了 new_cnt 里面。

vector<int> d;
int n, k;
int vis[11];

bool dfs(int x, bool larger, int cnt, int num) {
    if (x == (int)d.size()) {
        printf("%d\n", num);
        return true;
    }
    else {
        for (int i = larger ? 0 : d[x]; i <= 9; i ++) {
            vis[i]++;
            int new_cnt = cnt;
            if (vis[i] == 1) new_cnt++;
            if (new_cnt + (int)d.size() - x - 1 >= k && dfs(x + 1, larger | (i > d[x]), new_cnt, num * 10 + i))
                return true;
            vis[i]--;
        }
    }
    return false;
}

void solve(int x) {
    d.clear();
    while (x) {
        d.pb(x % 10);
        x /= 10;
    }
    reverse(ALL(d));
    while (1) {
        if (dfs(0, 0, 0, 0)) break;     // 当前位数搜不到就要扩大位数，否则 break
        int m = d.size() + 1;
        d.clear();
        d.push_back(1);     // 原来有 m 位，扩大为 m + 1 位，那么从最小的 1000000开始，有 m 个 0
        for (int i = 0; i < m - 1; i ++) d.push_back(0);         
    }
}

数位背包入门——梦幻岛宝珠

P3188 [HNOI2007]梦幻岛宝珠

思路

• 形如背包重量为 \(a * 2^x\) 的题目，可以用数位背包的方法来尝试解题
• 由高到低位考虑，\(f[i][j]\) 表示到第 \(i\) 为还剩 \(j\) 个 \(2^i\) 容量的最大价值。
• 由于重量的系数 和 物品个数限制，考虑到第 \(i\) 位时，后面的所有位加起来贡献到第 \(i\) 位的重量是有限的，所以直接和物品重量总数取 min
• 然后注意细节和转移，由于状态定义为还剩xxx时的最大价值，所以要用 剩的多反而背包价值更大 去更新剩的少的价值，代码中是后缀 max

const int N = 2010;
ll f[N], g[N];
int n, W;
// f[i][j] 到第 i 位，还剩 j 个容量的最大价值
vector<PII> item[35];
void solve() {
    for (int i = 0; i <= 31; i ++) item[i].clear();
    int sum = 0;    // 重量总数
    for (int i = 0; i < n; i ++) {
        int w, v;
        re(w), re(v);
        int lev = __builtin_ctz(w);
        w >>= lev;
        item[lev].pb({w, v});
        sum += w;
    }
    for (int i = 0; i <= sum; i++) f[i] = -2e18;
    f[0] = 0;
    for (int i = 30; i >=0 ; i--) {
        for (int j = 0; j <= sum; j++) g[j] = f[j], f[j] = -2e18; // 滚动数组
        int d = W >> i & 1;
        for (int j = 0; j <= sum; j ++) {       // 不选物品，i->i+1 背包状态转移，容量 * 2 + d
            f[min(sum, 2 * j + d)] = max(f[min(sum, 2 * j + d)], g[j]);
        }
        // 选物品，背包转移, f[i][j] = max(f[i][j], f[i - 1][j + w] + v);
        // w <= j <= sum, 所以需要记录 f[i][j] 为后缀 f[][] 最大值, 因为剩的更多价值更大，剩的少的价值应该被更新掉。
        for (int j = sum - 1; j >= 0; j--)
            f[j] = max(f[j], f[j + 1]);
        for (auto p: item[i]) {         
            for (int j = 0; j <= sum - p.first; j++) {
                f[j] = max(f[j], f[j + p.first] + p.second);
            }
        }
    }
    printf("%lld\n", f[0]);
}

2020-CCPC长春-D, Meaningless Sequence

• 有个小结论然后无脑做，有个二项式定理，\((1+c)^k = \Sigma_i^k(c^i * \binom{k}{i})\)

const int N = 3010, mod = 1e9 + 7;
ll power[N];

int main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    string s;
    cin >> s;
    int c, n = s.size();
    re(c);
    power[0] = 1;
    for (int i = 1; i <= N - 10; i++)
        power[i] = power[i - 1] * (c + 1) % mod;
    ll pre = 1, ans = 0;
    for (int i = 0; i < n; i ++) {
        if (s[i] == '0') continue;
        ans = (ans + pre * power[n - i - 1] % mod) % mod;
        pre = pre * c % mod;
    }
    ans += pre;
    printf("%lld\n", ans % mod);
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}

2020-ICPC济南-L, Bit Sequence

待补