B卷:

1.求最大的数和最小的数

题目描述:
数学课上，老师给你一些列的数，让你编程求出最大的数和最小的数？

输入:
第一行是数的个数n，第二行是n个数，中间有空格间隔。

输出:
输出占一行，先是最小的数，然后是最大数，中间有一个空格。

样例输入:

4
11 22 55 999

样例输出:

11 999

题解:
水题

代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0; i<n; i++) cin>>nums[i];
    cout<<*min_element(nums.begin(), nums.end())<<" "<<*max_element(nums.begin(), nums.end());
    return 0;
}

2.特别数的和

题目描述:
小明对数位中含有2、0、1、9的数字很感兴趣（不包括前导0），在1到40中这样的数包括1、2、9、10至32、39和40，共28个，他们的和是574。请问，在 1 到 n 中，所有这样的数的和是多少？

输入:
输入一行包含一个整数 n。

输出:
输出一行，包含一个整数，表示满足条件的数的和。

样例输入:

40

样例输出:

574

题解:
一个函数用来判断该数是否含有2,0,1,9,我们可以先把整数转换为字符串,然后的话就可以很容易判断了.

代码:

#include<bits/stdc++.h>
using namespace std;
bool Judge(int num)
{
    string str = to_string(num);  //整数转换成字符串
    int n = str.size();
    for(int i=0; i<n; i++)
    {
        if(str[i]=='2' || str[i]=='0' ||str[i]=='1' || str[i]=='9') return true;
    }
    return false;
}
long long sum(int n)
{
    long long ans = 0;
    for(int i=1; i<=n; i++)
    {
        if(Judge(i)) ans+=i;
    }
    return ans;
}
int main()
{
    int n;
    cin>>n;
    cout<<sum(n)<<endl;
    return 0;
}

3.推算星期几

题目描述:
给你某一天是星期几，那么过ab天之后是星期几？请编程实现。

输入:
第一行是n(n<100),表示下边n行，每行有三个数k a b，k表示某一天的是星期几，k用1-7表示星期一到星期天，两个正整数a，b，中间用单个空格隔开。0 < a <= 100, 0 < b <= 10000。

输出:
对应每一行的k a b，输出一个字符串，代表过ab天之后是星期几。
其中，Monday是星期一，Tuesday是星期二，Wednesday是星期三，Thursday是星期四，Friday是星期五，Saturday是星期六，Sunday是星期日。

样例输入:

2
2 1 1
7 3 2000

样例输出:

Wednesday
Tuesday

题解:
其实就是快速幂的变形.如果不用快速幂的话肯定是TLE.
快速幂的解法,之前我在学习的时候看到过一篇对我帮助很大的博客传送门

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 7;
string strs[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
int mostfastPow(ll base, ll power)
{
    ll ans = 1;
    while(power>1)
    {
        if(power % 2 == 1)
        {
            power -= 1;
            ans *= base;
        }
        power /= 2;
        base = base * base % mod;
    }
    return ans * base % mod;
}
int main()
{
    int n;
    cin>>n;
    int k;
    ll a, b;
    while(n--)
    {
        cin>>k>>a>>b;
        int ans = mostfastPow(a, b);
        int pos = (k+ans+7)%7;
        cout<<strs[pos-1]<<endl;
    }
    return 0;
}

4.最少需要多少雷达

题目描述:
假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离最多为d。示例图如上，x轴上方是海洋，x轴下方是大陆，p1,p2,p3表示岛屿。现在给你一些岛屿的坐标，请计算为覆盖这些小岛需要的最少的雷达数.

输入:
第一行是n和d，n代表岛屿的个数，d表示雷达覆盖的直径。接着下边n行是每个岛屿的x,y坐标。

输出:
假设所有岛屿都满足能够被雷达覆盖到，为覆盖到所有岛屿，输出需要的最少雷达数。

样例输入:

3 2
1 2
-3 1
2 1

样例输出:

2

题解:

这一题贪心算法的应用.
从上图能够看出,我们能够覆盖到此岛屿的雷达所在的区间，应该就是以该岛屿为圆心,雷达扫描范围d为半径的圆与x轴交点所在的区间.
所以遍历岛屿,得到一个区间数组,我们从第一个区间数组开始,利用贪心算法,我们将雷达安放至当前区间的最右侧(这样能够获得更大的扫描空间).
第一个雷达一定放在第一个区间的最右端点。让圆的范围尽可能的向右。

如果下一个区间的左端点在雷达的右边，那么ans++，并且雷达更新为这一个区间的右端点。

如果下一个区间的左端点在雷达的左边，ans不变，雷达不变。

如果下一个区间的左端点在雷达的左边，并且右端点也在雷达的左边，那么显然这时候的雷达不能覆盖这个小岛，需要把雷达更新为这个区间的右端点，sum不变。(如下图)

代码如下:

#include<bits/stdc++.h>
using namespace std;
int merge(vector<vector<double>> &intervals)
{
    if(intervals.size() == 0) return {};
    sort(intervals.begin(), intervals.end());
    vector<vector<double>> merged;
    int ans = 0;
    for(int i=0; i<intervals.size(); i++)
    {
        double L = intervals[i][0], R = intervals[i][1];
        if(merged.size()==0 || merged.back()[1]<L)
        {
            merged.push_back({L,R});
            ans++;
        }else if(merged.back()[1]>R){
            merged.back()[1] = R;
        }
    }
    return ans;
}
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, d;
    cin>>n>>d;
    vector<vector<double>> intervals;
    double x, y;
    bool flag = false;      //表示有无不可能覆盖到的岛屿
    for(int i=0; i<n; ++i){
        cin>>x>>y;
        if(d<0 || y<0 || abs(y)>d) flag = true;
        double add = sqrt(pow(d,2) - pow(y,2));
        intervals.push_back({x-add, x+add});
    }
    if(flag){
        cout<<-1<<endl;
    }
    else{
        int num = merge(intervals);
        cout<<num<<endl;
    }
    return 0;
}

