算法考试复习2

F.A

算法

发布于：Oct 28, 2020

借鉴了学长们的研究成果

0x01 单词排序

题目描述

小红学会了很多英文单词，妈妈为了帮小红加强记忆，拿出纸、笔，把 N 个单词写在纸上的一行里，小红看了几秒钟后，将这张纸扣在桌子上。妈妈问小红：“你能否将这 N 个单词按照字典排列的顺序，从小到大写出来？”小红按照妈妈的要求写出了答案。现在请你编写程序帮助妈妈检查小红的答案是否正确。注意：所有单词都由小写字母组成，单词两两之间用一个空格分隔。

输入

输入包含两行。

第一行仅包括一个正整数N(0<N≤26)。

第二行包含N个单词，表示妈妈写出的单词，两两之间用一个空格分隔。

单个单词长度不超过1010。

输出

输出仅有一行。针对妈妈写出的单词，按照字典排列的顺序从小到大排列成一行的结果，每个单词后带一个空格。

样例输入

1 2	4 city boy tree student

样例输出

1	boy city student tree

代码

#include <iostream>
#include<vector>
#include<string>
#include <iomanip>
#include<algorithm>
using namespace std;
typedef long long ll;
string res[30];
int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n;++i){
        cin >> res[i];
    }
    sort(res, res + n);
    for (int i = 0; i < n;++i){
        cout << res[i] << ' ';
    }
        return 0;
}

0x02 求数组的最长递减序列

题目描述

给定一个整数序列，输出它的最长递减（注意不是“不递增”）子序列。

输入

输入包括两行，第一行包括一个正整数N（N<=1000），表示输入的整数序列的长度。第二行包括用空格分隔开的N个整数，整数范围区间为[-30000,30000]。

输出

输出最长递减子序列，数字之间有一个空格。

样例输入

1 2	8 9 4 3 2 5 4 3 2

样例输出

9 5 4 3 2

代码

1
2

参考：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/
https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/solution/dong-tai-gui-hua-jie-zui-chang-zi-xu-lie-zi-chua-4/

#include <iostream>
#include<vector>
#include<string>
#include <iomanip>
#include<algorithm>
#include <stack>
using namespace std;
typedef long long ll;
int n;
int dp[1005]={1}, nums[1005], res[1005]={-1}; //oj好像没办法这样初始化
int main()
{
    cin >> n;
    for (int i = 0; i < n;++i){
        cin >> nums[i];
    }
    for (int i = 0; i < n;++i){
        dp[i] = 1;
        res[i] = -1;
        for (int j = 0; j < i;++j){
            if(nums[i]<nums[j]&&dp[j]+1>dp[i]) //严格递减
            {
                dp[i] = dp[j] + 1;
                res[i] = j;//方便找到字串
            }
        }
    }
    int maxn = 0;
    int num = 0;
    for(int i=0;i<n;i++)
    {
        if(dp[i]>maxn)
        {
            maxn=dp[i];
            num=i; //找到最优解
        }
    }
    stack<int> a;
    a.push(nums[num]);
    while(res[num]!=-1){
        a.push(nums[res[num]]);
        num = res[num];
    }
    while(!a.empty()){
        cout << a.top() << ' ';
        a.pop();
    }
}

0x03 矩形滑雪场

题目描述

zcb喜欢滑雪。他来到了一个滑雪场，这个滑雪场是一个矩形，为了简便，我们用r行c列的矩阵来表示每块地形。为了得到更快的速度，滑行的路线必须向下倾斜。例如样例中的那个矩形，可以从某个点滑向上下左右四个相邻的点之一。例如24-17-16-1，其实25-24-23…3-2-1更长，事实上这是最长的一条。

输入

第1行:两个数字r，c(1 ≤ r, c ≤ 100)，表示矩阵的行列。第2..r+1行:每行c个数，表示这个矩阵。

输出

仅一行:输出1个整数，表示可以滑行的最大长度。

