每日一题6.19(数位dp)

495684945

蓝桥杯国赛15分的题，很板的题，这题会就稳国一了，但是集训队好像很多人都不会这个板子

题目链接

495684945

[C++] 纯文本查看 复制代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int>PII;

void solve(){
	string str;
	int n;
	cin>>n;
	vector f(19,vector(3,vector<int>(19,-1)));
	auto dfs=[&](auto dfs,int u,int lst,int lead0,int cnt,int limit)->int{
		if(u==str.size()){
			if(cnt>=2)return 1;
			else return 0;
		}
		if(lst!=-1&&!lead0&&!limit&&f[u][lst][cnt]!=-1)return f[u][lst][cnt];
		int maxx=9,ans=0;
		if(limit)maxx=str[u]-'0';
		for(int i=0;i<=maxx;i++){
			int t=i&1;
			if(lst!=-1&&(t^lst)==0)continue;
			if(lead0&&i==0){
				ans+=dfs(dfs,u+1,-1,1,0,limit&&(i==maxx));
			}else{
				ans+=dfs(dfs,u+1,i&1,0,cnt+1,limit&&(i==maxx));
			}
		}
		if(!limit&&lst!=-1)f[u][lst][cnt]=ans;
		return ans;
	};
	auto check=[&](int mid)->bool{
		str=to_string(mid);
		for(int i=0;i<=18;i++)
			for(int j=0;j<=1;j++)
				for(int k=0;k<=18;k++)f[i][j][k]=-1;
		return dfs(dfs,0,-1,1,0,1)>=n;
	};
	check(5);
	int l=1,r=1e18;
	while(l+1<r){
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid;
	}
	cout<<r<<endl;
}

signed main(){
	int t=1;ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//	cin>>t;
	while(t--)solve();
	return 0;
}

Fengyj

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
#define int long long

int dp[20][2][3];

int dfs(vector<int> &num, int pos, int cnt, int ls, int limit, int lead0)
{
    if (pos == num.size())
    {
        return (cnt > 1) ? 1 : 0;
    }
    int res = 0;
    if (!limit && !lead0 && dp[pos][ls][cnt] != -1)
    {
        return dp[pos][ls][cnt];
    }
    int up = limit ? num[pos] : 9;

    for (int i = 0; i <= up; i++)
    {
        if (ls != -1 && (i & 1) == (ls & 1))
            continue;
        if (lead0 && i == 0)
        {
            res += dfs(num, pos + 1, cnt, -1, limit && i == up, 1);
        }
        else
        {
            res += dfs(num, pos + 1, min(2ll, cnt + 1), i & 1, limit && i == up, 0);
        }
    }

    if (!lead0 && !limit)
        dp[pos][ls][cnt] = res;

    return res;
}

bool check(int x, int n)
{
    memset(dp, -1, sizeof dp);
    vector<int> num;
    while (x)
    {
        num.push_back(x % 10);
        x /= 10;
    }
    reverse(num.begin(), num.end());

    return dfs(num, 0, 0, -1, 1, 1) >= n;
}

void solve()
{
    int n;
    cin >> n;
    int l = 1, r = 1e18;
    while (l < r)
    {

        int mid = l + r >> 1;
        if (check(mid, n))
            r = mid;
        else
            l = mid + 1;
    }
    cout << r << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin>>T;
    while (T--)
    {
        solve();
    }
    return 0;
}