2 条题解
-
2njnu19190132 LV 9 @ 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
-
22021-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