样例输入

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

样例输出

代码

#include <iostream>
#include<vector>
#include<string>
#include <iomanip>
#include<algorithm>
#include <stack>
#include<cmath>
using namespace std;
typedef long long ll;
struct node
{
    int x, y, h;

} a[10005];
bool cmp(node a,node b)
{
    return a.h<b.h;
}
int dp[10005];
bool check(node a,node b){//必须满足严格减小才可以滑下去，所以这里加判定
    if((b.h>a.h)&&((a.x==b.x&&abs(a.y-b.y)==1)||(a.y==b.y&&abs(a.x-b.x)==1)))
        return true;
    return false;
}
int main()
{
    int num = 0;
    int m, n;
    cin >> m >> n;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>a[num].h;
            a[num].x=i;
            a[num].y=j;
            num++;
        }
    }
    sort(a, a + num, cmp);
    int mmax = 1;//必定经过自己
    for (int i = 0; i < num;++i){
        dp[i] = 1;
        for (int j = 0; j < i;++j){
            if(check(a[j],a[i]))
                dp[i] = max(dp[i], dp[j] + 1);
        }
        mmax = max(dp[i], mmax);
    }
    cout << mmax << endl;
    return 0;
}

0x04 homework

题目描述

临近开学了，大家都忙着收拾行李准备返校，但 I_Love_C 却不为此担心! 因为他的心思全在暑假作业上：目前为止还未开动。

暑假作业是很多张试卷，我们这些从试卷里爬出来的人都知道，卷子上的题目有选择题、填空题、简答题、证明题等。而做选择题的好处就在于工作量很少，但又因为选择题题目都普遍很长。如果有 5 张试卷，其中 4 张是选择题，最后一张是填空题，很明显做最后一张所花的时间要比前 4 张长很多。但如果你只做了选择题，虽然工作量很少，但表面上看起来也已经做了4/5的作业了。

I_Love_C决定就用这样的方法来蒙混过关，他统计出了做完每一张试卷所需的时间以及它做完后能得到的价值（按上面的原理，选择题越多价值当然就越高咯）。

现在就请你帮他安排一下，用他仅剩的一点时间来做最有价值的作业。

输入

测试数据包括多组。每组测试数据以两个整数 M,N(1<M<20,1<N<10000) 开头，分别表示试卷的数目和 I_Love_C 剩下的时间。接下来有 M 行，每行包括两个整数 T,V(1<T<N,1<V<10000)分别表示做完这张试卷所需的时间以及做完后能得到的价值，输入以 0 0 结束。

输出

对应每组测试数据输出 I_Love_C 能获得的最大价值。保留小数点 2 位

提示：float 的精度可能不够，你应该使用 double 类型。

样例输入

样例输出

37.00

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n;
    int a[20],b[20];
    double ma[20];
    while(cin>>m>>n&&m!=0&&n!=0)
    {
        double maxn=0;
        for(int i=0;i<m;i++)
        {
            cin>>a[i];
            cin>>b[i];
            ma[i]=double(b[i])/a[i];
        }
        int f=0;
        int s;
        double vm;
        while(1)
        {
            if(f==m)
            break;
            vm=0;
            for(int i=0;i<m;i++)
            {
                if(ma[i]>vm)
                {
                    vm=ma[i];
                    s=i;
                }
            }
            if(n<a[s])
            {
                maxn=maxn+n*ma[s];
                break;
            }
            else
            {
                maxn=maxn+b[s];
                n=n-a[s];
                ma[s]=0;
                f++;
            }
        }
         cout<<setprecision(2)<<std::fixed<<maxn<<endl;
    }
}

0x05 区间包含问题

题目描述

已知 n 个左闭右开区间 [a,b)，对其进行 m 次询问，求区间[l,r]最多可以包含 n 个区间中的多少个区间，并且被包含的所有区间都不相交。

输入

输入包含多组测试数据，对于每组测试数据：

