题目练习地址：PIPIOJ

目录

1、进制转换（PIPIOJ）

2、PIPI数兔（PIPIOJ）

3、 数组查找（PIPIOJ）

4、旋转矩阵（PIPIOJ）

5、 PIPI的数字游戏（PIPIOJ）

6、赛车游戏（PIPIOJ）

---

1、进制转换（PIPIOJ）

题目描述：

请写出一段程序，将十进制数字转为八进制。

输入：

第一行输入T()表示测试样例个数。
对于每一组样例，包含一个数字N（）。

输出：

输出T个数字，代表转换成的八进制数（无前导0）。

输入样例：

2
8
100

输出样例

10
144

本题考查进制转换。

进制转换类题目包括三类：

（1）十进制转化为x进制，（2）x进制转换为十进制，（3）a进制转换为b进制

考生须掌握前两类（即（1）和（2））；

因为a进制转换为b进制可以拆分为a进制转换为十进制，然后十进制转换为b进制。（即（2）+（1）组合拳）

然而本题则是直接考察（1）的运用。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int x;
        cin>>x;
        vector<int>ans;
        do
        {
            ans.push_back(x%8);
            x/=8;
        }while(x!=0);
        //注意此处得到的vector数组是八进制数的反转，所以要逆向输出。
        for(int i=ans.size()-1;i>=0;i--)cout<<ans[i];
        cout<<endl;
    }
}

2、PIPI数兔（PIPIOJ）

题目描述：

一对刚出生的小兔一个月后就能长大成大兔，再过一个月就能生下一对小兔，并且此后每个月都生一对小兔，假设兔子不会死亡。
PIPI有一对刚出生的兔子，n个月后繁殖成多少对兔子？

输入描述：

多组输入。每组样例输入一个正整数n(1<=n<=50)，表示月数。

输出描述：

对于每组样例输出一个正整数，表示最终兔子的数量。

样例输入：

2
3

样例输出：

2
3

这题题目意思存在小问题，这里的一对兔子应该就是指的是一只兔子。

一只小兔子一个月后变成一只大兔子，一只大兔子每个月都会出生一个小兔子。同时兔子不会死亡

这题是典型的斐波那契数列知识点，（兔子数列）。

斐波那契数列是考研机试常考点，考察概率极大。必须掌握。

兔子数量和月数关系表

	0月后（此时仅有一只小兔子）	1月后	2月后	3月后	4月后	5月后
小兔子数量	1	0	1	1	2	3
大兔子数量	0	1	1	2	3	5
兔子总数量	1	1	2	3	5	8

通项公式：

第i个月后的大兔子数量 = 第i-1个月后的大兔子数量 + 第i-1个月后的小兔子数量 = 第i-1个月后的兔子总数（这里得出每个月大兔子数量等于上个兔子数量总和的结论）........（1）

第i个月后小兔子数量 = 第i-1个月后的大兔子数量 = 第i-2个月后的兔子总数。........(2)

（1）+（2）=》

第i个月后的兔子总数

=第i个月后的大兔子数量 + 第i个月后小兔子数量

= 第i-1个月后的兔子总数 + 第i-2个月后的兔子总数

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int dp[N];
signed main()
{
    //dp[i]表示第i个月后的兔子总数。
    dp[0]=1;
    dp[1]=1;
    for(int i=2;i<N;i++)dp[i]=dp[i-1]+dp[i-2];
    int x;
    while(cin>>x)
    {
        cout<<dp[x]<<endl;
    }
}

3、 数组查找（PIPIOJ）

题目描述：

给定一个包含n个整数的升序序列和m个待查询的数字x，请你查找序列中x第一次出现的位置，如果不存在输出-1。

输入描述：

第一行输入序列长度n()和查询数量m()。
第二行输入n个整数，代表序列的值，序列每个元素的值x满足()。
接下来输入m个要查询的整数x()。

输出描述：

对于每个查询，输出要查询的整数在序列中第一次出现的位置，若不存在，输出-1。

输入样例：

5 3
0 2 2 4 5
2 4 3

输出样例：

1
3
-1

本题考察二分查找知识点。

注意n*m的值最大到了，所以每次查询的时候不可用O(n)的算法。

这里每次查询要用二分，查询复杂度为O(logn)，总时间复杂度为O(mlogn)。

第一种写法，利用c++里面的自带的STL库，直接调用二分查找函数lower_bound()。非常方便，建议掌握。

lower_bound(arr,arr+n,x)-arr；(其中n为arr数组的长度）查询的是有序数组（上升数组）arr 里面第一个大于等于x的下标。

具体用法可自行百度搜索，不再累赘。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int arr[N];
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>arr[i];
    while(m--)
    {
        int x;
        cin>>x;
        //利用lower_bound()函数直接找出第一个大于等于x的下标位置并返回给k
        int k=lower_bound(arr,arr+n,x)-arr;
        //如果arr[k]不等于x说明数组中不存在x。因为如果存在的话，第一个大于等于x的数一定等于x本身。
        if(arr[k]!=x)cout<<-1<<endl;
        else cout<<k<<endl;
    }
}

第二种写法，就是自行手写二分。

