P9080 [PA 2018] Nowy kontrakt题目描述题目译自 PA 2018 Runda 2 Nowy kontrakt。给定一个长度为N NN的正整数序列a aa你需要对序列内数末尾添加数字的方法使序列严格单调递增你的目标是最小化添加数字的次数。在数a aa后添加数字t tt即为a ← a × 10 t a \gets a \times 10 ta←a×10t,其中t ∈ { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } t \in \{0,1,2,3,4,5,6,7,8,9\}t∈{0,1,2,3,4,5,6,7,8,9}输入格式第一行一个整数N NN表示序列长度。第2 22行至N 1 N1N1行每行一个数第i ii行表示序列中第i − 1 i-1i−1个数。输出格式一行一个整数表示最小操作次数。输入输出样例 #1输入 #13 8 5 13输出 #12说明/提示样例 1 解释对第2 22个数字和第3 33个数字分别添加一个数字即a 2 ← a 2 × 10 7 a_2 \gets a_2 \times 10 7a2​←a2​×107a 3 ← a 3 × 10 3 a_3 \gets a_3 \times 10 3a3​←a3​×103。 得到的新序列为( 8 , 57 , 133 ) (8,57,133)(8,57,133)是一个严格单调递增序列。操作次数为2 22还有其他的操作次数为2 22的方法但是不存在操作次数为1 11的方法。数据范围本题采用捆绑测试对于100 % 100\%100%的数据1 ≤ N ≤ 200000 1 \le N \le 2000001≤N≤2000001 ≤ a i ≤ 10 9 1 \le a_i \le 10^91≤ai​≤109C实现#includebits/stdc.husingnamespacestd;intn;longlongans;string a,b;intmain(){scanf(%d,n);cina;for(inti2;in;ab,i){cinb;if(a.size()b.size()||(a.size()b.size()ab))continue;if(ab){ans;b0;continue;}if(a.size()b.size()){if(a.substr(0,b.size())b){ansa.size()-b.size()1;bstring(a.size()-b.size()1,0);}elseif(a.substr(0,b.size())b){string ta.substr(b.size());if(t.find_first_not_of(9)string::npos){ansa.size()-b.size()1;bstring(a.size()-b.size()1,0);}else{ansa.size()-b.size();ba;for(intjb.size()-1;j0;j--){if(b[j]9)b[j]0;else{b[j];break;}}}}else{ansa.size()-b.size();bstring(a.size()-b.size(),0);}continue;}ansa.size()-b.size()1;bstring(b.size()1-b.size(),0);}printf(%lld,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容