算法OJ练习Ⅰ

问题 A: 小雏鸟的成人式 2

题目描述

陶行知先生说：“我们要活的书，不要死的书 ”。

小雏鸟们从书上都是对的到现在能去伪存真的去使用书籍，证明你们长大了。总之就是要有自己的主见，自己的思考。

大白希望大家都能拿到一百分，所以对100这个数以及他的倍数很喜欢。

大白发现，从1开始，一定能找出一个序列从小到大排列，使得每一项都是 恰好能且仅能 被100整除D次。

请你编写程序，找到这个数列里第N个数。

输入

多行。每行输入两个整数，表示D和N，N范围[1,100]，D范围[0,2]

输出

每行对应输入，给出一个符合题意的整数

样例输入

1
2
3
0 5
1 11
2 85

样例输出

1
2
3
5
1100
850000

思路及代码

这道题的关键之处在于那个恰好且仅能被100整除D次出，这样的话当D取0时第一百个数就不是100了，因为100时能被D取1时能整除一次的第一个数，所以当D取0时的第一百个数就变成了101，所以没到第100个数的时候会有一个跳变，可以先加个判断，若其是第一百个数就先给它加个1；这样就不会出现错误的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cmath>
using namespace std;
int D,N;
 
int main()
{
    while(cin >> D >> N)
    {   
        if(N == 100)
            N ++ ;
        if(D == 1)
            N *= 100;
        else if(D == 2)
            N *= 10000;
        cout << N << endl;
    }
        return 0;
}

问题 B: 小雏鸟的成人式 3

题目描述

陶行知先生说：“因为道德是做人的根本。根本一坏，纵然使你有一些学问和本领，也无甚用处。”

小雏鸟们需要时刻铭记在心，不管你长成什么样的的攻城狮，都必须三观正确。

涛涛轰这一天带着爱美酱来到了一个风景如画的地方游玩。艳阳高照，他俩玩的很尽兴，但是现在他们口渴了。

涛涛轰：“我要买饮料！”

店主：“我们这里有三种饮料，矿泉水1.5元一瓶，可乐2元一瓶，橙汁3.5元一瓶。”

涛涛轰：“好的，给我一瓶矿泉水。”

说完他掏出一张N元的大钞递给店主。

店主：“我忘了提醒你了，我们这里没有找客人钱的习惯的，多的钱我们都当小费收了的，嘿嘿。”

涛涛轰：“……”

涛涛轰环顾四周，就这一家商店，况且实在太渴了，看着脸热的粉扑扑的一头汗的爱美酱，就决定在这买了。不过涛涛轰想，与其把钱当小费送给他还不如自己多买一点饮料，反正早晚都要喝，但是要尽量少让他赚小费。

现在涛涛轰希望你能帮他计算一下，最少他要给店主多少小费。

输入

输入数据的第一行是一个整数T(1<=T<=100)，代表测试数据的数量。然后是T行测试数据，每个测试数据只包含一个正整数N（1<=N<=10000），N代表小明手中钞票的面值，以分为单位。
注意：商店里只有题中描述的三种饮料。

输出

对于每组测试数据，请你输出小明最少要浪费多少钱给店主作为小费，以分为单位。

样例输入

1
2
3
2
900
250

样例输出

1
2
0
50

代码及思路

首先题目中的橙汁价格=可乐价格＋矿泉水价格 ，所以我们可以不用考虑购买橙汁，可以去考虑购买可乐或者矿泉水因为可乐和矿泉水的价格只相差50分，可以转换成全部购买矿泉水，然后判断剩下的钱是否大于或者等于50分，满足，则可用矿泉水加上50分去换一瓶可乐，这样可以喝到最多的水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <cmath>
using namespace std;
int T,n;
int x,y;
 
int main()
{
    cin >> T;
    while(T --)
    {   
        cin >> n;
        x = n % 150;
        y = n / 150;
        while(x >= 50 && y > 0) {
            x -= 50;
            y -- ;
        }
        cout << x << endl;
    }
        return 0;
}

问题 C: 大白just大白

题目描述

大家都知道，大白对学术要求是很严格的。抄作业、考试作弊神马的在大白这简直不能忍。

这不刚刚过去的期末考试。有n个学生被查出来有问题。

大白给了他们申辩的机会，每个学生可以提交一段文字，作为申辩理由。但是大白发现来的人总会有一些奇怪的理由。

大白提前列了m个常见借口关键字。他想看看来申辩的学生中最烂的申辩理由是什么。

所谓最烂申辩理由就是，申辩里，含有常见借口关键字最多的。

含有关键字，指的是，理由中出现了一串和关键字完全匹配的字符串，如果出现大写小写不同，也认为匹配。比如，关键字是 bed 理由中出现Bedroom算含有一个关键字。

