图森未来秋招 2023.09.16 编程题目与题解

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

1、TuTu的子数列

TuTu得到了一个长度为\(n\)的数列\(a_1,a_2,\dots,a_n\)。

现在TuTu希望从原数列中挑出一个子数列（被挑出的子数列需要按照原来的顺序排列，但不一定要连续）。但是TuTu同时提出了一个要求，对于数列\(a_1,a_2,\dots,a_n\)中任意连续的\(k\)个数，它们中应该有\(x\)个数被包含在挑出的子数列中，其中\(x\)需要满足\(x\in[L,R]\)。

当然满足这个要求的子数列有很多个，TuTu认为一个被挑出的子数列的值是这个数列中的每个数之和。现在TuTu想让你计算所有可能被挑出的子数列的价值和是多少。

输入

第一行四个数\(n,k,L,R\)。

第二行\(n\)个数，表示数列\(a_1,a_2,\dots,a_n\)。

\(n\le 1000,1\le L\le R\le k\le 10, 0\le a_i\le 10^9\)

输出

输出一行一个数，表示答案。由于这个数可能会很大，你需要输出它对\(10^9+7\)取模后的结果。

样例

输入：
3 2 1 2
8 3 4

输出：
48

输入：
5 3 1 2
6 1 7 9 7

输出：
240

解答

可以看到，\(k\)值比较小，因此我们可以考虑使用状态压缩动态规划解决本题。

考虑一个\(k\)比特数\(s=s_{k-1}s_{k-2}\dots s_0\)，它用于表示一个连续\(k\)个数的选择情况。这意味着如果\(s\)的\(1\)比特数量处于区间\([L,R]\)内，那么这是一个合法的选择情况，并将它存入集合\(S\)中，否则这就不是一个合法的选择情况。

我们用这个\(k\)比特数\(s\)来表示当前我们遍历到第\(i(i\ge k)\)个数时，\(a\)中最近\(k\)个数的选择情况。更具体的说，\(s_j\)用来表示数\(a_{i-j}\)有没有被选上。接下来我们需要对第\(i+1\)个数做出决策，第\(i+1\)个数无非就两种决策，要么选，要么不选。因此，对于目前的\(s\)，无论第\(i+1\)个数做出哪种决策，都已经和第\(i-k+1\)个数做出的决策没有关系。如果第\(i+1\)个数不被选择，那么新的状态\(s\)是\(s_0'=(2\cdot s) \bmod (2^k-1)\)，也就是说每个数的选择情况都向后移动了\(1\)位；如果第\(i+1\)个数被选择，那么新的状态\(s\)是\(s_1'=(2\cdot s+1) \bmod (2^k-1)\)。

对于上面的两种新产生的状态，我们仍然需要判断它们的合法性。令\(t(s,0)\)表示后一个数没有被选择，并产生新状态\(s_0'\)，令\(t(s,1)\)表示后一个数被选择，并产生新状态\(s_1'\)。如果\(t(s,0)\)和\(t(s,1)\)不是一个合法状态，那么我们认为这些状态值都是未定义的，任何情况下都不能转移到非法状态。最终，我们就确保了到最后，所有统计出来的子序列都是合法的。

接下来的讨论，默认不能转移到非法情况，如果存在非法情况的出现，那么忽略。

与其计算所有子数组的权值和，我们首先计算这样的子数组有多少个。令状态\(f(i,s)(k\le i\le n,s\in S)\)表示对前\(i\)个数进行决策后，并且最近\(k\)个数的选择情况由\(s\)表示，这样的序列一共有多少个。

那么\(\forall s\in S\)，都有如下转移：

\(1\rightarrow f(k,s)\)

也就是说，前\(k\)个元素，只要选的个数在\([L,R]\)之间，都是合法的。对于任意状态\(f(i,s)\)，通过对元素\(a_{i+1}\)的两种不同决策，有如下转移：

\(f(i,s)\rightarrow f(i+1,t(s,0))\)
\(f(i,s)\rightarrow f(i+1,t(s,1))\)

其中，前一种决策说明了\(a_{i+1}\)没有被选择；后一种决策说明\(a_{i+1}\)被选择。

那么有了\(f(i,s)\)，我们可以计算所有子数列的权值和了。令\(g(i,s)\)表示状态\(f(i,s)\)中的所有子数列和。那么\(\forall s\in S\)，都有：