第一行包含两个整数 n ,m (1≤n≤100000,1≤m≤100) 。

接下来 n 行每行包含两个整数 a ,b (0≤a<b≤10^9) 。

接下来 m 行每行包含两个整数 l ,r (0≤l<r≤10^9) 。

输出

对于每组测试数据，输出 m 行，每行包含一个整数。

数据过大请使用快速输入输出。

样例输入

样例输出

1
2
3

1
1
2

代码

#include<iostream>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;

typedef struct node
{
    int l;
    int r;
}node;
bool cmp(node a, node b)
{
    return a.r < b.r;
}

int main()
{
    std::ios::sync_with_stdio(false);
    int n, m;
    while (cin >> n >> m)
    {
        node *nnum = new node[n];
        node *mnum = new node[m];
        for (int i = 0; i < n; i++)
        {
            cin >> nnum[i].l >> nnum[i].r;
        }
        for (int i = 0; i < m; i++)
        {
            cin >> mnum[i].l >> mnum[i].r;
        }
        sort(nnum, nnum + n, cmp);
        for (int i = 0; i < m; i++)
        {
            int res = 0;
            int k = mnum[i].l; //K初始的时候等于m数组的左边界
            for (int j = 0; j < n; j++)
            {
                if ((nnum[j].l >= k))
                {
                    if (nnum[j].r <= mnum[i].r)
                    {
                        res++;
                        k = nnum[j].r;  //每次更新成n数组的右边界
                    }
                    else  //右边界一旦超过，直接扔掉后面的部分结束质询
                    {
                        break;
                    }
                }
            }
            cout << res << endl;
        }
        delete[] nnum;
        delete[] mnum;
    }
}

0x06 最长子序列

题目描述

在一个数组中找出和最大的连续几个数。（至少包含一个数）

例如：

数组A[] = [-2,1,-3,4,-1,2,1,-5,4]，则连续的子序列[4,-1,2,1]有最大的和6.

输入

第一行输入一个不超过1000的整数n。

第二行输入n个整数A[i]。

输出

输出一个整数，表示最大的和。

样例输入

1
2

3
1 1 -2

样例输出

代码

#include <iostream>
#include<vector>
#include<string>
#include <iomanip>
#include<algorithm>
#include <stack>
#include<cmath>
using namespace std;
int main()
{
    int n;
    int a[1005];
    int b[1005]={0};
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n;i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i < n;++i){
        b[i] = max(b[i - 1] + a[i], a[i]);
        sum = max(b[i], sum);
    }
    cout << sum;
    return 0;
}

0x07 渊子赛马

题目描述

赛马是一古老的游戏，早在公元前四世纪的中国，处在诸侯割据的状态，历史上称为“战国时期”。在魏国作官的孙膑，因为受到同僚庞涓的迫害，被齐国使臣救出后，到达齐国国都。赛马是当时最受齐国贵族欢迎的娱乐项目。上至国王，下到大臣，常常以赛马取乐，并以重金赌输赢。田忌多次与国王及其他大臣赌输赢，屡赌屡输。一天他赛马又输了，回家后闷闷不乐。孙膑安慰他说：“下次有机会带我到马场看看，也许我能帮你。” 孙膑仔细观察后发现，田忌的马和其他人的马相差并不远，只是策略运用不当，以致失败。比赛前田忌按照孙膑的主意，用上等马鞍将下等马装饰起来，冒充上等马，与齐王的上等马比赛。第二场比赛，还是按照孙膑的安排，田忌用自己的上等马与国王的中等马比赛，在一片喝彩中，只见田忌的马竟然冲到齐王的马前面，赢了第二场。关键的第三场，田忌的中等马和国王的下等马比赛，田忌的马又一次冲到国王的马前面，结果二比一，田忌赢了国王。就是这么简单，现在渊子也来赛一赛马。假设每匹马都有恒定的速度，所以速度大的马一定比速度小的马先到终点（没有意外！！）。不允许出现平局。最后谁赢的场数多于一半(不包括一半)，谁就是赢家(可能没有赢家)。渊子有 N(1<=n<=1000)匹马参加比赛。对手的马的数量与渊子马的数量一样，并且知道所有的马的速度。聪明的你来预测一下这场世纪之战的结果，看看渊子能否赢得比赛。

