Memory search

skiing E a s y \color{green}{Easy} Easy

• d p [ i ] [ j ] dp[i][j] dp[i][j] indicates ( i , j ) (i, j) (i,j) the maximum distance of the position for memory search

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 333;
int dp[N][N], mp[N][N];
int n, m;
int dfs(int a, int b)
{
    if(dp[a][b]) return dp[a][b];
    dp[a][b] = 1;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    for(int i = 0; i < 4; ++i)
    {
        int x = dx[i] + a, y = dy[i] + b;
        if(x >= 1 && x <= n && y >= 1 && y <= m && mp[a][b] > mp[x][y])
        {
            dp[a][b] = max(dp[a][b], dfs(x, y) + 1);
        }
    }
    return dp[a][b];
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> mp[i][j];
    int ans = 0;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            ans = max(ans, dfs(i, j));
    cout << ans << endl;
    return 0;
}

knapsack

1, 01 Backpack E a s y \color{green}{Easy} Easy

Problem Description:

have N N N items and a capacity of V V V's backpack. What is the cost of item i c [ i ] c[i] c[i], the value is v a l [ i ] val[i] val[i]. Find out which items are loaded into the backpack to maximize the total value.

Idea:

01 backpack features, each item can be put or not. All may wish to set F ( i , j ) F(i, j) F(i,j) is expressed as, before i i i items in j j j is the maximum value of capacity, then its state transition equation is:

f ( i , j ) = m a x ( f ( i − 1 , j ) , f ( i − 1 , j − c [ i ] ) + v a l [ i ] ) f(i, j) = max(f(i-1,j), f(i-1, j-c[i])+val[i]) f(i,j)=max(f(i−1,j),f(i−1,j−c[i])+val[i])

Code:

cin >> n >> m;
    for(int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
        {
            //  If the current backpack capacity cannot hold the ith item, the value is equal to the first i-1 item
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // Yes, you need to make a decision whether to select the ith item
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           
    cout << f[n][m] << endl;

Space optimization:

Definition** f ( i ) f(i) f(i) * *: indicates that the capacity is i i i, then the transfer equation is:

f ( i ) = m a x ( f ( i ) , f ( i − c [ i ] ) + v a l [ i ] ) f(i) = max(f(i), f(i-c[i])+val[i]) f(i)=max(f(i),f(i − c[i])+val[i]) note that the enumeration of volumes should be in reverse order

Code:

cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;      // Processing while inputting
        for(int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
    }

    cout << f[m] << endl;

II Complete Backpack E a s y \color{green}{Easy} Easy

Problem Description:

have N N N items and a capacity of N N N's backpack, * * unlimited pieces of each item are available** The first i i What is the cost of i items c [ i ] c[i] c[i], the value is v a l [ i ] val[i] val[i]. Solve which items are loaded into the backpack, so that the total cost of these items does not exceed the backpack capacity, and the total value is the largest.

Solution: f ( i ) f(i) f(i) indicates the capacity is i i The maximum value of i is infinitely available. When enumerating the capacity, the transfer equation is: f ( i ) = m a x ( f ( i ) , f ( i − c [ i ] ) + v a l [ i ] ) f(i) = max(f(i), f(i-c[i])+val[i]) f(i)=max(f(i),f(i−c[i])+val[i])

Code:

cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;
        for(int j = v; j <= m; j++)
            f[j] = max(f[j], f[j - v] + w);
    }

    cout << f[m] << endl;

III Multiple Backpack M i d \color{orange}{Mid} Mid

Problem Description:

have N N N items and a capacity of V V V's backpack. The first i i i items have at most n [ i ] n[i] n[i] pieces are available at a cost of c [ i ] c[i] c[i], the value is v a l [ i ] val[i] val[i]. Solve which items are loaded into the backpack, so that the total cost of these items does not exceed the backpack capacity, and the total value is the largest.

Easy: 0 < N , V ⩽ 100 0 < N, V \leqslant 100 0<N,V⩽100 0 < v , w , s ⩽ 100 0 < v, w, s \leqslant 100 0<v,w,s⩽100

Solution: directly disassemble into 01 Backpack

Code:

#include<bits/stdc++.h>
using namespace std;
int n, m;
int f[1010];
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        int v, w, s; cin >> v >> w >> s;
        for(int j = 1; j <= s; ++j) // Do it once for s times
        for(int k = m; k >= v; --k)
            f[k] = max(f[k], f[k-v]+w);
    }
    cout << f[m];
    return 0;
}

