科大讯飞秋招 2023.09.15 编程题目与题解

发表于 2023-09-21 分类于笔试阅读次数：本文字数： 1.9k 阅读时长 ≈ 2 分钟

1、小红数数

小红正在数偶数：\(0,2,4,6,8,10,12,\dots\)

她把这些数连在了一起，形成一个无穷长的字符串："0246810121416...

小红想知道，这个字符串第\(n\)个字符是多少？

输入

一个正整数\(n\)。

\(1\le n\le 10^5\)

输出

字符串的第\(n\)个字符。

样例

输入：
6

输出：
1

解答

本题是一道简单模拟题，只需要将每一个偶数转化成字符串拼接上已有的字符串后面，直到字符串长度超过\(n\)即可，最终输出第\(n\)个字符。

代码

n = int(input())
s = ''
k = 0
while len(s) < n:
    s += str(k)
    k += 2
print(s[n - 1])

2、小红的递增子序列

小红有一个长度为\(n\)的排列，请你对排列进行重排，使得排列的最长递增子序列的长度为\(k\)。

输入

第一行两个整数\(n,k\)，表示排列的长度和最长递增子序列的长度。

\(1\le k\le n\le 10^5\)

输出

输出一行，包含\(n\)个整数，表示重排后的排列，如果有多种方案，输出任意一种即可。

样例

输入：
3 1

输出：
3 2 1

提示：
排列[3, 2, 1]的最长递增子序列的长度为1。

解答

基于贪心的思想，我们令最小的\(k\)个数递增，让最大的\(n-k\)个数递减即可，这样最大的\(n-k\)个数不会对答案造成任何的影响。

代码

1
2
3

n, k = map(int, input().split())
a = list(range(n, k, -1)) + list(range(1, k + 1))
print(*a)

3、科大讯飞飞凡计划

小红是科大讯飞飞凡计划的导师。已知小红所在的组共有\(n\)名成员，每名成员的业务能力为\(a_i\)，沟通能力为\(b_i\)。

现在，小红希望把所有成员分为两个小组进行小组竞争，为了公平，小红希望这两个小组的成员的业务能力之和相等，沟通能力之和也相等。请你帮小红给出一个合法的分组方案。

输入

第一行输入一个正整数\(n\)，代表总人数。

接下来的\(n\)行，每行输入两个正整数\(a_i,b_i\)，代表每个成员的业务能力。和沟通能力。

\(1\le n\le 50\)
\(1\le a_i,b_i\le 20\)

输出

如果不存在一种合法的分配方案，则直接输出\(-1\)。

否则第一行输入两个正整数\(k\)和\(n-k\)，分别代表两个小组的人数。

第二行输入\(k\)个正整数\(p_i\)，代表第一个小组的成员。

第三行输入\(n-k\)个正整数\(q_i\)，代表第二个小组的成员。

样例

输入：
3
1 2
3 4
4 6

输出：
2 1
1 2
3

提示：
第一个和第二个成员一组，第三个成员独自一组即可。

输入：
3
1 2
1 2
1 2

输出：
-1

解答

这道题可以使用动态规划进行解决。

首先，如果所有人的\(a_i\)之和或者是\(b_i\)之和为奇数，那么很明显没有办法划分出满足要求的两队人。

否则，我们令\(\displaystyle{s_a=\dfrac{1}{2}\sum_{i=1}^n a_i,s_b=\dfrac{1}{2}\sum_{i=1}^n b_i}\)。如果存在一个子集\(S\)满足\(\displaystyle{\sum_{i\in S} a_i=s_a,\sum_{i\in S} b_i=s_b}\)，那么\(S\)为一队人，其余人为另一队人，因此这题实际上可以使用和0-1背包问题类似的做法完成，只不过我们这里需要对状态进行追溯。

令\(f(i,j,k)\)表示选择了前\(i\)个人后，存在一个子集\(S\)，其所有\(a_i\)之和为\(j\)，所有\(b_i\)之和为\(k\)的情况。如果\(f(i,j,k)\neq 0\)，那么说明这样的子集是存在的，那么我们可以写出\(f(i,j,k)\)的其中一个状态转移方程为：

\(f(i,j)= \left \{\begin{aligned} &-1 & & \text{if}\quad i=1\land j=0\land k=0 \\ &0 & & \text{if}\quad i=1\land \neg (j=0\land k=0) \\ &-1 & & \text{if}\quad i>1\land f(i-1,j,k)\neq 0 \\ &1 & & \text{if}\quad i>1\land f(i-1,j,k)= 0\land j\ge a_i\land k\ge b_i\land f(i-1,j-a_i,k-b_i)\neq 0 \\ &0 & & \text{otherwise}\quad \\ \end{aligned}\right.\)

其中，\(f(i,j,k)\neq 0\)使还记录了它是从哪个状态转移而来。如果\(f(i,j,k)=1\)，那么第\(i\)个人被选上了，从\(f(i-1,j-a_i,k-b_i)\)转移而来；如果\(f(i,j,k)=-1\)，那么第\(i\)个人没被选上，从\(f(i-1,j,k)\)转移而来。

因此，我们最终判断是否满足\(f(n,s_a,s_b)\neq 0\)即可，并且通过其值，得到它的状态转移过程，并逆推出一个方案。

代码

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

const int N=50;
int f[N][504][504];
int n,a[N],b[N];
int main(){
    scanf("%d",&n);
    int sa=0,sb=0;
    for(int i=1;i<=n;i++){
        scanf("%d %d",&a[i],&b[i]);
        sa+=a[i];sb+=b[i];
    }
    if((sa&1)||(sb&1)) return puts("-1"),0;
    sa>>=1;sb>>=1;
    f[0][0][0]=-1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=sa;j++){
            for(int k=0;k<=sb;k++){
                if(j>=a[i]&&k>=b[i]&&f[i][j-a[i]][k-b[i]]){
                    f[i][j][k]=1;
                }
                if(f[i-1][j][k]) f[i][j][k]=-1;
            }
        }
    }
    if(f[n][sa][sb]==0) return puts("-1"),0;
    vector<int>x,y;
    for(int i=n,j=sa,k=sb;i>0;i--){
        if(f[i][j][k]==1) x.push_back(i),j-=a[i],k-=b[i];
        else y.push_back(i);
    }
    printf("%d %d\n",x.size(),y.size());
    for(int i=0;i<x.size();i++)
        printf("%d%c",x[i], " \n"[i+1==x.size()]);
    for(int i=0;i<y.size();i++)
        printf("%d%c",y[i], " \n"[i+1==y.size()]);
}