输入

输入有多组测试数据。每组测试数据包括 3 行：第一行输入 N。表示马的数量。第二行有 N 个整型数字，即渊子的 N 匹马的速度。第三行有 N 个整型数字，即对手的 N 匹马的速度。当 N 为 0 时退出。

输出

若通过聪明的你精心安排，如果渊子能赢得比赛，那么输出YES。否则输出NO。

样例输入

样例输出

1
2

YES
NO

代码

#include <iostream>
#include<vector>
#include<string>
#include <iomanip>
#include<algorithm>
#include <stack>
using namespace std;
typedef long long ll;
int n;
int a[1005];
int b[1005];
int main()
{
    while(cin>>n&&n!=0){
        for (int i = 0; i < n;++i){
            cin >> a[i];
        }
        for (int i = 0; i < n;++i){
            cin >> b[i];
        }
        sort(a, a + n);
        sort(b, b + n);
        int sum = 0;
        for (int i = 0; i < n;++i){
            for (int j = 0; j < n;++j){
                if(a[j]>b[i]){
                    sum++;
                    a[j] = 0;
                    break;
                }
            }
        }
        if(sum>=n/2+1){
            cout << "YES" << endl;
        }
        else
            cout << "NO" << endl;
    }
    return 0;
}

0x08 最长上升子序列

题目描述

给定一个长度为n的字符串S（只包含小写字母），给出q次查询，对于每次查询x，求出以S[x]（下标从0开始）为起始的最长上升子序列的长度（严格增）。

输入

第一行两个整数n,q(1<=n,q<=1e5)，意义见题目描述。

第二行一个长度为n的字符串S。

第三行q个整数x(0<=x<n)，表示q次查询。

输出

输出q个数（以空格分割，行末有空格），表示以S[x]为起始的最长上升子序列的长度。

样例输入

1
2
3

10 3
abbaaccbbd
2 5 8

样例输出

3 2 2

代码

#include<iostream>
using namespace std;
int n,q;
char a[100010];
int ans[100010],p[30];
int main()
{
    //cin>>n>>q;
    scanf("%d%d",&n,&q);
    //cin>>a;
    scanf("%s",a);
    for(int i=n-1;i>=0;i--)
    {
        ans[i]=1;
        for(int j=a[i]-'a'+1;j<26;j++)
            ans[i]=max(ans[i],p[j]+1);
        p[a[i]-'a']=ans[i];
    }
    int x;
    while(q--)
    {
    	scanf("%d",&x);
    	printf("%d ",ans[x]);
    }
}

0x09 区间第K小

题目描述

花花上算法课又偷偷摸鱼。她今天刚学会如何求解区间第k小的数，但是感觉没什么意思。于是她将题目稍稍改动了一下：对于一个长度为n的数列a来说，一共有n*(n+1)/2个子区间，对于数列a的每一个子区间，如果这个子区间的长度小于k，我们不管它，否则把该子区间的第k小的数加入新数列b（初始为空）。花花并不关心数列b里面的元素是什么，她只想知道新数列b中第k小的元素是多少。

例如，一个长度为4的数列a={5,3,4,9}，当k取3时只有三个子区间长度是>=3的：{5,3,4},{3,4,9}和{5,3,4,9}。分别提取各自的第3小的数加入b数列得到{5,9,5},其中第3小的数为9。

输入

第一行两个数n，k（1<=n, k<=1e5)意义见题目描述

第二行n个数表示数列a中的元素ai。(1<=ai<=1e9)

数据保证数列b中的元素个数不少于k个

输出

输出一个数，表示数列b中的第k小的数

样例输入