Mid: 0 < N ⩽ 1000 0 < N \leqslant 1000 0<N⩽1000 0 < V ⩽ 2000 0 < V \leqslant 2000 0<V⩽2000 0 < v , w , s ⩽ 2000 0 < v, w, s \leqslant 2000 0<v,w,s⩽2000

Solution: binary split each item. For example, if 12 items can be selected, they can be disassembled into 1, 2, 4 and 5. It is easy to know that 0-12 can be summed up from the above, as shown in the figure:

1	1	7	1+2+4
2	1+1	8	4+4
3	1+2	9	5+4
4	2+2	10	5+5
5	1+4	11	5+5+1
6	2+4	12	5+5+2

Code:

#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[2020];
struct Good{
    int v,w;
};
int main()
{
    cin >> n >> m;
    vector<Good>g;
    for(int i = 1; i <= n; ++i)
    {
        int v, w, s; cin >> v >> w >> s;
        for(int k = 1; k <= s; k <<= 1)
        {
            s -= k;
            g.push_back({k*v,k*w});
        }
        if(s > 0) g.push_back({s*v,s*w});
    }
    for(auto goods : g)
    for(int j = m; j >= goods.v; --j)
        f[j] = max(f[j], f[j-goods.v] + goods.w);
    cout << f[m];
    return 0;
}

Hard: 0 < N ⩽ 1000 0 < N \leqslant 1000 0<N⩽1000 0 < V ⩽ 20000 0 < V \leqslant 20000 0<V⩽20000 0 < v , w , s ⩽ 20000 0 < v, w, s \leqslant 20000 0<v,w,s⩽20000

Solution: Reference problem solution

IV Group Backpack E a s y \color{green}{Easy} Easy

Problem Description:

have N N N groups of items and a backpack with a capacity of $V $. There are several items in each group. At most one item in the same group can be selected. What is the volume of each item v i j v_{ij} vij, the value is w i j w_{ij} wij, where i i i is the group number, j j j is the group number. Solve which items are loaded into the backpack, so that the total volume of the items does not exceed the backpack capacity, and the total value is the largest. The data range is less than 100

Solution: 01 backpack for each group

Code:

#include<bits/stdc++.h>
using namespace std;
int n, m;
int f[110], v[110][110], w[110][110], s[110];
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n; ++i)
    {
        cin >> s[i];
        for(int j=1;j<=s[i]; ++j)
            cin >> v[i][j] >> w[i][j];
    }
    for(int i = 1; i <= n; ++i)// Enumerate groups, and then click OK
    {
        for(int k = m; k >= 0; --k)//Each h corresponds to each group of optimal solutions
        {
            for(int h = 1; h <= s[i]; ++h)
            if(k >= v[i][h]) f[k] = max(f[k], f[k-v[i][h]] + w[i][h]);
        }
    }
    cout << f[m];
    return 0;
}

Linear DP

Digital triangle E a s y \color{green}{Easy} Easy

• Template question
• d p [ i ] [ j ] dp[i][j] dp[i][j] indicates ( i , j ) (i, j) Maximum value of (i,j)
• State transition equation: from n − 1 n-1 n − 1 push forward d p [ i ] [ j ] = d p [ i ] [ j ] + m a x ( d p [ i + 1 ] [ j ] , d p [ i + 1 ] [ j + 1 ] ) dp[i][j] = dp[i][j] + max(dp[i+1][j], dp[i+1][j+1]) dp[i][j]=dp[i][j]+max(dp[i+1][j],dp[i+1][j+1])

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1001;
int dp[N][N], n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= i; ++j)
            cin >> dp[i][j];
    for(int i = n - 1; i >= 1; --i)
    {
        for(int j = 1; j <= i; ++j)
            dp[i][j] += max(dp[i+1][j], dp[i+1][j+1]);
    }
    cout << dp[1][1];
    return 0;
}