输入

一个输入可能有多个case，每个case第一行两个数。分别代表n 和 m

接下来m行，每行一个关键字（字符串）

再接下来n行字符串。m和n都不大于20

每一个借口和借口关键字只会包含大小写字母，长度不会超过4000个字符。

输出

对于每个case输出一行字符串，表示最烂的理由。若有多个理由包含相同数目的关键字，按输入顺序输出靠前的那个。

样例输入

1
2
3
4
5
6
7
8
9
10
11
2 3
love
cumt
ACM
ILoveCUMTACM
cumtAACM
2 2
A
b
Ab
bA

样例输出

1
2
ILoveCUMTACM
Ab

解题思路及代码

思路：开两个个string类型的数组， 将输入的字符串存起来，同时由于题目要求不考虑大小写，所以我们需要把字母全部转化为大写，这个时候就出现了一个问题，输出的时候需要输出原串，所以我们需要再开两个数组，对这两个数组进行操作，输出的时候输出原串。

问题 D: 小雏鸟的计算

题目描述

小雏鸟们的三角形翅膀终于长出健壮的肌肉和丰满的羽毛，已经跃跃欲试的去准备尝试挑战新的难题了。

考虑以下的算法：
\1. 输入 n
\2. 印出 n
\3. 如果 n = 1 结束
\4. 如果 n 是奇数 那么 n=3*n+1
\5. 否则 n=n/2
\6. GOTO 2
例如输入 22 得到的数列： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
据推测此算法对任何整数而言会终止 (当打印出 1 的时候)。虽然此算法很简单，但以上的推测是否真实却无法知道。然而对所有的n ( 0 < n < 1000000 )来说，以上的推测已经被验证是正确的。
给一个输入 n 透过以上的算法我们可以得到一个数列（1作为结尾）。此数列的长度称为n的cycle length。上面提到的例子 22的 cycle length为 16.
问题来了：对任2个整数i，j我们想要知道介于i，j（包含i，j）之间的数所产生的数列中最大的cycle length是多少。

输入

输入可能包含了好几行测试数据，每一行有一对整数 i，j 。

0< i，j < 1000000

输出

对每一对输入 i j你应该要输出 i j和介于i j之间的数所产生的数列中最大的cycle length。

样例输入

1
2
3
4
5
1 10
10 1
100 200
201 210
900 1000

样例输出

1
2
3
4
5
1 10 20
10 1 20
100 200 125
201 210 89
900 1000 174

思路及代码

题目需要统计的是使用这个算法的到数列的长度，只需要定义函数判断即可。

很显然这个算法是一个递归的，可以写成递归的形式来判断。

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
# include <iostream>
#include <algorithm>
using namespace std;
int i,j;
int c ;
void cycle(int x)
{
    if(x == 1) return ;
    if(x % 2 == 0) x /= 2;
    else x = 3 * x + 1;
    cycle(x);
    c ++ ;
}
int f(int y)
{
    c = 1 ;
    cycle(y);
    return c;
}
 
int main()
{
    while(cin >> i >> j)
    {
        int l = i , r = j ;
        int o = 0;
        if(i > j) swap(j,i);
        for(i; i <= j; i ++ )
            o = max(o, f(i));
        printf("%d %d %d\n",l,r,o);
    }
    return 0;
}

问题 E: 进制转换

题目描述

输入一个十进制正整数，然后输出它所对应的八进制数。

输入

输入一个十进制正整数n(1≤n≤106) 。

输出

输出n对应的八进制数，输出在一行。

样例输入

1
10

样例输出

1
12

代码及思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
 
using namespace std;
int num;
int main()
{
    int num;
 
    scanf("%d",&num);
 
    printf("%o",num);
 
    return 0;
}

问题 F: 排列问题

题目描述

输入一个可能含有重复字符的字符串，打印出该字符串中所有字符的全排列。

输入

单组测试数据，输入数据是一个长度不超过10个字符的字符串，以逗号结尾。

输出

打印出该字符串中所有字符的全排列。以字典序顺序输出，用空格分隔。

样例输入

1
abc,

样例输出

1
abc acb bac bca cab cba

代码及思路

思路：

1
2
3
4
5
//介绍getline()函数
istream &getline( char *buffer, streamsize num, char delim );
istream &getline( char *buffer, streamsize num );
//其中的buffer、num、delim的意思分别为
//buffer： 进行读入操作的输入流，num 存储读入的内容，delim 终结符
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    char str[11];
    cin.getline(str, 11, ',');
    int x = 0;
    for (; str[x] != '\0'; x++);
    sort(str, str + x);
    do {
        for (int i = 0; i < x; i++) {
            cout << str[i];
        }
        cout << " ";
    } while (next_permutation(str, str + x));
    return 0;
}

