17校招真题题集（3）11-15

分手后的思念是犯贱 2022-05-09 03:56 206阅读 0赞

注：本系列题目全是按照通过率降序来排列的，基本保证题目难度递增。

# 11、 #

# 题目名称：买苹果 #

来源：网易

## 题目描述 ##

小易去附近的商店买苹果，奸诈的商贩使用了捆绑交易，只提供6个每袋和8个每袋的包装(包装不可拆分)。 可是小易现在只想购买恰好n个苹果，小易想购买尽量少的袋数方便携带。如果不能购买恰好n个苹果，小易将不会购买。

## 输入描述: ##

输入一个整数n，表示小易想购买n(1 ≤ n ≤ 100)个苹果

## 输出描述: ##

输出一个整数表示最少需要购买的袋数，如果不能买恰好n个苹果则输出-1

示例1

## 输入 ##

## 输出 ##

分析：贪心：肯定8个一袋的越多越好，到了最后分情况判断即可

n=int(input())
    q=0
    while n>24:
        n-=8
        q+=1
    if n==24 or n==18 or n==20 or n==22:
        print(q+3)
    elif n==12 or n==16 or n==14:
        print(q+2)
    elif n==6 or n==8:
        print(q+1)
    else:
        print("-1")

另一种思路：动态规划/背包。