Longest ascending subsequence LIS M i d \color{orange}{Mid} Mid

• Template
• Using greed, the time complexity is O ( n l o g n ) O(nlogn) O(nlogn)

Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n; cin >> n;
    vector<int>a(n), dp(n + 1, 0x3f3f3f3f);
    int mx = dp[0];
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < n; ++i)
        // If not strictly ascending, use upper_bound
        *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
    int ans = 0;
    while (dp[ans] != mx) ans ++;
    cout << ans << endl;
    return 0;
}

Longest common subsequence LCS E a s y \color{green}{Easy} Easy

letter E a s y \color{green}{Easy} Easy

• d p [ i ] [ j ] dp[i][j] dp[i][j] indicates a a a) front of i i i) strings and b b b before j j The size of the longest common subsequence of j ￠ characters
  d p [ i ] [ j ] ⟮ m a x ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) d p [ i − 1 ] [ j − 1 ] , a [ i ] = = b [ i ] dp[i][j] \lgroup^{dp[i-1][j-1], a[i] == b[i]} _{max(dp[i-1][j], dp[i][j-1])} dp[i][j]⟮max(dp[i−1][j],dp[i][j−1])dp[i−1][j−1],a[i]==b[i]​​​​​​

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int dp[N][N];
int main()
{
    int n, m; cin >> n >> m;
    string a, b; cin >> a >> b;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
        {
            if(a[i - 1] == b[j - 1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    cout << dp[n][m] << endl;
    return 0;
}

number M I D \color{orange}{MID} MID

• Two permutations are given P 1 , P 2 P_1,P_2 P1, P2, please L C S LCS LCS， n ≤ 1 0 5 n \le 10^5 n≤105
• S o l : Sol: Sol: according to P 1 P_1 P1 ， yes P 2 P_2 P2 ＾ discretization, and then P 2 P_2 P2 + L I S LIS LIS is enough

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 1e5+10;
int dp[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	int n; cin >> n;
	vector<int>a(n), b(n);
	unordered_map<int,int>mp;
	for(int i = 0; i < n; ++i) cin >> a[i], mp[a[i]] = i;
	for(int i = 0; i < n; ++i) cin >> b[i];
	memset(dp, 0x3f, sizeof dp);
	int mx = dp[n];
	for(int i = 0; i < n; ++i)
		*upper_bound(dp, dp+n, mp[b[i]]) = mp[b[i]];
	int ans = 0;
	while( dp[ans] != mx) ans ++;
	cout << ans << endl; 	   
    return(0-0);
}

Edit distance M i d \color{orange}{Mid} Mid

• d p [ i ] [ j ] dp[i][j] dp[i][j] indicates a a a) front of i i i) characters become b b b) front of j j Less operands for groups of j # characters

  Transfer equation:
  d p [ i ] [ j ] dp[i][j] dp[i][j]​ =

  a. delete: d p [ i − 1 ] [ j ] + 1 dp[i-1][j] + 1 dp[i−1][j]+1

             2. add to: $dp[i][j-1] + 1$
                3. Replace: $dp[i-1][j-1] + 1$
                4. unchanged: $dp[i-1][j-1]$
  

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int N = 2020;
int dp[N][N]; 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	string a, b; cin >> a >> b;
	int n = a.size(), m = b.size();
	for(int i = 1; i <= n; ++i) dp[i][0] = i;
	for(int i = 1; i <= m; ++i) dp[0][i] = i;

	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j)
		{
			if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1];
			else {                                                
				dp[i][j] = min(min(dp[i-1][j] + 1, dp[i][j-1] + 1), dp[i-1][j-1] + 1);
			}
		}
	cout << dp[n][m] << endl;

    return(0-0);
}

Interval DP

Stone merging E a s y \color{green}{Easy} Easy

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 333, INF = 2e9;
int w[N], s[N], n;
int dp[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> w[i];
    for(int i = 1; i <= n; ++i) s[i] = s[i - 1] + w[i];
    
    for(int len = 2; len <= n; ++len)
    {
        for(int l = 1; len + l - 1 <= n; ++l)
        {
            int r = len + l - 1;
            dp[l][r] = INF;
            for(int k = l; k < r; ++k)
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r] + s[r] - s[l - 1]);
        }
    }
    cout << dp[1][n] << endl;
    return 0;
}

