本文涉及的基础知识点
本博文代码打包下载
C++二分查找
[JOIG 20
24] たくさんの数字 / Many Digits
题目形貌
JOI 高中的 Aoi 决定在 N × N N\times N N×N 的表格中写下 N 2 N^2 N2 个非负整数。具体地，给定两个长度为 N N N 的序列 A , B A,B A,B，她会在第 i i i 行第 j j j 列的格子上写下 A i + B j A_i+B_j Ai+Bj。
Aoi 想知道写出这些数必要多少个字符。也就是说，你必要求出写出的 N 2 N^2 N2 个整数在十进制下的位数的和。
输入格式
第一行输入一个整数 N N N。
第二行输入 N N N 个整数 A 1 , A 2 , … , A N A_1,A_2,\ldots,A_N A1,A2,…,AN。
第三行输入 N N N 个整数 B 1 , B 2 , … , B N B_1,B_2,\ldots,B_N B1,B2,…,BN。
输特殊式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
样例输出 #1
样例 #2
样例输入 #2
样例输出 #2
样例 #3
样例输入 #3
样例输出 #3
样例 #4
样例输入 #4
- 7436981378 523812834 456708479 413571178 506402783 5982710
- 09 52393662440120
- 310
- 4 501634329 506090236 527167431 485527116 439442403 568364549
提示
【样例解释 #1】
+ + + 20
\textbf{20
} 20
2 \textbf{2} 2 21 \textbf{21} 21 97 \textbf{97} 97 117 117 117 99 99 99 118 118 118 79 \textbf{79} 79 99 99 99 81 81 81 10
0 10
0 10
0 7 \textbf{7} 7 27 27 27 9 9 9 28 28 28 未加粗字体为 Aoi 填写的内容。
例如，第 1 1 1 行第 1 1 1 列的方格中的整数为 A 1 + B 1 = 97 + 20
= 117 A_1 + B_1 = 97 + 20
= 117 A1+B1=97+20
=117，位数为 3 3 3。第 3 3 3 行第 2 2 2 列的方格中的整数为 A 3 + B 2 = 7 + 2 = 9 A_3 + B_2 = 7 + 2 = 9 A3+B2=7+2=9，位数为 1 1 1。
9 9 9 个数的位数分别为 3 , 2 , 3 , 2 , 2 , 3 , 2 , 1 , 2 3, 2, 3, 2, 2, 3, 2, 1, 2 3,2,3,2,2,3,2,1,2，故位数之和为 3 + 2 + 3 + 2 + 2 + 3 + 2 + 1 + 2 = 20
3 + 2 + 3 + 2 + 2 + 3 + 2 + 1 + 2 = 20
3+2+3+2+2+3+2+1+2=20
。
该样例满意子任务 2 , 3 , 8 2,3,8 2,3,8 的限定。
【样例解释 #2】
+ + + 1 \textbf{1} 1 2 \textbf{2} 2 3 \textbf{3} 3 4 \textbf{4} 4 8 \textbf{8} 8 9 9 9 10
10
10
11 11 11 12 12 12 97 \textbf{97} 97 98 98 98 99 99 99 10
0 10
0 10
0 10
1 10
1 10
1 996 \textbf{996} 996 997 997 997 998 998 998 999 999 999 10
00 10
00 10
00 9995 \textbf{9995} 9995 9996 9996 9996 9997 9997 9997 9998 9998 9998 9999 9999 9999 未加粗字体为 Aoi 填写的内容。
例如，第 2 2 2 行第 3 3 3 列的方格中的整数为 A 2 + B 3 = 97 + 3 = 10
0 A_2 + B_3 = 97 + 3 = 10
0 A2+B3=97+3=10
0，位数为 3 3 3。第 4 4 4 行第 2 2 2 列的方格中的整数为 A 4 + B 2 = 9995 + 2 = 9997 A_4 + B_2 = 9995 + 2 = 9997 A4+B2=9995+2=9997，位数为 4 4 4。
可以得出答案为 46
46
46
。
该样例满意子任务 2 , 6 , 7 , 8 2,6,7,8 2,6,7,8 的限定。
【样例解释 #3】
方格中仅有一个整数 1 0 9 10
^9 10
9，位数为 10
10
10
，故位数之和为 10
10
10
。
该样例满意子任务 1 , 2 , 4 , 5 , 8 1,2,4,5,8 1,2,4,5,8 的限定。
【样例解释 #4】
该样例满意子任务 2 , 5 , 8 2,5,8 2,5,8 的限定。
【数据范围】
- 1 ≤ N ≤ 1.5 × 1 0 5 1\le N\le 1.5\times 10
^5 1≤N≤1.5×10
5；
- 1 ≤ A i ≤ 999 , 999 , 999 ( 1 ≤ i ≤ N ) 1\le A_i\le 999,999,999(1\le i\le N) 1≤Ai≤999,999,999(1≤i≤N)；
- 1 ≤ B j ≤ 999 , 999 , 999 ( 1 ≤ j ≤ N ) 1\le B_j\le 999,999,999(1\le j\le N) 1≤Bj≤999,999,999(1≤j≤N)。
【子任务】
- （ 5 5 5 分） N = 1 N=1 N=1；
- （ 11 11 11 分） N ≤ 20
00 N\le 20
00 N≤20
00；
- （ 15 15 15 分） A i ≤ 20
00 ( 1 ≤ i ≤ N ) A_i\le 20
00(1\le i\le N) Ai≤20
00(1≤i≤N)， B j ≤ 20
00 ( 1 ≤ j ≤ N ) B_j\le 20
00(1\le j\le N) Bj≤20
00(1≤j≤N)；
- （ 8 8 8 分） 1 0 8 ≤ A i ≤ 5 × 1 0 8 ( 1 ≤ i ≤ N ) 10
^8\le A_i\le 5\times 10
^8(1\le i\le N) 10
8≤Ai≤5×10
8(1≤i≤N)， 1 0 8 ≤ B j ≤ 5 × 1 0 8 ( 1 ≤ j ≤ N ) 10
^8\le B_j\le 5\times 10
^8(1\le j\le N) 10
8≤Bj≤5×10
8(1≤j≤N)；
- （ 22 22 22 分） 1 0 8 ≤ A i ( 1 ≤ i ≤ N ) 10
^8\le A_i(1\le i\le N) 10
8≤Ai(1≤i≤N)， 1 0 8 ≤ B j ( 1 ≤ j ≤ N ) 10
^8\le B_j(1\le j\le N) 10
8≤Bj(1≤j≤N)；
- （ 12 12 12 分） A i ≤ 1.5 × 1 0 5 ( 1 ≤ i ≤ N ) A_i\le 1.5\times 10
^5(1\le i\le N) Ai≤1.5×10
5(1≤i≤N)， B j = j ( 1 ≤ j ≤ N ) B_j = j(1\le j\le N) Bj=j(1≤j≤N)；
- （ 13 13 13 分） B j = j ( 1 ≤ j ≤ N ) B_j=j(1\le j\le N) Bj=j(1≤j≤N)；
- （ 14 14 14 分）无附加限定。
二分查找
对a，排序。
通过ib 罗列b。
和ib组成的项，i位数及以下的数目c：
{ a . l o w e r ( 1 0 i − i b ) a . b e g i n ( ) i ∈ [ 1 , 9 ] 0 i = = 0 a . s i z e ( ) i = = 10
\begin{cases} a.lower(10
^i-ib)_a.begin() & i \in[1,9] \\ 0 & i == 0 \\ a.size() & i == 10
\\ \end{cases} ⎩ ⎨ ⎧a.lower(10
i−ib)a.begin()0a.size()i∈[1,9]i==0i==10
代码
焦点代码
- #include <iostream>#include <sstream>#include <vector>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<string>#include<algorithm>#include<functional>#include<queue>#include <stack>#include<iomanip>#include<numeric>#include <math.h>#include <climits>#include<assert.h>#include<cstring>#include <bitset>using namespace std;template<class T = int>vector<T> Read(int n,const char* pFormat = "%d") { vector<T> ret(n); for(int i=0;i<n;i++) { scanf(pFormat, &ret[i]); } return ret;}template<class T = int>vector<T> Read( const char* pFormat = "%d") { int n; scanf("%d", &n); vector<T> ret; T d; while (n--) { scanf(pFormat, &d); ret.emplace_back(d); } return ret;}string ReadChar(int n) { string str; char ch; while (n--) { do { scanf("%c", &ch); } while (('\n' == ch)); str += ch; } return str;}template<class T1,class T2>void ReadTo(pair<T1, T2>& pr) { cin >> pr.first >> pr.second;}template<class INDEX_TYPE>class CBinarySearch{public: CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex, INDEX_TYPE tol = 1) :m_iMin(iMinIndex), m_iMax(iMaxIndex), m_iTol(tol) {} template<class _Pr> INDEX_TYPE FindFrist(_Pr pr) { auto left = m_iMin - m_iTol; auto rightInclue = m_iMax; while (rightInclue - left > m_iTol) { const auto mid = left + (rightInclue - left) / 2; if (pr(mid)) { rightInclue = mid; } else { left = mid; } } return rightInclue; } template<class _Pr> INDEX_TYPE FindEnd(_Pr pr) { INDEX_TYPE leftInclude = m_iMin; INDEX_TYPE right = m_iMax + m_iTol; while (right - leftInclude > m_iTol) { const auto mid = leftInclude + (right - leftInclude) / 2; if (pr(mid)) { leftInclude = mid; } else { right = mid; } } return leftInclude; }protected: const INDEX_TYPE m_iMin, m_iMax, m_iTol;};class Solution {public: long long Ans(vector<int>& a, vector<int>& b) { const int N = a.size(); sort(a.begin(), a.end()); long long ans = 0; for (const auto& ib : b) { int cnt[11] = { 0 }; cnt[10
- ] = a.size(); int mul = 1; for (int i = 1; i < 10
- ; i++) { mul *= 10
- ; cnt[i] = lower_bound(a.begin(), a.end(), mul - ib) - a.begin(); } for (long long i = 1; i <= 10
- ; i++) { ans += (cnt[i] - cnt[i - 1]) * i; } } return ans; }};int main() {#ifdef _DEBUG freopen("a.in", "r", stdin);#endif // DEBUG int n; cin >> n ; auto a = Read<int>(n); auto b = Read<int>(n); #ifdef _DEBUG Out(a, "a="); Out(b, ",b=");#endif auto res = Solution().Ans(a,b); cout << res << endl; return 0;}
- TEST_METHOD(TestMethod11) { a = { 97,79,7 }, b = { 20
- ,2,21 }; auto res = Solution().Ans(a,b); AssertEx(20
- LL, res); } TEST_METHOD(TestMethod12) { a = { 8,97,996,9995 }, b = { 1,2,3,4 }; auto res = Solution().Ans(a, b); AssertEx(46
- LL, res); } TEST_METHOD(TestMethod13) { a = { 500000000 }, b = { 500000000 }; auto res = Solution().Ans(a, b); AssertEx(10
- LL, res); } TEST_METHOD(TestMethod14) { a = { 436981378,523812834,456708479,413571178,506402783,5982710
- 09,523936624 }, b = { 40120
- 310
- 4,501634329,506090236,527167431,485527116,439442403,568364549 }; auto res = Solution().Ans(a, b); AssertEx(46
- 3LL, res); }
我想对大家说的话工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操纵有用学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙，那算法就是他的是睛失败+反思=成功 成功+反思=成功 视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的解说。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试情况
操纵体系：win7 开发情况： VS20
19 C++17
大概 操纵体系：win10
开发情况： VS20
22 C++17
如无特殊阐明，本算法用**C++**实现。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
