度小满秋招 2023.10.09 编程题目与题解

发表于 2023-10-11 分类于笔试阅读次数： 34 本文字数： 2.4k 阅读时长 ≈ 2 分钟

1、accept

给一个 $n \times m$ 的字符矩阵，请你判断将矩阵中的某一行按从左向右顺序或者某一列按从上到下顺序取出作为一个字符串后，该字符串中是否存在子串 "accept"。

输入

第一行包含一个正整数 $T$ ，表示数据组数。

接下来包含 $T$ 组数据，对于每组数据：

第一行包含两个正整数 $n$ 和 $m$ ，表示矩阵的行数和列数。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示矩阵每一行中的内容。

保证所有字符均为小写英文字符。

$100 %$ 的数据保证： $1 \leq T \leq 10, 1 \leq n, m \leq 100$

输出

对于每组数据，如果存在则输出 "YES" 否则输出 "NO"。

样例

输入：
2
10
dc
ac
ca
ec
cc
qe
gp
ht
ee
pd
2 10
dscacceptd
pqoxaccepw

输出：
YES
YES

提示：
第一组数据中，第二列中包舍了"accept"子串。
第二组数据中，第一行中包含了“accept"子串。

解答

首先枚举 "accept" 或者是其逆序 "tpecca" 是否在字符矩阵的每一行存在即可，可以使用内置的库完成。

至于纵向的处理，只需要将这个字符矩阵进行转置，再进行和刚刚相同的操作即可。

代码

p1 = "accept"
p2 = p1[::-1]


def solve(ls):
    for s in ls:
        if p1 in s or p2 in s:
            return True
    n, m = len(ls), len(ls[0])
    lt = ["" for _ in range(m)]
    for i in range(n):
        for j in range(m):
            lt[j] += ls[i][j]
    for s in lt:
        if p1 in s or p2 in s:
            return True
    return False


T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    ls = []
    for i in range(n):
        ls.append(input())
    print("YES" if solve(ls) else "NO")

2、数组排序

给定一个长度为 $n$ 的数组 $A$ ，数组下标为 $1$ 到 $n$ ，第 $i$ 个数记为 $a_{i}$ ，保证 $A$ 数组是 $1$ 到 $n$ 的一个排列。现在，小明将对 $A$ 数组按顺序进行 $m$ 次操作来对 $A$ 数组排序。第 $i$ 次操作会给定参数 $x_{i}$ 和 $y_{i} (x_{i} < y_{i})$ ，表示若 $a_{x_{i}} > a_{y_{i}}$ ，则交换 $a_{x_{i}}$ 和 $a_{y_{i}}$ 。若数组恢复有序，小明会立刻停止操作。

现在，你需要告诉小明 $A$ 数组最早在什么时恢复有序（本题有序指数组单调递增，即从小到大有序），即找到一个最小的非负整数 $p$ ，满足第 $p$ 次操作后，数组 $A$ 有序。特别地，若 $A$ 数组在第 $1$ 次操作前就有序，则 $p = 0$ ，若数组在 $m$ 次操作后仍然没有处于有序状态，则 $p = m + 1$ 。

输入

本题输入包含多组测试数据，输入第一行包含一个正整数 $T (1 \leq T \leq 100)$ ，表示数据组数。

接下来，每三行描述了一组测试数据。

每组测试数据中，第一行包含两个正整数 $n (2 \leq n \leq 20)$ 和 $m (1 \leq m \leq 200)$ ，分别表示 $A$ 数组长度和操作个数。

接下来一行包含 $n$ 个整数，描述了数组 $A$ ，保证数组 $A$ 为 $1$ 到 $n$ 的一个排列。

接下来一行包含 $2 m$ 个整数，按操作顺序描述了小明将要进行的操作，第 $2 i - 1$ 个整数和第 $2 i$ 个整数描述了第 $i$ 次操作 $(1 \leq i \leq m)$ ，分别代表了操作的两个参数 $x_{i}$ 和 $y_{i} (x_{i} < y_{i})$ 。

对于 $100 %$ 的数据，满足 $2 \leq n \leq 20, 1 \leq m \leq 200, 1 \leq T \leq 100$ 。

保证数组 $A$ 是 $1$ 到 $n$ 的一个排列。

输出

对于每组测试数据，输出包含一行一个整数，即满足题意的最小非负整数。

样例

输入：
2
5 2
1 2 4 3 5
1 2 3 4
2 1
1 2
1 2

输出：
2
0

提示：
对于样例的第一组测试数据：
初始A数组为:1 2 4 3 5
执行第1次操作后，数组A变为：1 2 4 3 5
执行第2次操作后，数组A变为：1 2 3 4 5
此时有序，故答案为2。
对于样例的第二组测试数据，数组初始即有序，故答案为0。

解答