5.购书

题目描述:
小明手里有m元钱全部用来买书，书的价格为10元，20元，50元，100元。问小明有多少种购书方案？（每种书可购买多本）

输入:
一个整数 n(n<100)，表示n个情况，接下来n行，每一行有一个整数m代表总共钱数。（0 <= m <= 1000）

输出:
对应每一行上的m, 输出购书方案数。

样例输入:

2
20
15

样例输出:

2
0

题解:
这一题动态规划的应用
将手中的钱看成是背包的容量,而每张钱币的价格就看成是物体的体积,将其转化成完全背包问题.我觉得比较复杂.

解动态规划问题的第一步,往往是构造我们的动态转移方程表达式,将一个大问题用很多子问题来表示.

我们用一个二维状态数组f[i].[j]来表示背包容量为j时,可以装前i种物品的方案种数. (牢记动态规划问题往往是从一个小表格开始的).
代价就是书的价格，价值就是方案数;

代码如下:

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[5]={0,10,20,50,100};
int dp[5][N];
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(dp, 0, sizeof(dp));
    for(int i=1; i<=4; i++) dp[i][0] = 1;  //初始化
    int n, m;
    cin>>n;
    for(int a=0; a<n; a++)
    {
        cin>>m;
        for(int i=1; i<=4; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(j>=v[i]) dp[i][j] = dp[i-1][j] + dp[i][j-v[i]];  //关键一步,动态转移方程
                else dp[i][j] = dp[i-1][j];
            }
        }
        cout<<dp[4][m]<<endl;
        for(int i=0; i<=4; i++)  //构建出的dp数组
        {
            for(int j=0; j<=m; j++)
                cout<<dp[i][j]<<" ";
            cout<<endl;
        }
    }
    return 0;
}

运行结果:

我们还可以将其优化为一维情形,f[j]表示背包容量为j时,可以装所有种类物品的方案总数:
即f[20] = dp[4].[20]

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[5]={0,10,20,50,100};
int n,f[N],b[N];
int dp[5][N];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>m;
        if(b[m])  //如果已经计算过了,直接输出
        {
            cout<<f[m]<<endl;
            continue;
        } 
        f[0]=1;                   //边界条件
        for(int i=1;i<=4;i++)     
            for(int j=v[i];j<=m;j++)  //每次j从v[i]开始,因为若j<v[i]的话,不可能买得起物品i,所以之前的数组不会有任何改变
            {
                f[j] += f[j-v[i]];
                b[j] = true;
            }
        cout<<f[m]<<endl;
        cout<<"构建出的一维dp数组为:"<<endl;
        for(int i=0; i<=m; i++) cout<<f[i]<<" ";
        cout<<endl;
    }
    return 0;
}

运行结果:

如果大家觉得本篇文章对你有所帮助的话,不妨去我的个人博客 --- 乔治的编程小屋逛逛吧.