问题 H: 求第k小

题目描述

给定n(1<=n<=1000000)个元素，求第k小数(1<=k<=n)。

输入

一组样例。第一行输入两个整数n和k。第二行输入n个不同的int范围内的数。

输出

输出一行，输出第k小数。

样例输入

1
2
5 2
1 5 3 2 4

样例输出

1
2

思路及代码

这道题目是求的第K小的数，通常来讲，第一时间想到的就说做一个排序，然后直接输出第K小就行了。

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
#include<iostream> 

using namespace std;

const int N = 1e6 + 10;
int n,m;
int q[N];
 
void quick_sort(int q[], int l, int r)
{
    if(l >= r) return;
    int x = q[l], i= l - 1,j = r + 1;
    while(i < j)
    {
        do i ++ ; while(q[i] < x);
        do j -- ; while(q[j] > x);
        if(i < j) swap(q[i] , q[j]);
    }
    quick_sort(q, l , j);
    quick_sort(q, j + 1 , r);
}
int main()
{
    cin>>n>>m;
    for(int i = 0; i < n; i ++ ) cin>>q[i];

    quick_sort(q, 0 , n - 1);
 
    printf("%d ", q[m-1]);
 
    return 0;
}

当然还有一种效率更高的方法，记得老师上课的时候讲过，先空在这里，过会再来填坑。

问题 I: 沙子的质量

题目描述

设有N堆沙子排成一排，其编号为1，2，3，…，N（N< =300）。每堆沙子有一定的数量，可以用一个整数来描述，现在要将N堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有4堆沙子分别为1 3 5 2我们可以先合并1、2堆，代价为4，得到4 5 2又合并1，2堆，代价为9，得到9 2，再合并得到11，总代价为4+9+11=24，如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22；问题是：找出一种合理的方法，使总的代价最小。输出最小代价。

输入

第一行一个数N表示沙子的堆数N。 第二行N个数，表示每堆沙子的质量。 a[i]< =1000。

输出

合并的最小代价。

样例输入

1
2
4
1 3 5 2

样例输出

1
22

代码及思路

思路：这道题是一道动态规划问题，可以将其划分为就解最优子问题的问题，例如，将其划分为两个方面。

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
#include <iostream>
 
using namespace std;
 
const int N = 307;
 
int s[N];
int f[N][N];
 
int main() {
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        s[i] += s[i - 1];
    }
 
    for (int i = n; i >= 1; i--) {
        for (int j = i; j <= n; j++) {
            if (j == i) {
                f[i][j] = 0;
                continue;
            }
            f[i][j] = 1e9;
            for (int k = i; k < j; k++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }
 
    cout << f[1][n] << endl;
 
    return 0;
}

问题 J: 最长公共子序列

题目描述

一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad” ,顺次选1，3，5个字符就构成子串” cad” ,现给定两个字符串，求它们的最长共公子串。

输入

第一行两个字符串用空格分开。两个串的长度均小于2000 。

输出

最长子串的长度。

样例输入

1
abccd aecd

样例输出

1
3

代码及思路

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
# include <iostream>
# include <cstring>
using namespace std;
const int  N = 2010;
int f[N][N];
string a,b;
 
int max(int a,int b)
{
   if (a>=b)  return a;
    return b; 
}
int main()
{
    int i,j,len_a,len_b;    
    cin >> a >> b;
    len_a = a.length();
    len_b = b.length();      
    for(i = 1;i <= len_a;i ++ )
       {
       for(j = 1 ;j <= len_b;j ++ )
           {
           if (a[i-1] == b[j-1]) f[i][j] = f[i-1][j-1] + 1;
           else f[i][j]=max(f[i-1][j],f[i][j-1]);
           }
       }     
    cout << f[len_a][len_b];
    return 0;
}

快速幂

快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以以[公式]的时间复杂度计算乘方。快速幂不仅本身非常常见，而且后续很多算法也都会用到快速幂。

让我们先来思考一个问题：7的10次方，怎样算比较快？

让我们先来思考一个问题：7的10次方，怎样算比较快？

方法1：最朴素的想法，77=49，497=343，… 一步一步算，共进行了9次乘法。

这样算无疑太慢了，尤其对计算机的CPU而言，每次运算只乘上一个个位数，无疑太屈才了。这时我们想到，也许可以拆分问题。

方法2：先算7的5次方，即77777，再算它的平方，共进行了5次乘法。

但这并不是最优解，因为对于“7的5次方”，我们仍然可以拆分问题。

方法3：先算77得49，则7的5次方为4949*7，再算它的平方，共进行了4次乘法。

模仿这样的过程，我们得到一个在 [公式] 时间内计算出幂的算法，也就是快速幂。

递归快速幂

刚刚我们用到的，无非是一个二分的思路。我们很自然地可以得到一个递归方程：

[公式]

计算a的n次方，如果n是偶数（不为0），那么就先计算a的n/2次方，然后平方；如果n是奇数，那么就先计算a的n-1次方，再乘上a；递归出口是a的0次方为1。

递归快速幂的思路非常自然，代码也很简单（直接把递归方程翻译成代码即可）：

1
2
3
4
5
6
7
8
9
10
11
12
13
//递归快速幂
int qpow(int a, int n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a;
    else
    {
        int temp = qpow(a, n / 2);
        return temp * temp;
    }
}

注意，这个temp变量是必要的，因为如果不把[公式]记录下来，直接写成qpow(a, n /2)*qpow(a, n /2)，那会计算两次[公式]，整个算法就退化为了 [公式] 。

在实际问题中，题目常常会要求对一个大素数取模，这是因为计算结果可能会非常巨大，但是在这里考察高精度又没有必要。这时我们的快速幂也应当进行取模，此时应当注意，原则是步步取模，如果MOD较大，还应当开long long。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//递归快速幂（对大素数取模）
#define MOD 1000000007
typedef long long ll;
ll qpow(ll a, ll n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 1)
        return qpow(a, n - 1) * a % MOD;
    else
    {
        ll temp = qpow(a, n / 2) % MOD;
        return temp * temp % MOD;
    }
}