只需要直接处理这个过程即可。如果数组 $A$ 已经有序，那么直接返回 $0$ 即可，接下来枚举每个交换操作，交换完后如果发现是有序的，那么可以直接返回。否则返回值 $m + 1$ 。这种做法完全可以做出这个数据范围下 $O (n m)$ 的这题。

以下介绍一种 $O (n + m)$ 的做法。在整个过程中，维护一个变量 $c$ ，表示有多少个数已经排在了正确的位置上，当 $c = n$ 时，说明数组已经有序。可以在 $O (1)$ 的时间内维护好 $c$ 变量，交换前处理排好序的下标的情况，交换后也处理排好序的下标的情况，从而完成变量 $c$ 的维护。

代码

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

const int N=100004;

int a[N],x[N],y[N],n,m;
int solve(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%d %d",&x[i],&y[i]);
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(a[i]==i) ++cnt;
    }
    if(cnt==n) return 0;
    for(int i=1;i<=m;i++){
        if(a[x[i]]>a[y[i]]){
            if(a[x[i]]==x[i]) --cnt;
            if(a[y[i]]==y[i]) --cnt;
            swap(a[x[i]],a[y[i]]);
            if(a[x[i]]==x[i]) ++cnt;
            if(a[y[i]]==y[i]) ++cnt;
        }
        if(cnt==n) return i;
    }
    return m+1;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        printf("%d\n",solve());
    }
}

3、最小的区间

给定一个长度为 $n$ 的数组 $A$ ，下标为 $1$ 到 n。给定一个长度为 $m$ 的数组 $B$ ，下标为 $1$ 到 $m$ ，数组 $B$ 中第 $i$ 个数记为 $b_{i}$ 。请找出长度最小的连续区间 $[l, r]$ （ $1 \leq l \leq r \leq n$ 且 $l, r$ 为整数），使得该区间对于所有满足 $1 \leq x \leq m$ 的正整数 $x$ 均有：正整数 $x$ 在 $A$ 数组的下标落在区间 $[l, r]$ 的所有数中至少现了 $b_{x}$ 次。

注意，对于任意一个连续区间 $[l, r] ，区间的长度定义为$ r-l+1$。

输入

输入第一行包含两个数 $n (1 \leq n \leq 10^{5})$ 和 $m (1 \leq m \leq 10^{5})$ ，分别表示数组 $A$ 和 $B$ 的长度。

输入第二行包含 $n$ 个整数，描述了数组 $A$ 。

输出第三行包含 $m$ 个整数，描述了数组 $B$ 。

对于 $100 %$ 的数据，满足 $1 \leq n, m \leq 10^{5}$ 。

保证数组 $A$ 和数组 $B$ 中所有数均为不超过 $10^{5}$ 的非负整数，保证数组 $B$ 不全为 $0$ 。

输出

输出包含一行一个整数，表示最小的符合要求的区间的长度。

如果不存在符合要求的区间，请输出 $- 1$ 。

样例

输入：
8 5
2 3 3 1 2 4 2 5
1 2 0 0 0

输出：
4

提示：
样例中，区间[4,7]是长度最小的满足条件的区间，其区间长度为7-4+1=4。
样例中需要满足的条件是“1至少出现1次”，“2至少出现2次”，“3、4、5至少出现0次”。

解答

我们可以使用双指针法完成这题。我们可以使用枚举左指针 $l$ ，并且找到最大的 $r (r \leq n + 1)$ 指针使得区间 $[l, r)$ 中的所有出现次数都满足数组 $b$ ，从而把答案 $r - l$ 进行统计（如果 $r$ 存在）。

这个过程怎么维护呢？使用一个 $c$ 数组用于统计 $a [l, r)$ 中的元素个数，以及集合 $S$ 用于记录满足 $1 \leq x \leq m, c_{x} < b_{x}$ 的那些 $x$ 值。随着右指针右移， $S$ 集合元素逐渐减少，直到为空，这时 $r - l$ 为所求的答案。接下来去除 $a_{l}$ 元素，集合 $S$ 有可能新添加一个元素 $a_{l}$ 。由此使用双指针法即可完成本题。

代码

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

const int N=100004;

int a[N],b[N],n,m;
int cnt[N];
unordered_set<int>st;
void add(int x,int op){
    if(x>m) return;
    if(op==1){
        if(++cnt[x]>=b[x])
            st.erase(x);
    }
    else{
        if(--cnt[x]<b[x])
            st.insert(x);
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++){
        scanf("%d",&b[i]);
        if(b[i]) st.insert(i);
    }
    int ans=1e9;
    for(int l=1,r=1;l<=n;l++){
        for(;r<=n&&!st.empty();r++){
            add(a[r],1);
        }
        if(st.empty()){
            ans=min(ans,r-l);
        }
        add(a[l],-1);
    }
    if(ans>n) ans=-1;
    printf("%d\n",ans);
}