1 2	4 3 5 3 4 9

样例输出

代码

//没看懂
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
int n, k;
long long max_position(int x)
{
    long long result = 0;             
    int l = 0, r = -1, num = 0;
    while (r < n)
    {
        if (num < k)                   
        {
            if (a[r + 1] <= x)num++;
            r++;
        }
        else
        {
            result += n - r;
            if (a[l] <= x)num--;
            l++;
        }
    }
    return result;
}
int main()
{
    cin >> n >> k;
    int*b=new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b, b + n);
    int len = unique(b, b + n) - b;    
    int l = 0, r = len - 1;
    int ans = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        long long ret = max_position(b[mid]);
        if (ret >= k)        
        {
            ans = b[mid];
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << ans;
    return 0;
}

0x0A 元素整除问题

题目描述

输入20个整数，输出其中能被数组中其它元素整除的那些数组元素。

输入

输入20个整数

输出

按输入顺序输出符合要求的数字，每行输出一个整数。

样例输入

1	2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

样例输出

代码

#include <iostream>
#include<vector>
#include<string>
#include <iomanip>
#include<algorithm>
#include <stack>
#include<cmath>
using namespace std;
int main()
{
    int a[20],b[20];
    for(int i=0;i<20;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b,b+20);
    for(int i=0;i<20;i++)
    {
        //cout<<b[i]<" ";
        int sign=0;
        for(int j=0;j<20;j++)
        {
            if(b[j]<a[i])
            {
                if(a[i]%b[j]==0)
                    sign=1;
            }
            else
                break;
        }
        if(sign==1)
            cout<<a[i]<<endl;
    }
    return 0;
}

0x0B 八皇后问题

题目描述

努比亚和苏丹没有子女，所以他要从一些有集成资格的继承者中挑选一个出来继承王位。他希望这个继承者足够聪明，所以他准备了一个西洋棋盘，上面的每个格子中均有一个 1-99 的数字。他又准备了 8 个皇后棋子。

8 皇后的规则就是不能有任何棋子同行或者同列或者同斜线，在满足这个规则的同时，王位继承者还需要让 8 个皇后所在的位置的数字的和是最大的。

输入

输入一个数字 k(k≤20)，代表棋盘的数量。

接下来有 k 个棋盘，每个棋盘有 64 个数字，分成 8 行 8 列输入，具体可见样例，每一个数字均小于 100。

输出

每一个棋盘对应输出最大的数值，一共输出 k行

样例输入

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 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

样例输出