大家知道，递归虽然简洁，但会产生额外的空间开销。我们可以把递归改写为循环，来避免对栈空间的大量占用，也就是非递归快速幂。

非递归快速幂

我们换一个角度来引入非递归的快速幂。还是7的10次方，但这次，我们把10写成二进制的形式，也就是 [公式] 。

现在我们要计算 [公式] ，可以怎么做？我们很自然地想到可以把它拆分为 [公式] . 实际上，对于任意的整数，我们都可以把它拆成若干个 [公式] 的形式相乘。而这些[公式]，恰好就是 [公式] 、[公式]、[公式]……我们只需不断把底数平方就可以算出它们。

我们先看代码，再来仔细推敲这个过程：

1
2
3
4
5
6
7
8
9
10
11
//非递归快速幂
int qpow(int a, int n){
    int ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans *= a;  //ans乘上当前的a
        a *= a;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return ans;
}

最初ans为1，然后我们一位一位算：

1010的最后一位是0，所以a^1这一位不要。然后1010变为101，a变为a^2。

101的最后一位是1，所以a^2这一位是需要的，乘入ans。101变为10，a再自乘。

10的最后一位是0，跳过，右移，自乘。

然后1的最后一位是1，ans再乘上a^8。循环结束，返回结果。

preview

这里的位运算符，**>>是右移，表示把二进制数往右移一位，相当于/2；&是按位与，&1可以理解为取出二进制数的最后一位**，相当于%2==1。这么一等价，是不是看出了递归和非递归的快速幂的关系了？虽然非递归快速幂因为牵扯到二进制理解起来稍微复杂一点，但基本思路其实和递归快速幂没有太大的出入。

快速幂的拓展

上面所述的都是整数的快速幂，只要a的数据类型支持乘法且满足结合律，快速幂的算法都是有效的。矩阵、高精度整数，都可以照搬这个思路。下面给出一个模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//泛型的非递归快速幂
template <typename T>
T qpow(T a, ll n)
{
    T ans = 1; // 赋值为乘法单位元，可能要根据构造函数修改
    while (n)
    {
        if (n & 1)
            ans = ans * a; // 这里就最好别用自乘了，不然重载完*还要重载*=，有点麻烦。
        n >>= 1;
        a = a * a;
    }
    return ans;
}

例如，矩阵快速幂的一个经典应用是求斐波那契数列：

子序列

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
# include <iostream>

# include <cstring>

using namespace std;
const int  N = 2010;
int f[N][N];
string a,b;

int max(int a,int b)
{
   if (a>=b)  return a;
    return b; 
}
int main()
{
    int i,j,len_a,len_b;    
    cin >> a >> b;
    len_a = a.length();
    len_b = b.length();      
    for(i = 1;i <= len_a;i ++ )
       {
       for(j = 1 ;j <= len_b;j ++ )
           { 
           if (a[i-1] == b[j-1]) f[i][j] = f[i-1][j-1] + 1;
           else f[i][j]=max(f[i-1][j],f[i][j-1]);
           }
       }     
    cout << f[len_a][len_b];
    return 0;
}

快速幂部分知识摘自于：https://zhuanlan.zhihu.com/p/95902286

算法OJ
算法OJ

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！