layout: post
title: 牛客网2017年校招全国统一模拟笔试(第一场)编程题集合
date: 2017-05-27
tag: oj
目录
- TOC
{:toc}
好多鱼！
牛牛有一个鱼缸。鱼缸里面已经有n条鱼，每条鱼的大小为fishSize[i] (1 ≤ i ≤ n,均为正整数)，牛牛现在想把新捕捉的鱼放入鱼缸。鱼缸内存在着大鱼吃小鱼的定律。经过观察，牛牛发现一条鱼A的大小为另外一条鱼B大小的2倍到10倍(包括2倍大小和10倍大小)，鱼A会吃掉鱼B。考虑到这个，牛牛要放入的鱼就需要保证：
1、放进去的鱼是安全的，不会被其他鱼吃掉
2、这条鱼放进去也不能吃掉其他鱼
鱼缸里面已经存在的鱼已经相处了很久，不考虑他们互相捕食。现在知道新放入鱼的大小范围[minSize,maxSize](考虑鱼的大小都是整数表示),牛牛想知道有多少种大小的鱼可以放入这个鱼缸。
输入描述:
输入数据包括3行.
第一行为新放入鱼的尺寸范围minSize,maxSize(1 ≤ minSize,maxSize ≤ 1000)，以空格分隔。
第二行为鱼缸里面已经有鱼的数量n(1 ≤ n ≤ 50)
第三行为已经有的鱼的大小fishSize[i](1 ≤ fishSize[i] ≤ 1000)，以空格分隔。
输出描述:
输出有多少种大小的鱼可以放入这个鱼缸。考虑鱼的大小都是整数表示
输入例子:
1 12
1
1
输出例子:
3
AC代码
#include<iostream>
using namespace std;
int a[55]; int mi,ma;
int n; int main(){
cin >> mi >> ma;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
int ans = 0;
for(int i = mi; i <= ma; i++){
int flag = 1;
for(int j = 0; j < n; j++){
if( (i >= a[j] * 2 && i <= a[j] * 10) || (i * 2 <= a[j] && i * 10 >= a[j]) ){ //吃和被吃的规则
flag = 0;
}
}
if(flag)
ans++;
}
cout << ans << endl; //不需要考虑新放入的鱼之间会互相吃掉
}
循环单词
如果一个单词通过循环右移获得的单词，我们称这些单词都为一种循环单词。 例如：picture 和 turepic 就是属于同一种循环单词。 现在给出n个单词，需要统计这个n个单词中有多少种循环单词。
输入描述:
输入包括n+1行：
第一行为单词个数n(1 ≤ n ≤ 50)
接下来的n行，每行一个单词word[i]，长度length(1 ≤ length ≤ 50)。由小写字母构成
输出描述:
输出循环单词的种数
输入例子:
5
picture
turepic
icturep
word
ordw
输出例子:
2
思路分析
- 数据量比较小，就使用了STL的Map来实现，将每个字符串的所有循环形式存起来，每次有新的字符串时先判断是否已经存在，如果已经存在则统计结果+1，否则将其所有循环形式进行存储
AC代码
#include<iostream>
#include<map>
#include<string>
using namespace std;
int n;
map<string, int> mp;
int main() {
while (scanf("%d", &n) != EOF) {
string s, tem;
int ans = 0;
for (int i = 0; i < n; i++) {
cin >> s;
if (mp[s] == 0) //表示一个新的字符串
ans++;
for (int j = 0; j < s.length(); j++) {
tem = s.substr(j, s.length() - j) + s.substr(0, j); //substr参数1-off，参数2-Count
mp[tem] = 1;
}
}
cout << ans << endl;
}
return 0;
}
添加笔记
DNA合成
DNA分子是以4种脱氧核苷酸为单位连接而成的长链，这4种脱氧核苷酸分别含有A,T,C,G四种碱基。碱基互补配对原则：A和T是配对的，C和G是配对的。如果两条碱基链长度是相同的并且每个位置的碱基是配对的，那么他们就可以配对合成为DNA的双螺旋结构。现在给出两条碱基链，允许在其中一条上做替换操作：把序列上的某个位置的碱基更换为另外一种碱基。问最少需要多少次让两条碱基链配对成功
输入描述:
输入包括一行：
包括两个字符串,分别表示两条链,两个字符串长度相同且长度均小于等于50。
输出描述:
输出一个整数，即最少需要多少次让两条碱基链配对成功
输入例子:
ACGT TGCA
输出例子:
0
思路分析
- 接统计下标相同的位置上匹配的内容，如果匹配则+1，最后用总长度-匹配长度即可
AC代码
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str1, str2;
int count = 0;
while (cin>>str1>>str2)
{
for (int i = 0; i < str1.length(); i++)
{
if (str1[i]=='A'&&str2[i]=='T')
{
count++;
}
if (str1[i]=='C'&&str2[i]=='G')
{
count++;
}
if (str1[i]=='T'&&str2[i]=='A')
{
count++;
}
if (str1[i]=='G'&&str2[i]=='C')
{
count++;
}
}
cout << (str1.length()-count);
}
return 0;
}
连续整数
牛牛的好朋友羊羊在纸上写了n+1个整数，羊羊接着抹除掉了一个整数，给牛牛猜他抹除掉的数字是什么。牛牛知道羊羊写的整数神排序之后是一串连续的正整数，牛牛现在要猜出所有可能是抹除掉的整数。例如：
10 7 12 8 11 那么抹除掉的整数只可能是9
5 6 7 8 那么抹除掉的整数可能是4也可能是9
输入描述:
输入包括2行：
第一行为整数n(1 <= n <= 50)，即抹除一个数之后剩下的数字个数
第二行为n个整数num[i] (1 <= num[i] <= 1000000000)
输出描述:
在一行中输出所有可能是抹除掉的数,从小到大输出,用空格分割,行末无空格。如果没有可能的数，则输出mistake
输入例子:
2
3 6
输出例子:
mistake
AC代码
- 边界条件的判断
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
int main()
{
int N;
int num;
vector<int> vec; //1 <= num[i] <= 1000000000 正整数
while (cin >> N)
{
for (int i = 0; i < N; i++)
{
cin >> num;
vec.push_back(num);
}
if (N == 1 && vec[0] != 1)
{
cout << vec[0] - 1 <<' '<< vec[0] + 1;
break;
}
if (N == 1 && vec[0] == 1)
{
cout << vec[0] + 1;
break;
}
sort(vec.begin(), vec.end());
int count = 0;
int count1 = 0;
int pos = 0;
for (int i = 1; i < N; i++)
{
num = vec[i] - vec[i - 1];
if (num == 2)
{
pos = i;
count++;
}
if (num == 1)
{
count1++;
}
}
if (count == 1 && ((count + count1) == N - 1))
{
cout << vec[pos] - 1;
}
else if (count1 == N - 1&&vec[0]==1)
{
cout<<vec[N-1]+1;
}
else if (count1 == N - 1)
{
cout << vec[0] - 1 <<' '<< vec[N - 1] + 1;
}
else
{
cout << "mistake";
}
}
return 0;
}
//测试用例:
//4
//5 2 1 2
//
//对应输出应该为 :
//
// mistake
//
// 你的输出为 :
//
//mistake06
//测试用例:
//1
//166
//
//对应输出应该为 :
//
// 165 167
//
// 你的输出为 :
//
// 167
//测试用例:
//1
//1
//
//对应输出应该为 :
//
// 2
超级素数幂
如果一个数字能表示为p^q(^表示幂运算)且p为一个素数,q为大于1的正整数就称这个数叫做超级素数幂。现在给出一个正整数n,如果n是一个超级素数幂需要找出对应的p,q。
输入描述:
输入一个正整数n(2 ≤ n ≤ 10^18)
输出描述:
如果n是一个超级素数幂则输出p,q,以空格分隔,行末无空格。
如果n不是超级素数幂，则输出No
输入例子:
27
输出例子:
3 3
思路分析
- 我们首先计算出top=Log(n)/log(2)，这里的top就是q所能取得到的最大值，然后我们从2开始枚举到top，每次计算i次根号n，在其为素数的情况下计算i次根号n的i次方是否为n，如果是则输出，否则计算下一次，如果一直计算到top都没有的话则输出No
AC代码
#include<iostream>
#include <cmath>
using namespace std;
bool isprime(long long N)
{
for (long long i = 2; i <= sqrt(N);i=i+1)
{
if (N%i==0)
{
return false;
}
}
return true;
}
long long Get_basep_q(long long p,long long q) //求p的q次幂,直接用pow，AC不过
{
long long ret = 1;
long long temp = p;
while (q)
{
if (q%2==1) //q为偶数最后进判断，q为奇数
{
ret *= temp;
}
temp = temp*temp;
q /= 2;
}
return ret;
}
//p的q次幂
int main()
{
long long N;
while (cin>>N)
{
long long maxq = log10(N) / log10(2);
bool flag = false;
for (long long i = 2; i <= maxq;i++)
{
long long basep = pow(N,1.0/i);
if (isprime(basep))
{
long long sum =Get_basep_q(basep,i);
if (sum==N)
{
cout << basep << ' ' << i;
flag = true;
break;
}
}
}
if (flag==false)
{
cout << "No" << endl;
}
}
}
序列和
给出一个正整数N和长度L，找出一段长度大于等于L的连续非负整数，他们的和恰好为N。答案可能有多个，我我们需要找出长度最小的那个。
例如 N = 18 L = 2：
5 + 6 + 7 = 18
3 + 4 + 5 + 6 = 18
都是满足要求的，但是我们输出更短的 5 6 7
输入描述:
输入数据包括一行：
两个正整数N(1 ≤ N ≤ 1000000000),L(2 ≤ L ≤ 100)
输出描述:
从小到大输出这段连续非负整数，以空格分隔，行末无空格。如果没有这样的序列或者找出的序列长度大于100，则输出No
输入例子:
18 2
输出例子:
5 6 7
AC代码
- 等差数列求和问题
#include<iostream>
using namespace std;
int main()
{
int N, L;
while (cin>>N>>L) //长度为L的等差数列求第一项
{
bool flag = false;
for (int i = L; i <= 100;i++)
{
if ((2 * N - i*i + i) % (2 * i)==0)
{
int a1 = (2 * N - i*i + i) / (2 * i); //首项
for (int j = 0; j < i;j++)
{
if (j==0)
{
cout << a1;
}
else
{
cout <<' '<< a1 + j;
}
}
flag = true;
break;
}
}
if (flag==false)
{
cout << "No" << endl;
}
}
return 0;
}
页码统计
牛牛新买了一本算法书，算法书一共有n页，页码从1到n。牛牛于是想了一个算法题目：在这本算法书页码中0~9每个数字分别出现了多少次？
输入描述:
输入包括一个整数n(1 ≤ n ≤ 1,000,000,000)
输出描述:
输出包括一行10个整数，即0~9这些数字在页码中出现的次数，以空格分隔。行末无空格。
输入例子:
999
输出例子:
189 300 300 300 300 300 300 300 300 300
思路分析
从1~9这9个数字的计算我们可以找到如下规律（以下除0以外全部以1为基数）
(1)当这一位比要找的数字大时：直接求（高位+1）*base
例如12213中，我们找百位的1，则百位出现1的情况为100~199,1100~1199,2100~2199,…..,11100~11199,12100~12199,一共1300个，刚到等于高位数字+1再乘以当前位数，即(12+1)*100;
(2)当这一位比要找的数字小时：直接求（高位）*base
例如12013中，我们找百位的1，则百位出现1的情况为100~199,1100~1199,2100~2199,…..,11100~11199,一共1200个，刚到等于高位数字再乘以当前位数，即12*100;
(3)当这一位等于要找的数字时：
例如12113中，我们找百位的1，则百位出现1的情况为100~199,1100~1199,2100~2199,…..,11100~11199,12100~12199,一共1200个，刚到等于高位数字再乘以当前位数，即12*100;除了这些数字以外，还有12100~12113这14个数字，即低位数+1，即13+1.
举个栗子：
对统计1~785012中5出现的个数
我们先考虑5在低位第三位出现的次数，我们就将第三位固定为5：XXX5XX。
此时，问题就转化为，“X”处一共有多少种组合方式。
高位的3位可以从000到785之间，低位的2位可以从00到99之间。
但是，当高3位为785时，7855XX无论如何都超过了785012，因此，高三位可以选择的只有000~784（共785个数字），高三位和低二位一共有785*100种组合方式。
我们再考虑5在低位第四位出现的次数，我们就将第四位固定为5：XX5XXX。
与前面相同，高位的二位可以从00到78之间，低位的三位可以从000到999之间。
当高位是00到77时，与前面一种情况是相同的，一共可以组合出78*1000种情况。
当高位是78时，785XXX就有超过785012的可能了，后三位的选择局限在000到012之间，共13中情况。
两者结合就是：78*1000+13
最后考虑5在低位第5位出现的次数，我们就将第五位固定为5：X5XXXX。
与前面相同，最高位可以从0取到7，低四位可以从0000取到9999.
当最高位为0到6时，与第一种情况相同，一共可以组合出7*10000中情况。
当高位是7时，与前面的情况不同的是，75XXXX是不会越界的，后四位可以从0000取到9999，所以可以组合出10000中情况。
两者结合就是：7*10000+10000
设我们讨论的当前位的值为A，我们统计的数字为B，我们前面讨论的三种情况，其实分别是：A小于B时，A等于B时，A大于B时。
AC代码
#include <iostream>
using namespace std;
int getNum(int n, int x)
{
int ret = 0;
int cur = n, high, low, temp;
for (int base = 1; cur;base*=10,cur/=10) //位数
{
temp = cur % 10; //依次去n的每一位和x比较
high = n / (base*10);
low = n%base;
if (x==0) //对0特殊处理
{
if (high)
{
high--;
}else
break;
}
ret += base*high; //当这一位比要找的数字小时
if (temp>x) // 当这一位比要找的数字大时
{
ret += base;
}
else if (temp == x) //当这一位等于要找的数字时
{
ret += low + 1;
}
}
return ret;
}
int main()
{
int N;
while (cin>>N)
{
for (int i = 0; i < 10;i++)
{
if (i==0)
{
cout << getNum(N, i);
}
else
{
cout << ' ' << getNum(N, i);
}
}
}
return 0;
}
添加笔记
01翻转
牛牛正在挑战一款名为01翻转的游戏。游戏初始有A个0,B个1，牛牛的目标就是把所有的值都变为1，每次操作牛牛可以任意选择恰好K个数字，并将这K个数字的值进行翻转(0变为1，1变为0)。牛牛如果使用最少的操作次数完成这个游戏就可以获得奖品，牛牛想知道最少的操作次数是多少？
例如:A = 4 B = 0 K = 3
0000 -> 1110 -> 1001 -> 0100 -> 1111
需要的最少操作次数为4
输入描述:
输入为一行：
一共三个整数A(0 ≤ A ≤ 100,000),B(0 ≤ B ≤ 100,000),K(1 ≤ K ≤100,000).以空格分隔
输出描述:
输出一个整数，表示最少需要的操作次数。如果不能完成，则输出-1
输入例子:
4 0 3
输出例子:
4
思路分析
-
我们的主题思路采用BFS，因为题目中对于进行反转的数字可以随意选择，且最终的目的是将所有的数字都反转为1，因此我们只需要记录0的个数即可，当0的个数为0时即达到
-
不会做存，参考
AC代码
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int a, b, k;
bool vis[200005];
struct node {
int a_num, b_num, step;
node() {
step = 0;
}
};
queue<node> q;
int main() {
while (cin >> a >> b >> k) {
if (a == 0) {
cout << 0 << endl;
continue;
}
else if (a + b < k) {
cout << -1 << endl;
continue;
}
else if (a == k) {
cout << 1 << endl;
continue;
}
while (!q.empty()) q.pop();
node cur, tem;
cur.a_num = a; cur.b_num = b;
memset(vis, false, sizeof(vis));
q.push(cur);
vis[cur.a_num] = true;
bool key = false;
while (!q.empty()) {
cur = q.front(); q.pop();
if (cur.a_num == 0) {
cout << cur.step << endl;
key = true;
break;
}
for (int i = k; i > 0; i--) {
tem = cur;
if (tem.a_num >= i && tem.b_num >= (k - i)) {
tem.a_num += k - i - i;
tem.b_num += i - (k - i);
tem.step++;
if (vis[tem.a_num] == false) {
vis[tem.a_num] = true;
q.push(tem);
}
}
}
}
if (key == false)
cout << -1 << endl;
}
return 0;
}