2 条题解

  • 2
    @ 2021-06-02 18:42:44

    有点贪心的意思,先考虑全由99组成,比如495=99+99+99+99+99;然后在看一般情况:1096=9911+7,转化为=994+700=99*3+799。就可以进一步看十位个位与其他高位的关系。

    #define method_1
    
    #ifdef method_1
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    #include<ctime>
    #include<cstring>
    #include<string>
    #include<queue>
    #include<set>
    #include<map>
    #include<vector>
    #include<bitset>
    #include<stack>
    using namespace std;
    
    #define D(x) cout<<#x<<" = "<<x<<"  "
    #define E cout<<endl
    #define rep(i,s,t) for(int (i)=(s);(i)<=(t);(i)++)
    #define rep0(i,s,t) for(int i=(s);i<(t);i++)
    #define rrep(i,t,s) for(int i=(t);i>=(s);i--)
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    const int N=1e5+5;
    const int INF=0x3f3f3f3f;
    const double pi=acos(-1.0);
    
    int T,ans=0;
    ll n;
    
    void output(){
    //  cout<<res;
    }
    void solve(){
        cin>>n;
        ll k=n/100;
        ll p=n%100;
        if(p+1>=100-k)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    int main(){
        //freopen("data.in","r",stdin);
        cin>>T;
        while(T--)
        solve();
        output();
        return 0;
    }
    #endif
    #ifdef method_2
    
    #endif
    
    
    
    
    
  • 2
    @ 2021-05-27 23:00:12

    D题题解:
    对于9900以上的数总是成立的,因为\(x=99+99+...+\overline{99ab}\)
    对于9900以下的数,用类似筛法的方法,若\(x,y\)是满足性质的数,而\(x+y\)也是满足性质的。这样的
    方法是\(O(N^2)\)的,但常数很小。

    (不过比赛中看到了更有趣的方法,以上方法仅供参考)
    Code:

    #include<bits/stdc++.h>
    using namespace std;
    int dp[20000];
    vector<int> vec;
    int main()
    {
        for(int i=1;i<=9999;i++)
        {
            int cnt = 0;
            int x = i;while(x) 
            {
                if(x%10==9) cnt++; else cnt = 0;
                x/=10; 
                if(cnt == 2) vec.push_back(i); // 筛出所有含99的数
            }
        }
        dp[0]=1;
        for(int i=0;i<=9900;i++)
        {
            if(dp[i] == 0) continue;
            for(int j=0;j<vec.size();j++) dp[i+vec[j]] = 1; 
            //若i满足,vec[j]满足,则i+vec[j]也满足。
        }
        int t;cin>>t;
        while(t--)
        {
            long long int x; cin>>x;
            if(x>9900 || dp[x] == 1) cout<<"YES\n";else cout<<"NO\n"; 
        }
        return 0;
    }
    
    
  • 1

信息

ID
1254
难度
6
分类
动态规划 | 数论 点击显示
标签
递交数
209
已通过
32
通过率
15%
被复制
4
上传者