A.
和洛谷上的删数思路一致,后者是找峰顶,这个是找谷底
从前到后枚举每一位与要添加的数比大小,如果要添加的数 <= 该位的数,就继续枚举,否则就将这个数添加在其前面
B.
需要移动的步数 = 两个点所在的层数之差的绝对值,只要计算出所在层数就可以
一开始没想明白怎么算这个层数,先把每个点都变换到了整个图的左下角的1/4块
if x > n / 2, x = n + 1 - x; if y > n / 2, y = n + 1 - y;
两个点 P (x1,y1) Q(x2,y2);
ans = abs ( min (x1,y1) - min(x2, y2) )
C.
b[i] <= a[i-1] && b[i] <= a[i]
所以答案就是b[i] = min (a[i[, a[i-1]) ,初始化 a[0] = a[n+1] = 1e9 + 1;
D.
E.
从高到低枚举每一位
首先考虑如何求得一个数字在该数组的位置
对于一个数字 abcde
从 0 开始计数,其所处位置为 a * 9^4 + b * 9^3 + c * 9^2 + d * 9^1 + e * 9^0 + 1
其中,如果 a >= 4,则在计算位置时 a -= 1,因为不能包含4这个数,bcde以此类推
对上面式子进一步解释,也就是其位置 = 以 0 ~ a-1 开头的不含4的五位数个数 + 以 0 ~ b-1 开头的不含4的四位数个数+ 三位 + 两位 + 一位 + 1
如果是从 1 开始计数,那么就 - 1 得到 a * 9^4 + b * 9^3 + c * 9^2 + d * 9^1 + e * 9^0
只需要将这个过程倒推就可以得到对应位置的数字
每次另 k 对 9 取余,所得即为该位的数字,注意,如果余数 >= 4 ,需要 +1
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> typedef long long LL; using namespace std; int T; LL k; int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>T; while(T--) { string a = ""; cin>>k; while(k) { int t = k % 9; if(t >= 4) t++; a += '0' + t; k /= 9; } int siz = a.size(); reverse(a.begin(),a.end()); cout<<a<<'\n'; } return 0; }View Code
另一个正向推的解法
从最高位向最低位依次枚举1 - 9, 不包含4, 一定是从小到大枚举
变量poi 记录第 i 位数字,初始 poi = 0
那么对于第 i 位数字 j,以它为开头的不含 4 的数字个数为 9^(i-1),如果 k > 9^(i-1),则 k -= 9^(i-1), poi = j ,
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<bits/stdc++.h> typedef long long LL; using namespace std; int T; LL s[20]; LL k; LL ans; int main() { ios::sync_with_stdio(false); cin.tie(0); s[0] = 1; s[1] = 9; for(int i = 2;i <= 17;i++) s[i] = 9 * s[i-1]; cin>>T; while(T--) { cin>>k; k++; ans = 0; for(int i = 15;i >= 1;i--) { int now = 0; for(int j = 1;j <= 9;j++) { if(j == 4) continue; if(k > s[i-1]) { k -= s[i-1]; now = j; } } ans = ans * 10 + now; } cout<<ans<<'\n'; } return 0; }View Code
同时4也可以变成任何0 - 9 的数
标签:int,LL,862,cin,long,codeforces,枚举,ans,round From: https://www.cnblogs.com/xxx3/p/17289102.html