\(\displaystyle{\sum_{j=0}^{k-1} a_{k-j}\cdot s_j\rightarrow g(i,s)}\)

对比\(f(k,s)\)，这个转移是显而易见的。对于任意状态\(g(i,s)\)，通过对元素\(a_{i+1}\)的两种不同决策，同样有如下转移：

\(g(i,s)\rightarrow g(i+1,t(s,0))\)
\(g(i,s)\rightarrow g(i+1,t(s,1))+f(i,s)\cdot a_{i+1}\)

其中前一种决策说明了\(a_{i+1}\)没有被选择，和值不变；后一种决策说明\(a_{i+1}\)被选择，由于当前有\(f(i,s)\)个序列都需要添加一个元素\(a_{i+1}\)，因此这些子数组的和要额外添加\(f(i,s)\cdot a_{i+1}\)。

因此，这道题的最终答案为\(\displaystyle{\sum_{s\in S} f(n,s)}\)。

代码

# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1024;
ll f[N][N],s[N][N],a[N];
ll mod=1e9+7;
int n,k,l,r;
int ok[N];
int g[N][2];
int main(){
    scanf("%d %d %d %d",&n,&k,&l,&r);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int st=0;st<(1<<n);st++){
        int k=__builtin_popcount(st);
        if(l<=k&&k<=r) ok[st]=1;
    }
    int msk=(1<<k)-1;
    for(int st=0;st<(1<<k);st++){
        if(!ok[st]) continue;
        int s0=(st<<1)&msk,s1=(st<<1|1)&msk;
        if(ok[s0]) g[st][0]=s0;
        if(ok[s1]) g[st][1]=s1;
        f[k][st]=1;
        for(int j=0;j<k;j++)
            if(st>>j&1) s[k][st]+=a[k-j];
        s[k][st]%=mod;
    }
    for(int i=k;i<n;i++){
        for(int st=0;st<(1<<k);st++){
            if(!ok[st]) continue;
            if(g[st][0]){
                int su=g[st][0];
                f[i+1][su]=(f[i+1][su]+f[i][st])%mod;
                s[i+1][su]=(s[i+1][su]+s[i][st])%mod;
            }
            if(g[st][1]){
                int su=g[st][1];
                f[i+1][su]=(f[i+1][su]+f[i][st])%mod;
                s[i+1][su]=(s[i+1][su]+s[i][st]+f[i][st]*a[i+1])%mod;
            }
        }
    }
    ll ans=0;
    for(int st=0;st<(1<<k);st++)
        if(ok[st]) ans=(ans+s[n][st])%mod;
    printf("%lld\n",ans);
}

2、TuTu去除数字

TuTu的日常工作中需要完成各种各样的项目，同时需要给自己编写的项目写文档。由于TuTu上班打盹，他发现自己在文档中不小心混入了很多数字。已知TuTu现在的这个文档是完全由英文字母和空格构成的，你需要将文档中的所有数字去除。

具体来说，现有一份文档\(s\)，其中可能有数字混杂其中，你需要修改这个文档：

首先你需要将\(s\)中的所有数字替换成空格文档：
接下来，你需要对文档进行检查，为了文档的美观度，文档中不允许同时两个及以上的连续空格，你需要将多余的空格删除。同时你需要证文档的开头和结尾也是不存在空格的。

输入

输入一行一个字符串\(s\)，保证\(s\)中只有大小写英文字母、阿拉伯数字与空格。

保证\(s\)的第一个字符与最后一个字符均不为空格，且至少存在一个英文字母。

保证\(|s|\le 10^5\)，保证数据中本身不会出现两个及以上连续的空格。

输出

输出一行一个字符串，表示处理后的\(s\)。

样例

输入：
Hel1o w0rLd

输出：
Hel o w rLd

解答

这题可以使用正则表达式表达式完成。

使用\d将所有字符转换成空格。
使用strip()去除两侧的空格。
使用\s+将相邻连续的多个空白字符转换成单个空格。

代码

import re

s = input()
s = re.sub(r'\d', ' ', s).strip()
s = re.sub(r'\s+', ' ', s)
print(s)

3、TuTu排雷

TuTu 设计自动驾驶卡车的同时，还设计了一种新型的自动排雷器可以帮助在雷场自动化排雷。

