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

1、小红数数

小红正在数偶数:0,2,4,6,8,10,12,

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

小红想知道,这个字符串第 n 个字符是多少?

输入

一个正整数 n

1n105

输出

字符串的第 n 个字符。

样例

1
2
3
4
5
输入:
6

输出:
1

解答

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

代码

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

2、小红的递增子序列

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

输入

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

1kn105

输出

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

样例

1
2
3
4
5
6
7
8
输入:
3 1

输出:
3 2 1

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

解答

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

代码

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

3、科大讯飞飞凡计划

小红是科大讯飞飞凡计划的导师。已知小红所在的组共有 n 名成员,每名成员的业务能力为 ai,沟通能力为 bi

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

输入

第一行输入一个正整数 n,代表总人数。

接下来的 n 行,每行输入两个正整数 ai,bi,代表每个成员的业务能力。 和沟通能力。

  • 1n50
  • 1ai,bi20

输出

如果不存在一种合法的分配方案,则直接输出 1

否则第一行输入两个正整数 k nk,分别代表两个小组的人数。

第二行输入 k 个正整数 pi,代表第一个小组的成员。

第三行输入 nk 个正整数 qi,代表第二个小组的成员。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
输入:
3
1 2
3 4
4 6

输出:
2 1
1 2
3

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

输入:
3
1 2
1 2
1 2

输出:
-1

解答

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

首先,如果所有人的 ai 之和或者是 bi 之和为奇数,那么很明显没有办法划分出满足要求的两队人。

否则,我们令 sa=12i=1nai,sb=12i=1nbi。如果存在一个子集 S 满足 iSai=sa,iSbi=sb,那么 S 为一队人,其余人为另一队人,因此这题实际上可以使用和 0-1 背包问题类似的做法完成,只不过我们这里需要对状态进行追溯。

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

f(i,j)={1ifi=1j=0k=00ifi=1¬(j=0k=0)1ifi>1f(i1,j,k)01ifi>1f(i1,j,k)=0jaikbif(i1,jai,kbi)00otherwise

其中,f(i,j,k)0 使还记录了它是从哪个状态转移而来。如果 f(i,j,k)=1,那么第 i 个人被选上了,从 f(i1,jai,kbi) 转移而来;如果 f(i,j,k)=1,那么第 i 个人没被选上,从 f(i1,j,k) 转移而来。

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 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()]);
}

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