首页 > 其他分享 >abc234E 不小于X的数位构成等差数列的最小数字

abc234E 不小于X的数位构成等差数列的最小数字

时间:2024-03-12 22:00:16浏览次数:26  
标签:return int rep long abc234E 等差数列 数位

给定X,求不小于X的整数,满足各个数位正好构成等差数列。
1<=X<=1E17

直接枚举首项和公差,找出所有可行的解,取最优值即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,a,b) for(int i=b; i>=a; i--)

int x;
set<int> ans;
void check(int d, int a) {
    if (d == 0 && a == 0)
        return;
    int u = a;
    while (a < x) {
        u += d;
        if (u < 0 || u > 9) {
            return;
        }
        a = a * 10 + u;
    }
    ans.insert(a);
}
void solve() {
    cin >> x;
    rep(i,-9,9) rep(j,0,9) {
        check(i,j);
    }
    cout << *ans.lower_bound(x) << "\n";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}

标签:return,int,rep,long,abc234E,等差数列,数位
From: https://www.cnblogs.com/chenfy27/p/18069439

相关文章

  • 线段树维护区间等差数列
    线段树维护区间等差数列我们采用用两个懒标记分别维护等差数列首项k和公差d维护时有个细节是假如我有左右两个区间需要合并信息时我们对于左边还是k和d但是对于右边信息此时k应该变成k+len*d,公差还是dlen表示的是右边区间长度牛牛的等差数列#include......
  • [蓝桥杯 2019 省 B] 等差数列
    实际上这道题不需要先排序再求gcd,因为无论是哪两项之前作差,都不会影响最后的gcd的结果。因为公差是从a2-a1开始算的,因此i=1时要特殊处理,不能把a1-0计入贡献,否则会算出错误的gcd。即作差时不要加上a1-0,统计最值时不要漏掉a1#include<iostream>#include<stdio.h>#include<a......
  • 数位dp板子(待补充)
    #include<iostream>#include<vector>#include<algorithm>#include<math.h>#include<string>#include<string.h>#include<iomanip>#include<map>#include<queue>usingnamespacestd;typedeflonglongll;......
  • 数位DP 学习笔记
    什么是数位DP数位dp是与数字相关的一类计数问题。这这类问题中,一般给定一些限制条件,求满足第\(K\)小的数是多少,或者求区间\([L,R]\)内有多少个满足条件的数。本文主要讲述如何解决求区间\([L,R]\)内有多少个满足条件的数这一类问题。为什么要用数位dp对于上述问题,如果......
  • 花神的数论题(数位dp)
    花神的数论题题目描述设\(\text{sum}(i)\)表示\(i\)的二进制表示中\(1\)的个数。给出一个正整数\(N\),花神要问你\(\prod_{i=1}^{N}\text{sum}(i)\),也就是\(\text{sum}(1)\sim\text{sum}(N)\)的乘积。数据范围\(1\leN\le10^{15}\)。解法首先我们要......
  • 所有十进制数位中不含2的正整数的倒数和
    \(x\ge1\),首先证明个简单的引理:\[\frac1x>\frac9{10}(\sum_{i=0}^9\frac1{10x+i}-\frac1{10x+2})\]不妨设\[f(x)=\frac1x((\sum\limits_{i=0}^9\frac1{10x+i})-\frac1{10x+2})\\f(x)=\frac{4536+211284x+2812995x^2+17430700x^3+59386250x^4+11......
  • 数位 DP 做题记录
    数位DP数位DP的常见套路就是记录当前到哪一位,是否抵着上界,转移时枚举当前可以填哪些数,做一遍记忆化搜索。P3413SAC#1-萌数题意:求\([l,r]\)中有多少个数中含有回文子串。思路:如果存在回文子串,那么必然有相邻两位相同或者间隔一位相同,在数位DP时额外记录前2位就可以......
  • 牛牛的等差数列(树状数组,区间加等差数列、区间求和)
    https://ac.nowcoder.com/acm/contest/5157/C区间加等差数列,区间求和树状数组,二阶差分\(b_i=a_i-a_{i-1}\)\(c_i=b_i-b_{i-1}\)\[\sum_{i=1}^na_i=\sum_{i=1}^n\sum_{j=1}^ib_j=\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^jc_k\\=\sum_{k=1}^nc_k\sum_{i,j}[k\......
  • 数位DP的一般方法
    数位DP?数位DFS!P2657[SCOI2009]windy数-洛谷|计算机科学教育新生态(luogu.com.cn)不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。windy想知道,在a和b之间,包括a和b,总共有多少个windy数?我们使用DFS解决。数位DFS要设计好状态,考虑好哪些条件会......
  • 数位dp笔记
    数位dp学习笔记数位dp的问题题型一般是给定一个闭区间[L,R],求这个区间中满足“某种条件”的数的个数的总数对于这类问题,我们首先统计[L,R]范围的满足条件的数字转化成统计[1,N]内满足条件的数字的数量那么ans[L,R]=ans[1,R]-ans[1,L-1];先将n转换成字符串str,使用记忆化搜索......