Easy 与 Hard 的唯一区别是 Tn,以及字符集的范围。 Easy, Hard 是 EX 的子问题,若能通过 EX,在做简单修改后,必能通过 Easy, Hard。

Tokitsukaze 在古老的遗迹中找到一张破旧的卷轴,上面写着的一串长度为 n 的数字正是打开遗迹深处宝箱的密码。虽然卷轴上的一些数字已经模糊不清,但 Tokitsukaze 可以根据从世界各地打听到关于密码的情报来还原出真正的密码。令密码为整数 x,情报如下:

  • 情报1. x 没有前导 0。
  • 情报2. x 是 8 的倍数。
  • 情报3. Tokitsukaze 获得了另一个长度为 n 的整数 y,密码 x 满足 x≤y。
  • 情报4. 在模糊不清的数字中,Tokitsukaze 知道其中一些数位上的数字是相同的,她会将这些数位使用小写字母标记出来,标记着相同字母的数位上的数字一定相同,标记着不同字母的数位上的数字一定互不相同;而另一些数字没有任何情报,它可能是 '0' 到 '9' 中的任意一个,这种数字 Tokitsukaze 会将它们用下划线 '_' 标记出来。

输入格式

第一行包含一个整数 T (1≤T≤100),表示 T组测试数据。

对于每组测试数据:

  • 第一行包含一个整数 n (1≤n≤9),表示密码的长度。
  • 第二行包含一个长度为 n 的字符串 s,仅包含 '0' 到 '9', 'a', 'b', 'c', 'd' 以及 '',并且保证 '' 最多只会出现一次。
  • 第三行包含一个长度为 n 的非负整数 y,保证 y 不包含前导 0。

输出格式

对于每组测试数据,输出一个整数,表示不同的密码数量对 10^9+7 取模后的结果。

示例1

输入
5
2
10
99
2
16
99
2
16
15
2
0a
10
2
bb
99
输出
0
1
0
0
1

示例2

输入
5
2
cd
99
2
a_
99
1
_
9
9
abcd_abcd
999999999
9
9b2d_bc8d
999999999
输出
10
11
2
5600
1040

题目分析

枚举

代码实现

#include <iostream>
#include <unordered_set>
using namespace std;
using LL = long long;
const int MOD = 1e9 + 7;

int t, n;
LL y;
string s;
bool check(LL num, LL y) {
    if(s.length() != n) return 0;
    if(num > y) return 0;
    return !((num
}
void solve() {
    LL cnt = 0;
    unordered_set <LL> st;
    cin >> n >> s >> y;
    for(int a = 0; a <= 9; ++a) {
        for(int b = 0; b <= 9; ++b) {
            if(b == a) continue;
            for(int c = 0; c <= 9; ++c) {
                if(a == c || b == c) continue;
                for(int d = 0; d <= 9; ++d) {
                    if(a == d || b == d || c == d) continue;
                    for(int _ = 0; _ <= 9; ++_) {
                        LL num = 0;
                        for(auto& ch : s) {
                            if(ch == 'a') num = num * 10 + a;
                            else if (ch == 'b') num = num * 10 + b;
                            else if (ch == 'c') num = num * 10 + c;
                            else if (ch == 'd') num = num * 10 + d;
                            else if (ch == '_') num = num * 10 + _;
                            else num = num * 10 + (ch - '0');
                            if(n != 1 && !num) break;
                        }
                        if(n != 1 && !num) continue;
                        if(check(num, y)) {
                            cnt = (cnt + (st.find(num) == st.end()))
                            st.insert(num);
                        }
                    }
                }
            }
        }
    }
    cout << cnt << '\n';
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) solve();
    return 0;
}
分类: EnumString

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status