可以去我动态规划系列文章找。[https://blog.csdn.net/hebtu666/article/details/81777273][https_blog.csdn.net_hebtu666_article_details_81777273]

# 12、 #

# 问题名称：素数对 #

来源：腾讯

## 题目描述 ##

给定一个正整数，编写程序计算有多少对质数的和等于输入的这个正整数，并输出结果。输入值小于1000。  
如，输入为10, 程序应该输出结果为2。（共有两对质数的和为10,分别为(5,5),(3,7)）

## 输入描述: ##

输入包括一个整数n,(3 ≤ n < 1000)

## 输出描述: ##

输出对数

示例1

## 输入 ##

## 输出 ##

分析：这种数据范围直接暴力即可。先找素数，然后在素数里找合是n的数对

n=int(input())
    l=[2]
    for i in range(3,1000)://找素数
        q=1
        for j in range(2,i):
            if i%j==0:
                q=0
                break
        if q==1:
            l.append(i)
    s,k=0,0
    for i in l://找素数对
        for j in l:
            if i+j==n:
                s+=1//所有的
                if i==j://相同的
                    k+=1
    print((s+k)//2)

# 13、 #

# 问题名称：不要二 #

来源：网易

## 题目描述 ##

二货小易有一个W\*H的网格盒子，网格的行编号为0~H-1，网格的列编号为0~W-1。每个格子至多可以放一块蛋糕，任意两块蛋糕的欧几里得距离不能等于2。  
对于两个格子坐标(x1,y1),(x2,y2)的欧几里得距离为:  
( (x1-x2) \* (x1-x2) + (y1-y2) \* (y1-y2) ) 的算术平方根  
小易想知道最多可以放多少块蛋糕在网格盒子里。

## 输入描述: ##

每组数组包含网格长宽W,H，用空格分割.(1 ≤ W、H ≤ 1000)

## 输出描述: ##

输出一个最多可以放的蛋糕数

示例1

## 输入 ##

3 2

## 输出 ##

分析：找规律：

所谓欧几里得距离不能等于二，因为行列都为整数，所以只可能是某一列坐标相等而行坐标相差2，或者行坐标相等而列坐标相差2。

![6536808_1517154778860_67CF1875A8AE2E930CB4CB1570819285][]

就这么摆呗

l=(input().split())
    m=int(l[0])
    n=int(l[1])
    //横竖一个一个分边界情况
    if m%4==0:
        kk=m
        gg=m
    elif m%4==1:
        kk=m+1
        gg=m-1
    elif m%4==2:
        kk=m+2
        gg=m-2
    elif m%4==3:
        kk=m+1
        gg=m-1
    if n%4==0:
        a=(n/4)*(kk+gg)
    elif n%4==1:
        a=((n-1)/4)*(kk+gg)+kk/2
    elif n%4==2:
        a=((n-2)/4)*(kk+gg)+kk
    elif n%4==3:
        a=((n-3)/4)*(kk+gg)+kk+gg/2
    print(int(a))

其实不需要找规律，递推也可以  
定义一个数组a\[1000\]\[1000\],初始值都为0，从a\[0\]\[0\]开始,将a\[0\]\[2\]和a\[2\]\[0\]置为-1,遍历数组，不是-1的地方可以放蛋糕

#include<iostream>
    using namespace std;
    int a[1000][1000] = {0};
    int main()
    {
        int w,h,res = 0;
        cin >> w >> h;
    
        for(int i=0;i<w;i++)
        {
            for(int j=0;j<h;j++)
            {
                if(a[i][j]==0)
                {
                    res++;
                    if((i+2)<w) a[i+2][j] = -1;
                    if((j+2)<h) a[i][j+2] = -1;
                }
            }
        }
        cout << res;
        return 0;
    }

# 14、 #

# 问题名称：统计回文 #

来源：网易

## 题目描述 ##

“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。花花非常喜欢这种拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一个回文串。你接受花花的请求，帮助她寻找有多少种插入办法可以使新串是一个回文串。如果字符串B插入的位置不同就考虑为不一样的办法。  
例如：  
A = “aba”，B = “b”。这里有4种把B插入A的办法：  
\* 在A的第一个字母之前: "baba" 不是回文  
\* 在第一个字母‘a’之后: "abba" 是回文  
\* 在字母‘b’之后: "abba" 是回文  
\* 在第二个字母'a'之后 "abab" 不是回文  
所以满足条件的答案为2

## 输入描述: ##

每组输入数据共两行。
    第一行为字符串A
    第二行为字符串B
    字符串长度均小于100且只包含小写字母

## 输出描述: ##

输出一个数字，表示把字符串B插入字符串A之后构成一个回文串的方法数

示例1

## 输入 ##

aba
    b

## 输出 ##

分析：直接按题意模拟一下即可。

python

a=input()
    b=input()
    kk=0
    for i in range(len(a)+1):
        gg=a[0:i]+b+a[i:]
        if gg==gg[::-1]:
            kk+=1
    print(kk)

c++

#include<iostream>
    #include<string>
    using namespace std;
    bool Huiwen(string str1)   //判断回文
        {
        int length=str1.length();
        for(int i=0;i<length;i++)
            {
            if(str1[i]!=str1[length-1])
                return false;
            length=length-1;
             }
        return true;
         }
    int main()
      {
        string str1,str2,temp;
        int count,len;
        while(cin>>str1>>str2)
        {
            count = 0;
            temp=str1;
            len=str1.length()+1;
            for(int i=0;i<len;i++)
            {
                str1=temp;
                str1.insert(i,str2);   //在A字符串中以此插入B字符串
                if(Huiwen(str1))       //判断是否是回文
                    count=count+1;    //统计回文    
            }
            cout<<count<<endl;
        }
        return 0;
      }

# 15、 #

# 题目名称：构造队列 #

来源：网易有道

## 题目描述 ##

小明同学把1到n这n个数字按照一定的顺序放入了一个队列Q中。现在他对队列Q执行了如下程序：

while(!Q.empty())              //队列不空，执行循环
    
    {
    
        int x=Q.front();            //取出当前队头的值x
    
        Q.pop();                 //弹出当前队头
    
        Q.push(x);               //把x放入队尾
    
        x = Q.front();              //取出这时候队头的值
    
        printf("%d\n",x);          //输出x
    
        Q.pop();                 //弹出这时候的队头
    
    }

做取出队头的值操作的时候，并不弹出当前队头。  
小明同学发现，这段程序恰好按顺序输出了1,2,3,...,n。现在小明想让你构造出原始的队列，你能做到吗？\[注：原题样例第三行5有错，应该为3，以下已修正\]

## 输入描述: ##

第一行一个整数T（T ≤ 100）表示数据组数，每组数据输入一个数n（1 ≤ n ≤ 100000），输入的所有n之和不超过200000。

## 输出描述: ##

对于每组数据，输出一行，表示原始的队列。数字之间用一个空格隔开，不要在行末输出多余的空格.

示例1

## 输入 ##

4
    1
    2
    3
    10

## 输出 ##

1
    2 1
    2 1 3
    8 1 6 2 10 3 7 4 9 5

分析：逆向考虑：

c++

#include <iostream>
    #include <deque>
    using namespace std;
     
    int main()
    {
        int n, k;
        cin >> k;
        while(k > 0)
        {
            deque<int> q;
            k--;
            cin >> n;
            for(int i = n; i > 0; i--)
            {
                q.push_front(i);
                int t = q.back();
                q.pop_back();
                q.push_front(t);
            }
            for(int i = 0; i < q.size(); i++)
                cout << q[i] << " ";
            cout << endl;
        }
    }

python

nn=int(input())
    sum=[]
    for i in range(0,nn):
        n=int(input())
        line = list([j+1 for j in range(n)])
        res=[]
        while n:
            num=line.pop()
            res.insert(0,num)
            num = res.pop()
            res.insert(0,num)
            n-=1
        sum.append(res)
    for res in sum:
        print(" ".join(list(map(str,res))))

[https_blog.csdn.net_hebtu666_article_details_81777273]: https://blog.csdn.net/hebtu666/article/details/81777273
[6536808_1517154778860_67CF1875A8AE2E930CB4CB1570819285]: https://uploadfiles.nowcoder.net/images/20180128/6536808_1517154778860_67CF1875A8AE2E930CB4CB1570819285