深信服秋招 2023.09.20 编程题目与题解

发表于 2023-09-25 分类于笔试阅读次数：本文字数： 2.8k 阅读时长 ≈ 3 分钟

1、馍馍检测病毒

馍馍发现了一种新型网络病毒，可以隐藏在图片中，图片可以简单的看成一个\(N\times N\)的矩阵。

这个矩阵每个格子要么是白，用字符'.'表示，要么是黑，用字符'#'表示。

经过馍馍的分析，如果一张图片中包含一个特殊的\(M\times M\)的矩阵，那么这张图片可能包含病毒。我们称\(M\times M\)的矩阵为“馍馍来检测病毒的超生逼特征矩阵”。

现在告诉你一个\(N\times N\)的图片矩阵，和一个\(M\times M\)的“馍馍来检测病毒的超生逼特征矩阵”。

你需要判断该图片是否包含病毒。即"馍馍来检测病毒的超牛逼特征矩阵"通过平移可以完全重合在图片中的一个子矩阵里。

输入

第一行一个整数\(T(1\le T\le 5)\)，表示测试数据的组数。

对于每组测试数据，第一行两个整数\(N,M(1\le N,M\le 50)\)。

接下来\(N\)行，每行\(N\)个字符，用来描述待判断的图片A。

接下\(来\)M行，每行\(M\)个字符，用来描述“馍馍来检测病毒的超牛逼特征矩阵”。

输出

共\(T\)行，对于每组测试数据，如果包含，输出"Yes"，否则输出"No"(不包括引号)。

样例

输入：
2
3 2
#.#
.#.
#.#
#.
.#
4 1
....
....
....
....
#

输出：
Yes
No

解答

我们只需要枚举原矩阵的每个格子作为模板的左上角即可，然后再一一和模板矩阵比对即可完成。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=54;
char s[N][N],t[N][N];
int n,m;

int solve(){
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%s",s[i]);
    for(int i=0;i<m;i++)
        scanf("%s",t[i]);
    for(int x=0;x+m-1<n;x++){
        for(int y=0;y+m-1<n;y++){
            int ok=1;
            for(int i=0;i<m&&ok;i++)
                for(int j=0;j<m&&ok;j++)
                    if(s[x+i][y+j]!=t[i][j]) ok=0;
            if(ok) return 1;
        }
    }
    return 0;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        puts(solve()?"Yes":"No");
    }
}

2、SXF序数

一个\(N\)位的正整数，如果把它的各个数位重新排列，则可以得到一些新的\(N\)位正整数。

如果原数在所有的新数中是第\(K\)大的（降序排序的第\(K\)个）则称原数的SXF序数为\(K\)。

例如，一个\(4\)位数\(7225\)，把它的各个数位重新排列，得到的新的\(4\)位数中，最大的是\(7522\)，第二大的是\(7252\)，第三大的就是原数\(7225\)，所以\(7225\)的SXF序数为\(3\)。

现在给定一个正整数\(a\)，请计算出它的SXF序数。

输入

第一行是一个正整数\(T(1\le T\le10^4)\)，表示接下来有\(T\)组测试数据。

接下来是各组测试数据。

每组测试数据只有一行，该行仅有一个正整数\(a(1\le a\le10^9)\)，表示给定的正整数。

输出

对于每组测试数据输出一行，仅有一个整数，表示\(q\)的SXF序数。

样例

解答

前置知识：假设现在有\(m\)类元素，第\(i\)类一共有\(c_i\)个，那么这些元素组成的不同的排列数量为\(\dfrac{(c_1+c_2+\dots+c_m)!}{c_1!\cdot c_2!\cdot \dots\cdot c_m!}\)。

我们将输入的一个数\(n\)视为是一个排列\(n_1,n_2,\dots,n_d\)即可，为了计算比它字典序更大的排列数量，我们可以采取以下方法：首先假设排列的第一个元素\(p_1\)比\(n_1\)大，那么后面的元素可以随意填充，使用上面的公式就可以计算出排列的数量，枚举\(p_1\)的值，其中\(p_1\)大于\(n_1\)。计算完成后，将\(n_1\)填入\(p_1\)，接下来对\(p_2\)做类似的操作（我们这时忽略第\(1\)个位置）：枚举\(p_2\)填入的元素，其中\(p_2>n_2\)，并使用上面的公式统计排列数……一直到第\(d\)位完成。

最终，我们统计出了字典序比\(n_1,n_2,\dots,n_d\)大的排列数量，再加上\(1\)就是题目中所提到的SXF序数。

代码

#include <bits/stdc++.h>
using namespace std;

int fac[14];
int cal_per(vector<int>&a){
    int den=1,s=0;
    for(int x:a){
        den*=fac[x];
        s+=x;
    }
    int num=fac[s];
    return num/den;
}
int solve(int n){
    int ans=0;
    vector<int>d,c(10);
    for(int m=n;m;m/=10){
        d.push_back(m%10);
        ++c[m%10];
    }
    for(int i=d.size()-1;i>=0;i--){
        int w=d[i];
        for(int j=w+1;j<10;j++){
            if(c[j]>0){
                --c[j];
                ans+=cal_per(c);
                ++c[j];
            }
        }
        --c[w];
    }
    return ans+1;
}
int main(){
    fac[0]=1;
    for(int i=1;i<=11;i++)
        fac[i]=fac[i-1]*i;
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        printf("%d\n",solve(n));
    }
}

3、CWPP平台告警

