2020 is a special integer, it’s formed of two same integers (20 and 20).
We call a number is a good number, if and only if it can be formed of two same integers(without leading zero).
For example: 2020 11, 19991999 are good numbers, but 303, 1122, 1221 are not.
Now you need to count the number of good numbers in
[
1
,
N
]
[1,N]
[1,N]
題意
給出一個 <=1e18 的n 求從1到n中有多少個數是由兩個相同的數構成的，
思路
輸入字串寫出打表程式，發現
奇數時答案為s.size()/2 個9
偶數時把字串分成兩半，如果后面的數大于等于前面的，就輸出前面的數，否則把字串轉換為數減一后輸出，
代碼
打表代碼
#include <bits/stdc++.h>
using namespace std;
bool ok(string s)
{
int len = s.size();
if(len & 1) return false;
string now1 = "" , now2 = "";
for(int i=0;i<len/2;i++)
now1 += s[i];
for(int i=len/2;i<len;i++)
now2 += s[i];
// cout<<now1<<" "<<now2<<endl;
return now1 == now2;
}
int main()
{
//ok("1111");
int ans = 0;
for(int i=1;i<=10000;i++)
{
stringstream ss;
string s;
ss<<i;
ss>>s;
if(ok(s)) ans++;
cout<<i<<" "<<ans<<endl;
}
}
AC代碼
#include <bits/stdc++.h>
using namespace std;
bool ok(string s)
{
int len = s.size();
if(len & 1) return false;
string now1 = "" , now2 = "";
for(int i=0;i<len/2;i++)
now1 += s[i];
for(int i=len/2;i<len;i++)
now2 += s[i];
// cout<<now1<<" "<<now2<<endl;
return now1 == now2;
}
int main()
{
string s;
cin>>s;
int len = s.size();
if(len & 1)
{
int l = len/2;
for(int i=0;i<l;i++) cout<<"9";
}
else
{
string now1 = "" , now2 = "";
for(int i=0;i<len/2;i++)
now1 += s[i];
for(int i=len/2;i<len;i++)
now2 += s[i];
if(now2>=now1) cout<<now1<<"\n";
else
{
stringstream ss;
ss<<now1;
int n;
ss>>n;
n--;
cout<<n<<"\n";
}
}
}
/*
1000000
999
10000
99
100
9
*/
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/241465.html
標籤：其他