专栏文章

题解：SP10649 MYQ10 - Mirror Number

LL0_0
SP10649题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miot1rs7
此快照首次捕获于
2025/12/03 00:41
3 个月前
此快照最后确认于
2025/12/03 00:41
3 个月前
查看原文
Mirror Number是只有数字 0,1,80,1,8 的回文数字，更严谨的定义是：
定义 Mirror Number 是一个自然数 nn，满足：设 n=a0+10a1+102a2+⋯+10mam, m∈N,ai∈{0,1,2,3,4,5,6,7,8,9} (∀0≤i≤m∧i∈N),n=a_0+10a_1+10^2a_2+\cdots+10^ma_m,\ m\in\N,a_i\in\{0,1,2,3,4,5,6,7,8,9\}\ (\forall 0\le i\le m\land i\in\N), 那么对于任意 0≤i≤m∧i∈N0\le i\le m\land i\in\N，有 ai∈{0,1,8}a_i\in\{0,1,8\}，且 ai=am−ia_i=a_{m-i}。
设 dp[i] 是位数为 i 的 Mirror Number 的数量（没有前导零，所以这里 00 的位数是 00），可以推出 dpi={2×3⌈i/2⌉−1for i>01otherwisedp_i=\begin{cases}2\times 3^{\lceil i/2\rceil-1}&\text{for}\ i>0\\1&\text{otherwise}\end{cases}
接下来考虑计算答案，定义一个函数 get(x) 表示区间 [0,x] 内 Mirror Number 的数量，如果 x=0x=0，那么直接返回 11。否则，首先考虑位数小于 xx 的位数 len\mathrm{len} 的数，它们对返回值的贡献是 ∑i=0len−1dpi\displaystyle\sum_{i=0}^{\mathrm{len}-1}dp_i；然后考虑位数为 len\mathrm{len} 的数，从最高位（第 11 高位）开始，枚举到第 ⌈len/2⌉\lceil \mathrm{len}/2\rceil 高位，对于枚举的第 ii 高位，从小到大填 0,1,80,1,8 中的数字，在填的数字小于 xx 的第 ii 高位数字 xix_i 时，将答案增加 3⌈r/2⌉3^{\lceil r/2\rceil}，其中 r=len−2(i+1)r=\mathrm{len}-2(i+1)，然后，如果填数字到大于 xix_i 时，直接返回答案，否则将这个填的数字拼接到一个新的数字 ss（初始为 00）的末尾，然后继续枚举数位，当枚举结束后，如果 lenlen 是奇数，将 ss 的除去最后一位的数字的反转拼接到 ss 末尾，否则将 ss 整体反转得到的数字拼接到 ss 末尾，如果发现 s≤xs\le x，则将答案增加 11，因为在枚举数位的时候没有统计这个数字的答案。
还需要一个函数 check(x)，检查 xx 是不是 Mirror Number，这直接根据定义去判断即可。
当输入 a,ba,b 时，最终答案等于 get(b)-get(a)+check(a)，由于题目范围中 Mirror Number 的自由度不超过 2222，所以 get 返回值不超过 3223^{22}，可以用 long long 返回。
时间复杂度是 O(Tlg⁡a+Tlg⁡b)=O(Tlg⁡b)\mathcal{O}(T\lg a+T\lg b)=\mathcal{O}(T\lg b)。（耗时 0.43s⁡0.43\operatorname{s}）
代码：
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T, nxt[9] = {1, 8, 0, 0, 0, 0, 0, 0, 10};
string a, b;
ll dp[45];
bool check(string x){
	for(int i=0;i*2<=x.length();i++){
		if (x[i] != x[x.length()-i-1] || (x[i] != '0' && x[i] != '1' && x[i] != '8'))
			return 0;
	}
	return 1;
}
ll pow3(ll y){
    return y?pow3(y-1)*3:1;
}
ll get(string x){
    if (x.length() == 1 && x[0] == '0') return 1;
    // [0, x]
    ll len = x.length(), ans = 0;
    // 小于len位
    for (int i=0;i<len;i++) ans += dp[i];
    // 等于len位
    string s;
    for(int i=0;i*2+1<=len;i++){
    	int num = x[i] - '0', c = i==0;
    	while(c < num){
    		// 已用长度：i+1 => ans += 3^(len-2*(i+1) )
    		if (2*i+1 == len) ans++;
    		else {
                int re = len - 2*(i+1);
                ans += pow3(re/2 + re%2);
            }
    		c = nxt[c];
		}
        if (c == num) s += x[i];
		else return ans;
	}
    string t = s.substr(0, s.length() - len%2);
    reverse(t.begin(), t.end());
    s += t;
    ans += (s <= x);
    return ans;
}

int main(){
    cin>>T;
    dp[0] = 1;
    for(int i=1;i<=44;i++){
        dp[i] = 2 * pow3(i/2 + i%2 - 1);
    }
    while(T--){
        cin>>a>>b;
        cout << get(b) - get(a) + check(a) << endl;
    }
}
（后记：代码调试了很久）

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...