深信服CWPP平台的告警事件管理页面可以按照时间顺序或者告警等级筛选用户所关注的安全事件。现在深信服CWPP平台上已经管理了\(N\)台主机，主机编号从\(1\)到\(N\)。这些主机根据运行的业务不同，各自的安全等级\(s_i\)都不相同，举例来说，作为内网网关主机的安全等级就高于作为外部公开资源数据库的主机。每一台主机还有一个安全威胁评分\(v_i\)，\(v_i\)的值越大，主机就越不安全。

为了方便运维人员，深信服CWPP平台拥有筛选管理主机并优先展示高安全等级主机的功能。

具体来讲，用户可以指定一个告警闯值水位线\(h\)，筛选出威胁评分高于该闽值水位线的主机，即筛选出\(h\le v_i\)的主机。然后为了方便用户查看最关注的高安全等级主机，深信服CWPP平台在筛选后还会将安全等级\(s_i\)最高的主机展示到第一条告警的位置。

虽然主机的安全等级可以在系统运行前就进行配置，但是主机的安全威胁评分\(v_i\)是实时进行更新和维护的。

所以要求你的算法具有可维护性，即需要支持对于\(M\)次连续操作（共两种操作类型，详见下文），既可以随时修改某一台主机\(x\)的安全威胁评分\(v_x\)，又可以随时基于不同的告警值水位线\(h\)进行查询。

现在给你这\(N\)台主机安全等级\(s_i\)以及初始的安全威胁评分\(v_i\)。请你设计一个算法支持这\(M\)次连续操作。

输入

第一行输入两个正整数\(N,M(1\le N,M\le 10^5)\)分别表示深信服CWPP平台上保护主机的数目\(N\)和进行操作的次数\(M\)。

接下来\(N\)行，输入两个正整数\(s_i,u_i(1 \le s_i,v_i\le 10^9)\)表示第\(i\)台主机安全等级\(s_i\)以及初始的安全威胁评分\(v_i\)，保证安全等级\(s_i\)各不相同。

接下来\(M\)行，输入若干个操作，对于每个操作首先输入一个操作类型\(op\)（\(op\)为\(1\)或\(2\)）。

当\(op\)的值为\(1\)时，表示进行查询操作，此时还需要继续输入一个参数\(h(1\le h\le 10^9)\)，表示该次查询的告警闯值水位线。

当\(op\)的值为\(2\)时，表示进行修改操作，此时还需要继续输入两个参数\(x,v_x(1\le x\le N, 1\le v_x\le 10^9)\)，表示需要将第\(x\)台主机的安全威胁评分改为\(v_x\)。

输入保证，至少进行一次查询操作。

\(1\le N,M\le 10^5\)
\(1\le s_i,v_i\le 10^9\)
\(1\le h\le 10^9\)
\(1\le x\le N\)

输出

对于每一次查询操作，输出评分超过阈值水位线的最高安全等级机器的编号。

样例

解答

这题的做法比较麻烦，因为它涉及到了动态修改，需要一些数据结构来操作。

这里我们选择了使用支持单点修改的线段树，它支持在\(O(\log n)\)的时间内对数组的元素进行修改和求解区间最大值。

我们首先对所有节点机器按照风险等级进行排序，接下来依据排序后的结果初始化线段树。对于题目的两种操作：

每次修改操作则是将对应位置的机器的风险分数直接修改即可，线段树可以直接更新。
对于每次查询操作，我们考虑对后缀进行二分，也就是找到一个最短的后缀，其区间最大值至少为\(h\)，那么这时这个后缀的第一个机器恰好就是所求机器，将它映射回自身的编号即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100004;

int l[N<<2],r[N<<2],mx[N<<2];
int a[N];

# define ls p<<1
# define rs p<<1|1
void build(int p,int tl,int tr){
    l[p]=tl;r[p]=tr;
    if(tl==tr){
        mx[p]=a[tl];return;
    }
    int mid=(tl+tr)>>1;
    build(ls,tl,mid);
    build(rs,mid+1,tr);
    mx[p]=max(mx[ls],mx[rs]);
}
void update(int p,int q,int x){
    if(l[p]==r[p]){
        mx[p]=x;
        return;
    }
    int mid=(l[p]+r[p])>>1;
    if(q<=mid) update(ls,q,x);
    else update(rs,q,x);
    mx[p]=max(mx[ls],mx[rs]);
}
int que(int p,int ql,int qr){
    if(ql<=l[p]&&r[p]<=qr) return mx[p];
    int mid=(l[p]+r[p])>>1;
    int ans=0;
    if(ql<=mid) ans=que(ls,ql,qr);
    if(qr>mid) ans=max(ans,que(rs,ql,qr));
    return ans;
}

int s[N],v[N],id[N],pos[N],n,q;
int que_id(int h){
    if(que(1,1,n)<h) return -1;
    int l=1,r=n;
    while(l<r){
        int mid=(l+r+1)>>1;
        if(que(1,mid,n)>=h) l=mid;
        else r=mid-1;
    }
    return id[l];
}
int main(){
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&s[i],&v[i]);
        id[i]=i;
    }
    sort(id+1,id+n+1,[](int x,int y){return s[x]<s[y];});
    for(int i=1;i<=n;i++)
        pos[id[i]]=i;
    for(int i=1;i<=n;i++)
        a[pos[i]]=v[i];
    build(1,1,n);
    int op,x,y,h;
    while(q--){
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&h);
            printf("%d\n",que_id(h));
        }
        else{
            scanf("%d %d",&x,&y);
            update(1,pos[x],y);
        }
    }
}