题意

这题目描述真的考语文呢,

给数组A(0-index),B

1. 给B排序去重
2. 遍历B,对每个值,找A中十进制表示中包含该值的下标,和A中的那个值
3. 除此以外还有,还要输出每个值,输出下标的个数,在找不到时不输出,还要输出所有值的总个数
4. 所以输出格式是 总数, [B中的值, 下标个数, [A中下标, A中的值,] ]

范围, 每个值 非负且不大于0xffffffff

方法

数值转换成字符串

我们把数组用 sort 进行排序,并利用b[i] != b[i-1]忽略掉重复.

此后就是朴素的实现题意即可

先遍历数组$BB$B,每次遍历数组$AA$A,如果满足字符包含，则记录下标。

对于每一个B的遍历,在统计完下标后再进行输出转换。

在所有统计完后就能得到输出总数了。

其中十进制包含我们使用sprintf完成数字到字符串的转换,strstr来完成字符串包含关系的检测

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i = (a);i<(b);i++)

bool vinv(ll v0,ll v1){ // v0 是否在 v1 中
    char s0[20];
    char s1[20];
    rep(i,0,20)s0[i]=s1[i]=0;
    sprintf(s0,"%lld",v0); // 转换成字符串
    sprintf(s1,"%lld",v1); // 转换成字符串
    return strstr(s1,s0) != NULL; // 字符串搜索
}

int main(){
    int n,m;
    while(~scanf("%d",&n)){
        vector<ll> a;
        rep(i,0,n){
            ll v;
            scanf("%lld",&v);
            a.push_back(v); // 读入a
        }
        scanf("%d",&m);
        vector<ll> b;
        rep(i,0,m){
            ll v;
            scanf("%lld",&v);
            b.push_back(v); // 读入b
        };
        sort(b.begin(),b.end());
        vector<ll> ans;
        rep(i,0,m){
            if(i > 0 && b[i] == b[i-1])continue; // 忽略重复
            vector<ll>idxs = {};
            rep(j,0,n){
                if(vinv(b[i],a[j])){
                    idxs.push_back(j);
                }
            }
            if(idxs.size()){
                ans.push_back(b[i]);
                ans.push_back(idxs.size());
                for(auto idx:idxs){
                    ans.push_back(idx);
                    ans.push_back(a[idx]);
                }
            }
        }
        printf("%d",int(ans.size()));
        for(auto v: ans){
            printf(" %lld", v);
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

设数组B的大小为m,数组A的大小为n

时间复杂度: 最开始对数组B排序为$O(m\cdot log(m\left)\right)O(m\; \backslash cdot\; log(m))$O(m⋅log(m)),对于查找满足条件的先循环数组B再每次从A中查找,所以是双重循环,所以时间复杂度为$O\left(mn\right)O(mn)$O(mn)

空间复杂度: 空间一部分是用在读入数据$O(m+n)O(m+n)$O(m+n),另一部分是记录结果,而结果最坏情况是两两都匹配,所以空间复杂度也是$O\left(mn\right)O(mn)$O(mn)

基于十进制比较

其中, 判断包含关系的通过十进制的移位来比较

以样例数据中,3 是否包含在 453456中为例

需要注意的是，0需要特殊处理。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i = (a);i<(b);i++)

bool vinv(ll v0,ll v1){ // v0 是否在 v1 中
    if(v0 == 0){ // 零特殊检查
        if(v1 == 0)return true;
        while(v1 != 0){
            if(v1 % 10 ==0)return true;
            v1/=10;
        }
        return false;
    }
    
    while(v0 <= v1){
        ll b = 1; // 按位检查
        bool eq = true;
        while(b <= v0){
            if( (v0/b)%10 != (v1/b)%10 )eq = false;
            b*=10;
        }
        if(eq)return true;
        v1/=10; // 移动v1 再次对比
    }
    return false;
}

int main(){
    int n,m;
    while(~scanf("%d",&n)){
        vector<ll> a;
        rep(i,0,n){
            ll v;
            scanf("%lld",&v);
            a.push_back(v); // 读入a
        }
        scanf("%d",&m);
        vector<ll> b;
        rep(i,0,m){
            ll v;
            scanf("%lld",&v);
            b.push_back(v); // 读入b
        };
        sort(b.begin(),b.end());
        vector<ll> ans;
        rep(i,0,m){
            if(i > 0 && b[i] == b[i-1])continue; // 忽略重复
            vector<ll>idxs = {};
            rep(j,0,n){
                if(vinv(b[i],a[j])){
                    idxs.push_back(j); // 包含则记录 下标
                }
            }
            if(idxs.size()){ // 按照要求输出储存数据
                ans.push_back(b[i]); 
                ans.push_back(idxs.size());
                for(auto idx:idxs){
                    ans.push_back(idx);
                    ans.push_back(a[idx]);
                }
            }
        }
        printf("%d",int(ans.size()));
        for(auto v: ans){
            printf(" %lld", v);
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

时间复杂度: 最开始对数组B排序为$O(m\cdot log(m\left)\right)O(m\; \backslash cdot\; log(m))$O(m⋅log(m)),对于查找满足条件的先循环数组B再每次从A中查找,所以是双重循环,所以时间复杂度为$O\left(mn\right)O(mn)$O(mn)

空间复杂度: 空间一部分是用在读入数据$O(m+n)O(m+n)$O(m+n),另一部分是记录结果,而结果最坏情况是两两都匹配,所以空间复杂度也是$O\left(mn\right)O(mn)$O(mn)