代码

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
int map[8][8],x[8],ans,sum;
bool check(int xx,int yy)
{
    for(int i = 0; i < xx; i++)
    {
        if(yy == x[i]) return false;
        if(abs(xx - i) == abs(yy - x[i])) return false;
    }
    return true;
}
void queen(int n)
{
    if(n == 8){ans = max(ans,sum);return;}
    for(int i = 0; i < 8; i++)
    {
        if(check(n,i))
        {
            x[n] = i;
            sum += map[n][i];
            queen(n+1);
            x[n] = -1;
            sum -= map[n][i];
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ans = 0;
        sum = 0;
        for(int i = 0; i < 8; i++)
            for(int j = 0; j < 8; j++)
                scanf("%d",&map[i][j]);
        memset(x,-1,sizeof(x));
        queen(0);
        printf("%d\n",ans);
    }
    return 0;
}

0x0C 组合运算式

题目描述

请考虑一个被空格分隔的，由1到N的整数组成的递增数列：1 2 3 …N。现在请在数列中插入表示加的“+”，或者表示减“-”，亦或者表示空白的“ ”(例如1-2 3就等于1-23)，来将每一对数字组合成一个表达式（第一个数字前无空格）。计算该表达式的结果并判断其值是否为0。请你写一个程序找出所有产生和为零的长度为N的数列。

输入

输入为一行，包含一个整数N，3*≤N≤*9。

输出

输出为所有在每对数字间插入“+”, “-”, 或 “ ”后能得到和为零的数列，并按照字典（ASCII码）序排列。

样例输入

样例输出

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

代码

#include<iostream>
#include<stdio.h>
using namespace std;
int n;
int OP[15] = {1,1};
void dfs(int d,int sum,int pre,int s)
{
    sum += pre;
    if(d == n)
    {
        if(!sum)
        {
            printf("1");
            for(int i = 2; i <= n; i++)
            {
                if(!OP[i]) printf(" %d",i);
                else if(OP[i] == 1) printf("+%d",i);
                else printf("-%d",i);
            }
            printf("\n");
        }
        return;
    }
    if(s<=3){
        OP[d+1] = 0;
        if(pre >= 0) dfs(d+1,sum-pre,pre*10+d+1,s+1);
        else dfs(d+1,sum-pre,pre*10-d-1,s+1);
    }
    OP[d+1] = 1;
    dfs(d+1,sum,d+1,s);
    OP[d+1] = 2;
    dfs(d+1,sum,-d-1,s);
}
int main()
{
    scanf("%d",&n);
    dfs(1,0,1,0);
    return 0;
}

0x0D 无脑博士的试管们

题目描述

无脑博士有三个容量分别是 A,B,C 升的试管，A,B,C分别是三个从 1到 20的整数，最初，A 和 B 试管都是空的，而 C 试管是装满硫酸铜溶液的。有时，无脑博士把硫酸铜溶液从一个试管倒到另一个试管中，直到被灌试管装满或原试管空了。当然每一次灌注都是完全的。由于无脑博士天天这么折腾，早已熟练，溶液在倒的过程中不会有丢失。

写一个程序去帮助无脑博士找出当 A 试管是空的时候，C 试管中硫酸铜溶液所剩量的所有可能性。

输入

多组测试用例，对于每组测试用例，输入包括一行，为空格分隔开的三个数，分别为整数 A,B,C。

输出

输出包括一行，升序地列出当 A 试管是空的时候，C 试管溶液所剩量的所有可能性。

样例输入

2 5 10

样例输出

1	5 6 7 8 9 10

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<set>
using namespace std;
set<int> s;
int na,nb,nc;
bool visited[25][25][25];
void dfs(int a,int b,int c)
{
    if(visited[a][b][c]) return;
    visited[a][b][c] = true;
    if(!a) s.insert(c);
    if(a <= nb-b) dfs(0,a+b,c);
    else dfs(a-nb+b,nb,c);
    if(b <= na-a) dfs(a+b,0,c);
    else dfs(na,a-na+b,c);
    if(a <= nc-c) dfs(0,b,a+c);
    else dfs(a-nc+c,b,nc);
    if(c <= na-a) dfs(a+c,b,0);
    else dfs(na,b,c-na+a);
    if(b <= nc-c) dfs(a,0,b+c);
    else dfs(a,b-nc+c,nc);
    if(c <= nb-b) dfs(a,b+c,0);
    else dfs(a,nb,c-nb+b);
}
int main()
{
    while(~scanf("%d %d %d",&na,&nb,&nc))
    {
        s.clear();
        memset(visited,0,sizeof(visited));
        dfs(0,0,nc);
        set<int>::iterator it = s.begin();
        printf("%d",*it);
        it++;
        for(; it != s.end(); it++)
        {
            printf(" %d",*it);
        }
        printf("\n");
    }
    return 0;
}

二分查找

二分查找算法考试复习(不仅仅是二分查找，还有一些水题) 单词排序题目描述小红学会了很多英文单词，妈妈为了帮小红加强记忆，拿出纸、笔，把 N 个单词写在纸上的一行里，小红看了几秒钟后，将这...

快速跳过青年大学习

本教程适用于安卓手机准备既然要优雅地完成大学习，首先得让微信给我们一个输入自己的代码的机会按照如下步骤可以打开微信的开发工具微信浏览器网页打开http://debugx5.qq.c...