具体代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int arr[N];
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)cin>>arr[i];
    while(m--)
    {
        int x;
        cin>>x;
        int l=0,r=n;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(arr[mid]>=x)r=mid;
            else l=mid+1;
        }
        if(arr[l]!=x)cout<<-1<<endl;
        else cout<<l<<endl;
    }
}

这里建议能用STL的二分就使用它，因为它很方便。

4、旋转矩阵（PIPIOJ）

题目描述：

给定一个n*n的矩阵M，请将M顺时针旋转90°后输出。

输入描述：

第一行输入T()表示测试样例个数。
对于每一组样例，第一行输入数字n()，代表矩阵大小。
接下来输入一个n*n的二维整数数组，代表需要旋转的矩阵。

输出描述：

对于每一组样例，输出按顺时针旋转90°后的矩阵。

输入样例：

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

输出样例：

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

模拟题，直接输出即可，代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e3+10;
int arr[N][N];
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cin>>arr[i][j];
            }
        }
        for(int i=1;i<=n;i++)//i表示列
        {
            for(int j=n;j>=1;j--)//j表示行
            {
                cout<<arr[j][i]<<" ";
            }
            cout<<endl;
        }
    }
}

5、 PIPI的数字游戏（PIPIOJ）

题目描述：

PIPI有n个数字，每个数字都可以重复选取。他想用这些数字累加出一个目标数m，请问他至少用多少个数字才能凑出m？如果无法凑出，输出-1。

输入描述：

第一行输入T（）表示测试样例个数。 
对于每一组样例，第一行有两个整数n（）和 m ()。
第二行包含n个整数，每个整数的值x满足（）。

输出描述:

对于每组样例，输出最少需要的数字数量，不能凑出输出-1。

输入样例：

2
3 6
1 2 3
2 3
2 4

输出样例：

2
-1

简单dp题，这个题和完全背包有相似之处。

不会的同学可以去回顾一下01背包和完全背包这两个经典dp题的做题思路。

假设dp[i][j]表示前i种数至少花多少个数才能凑出j。

那么此时dp[n][m]就是我们所需要求的答案。

本题的状态转移方程为：

（arr[i]表示第i个数字的值）

看不懂此状态转移方程的同学，可以在网上深度学习01背包和完全背包的相关知识后再来看。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int arr[510];
int dp[510][1010];
//dp[i][j]表示前i种数至少花多少个数才能凑出j。
//此时dp[n][m]就是我们所需要求的答案。
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++)cin>>arr[i];
        //进行dp数组的初始化
        memset(dp,0x3f,sizeof dp);
        for(int i=0;i<=n;i++)dp[i][0]=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=m;j++)
            {
                dp[i][j]=dp[i-1][j];
                if(j>=arr[i])dp[i][j]=min(dp[i][j],dp[i][j-arr[i]]+1);
            }
        }
        if(dp[n][m]==0x3f3f3f3f)cout<<-1<<endl;
        else cout<<dp[n][m]<<endl;
    }
}

6、赛车游戏（PIPIOJ）

题目描述：

一条赛道上有n个停车点，每个停车点都有一辆车，第i辆车可以最多行驶a[i]个停车点。
PIPI可以在任意一个停车点换车，问PIPI最少换几次车可以到达终点（第n个停车点）。

输入描述：

第一行输入T（）表示测试样例个数。 
对于每组样例，第一行输入停车点数量n()。
第二行输入n个整数，代表第i辆车最多可以行驶a[i]个停车点()。

输出描述：

对于每组测试用例，输出到达终点的最少换车次数。如果不能到达终点，输出-1。

输入样例：

3
5
2 3 1 1 4
3
3 2 1
3
1 0 2

输出样例：

1
0
-1

本题考察模拟加贪心，

当然也可以用dp加线段树区间查询的方法来做。

新手推荐使用模拟和贪心的做法。一般来说考研机试不会单独考察线段树等高级数据结构。

本题的模拟和贪心做法具备一定的思考量。

具体思路如下：

当我在位置i起步的时候，

那么我最远可以走到i+arr[i]的位置，

假如中途我需要换车，那么我肯定只能在【i+1，i+arr[i]】的位置换车。

那么我选换车点的时候选择换车后能达到的位置最远的点换车是最优的。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int INF=1e18;
int arr[N],dp[N];
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>arr[i];
        int mx=0;
        int ans=0;
        int r=1+arr[1];
        for(int i=1;i<=n;i++)
        {
            mx=max(mx,i+arr[i]);
            if(i>r)
            {
                ans=-1;
                break;
            }
            if(i==r)
            {
                r=mx;
                ans++;
            }
            if(r>=n)
            {
                break;
            }
        }
        cout<<ans<<endl;
    }
}

23年总体难度不大。略易于往年机试真题。

考生在复习时须着重突出二分和dp算法的学习。

平时练习基础算法时推荐：洛谷题单/acwing算法基础课

平时训练打比赛推荐：牛客/codeforces，（每年机试会有那么一两道思维题，而codeforces上的题很适合锻炼思维），平时多打打牛客的周赛和小白赛。周赛难度较低，思维题和算法题都有，适合考研机试的同学练手。