Longest palindrome subsequence m i d \color{orange}{mid} mid

• d p [ i ] [ j ] dp[i][j] dp[i][j] indicates i i i) to j j Maximum palindrome length of j
• Transfer equation: [ d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , m a x ( d p [ i ] [ j − 1 ] , d p [ i + 1 ] [ j ] ) ) , s [ i ] ! = s [ j ] d p [ i ] [ j ] = d p [ i + 1 ] [ j − 1 ] + 2 , s [ i ] = = s [ j ] ] ] \left [ _{dp[i][j] = max(dp[i][j], max(dp[i][j-1],dp[i+1][j])), s[i] !=s[j]} ^{dp[i][j] = dp[i+1][j-1] + 2, s[i] == s[j]]} \right ] [dp[i][j]=max(dp[i][j],max(dp[i][j−1],dp[i+1][j])),s[i]!=s[j]dp[i][j]=dp[i+1][j−1]+2,s[i]==s[j]]​]

Code:

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        vector<vector<int>>dp(n,  vector<int>(n));
        for(int len = 1; len <= n; ++len)
            for(int l = 0; l + len - 1 < n; ++l)
            {
                int r = len + l - 1;
                if(len == 1) dp[l][r] = 1;
                else {
                    if(s[l] == s[r]) dp[l][r] = dp[l+1][r-1] + 2;
                    else {
                        dp[l][r] = max(dp[l][r], max(dp[l+1][r], dp[l][r-1]));
                    }
                }
            }
        int ans = 0;
        for(auto &arr : dp)
            for(auto &x : arr)
                ans = max(ans, x);
        return ans;
    }
};

Tree DP

A party without a boss E a s y \color{green}{Easy} Easy

Topic meaning: Ural university has N N N employees, No 1 ∼ N 1 \sim N 1∼N​. Their relationship is like a tree with the principal as the root, and the parent node is the direct boss of the child node. Everyone has a happy value. Select several people to maximize the happy value. No employee is willing to work with his direct boss

• d p [ i ] [ 1 ] dp[i][1] dp[i][1] indicates selection i i Maximum value of i, d p [ i ] [ 0 ] dp[i][0] dp[i][0] means no selection i i Maximum value of i +

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 6010;
int e[N], ne[N], h[N], idx;
int happy[N], n, dp[N][2];
bool f[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    dp[u][1] = happy[u];
    
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);
        dp[u][0] += max(dp[j][0], dp[j][1]);
        dp[u][1] += dp[j][0]; 
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> happy[i];
    
    memset(h, -1, sizeof h);
    
    for(int i = 1; i < n; ++i)
    {
        int a, b; cin >> a >> b;
        f[a] = true;
        add(b, a);
    }
    int root = 1;
    while(f[root]) root++;
    dfs(root);    
    cout << max(dp[root][1], dp[root][0]) << endl;
    return 0;
}

Digital DP

digit D P DP DP} problem usually gives an interval [ L , R ] [L,R] [L,R], the number of numbers satisfying the given conditions in the interval. The solution is to prefix and solve: ∑ i = 1 R a n s i − ∑ i = 1 L − 1 a n s i \sum_{i=1}^{R}ans_i - \sum_{i=1}^{L-1} ans_i ∑i=1R​ansi​−∑i=1L−1​ansi​​​

Template:

int dfs(int pos, int pre, int lead, int limit){
    if(!pos) { boundary }
    if(!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
    int res = 0;
    int mx = limit ? a[pos] : 9;
    for(int i = 0; i < mx; ++i)
    {
        if( Inconformity ) continue;
        res += dfs(pos - 1, , , limit && i == mx);
    }
    return limit ? res : dp[pos][pre] = res;
}

int cal(int x)
{
    memset(dp, -1, sizeof dp);
    len = 0;
    while (x) a[++len] = x % 10, x /= 10;
    return dfs(len, , 1 ,1 );
}
int main()
{
    cin >> L >> R;
    cout << cal(R) - cal(L - 1) << endl;
    return 0;
}

correlation function

cal function:

initialization d p dp dp array is - 1 and the number length is 0;

Basic parameters:

l e n len len denotes the length of this number, a i a_i ai represents the specific number of each digit
r e t u r n return return: you need to make a judgment according to the meaning of the question
p o s pos pos represents the number of digits of a number
l i m i t limit Limit indicates the relevant limit
p r e pre pre stands for precursor
$lead indicates whether leading zeros exist

dfs function:

r e s res res record the answers, m x mx mx represents the maximum value of this bit. In addition, memory search is adopted.

if(!limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];

• Only unlimited and no leading zeros can be regarded as finished searching, otherwise they are not finished searching

return limit ? res : dp[pos][pre] = res;

• If there are restrictions at the end, return r e s res res, otherwise return d p [ p o s ] [ p r e ] dp[pos][pre] dp[pos][pre]

subject

Don't 62 M i d \color{orange}{Mid} Mid

Find the interval [ L , R ] [L, R] The number of times 4 or 62 cannot occur in [L,R]

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int l, r, dp[N][N], len, a[N];
//a[i] represents the number of bits I, dp[i][j] represents the number of bits I, and the preceding bit is the number of satisfied numbers of pre
int dfs(int pos, int pre, bool limit)
{
	if(!pos) return 1; // Enumeration bit ends and returns 1
	if( !limit && dp[pos][pre] != -1) return dp[pos][pre];
	// Memory search, there is no limit, and this is searched, you can return directly
    int res = 0;
	int mx = limit ? a[pos] : 9; // Judge whether it is limited
	for(int i = 0; i <= mx; ++i)
	{
       	// Not satisfied with the meaning of the question
		if(i == 4 || ( i == 2 && pre == 6)) continue;
		res += dfs(pos - 1, i, limit && i == mx);
		// Enumerate the next bit, and the previous bit is i. if there is a limit and the maximum is reached, the next bit will also be limited
    }
	return limit ? res : dp[pos][pre] = res;
}

int cal( int x )
{
	memset(dp, -1, sizeof dp); // initialization
	len  = 0; // Gets each bit of the number
	while ( x ) a[ ++ len] = x % 10 , x /= 10;
	return dfs(len, 0, 1);
}

int main()
{
	while(cin >> l >> r, l && r)
		cout << cal(r) - cal(l - 1) << endl;
	return 0;
}

windy number H a r d \color{red}{Hard} Hard

Question meaning: find the interval [ L , R ] [L, R] The difference of adjacent numbers between [L,R] is not less than 2 2 Number of 2

• tag: initially, p r e pre pre to set to a ≤ − 2 \le -2 The number of ≤− 2 is to find the first place of the target number

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int l, r, dp[N][N], len, a[N];
int dfs(int pos, int pre, int lead, bool limit)
{
	if(!pos) return 1;
	if( !limit && !lead && dp[pos][pre] != -1) return dp[pos][pre];
	int res = 0;
	int mx = limit ? a[pos] : 9;
	for(int i = 0; i <= mx; ++i)
	{
		if(abs(pre - i) < 2) continue;
		if(lead && !i) { // Continue to find the first digit that matches the number
			res += dfs(pos - 1, -2, 1, limit && i == mx);
		}
		else {
			res += dfs(pos - 1, i, 0, limit && i == mx);
		}
	}
	return limit ? res : dp[pos][pre] = res;
}
int cal( int x )
{
	memset(dp, -1, sizeof dp);
	len  = 0;
	while ( x ) a[ ++ len] = x % 10 , x /= 10;
	return dfs(len, -2, 1, 1);
}
int main()
{
	cin >> l >> r;
		cout << cal(r) - cal(l - 1) << endl;
	return 0;
}

Digital game II M i d \color{orange}{Mid} Mid

Meaning: Calculation [ L , R ] [L, R] [L,R] the number of digits that do not decrease

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int l, r, dp[N][N], len, a[N];

int dfs(int pos, int pre, bool limit)
{
	if(!pos) return 1;
	if( !limit && dp[pos][pre] != -1) return dp[pos][pre];
	int res = 0;
	int mx = limit ? a[pos] : 9;
	for(int i = 0; i <= mx; ++i)
	{
		if(i < pre) continue;
		res += dfs( pos - 1, i, limit && i == mx);
	}
	return limit ? res : dp[pos][pre] = res;
}
int cal( int x )
{
	memset(dp, -1, sizeof dp);
	len  = 0;
	while ( x ) a[ ++ len] = x % 10 , x /= 10;
	return dfs(len, 0, 1);
}
int main()
{
	while(cin >> l >> r)
		cout << cal(r) - cal(l - 1) << endl;
	return 0;
}

Digital game I M i d \color{orange}{Mid} Mid

Meaning: Calculation [ L , R ] [L, R] [L,R] sum of each digit m o d p mod p modp​ n n N = = number of 0

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int l, r, dp[N][N], len, a[N], n;
int dfs(int pos, int sum, bool limit)
{
	if(!pos) return sum % n == 0;
	if( !limit && dp[pos][sum] != -1) return dp[pos][sum];
	int res = 0;
	int mx = limit ? a[pos] : 9;
	for(int i = 0; i <= mx; ++i)
	{
		res += dfs( pos - 1, sum + i, limit && i == mx);
	}
	return limit ? res : dp[pos][sum] = res;
}
int cal( int x )
{
    if(!x) return 1;
	memset(dp, -1, sizeof dp);
	len  = 0;
	while ( x ) a[ ++ len] = x % 10 , x /= 10;
	return dfs(len, 0, 1);
}
int main()
{
	while(cin >> l >> r >> n)
		cout << cal(r) - cal(l - 1) << endl;
	return 0;
}

Number of degrees H a r d \color{red}{Hard} Hard

Meaning: Calculation [ L , R ] [L, R] [L,R] exactly K K K B B The number of the sum of the powers of B, and these books are different

• tag: in essence, it is seeking B B B-ary lower 1 1 The number of 1 should be equal to K K K​，​

Code:

#include<bits/stdc++.h>

using namespace std;
const int N = 35;
int l, r, dp[N][N], len, a[N], k , b;
int dfs(int pos, int sum, bool limit)
{
	if(!pos) return sum == k;
	if( !limit && dp[pos][sum] != -1) return dp[pos][sum];
	int res = 0;
	int mx = limit ? a[pos] : b - 1;
	for(int i = 0; i <= mx; ++i)
	{
        //If the previous coefficient is not 1 or reaches k, skip
		if( (i==1 && sum == k)|| i > 1) continue;
		res += dfs(pos - 1, sum + ( i == 1), limit && i == mx);
	}
	return limit ? res : dp[pos][sum] = res;
}
int cal( int x )
{
	memset(dp, -1, sizeof dp);
	len  = 0;
	while ( x ) a[ ++ len] = x % b , x /= b;
	return dfs(len, 0, 1);
}
int main()
{
	while(cin >> l >> r >> k >> b)
		cout << cal(r) - cal(l - 1) << endl;
	return 0;
}

Counting problem M i d \color{orange}{Mid} Mid

Meaning: Calculation [ L , R ] [L, R] Number of $0 \sim 9 $between [L,R]

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 35;
int l, r, dp[N][N], len, a[N];
int dfs(int pos, int sum, int num, bool lead, bool limit)
{
	if(!pos) {
		if(lead && !num) return 1;
		return sum;
	}
	if( !limit && !lead && dp[pos][sum] != -1) return dp[pos][sum];
	int res = 0;
	int mx = limit ? a[pos] : 9;
	for(int i = 0; i <= mx; ++i)
	{
		int t;
		if( i == num) {
			if(!num) t = sum + (lead == 0);
			else t = sum + 1;
		}
		else t = sum;
		res += dfs(pos - 1, t, num, lead && i == 0, limit && i == mx);
	
	}
	return limit ? res : (lead ? res : dp[pos][sum] = res);
}

int cal( int x, int num)
{
	memset(dp, -1, sizeof dp);
	len  = 0;
	while ( x ) a[ ++ len] = x % 10 , x /= 10;
	return dfs(len, 0,num, 1, 1);
}

int main()
{
	while(cin >> l >> r, l && r) {
		if(l > r) swap(l ,r);
		for(int i = 0; i < 10; ++i)
			cout << cal(r, i) - cal(l-1, i) << " \n"[i == 9];
	}
	return 0;
}

Homogeneous distribution H a r d \color{red}{Hard} Hard

Problem meaning: find out [ L , R ] [L, R] The sum of the numbers between [L,R] can divide the number of the original book

Sol: apply digital DP template, m o d mod mod represents the sum of each digit, s u m sum sum ， stands for the original number. If this is found s u m sum The original number of sum will reach 1 0 18 10^{18} 1018. The memory array cannot be stored, so we consider enumerating the sum of each digit, that is, modulus

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL l, r,len, dp[20][200][200], a[20], Mod;
LL dfs( int pos, int mod, LL sum, bool limit)
{
	if(!pos) {
		return (sum == 0 && mod == Mod);
	}
	if( !limit && dp[pos][mod][sum] != -1) return dp[pos][mod][sum];
	LL res = 0;
	int mx = limit ? a[pos] : 9;
	for(int i = 0; i <= mx; ++i)
		res += dfs( pos - 1, (mod + i),( sum * 10 + i) % Mod, limit && i == mx);
	return limit ? res : dp[pos][mod][sum] = res;
}

LL cal( LL x )
{
	len = 0;
	while (x) a[ ++len] = x % 10, x /= 10;
	LL ans = 0;//Enumeration module, that is, the sum of each digit and
	for( Mod = 1; Mod <= 9 * len; ++Mod)
	{
		memset(dp, -1, sizeof dp);
		ans += dfs(len, 0, 0, 1);
	}
	return ans;
}

int main()
{
	cin >> l >> r;
	cout << cal(r) - cal(l-1) << endl;
	return 0;
}

Classy Numbers H a r d \color{red}{Hard} Hard

Meaning: Calculation [ L , R ] [L, R] The non-zero number of each number between [L,R] shall not exceed three

Sol: a set of templates is enough

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL l, r,len, dp[20][20], a[20];
LL dfs( int pos, int sum, bool lead, bool limit)
{
	if(!pos) {
		return 1;
	}
	if( !limit && !lead && dp[pos][sum] != -1) return dp[pos][sum];
	LL res = 0;
	int mx = limit ? a[pos] : 9;
	for(int i = 0; i <= mx; ++i)
	{
		if(i != 0 && sum >= 3) continue;
		res += dfs(pos - 1, sum + (i != 0), lead && i == 0, limit && i == mx);
	}
	return limit ? res : (lead ? res : dp[pos][sum] = res);
}
LL cal( LL x )
{
	len = 0;
	while (x) a[ ++len] = x % 10, x /= 10;
	return dfs(len, 0, 1, 1);
}
int main()
{
	int T; cin >> T;
	memset(dp, -1, sizeof dp);
	while ( T -- )
	{
		cin >> l >> r;
		cout << cal(r) - cal(l-1) << endl;
	}
	return 0;
}

Number theory of flower god H a r d \color{red}{Hard} Hard

Meaning: s u m i sum_i sumi said i i The number of 1 in the binary of i + ∏ i = 1 n s u m i \prod_{i=1}^{n}sum_i ∏i=1n​sumi​​​

Sol: we define G k G_k Gk is ∑ i = 1 n ( s u m i = = k ) \sum_{i=1}^n (sum_i == k) Σ i=1n (sumi = = k), the easy answer is: ∏ i = 1 50 i G i \prod_{i=1}^{50} i^{G_i} Π i=150 Π iGi, calculated by digit dp 1 ∼ n 1 \sim n 1 ∼ n G i G_i Gi, and then fast power calculation

Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod =10000007;
LL x,len, dp[64][64], a[64], G[64], P;
LL qpow( LL a, LL b)
{
    LL res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        b >>= 1;a = a * a % mod;}
    return res;
}
LL dfs( int pos, int sum, bool limit)
{
	if(!pos) {
		return sum == P;
	}
	if( !limit &&  dp[pos][sum] != -1) return dp[pos][sum];
	LL res = 0;
	int mx = limit ? a[pos] : 1;
	for(int i = 0; i <= mx; ++i)
	{
		if(sum > P) continue;
		res += dfs(pos - 1, sum + (i != 0), limit && i == mx);
	}
	return limit ? res : dp[pos][sum] = res;
}
LL cal( LL x )
{
	len = 0;
	while (x) a[ ++len] = x % 2, x /= 2;
	for( P = 1; P < 50; ++P)
	{
		memset(dp, -1, sizeof dp);
		G[P] = dfs(len, 0, 1); 
	}
	LL ans = 1;
	for(int i = 1; i < 50; ++i)
		ans = ans * qpow(i, G[i])% mod;
	return ans % mod;	
}
int main()
{
	cin >> x;
	cout << cal(x) << endl;
	return 0;
}