这个自动排雷器是一个正方形，每一次可以同时排掉角上的四个不同的地雷，即这四个地雷\((x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4)\)需要构成一个平行于坐标轴的正方形，也就是满足：

\(x_1 = x_2,x_3 = x_4,y_1 = y_3,y_2 = y_4\)
\(|x_1-x_3|=|y_1 -y_2|\)
\(|x_1-x_3|>0\)

需要注意的是，每一次必须排掉不同的四个雷，当存在的地雷个数不足四个或者存在的地雷无法满足这个要求的时候，则没有更多的雷可以被排掉了。

现在TuTu已经探测出了当前雷区的所有地雷的分布，想请你安排探测器的使用方式，排除尽可能多的雷。

输入

第一行包含一个整数\(T\)，表示数据组数。

接下来\(T\)组数据。

每组数据的第一行包含一个整数\(n\)。

接下来\(n\)行，每行包含两个整数\(x,y\)，表示一个地雷的坐标。

请注意，地雷的位置可能会重叠，即一个位置上可能会存在多个地雷。

\(1\le n\le 20,0\le x,y\le 100,1\le T\le 10\)

输出

\(T\)行，每行包含一个整数，表示能排掉的最多地雷数。

样例

解答

这题不难想到使用状态压缩动态规划进行解决。

首先，我们预处理出任意顶点组合\((i,j,k,l)\)，其中\(0\le i<j<k<l<n\)，并判断这\(4\)个顶点是否为题目中要求的正方形，如果是，那么将\(2^i+2^j+2^k+2^l\)添加到决策集合\(S\)中。具体的判断方法是通过\(24\)种排列，作为正方形的左上角，右上角，右下角，左下角，并判断是否满足正方形的条件即可。

我们令\(s\)表示成一个\(n\)比特数，其中第\(i\)比特为\(1\)表示第\(i\)颗地雷被排掉，否则就没有被排掉，由此用这一个数成功表示了当前的地雷排除状态。令状态\(f(s)\)表示\(s\)中表示的情况是否能够得到，那么我们可以写出如下状态转移方程：

\(f(s)= \left \{\begin{aligned} &1 & & \text{if}\quad s=0 \\ &\bigvee_{x\in S,(x\text{ and }s)=x} f(s\text{ xor }x) & & \text{if}\quad s>0 \end{aligned}\right.\)

方程的第二行意味着之前排雷工作\(f(s\text{ xor }x)\)如果是可行的，那么当前排掉了决策\(x\)中的雷，因此\(f(s)\)也是可行的。

最终，选择满足\(f(s)=1\)的状态，且\(s\)的比特数最大，此时输出\(s\)的比特数。

为了保证效率，在实现的时候，我们只从满足\(f(s)=1\)的状态转移出去。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
# define X first
# define Y second
using namespace std;
typedef long long ll;
const int N=20;
pi p[N];
bool f[1<<N];
int n;
vector<int>st;
bool ok(vector<int>a){
    vector<pi>q;
    for(int x:a) q.push_back(p[x]);
    sort(q.begin(),q.end());
    for(int i=1;i<a.size();i++)
        if(q[i]==q[i-1]) return 0;
    do{
        if(!(q[0].X==q[1].X&&q[2].X==q[3].X&&q[0].Y==q[3].Y&&q[1].Y==q[2].Y)) continue;
        vector<int>v{abs(q[0].Y-q[1].Y),abs(q[2].Y-q[3].Y),q[0].X-q[3].X,abs(q[1].X-q[2].X)};
        if(unique(v.begin(),v.end())-v.begin()==1) return 1;
    }while(next_permutation(q.begin(),q.end()));
    return 0;
}
int solve(){
    scanf("%d",&n);
    memset(f,0,sizeof(f));
    st.clear();
    for(int i=0;i<n;i++)
        scanf("%d %d",&p[i].X,&p[i].Y);
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            for(int k=j+1;k<n;k++)
                for(int l=k+1;l<n;l++)
                    if(ok({i,j,k,l}))
                        st.push_back(1<<i|1<<j|1<<k|1<<l);
    f[0]=1;
    int ans=0;
    for(int s=0;s<(1<<n);s++){
        if(!f[s]) continue;
        ans=max(ans,__builtin_popcount(s));
        for(int w:st){
            if((s&w)==0) f[s|w]=1;
        }
    }
    return ans;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        printf("%d\n",solve());
    }
}