1、小红数数
小红正在数偶数:
她把这些数连在了一起,形成一个无穷长的字符串:"0246810121416...
小红想知道,这个字符串第 个字符是多少?
输入
一个正整数 。
输出
字符串的第 个字符。
样例
解答
本题是一道简单模拟题,只需要将每一个偶数转化成字符串拼接上已有的字符串后面,直到字符串长度超过 即可,最终输出第 个字符。
代码
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、小红的递增子序列
小红有一个长度为 的排列,请你对排列进行重排,使得排列的最长递增子序列的长度为 。
输入
第一行两个整数 ,表示排列的长度和最长递增子序列的长度。
输出
输出一行,包含 个整数,表示重排后的排列,如果有多种方案,输出任意一种即可。
样例
1 2 3 4 5 6 7 8
| 输入: 3 1
输出: 3 2 1
提示: 排列[3, 2, 1]的最长递增子序列的长度为1。
|
解答
基于贪心的思想,我们令最小的 个数递增,让最大的 个数递减即可,这样最大的 个数不会对答案造成任何的影响。
代码
1 2 3
| n, k = map(int, input().split()) a = list(range(n, k, -1)) + list(range(1, k + 1)) print(*a)
|
3、科大讯飞飞凡计划
小红是科大讯飞飞凡计划的导师。已知小红所在的组共有 名成员,每名成员的业务能力为 ,沟通能力为 。
现在,小红希望把所有成员分为两个小组进行小组竞争,为了公平,小红希望这两个小组的成员的业务能力之和相等,沟通能力之和也相等。请你帮小红给出一个合法的分组方案。
输入
第一行输入一个正整数 ,代表总人数。
接下来的 行,每行输入两个正整数 ,代表每个成员的业务能力。
和沟通能力。
输出
如果不存在一种合法的分配方案,则直接输出 。
否则第一行输入两个正整数 和 ,分别代表两个小组的人数。
第二行输入 个正整数 ,代表第一个小组的成员。
第三行输入 个正整数 ,代表第二个小组的成员。
样例
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
|
解答
这道题可以使用动态规划进行解决。
首先,如果所有人的 之和或者是 之和为奇数,那么很明显没有办法划分出满足要求的两队人。
否则,我们令 。如果存在一个子集 满足 ,那么 为一队人,其余人为另一队人,因此这题实际上可以使用和 0-1 背包问题类似的做法完成,只不过我们这里需要对状态进行追溯。
令 表示选择了前 个人后,存在一个子集 ,其所有 之和为 ,所有 之和为 的情况。如果 ,那么说明这样的子集是存在的,那么我们可以写出 的其中一个状态转移方程为:
其中, 使还记录了它是从哪个状态转移而来。如果 ,那么第 个人被选上了,从 转移而来;如果 ,那么第 个人没被选上,从 转移而来。
因此,我们最终判断是否满足 即可,并且通过其值,得到它的状态转移过程,并逆推出一个方案。
代码
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()]); }
|