Do not upgrade 666 H a r d \color{red}{Hard} Hard

Sub question: Don't 666

Sol: a number is divided into a + b a+b a+b, for example: 82342 = 80000 + 2342 82342 = 80000+2342 82342=80000+2342​​​​
( a + b ) 3 = a 3 + b 3 + 3 ∗ a 2 ∗ b + 3 ∗ a ∗ b 2 (a+b)^3 = a^3 + b^3+3*a^2*b+3*a*b^2 (a+b)3=a3+b3+3∗a2∗b+3∗a∗b2​​​
Number of conditions satisfied, c n t cnt cnt is the number of these numbers: ( a 3 ∗ c n t + ( b 3 + c 3 + ⋅ ⋅ ⋅ ) + 3 ∗ a 2 ∗ ( b + c + ⋅ ⋅ ⋅ ) + 3 ∗ a ∗ ( b 2 + c 2 + ⋅ ⋅ ⋅ ) ) (a^3*cnt + (b^3 + c^3 + ···) + 3 * a^2*(b+c+···) + 3*a*(b^2 + c^2+···)) (a3∗cnt+(b3+c3+⋅⋅⋅)+3∗a2∗(b+c+⋅⋅⋅)+3∗a∗(b2+c2+⋅⋅⋅))​​
digit d p dp dp maintains its number, sum, square sum, cubic sum

Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 30, mod = 1e9+7;
LL l, r, len, a[N], ten[N];
struct s
{ 
    LL x, sum, sqr, cub;
} dp[20][10][10];
s dfs(int pos, int mod1, int mod2, bool limit ){
	if(!pos) return (s){mod1&&mod2, 0, 0, 0};
	if( !limit && dp[pos][mod1][mod2].x != -1) return dp[pos][mod1][mod2];
	int mx = limit ? a[pos] : 9;
	s res = {0, 0, 0, 0};
	for(int i = 0; i <= mx ; ++i)
	{
		if( i == 6) continue;
		s t = dfs(pos - 1, (mod1 + i) % 6, (mod2 * 10 + i) % 6, limit && i == mx);
		LL d = (LL)i * ten[pos] % mod;

	    res.x = (res.x + t.x) % mod;
        res.sum = (res.sum + d * t.x % mod  + t.sum) % mod;
        res.sqr = (res.sqr + t.x * d % mod * d % mod + 2LL * d % mod * t.sum % mod + t.sqr) % mod;
        res.cub = (res.cub + t.x * d % mod * d % mod * d % mod + 3LL * d % mod * d % mod * t.sum % mod + 3LL * d % mod * t.sqr % mod + t.cub) % mod;
	}
	return limit ? res : dp[pos][mod1][mod2] = res;
}

LL cal(LL x)
{
	len = 0;
	while ( x ) a[ ++len] = x % 10, x /= 10;
	return dfs(len, 0, 0 , 1).cub;	
} 

int main()
{
	memset(dp, -1, sizeof dp);
	ten[1] = 1;
	for(int i = 2; i <= 20; ++i) ten[i] = ten[i-1]*10;	
	while (cin >> l >> r )
		cout << (cal(r) - cal(l - 1)+mod) % mod << endl;
	return 0;	
}