http://codeforces.com/problemset/problem/899/D
题意:给你1,2,...,n,现在要求取出一对数相加为x。x需要满足:以最多个9结尾。现在给你n,求这样的数对有几个。
*例如,9099算以两个9结尾
题解:设题意的x最多以k个9结尾。
①先想到要求这个k是多少,可以发现一个特殊的数字5,50,500,...。当n<5时,k=0;当n>=5&&n>50时,k=1;当n>=50&&n<500时,k=2...也就是说x是这一样一个数:Z999......(0<=Z<=8,后面接上k个9)。
②经过第一步分解成Z个子问题之后,现在要求解子问题的数对。这个求解就可以自己总结出结论了,可以以14这个输入总结得到。
代码:
#include<bits/stdc++.h> #define debug cout<<"aaa"<<endl #define d(a) cout<<a<<endl #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define LL long long #define lson l,mid,root<<1 #define rson mid+1,r,root<<1|1 #define MIN_INT (-2147483647-1) #define MAX_INT 2147483647 #define MAX_LL 9223372036854775807i64 #define MIN_LL (-9223372036854775807i64-1) using namespace std; const int N = 100000 + 5; const int M = N * N + 5; const int mod = 1000000000 + 7; const int INF = 0x3f3f3f3f; const double eps = 1e-8; int main(){ LL n,k,temp=1,A,ans=0; cin>>n; LL num=5; //小于5的时候特判,这时候k等于9 if(n<5){ cout<<n*(n-1)/2<<endl; return 0; } //求解最多以几个9结尾 for(int i=1;i<=11;i++){ if(n<num){ k=i-1; break; } num*=10; } num=0; for(int i=1;i<=k;i++){ num=num*10+9; temp*=10; } for(int i=0;i<=8;i++){ //A就是Z999... //num是999... A=i*temp+num; if(n<(A+1)/2){ break; } else if(n>(A-1)){ ans=ans+A/2; } else{ ans=ans+(n-(A+1)/2+1); } } cout<<ans<<endl; return 0; }