重生之我是机试coding怪

2023-06-26

字数统计: 7.3k字 | 阅读时长≈ 36分

重生之我是机试coding怪

免责申明：我不是coding很厉害的人，我用的方法也是最笨的方法，但是每道题都可以AC，可以作为参考，网上还有很多比我复杂度更低思路更清晰的方法。

2 暴力求解

对于我这种编程思维很弱的人来说，暴力求解就是我滴最爱捏~

2.1枚举

例题2.1 abc

设a、b、c均是0到9之间的数字，abc、bcc是两个三位数，且有：abc+bcc=532。求满足条件的所有a、b、c的值。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    // 设a、b、c均是0到9之间的数字，abc、bcc是两个三位数，且有：abc+bcc=532。求满足条件的所有a、b、c的值。
    for (int a = 0; a < 10; a++)
    {
        for (int b = 0; b < 10; b++)
        {
            for (int c = 0; c < 10; c++)
            {
                int num1 = a * 100 + b * 10 + c;
                int num2 = b * 100 + c * 10 + c;
                if(num1 + num2 == 532)
                {
                    cout << a << " " << b << " " << c << " " << endl;
                }
            }
        }
    }
    return 0;
}

例题2.2 反序数

设N是一个四位数，它的9倍恰好是其反序数（例如：1234的反序数是4321）* *求N的值

#include<bits/stdc++.h>
using namespace std;

int Reverse1(int x)
{
    int revx = 0;
    while(x != 0)
    {
        revx *= 10;
        revx += x % 10;
        x /= 10;
    }
    return revx;
}
int main()
{
    for(int i = 1000; i < 10000; i++)
    {
        if(i * 9 == Reverse1(i))
        {
            cout<<i<<endl;
        }
    }
    return 0;
}

例题2.3 对称平方数1

打印所有不超过256，其平方具有对称性质的数。如2，11就是这样的数，因为2*2=4，11*11=121。

#include<bits/stdc++.h>
using namespace std;
int Reverse2(int x)
{
    int revx = 0;
    while(x != 0)
    {
        revx *= 10;
        revx += x % 10;
        x /= 10;
    }
    return revx;
}

int main()
{
    for(int i = 0; i < 257; i++)
    {
        if(i * i == Reverse2(i * i))
        {
            cout<<i<<endl;
        }
    }
    return 0;
}

习题2.1 与7无关的数

一个正整数,如果它能被7整除,或者它的十进制表示法中某个位数上的数字为7, 则称其为与7相关的数.现求所有小于等于n(n<100)的与7无关的正整数的平方和。

案例可能有多组。对于每个测试案例输入为一行,正整数n,(n<100)

对于每个测试案例输出一行，输出小于等于n的与7无关的正整数的平方和。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int num = 0;
    int n;
    int tag = 1;
    do
    {
        cin>>n;
    } while (n <= 0);

    for(int i = 1; i <= n; i++)
    {
        int a = i / 10;
        int b = i % 10;
        if(i % 7 == 0)
        {
            tag = 0;
        }
        else if(a == 7 || b == 7)
        {
            tag = 0;
        }

        if(tag)
        {
            num += i*i;
        }
        tag = 1;
    }
    cout<<num<<endl;
    return 0;
}

习题2.2 百鸡问题

用小于等于n元去买100只鸡，大鸡5元/只，小鸡3元/只,还有1/3元每只的一种小鸡，分别记为x只,y只,z只。编程求解x,y,z所有可能解。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int money;
    do {
        cin>>money;
    } while (money<=0);

    for(int x = 0; x <= 100; x++)
    {
        for(int y = 0; y <= 100 - x; y++)
        {
            for(int z = 0; z <= 100 - x - y; z++)
            {
                if((x * 5 + y * 3 + z * 0.333 <= money)&&(x + y + z == 100))
                {
                    cout<<"x="<<x<<",y="<<y<<",z="<<z<<endl;
                }
            }
        }
    }

    return 0;
}

习题2.3 Old Bill

Among grandfather’s papers a bill was found. 72 turkeys $679 The first and the last digits of the number that obviously represented the total price of those turkeys are replaced here by blanks (denoted _), for they are faded and are illegible. What are the two faded digits and what was the price of one turkey? We want to write a program that solves a general version of the above problem. N turkeys $XYZ The total number of turkeys, N, is between 1 and 99, including both. The total price originally consisted of five digits, but we can see only the three digits in the middle. We assume that the first digit is nonzero, that the price of one turkeys is an integer number of dollars, and that all the turkeys cost the same price. Given N, X, Y, and Z, write a program that guesses the two faded digits and the original price. In case that there is more than one candidate for the original price, the output should be the most expensive one. That is, the program is to report the two faded digits and the maximum price per turkey for the turkeys.

The first line of the input file contains an integer N (0<N<100), which represents the number of turkeys. In the following line, there are the three decimal digits X, Y, and Z., separated by a space, of the original price $XYZ.

For each case, output the two faded digits and the maximum price per turkey for the turkeys.

// 72只火鸡_679_ N只火鸡（>=1，<=99)  一个数不为0  火鸡单价为总数
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int num_t;
    int x,y,z;
    while (cin>>num_t)
    {
        cin>>x>>y>>z;
        int ave_t_p = 0;
        // _xyz_ 9xyz9
        int max_p = 9 * 10000 + x * 1000 + y * 100 + z * 10 + 9;
        int p = 1;
        while (p * num_t <= max_p)
        {
            int total_p = p * num_t;
            if(((total_p / 10000) > 0) && ((total_p / 10000) < 10))
            {
                int a = (total_p % 10000) / 1000;
                int b = (total_p % 1000) / 100;
                int c = (total_p % 100) / 10;
                if(a == x && b == y && c == z)
                {
                    if(p > ave_t_p)
                    {
                        ave_t_p = p;
                    }
                }
            }
            p++;
        }

        int total_p = num_t * ave_t_p;
        // cout<<total_p<<endl;
        int o = total_p / 10000;
        int q = total_p % 10;
        if(total_p != 0)
        {
            cout<<o<<" "<<q<<" "<<ave_t_p<<endl;
        } else
        {
            cout<<0<<endl;
        }
    }

    return 0;
}

2.2 模拟

2.2.1 图形排版

2.4 输出梯形

#include<bits/stdc++.h>
using namespace std;

int main()
{
    // 输出梯形  输入一个高度h  输出为一个高度为h，上底板长度为h的梯形
    int h;
    do {
        cin>>h;
    } while (h < 1 || h > 1000);

    int num1 = 0;
    int num2 = 0;

    int row = h;
    int col = h + 2 * (h - 1);

    for(int i =0; i < row; i++)
    {
        while (num1 <= col - (h + i * 2))
        {
            cout<<" ";
            num1++;
        }
        while (num2 <= (h + 2 * i))
        {
            cout<<"*";
            num2++;
        }
        cout<<endl;
        num1 = num2 = 0;
    }


    return 0;
}

2.5 叠筐

需要的时候，就把一个个大小差一圈的筐叠上去，使得从上往下看时，边筐花色交错。这个工作现在要让计算机来完成，得看你的了。

输入是一个个的三元组，分别是，外筐尺寸n（n为满足0<n<80的奇整数），中心花色字符，外筐花色字符，后二者都为ASCII可见字符；

输出叠在一起的筐图案，中心花色与外筐花色字符从内层起交错相叠，多筐相叠时，最外筐的角总是被打磨掉。叠筐与叠筐之间应有一行间隔。

11 B A

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 80 + 10;

char matrix[MAXN][MAXN];

int main() {
    int n;                                          //叠框大小
    char center;                                    //中心花色字符
    char outside;                                   //外筐花色字符
    bool firstCase = true;                          //第一组数据标志
    while (scanf("%d %c %c", &n, &center, &outside) != EOF) {
        if (firstCase == true) {
            firstCase = false;
        } else {
            printf("\n");
        }
        for (int i = 0; i <= n / 2; ++i) {          //(i, i)是每圈左上角坐标
            int j = n - i - 1;                      //(j, j)是每圈右下角坐标
            int length = n - 2 * i;                 //求当前圈的边长
            char current;                           //求当前圈填充字符
            if ((n / 2 - i) % 2 == 0) {
                current = center;
            } else {
                current = outside;
            }
            for (int k = 0; k < length; ++k) {      //为当前圈赋值
                matrix[i][i + k] = current;         //上边赋值
                matrix[i + k][i] = current;         //左边赋值
                matrix[j][j - k] = current;         //下边赋值
                matrix[j - k][j] = current;         //右边赋值
            }
        }
        if (n != 1) {                               //剔除4个角
            matrix[0][0] = ' ';
            matrix[0][n - 1] = ' ';
            matrix[n - 1][0] = ' ';
            matrix[n - 1][n - 1] = ' ';
        }
        for (int i = 0; i < n; ++i) {               //逐行逐列打印
            for (int j = 0; j < n; ++j) {
                printf("%c", matrix[i][j]);
            }
            printf("\n");
        }
    }
    return 0;
}

2.2.2 日期问题

2.6 今天第几天？

输入年、月、日，计算该天是本年的第几天。

包括三个整数年(1<=Y<=3000)、月(1<=M<=12)、日(1<=D<=31)。

输入可能有多组测试数据，对于每一组测试数据，输出一个整数，代表Input中的年、月、日对应本年的第几天。

#include<bits/stdc++.h>
using namespace std;

bool IsRunYear(int year)
{
    return (year % 100 != 0 && year % 4 ==0) || (year % 400 == 0);
}
int daytab[2][13] =
        {
                {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
                {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
        };

int main()
{
    // 输入年、月、日，计算该天是本年的第几天。
    // 输入可能有多组测试数据，对于每一组测试数据， 输出一个整数，代表Input中的年、月、日对应本年的第几天。
    // 闰年 -> 2月有29天   判断：当年数不能被100整除，若其能被4/400整除时  闰年
    // 1 2 3 4 5 6 7 8 9 10 11 12
    // 31 28 31 30 31 30 31 31 30 31 30 31
    // 31 29 31 30 31 30 31 31 30 31 30 31

    int year,month,day;
    // cin>>year>>month>>day;

    while (cin>>year>>month>>day)
    {
        int num = 0;

        int row = IsRunYear(year);

        for(int i = 0; i < month; i++)
        {
            num += daytab[row][i];
        }
        num += day;

        cout<<num<<endl;
    }
    return 0;
}

2.7 打印日期

给出年分m和一年中的第n天，算出第n天是几月几号。

输入包括两个整数y(1<=y<=3000)，n(1<=n<=366)。

可能有多组测试数据，对于每组数据，按 yyyy-mm-dd的格式将输入中对应的日期打印出来。

#include<bits/stdc++.h>
#include<cstring>
#include<string>
using namespace std;

bool IsRunYear(int year)
{
    return (year % 100 != 0 && year % 4 ==0) || (year % 400 == 0);
}
int daytab[2][13] =
        {
                {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
                {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
        };

int main()
{
    int year, num;

    while (cin>>year>>num)
    {
        int row = IsRunYear(year);

        int mouth,day;

        for(mouth = 1; mouth < 12; mouth++)
        {
            if(num - daytab[row][mouth] >= 0)
            {
                num -= daytab[row][mouth];
            } else
            {
                break;
            }
        }

        string m,d;
        if(num == 0)
        {
            mouth--;
            day = daytab[row][mouth];

        } else
            day = num;

        if(mouth < 10)
            m = "0" + to_string(mouth);
        else
            m = to_string(mouth);
        if(day < 10)
            d = "0" + to_string(day);
        else
            d = to_string(day);

        cout<<year<<"-"<<m<<"-"<<d<<endl;
    }

    return 0;
}

3 排序和查找

3.1 排序

3.1 排序

对输入的n个数进行排序并输出。

输入的第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。

可能有多组测试数据，对于每组数据，将排序后的n个整数输出，每个数后面都有一个空格。每组测试数据的结果占一行。

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int MAX = 100;
int arr[MAX];

int main()
{
    int n;
    cin>>n;

    for(int i = 1; i <= n; i++)
    {
        cin>>arr[i];
    }

    sort(arr + 1, arr +n +1);

    for(int i = 1; i <= n; i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;


    return 0;
}

3.2 成绩排序

用一维数组存储学号和成绩，然后，按成绩排序输出。

输入第一行包括一个整数N(1<=N<=100)，代表学生的个数。接下来的N行每行包括两个整数p和q，分别代表每个学生的学号和成绩。

按照学生的成绩从小到大进行排序，并将排序后的学生信息打印出来。如果学生的成绩相同，则按照学号的大小进行从小到大排序。

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int MAX = 120;

struct Student
{
    int number;  // 学号
    int score;   // 成绩
};

Student arr[MAX];

bool Compare(Student x, Student y)
{
    if(x.score == y.score)
        return x.number < y.number;
    else
        return x.score < y.score;
}

int main()
{
    int num;
    cin>> num;

    for(int i = 1; i <= num; i++)
    {
        cin>>arr[i].number>>arr[i].score;
    }
    sort(arr + 1, arr + num + 1, Compare);
    for (int i = 1; i <= num; ++i)
    {
        cout<<arr[i].number<<" "<<arr[i].score<<endl;
    }

    return 0;
}

3.2 成绩排序2

题目：输入任意（用户，成绩）序列，可以获得成绩从高到低或从低到高的排列,相同成绩
都按先录入排列在前的规则处理。

示例：
jack 70
peter 96
Tom 70
smith 67

从高到低成绩
peter 96
jack 70
Tom 70
smith 67

从低到高

smith 67

jack 70
Tom 70
peter 96

注意一个case里面有多组样例，请用循环处理输入输入多行，先输入要排序的人的个数，然后输入排序方法0（降序）或者1（升序）再分别输入他们的名字和成绩，以一个空格隔开。

按照指定方式输出名字和成绩，名字和成绩之间以一个空格隔开。

#include <stdio.h>
#include <algorithm>

struct Stu{
    char name[10];
    int score;
    int num;
}stu[1000];

bool cmp0(Stu a,Stu b){
    if(a.score!=b.score){
        return a.score>b.score;
    }else{
        return a.num<b.num;
    }
}

bool cmp1(Stu a,Stu b){
    if(a.score!=b.score){
        return a.score<b.score;
    }else{
        return a.num<b.num;
    }
}

int main()
{
    int n,temp;
    while(scanf("%d%d",&n,&temp)!=EOF){
        for(int i=0;i<n;i++){
            scanf("%s%d",stu[i].name,&stu[i].score);
            stu[i].num=i;
        }
        if(temp==1){
            std::sort(stu,stu+n,cmp1);
        }
        else if(temp==0){
            std::sort(stu,stu+n,cmp0);
        }
        for(int i=0;i<n;i++){
            printf("%s %d\n",stu[i].name,stu[i].score);
        }
    }
    return 0;
}

3.2 查找

3.4 找x

输入一个数n，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1）。

测试数据有多组，输入n(1<=n<=200)，接着输入n个数，然后输入x。

对于每组输入,请输出结果。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,x;
    cin>>n;
    int arr[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>arr[i];
    }
    cin>>x;
    int answer = -1;
    for (int i = 0; i < n; ++i)
    {
        if(arr[i] == x)
        {
            answer = i;
            break;
        }
    }

    cout<<answer<<endl;

    return 0;
}

3.5 查找

输入数组长度 n 输入数组 a[1…n] 输入查找个数m 输入查找数字b[1…m] 输出 YES or NO 查找有则YES 否则NO 。

输入有多组数据。每组输入n，然后输入n个整数，再输入m，然后再输入m个整数（1<=m,n<=100）。

如果在n个数组中输出YES否则输出NO。

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,m;
    cin>>n;
    int a[n];
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
    }
    cin>>m;
    int b[m];
    for (int i = 0; i < m; ++i)
    {
        cin>>b[i];
    }

    for (int i = 0; i < m; ++i)
    {
        int tag = b[i];
        int isfind = 0;
        for (int j = 0; j < n; ++j)
        {
            if(a[j] == tag)
            {
                isfind = 1;
                cout<<"YES"<<endl;
                break;
            }
        }
        if(!isfind)
            cout<<"NO"<<endl;
        isfind = 0;
    }

    return 0;
}

4 字符串

4.1 字符串操作

4.1 特殊乘法

写个算法，对2个小于1000000000的输入，求结果。特殊乘法举例：123 * 45 = 14 +15 +24 +25 +34+35

输入：两个小于1000000000的数

输入可能有多组数据，对于每一组数据，输出Input中的两个数按照题目要求的方法进行运算后得到的结果。

#include<bits/stdc++.h>
#include<string>
using namespace std;

int main()
{
    string str1,str2;
    cin>>str1>>str2;

    int len1 = str1.length();
    int len2 = str2.length();

    int sum = 0;

    for (int i = 0; i < len1; ++i)
    {
        for (int j = 0; j < len2; ++j)
        {
            sum += (str1[i] - '0') * (str2[j] - '0');
        }
    }

    cout<<sum<<endl;

    return 0;
}

4.2 密码翻译

在情报传递过程中，为了防止情报被截获，往往需要对情报用一定的方式加密，简单的加密算法虽然不足以完全避免情报被破译，但仍然能防止情报被轻易的识别。我们给出一种最简的的加密方法，对给定的一个字符串，把其中从a-y,A-Y的字母用其后继字母替代，把z和Z用a和A替代，则可得到一个简单的加密字符串。

读取这一行字符串，每个字符串长度小于80个字符

对于每组数据，输出每行字符串的加密字符串。

#include<bits/stdc++.h>
#include<algorithm>
#include<string>
using namespace std;

int main()
{
    string str;

    while (getline(cin,str))
    {
        int len = str.length();

        for (int i = 0; i < len; ++i)
        {
            if(str[i] == 'z' || str[i] == 'Z')
            {
                str[i] -= 25;
            }
            else if (('A'<=str[i] && str[i]<='Y')||('a'<=str[i] && str[i]<='y'))
            {
                str[i]++;
            }
        }

        cout<<str<<endl;
    }

    return 0;
}

4.3 简单密码

Julius Caesar曾经使用过一种很简单的密码。对于明文中的每个字符，将它用它字母表中后5位对应的字符来代替，这样就得到了密文。比如字符A用F来代替。如下是密文和明文中字符的对应关系。密文 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 明文 V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 你的任务是对给定的密文进行解密得到明文。你需要注意的是，密文中出现的字母都是大写字母。密文中也包括非字母的字符，对这些字符不用进行解码。

输入中的测试数据不超过100组。每组数据都有如下的形式，而且各组测试数据之间没有空白的行。一组测试数据包括三部分： 1. 起始行 - 一行，包括字符串 “START” 2. 密文 - 一行，给出密文，密文不为空，而且其中的字符数不超过200 3. 结束行 - 一行，包括字符串 “END” 在最后一组测试数据之后有一行，包括字符串 “ENDOFINPUT”。

对每组数据，都有一行输出，给出密文对应的明文。

#include<bits/stdc++.h>
#include<algorithm>
#include<string>
using namespace std;

int main()
{
    string str;

    while(getline(cin,str))
    {
        if(str == "ENDOFINPUT")
            break;
        getline(cin,str);
        for (int s = 0; s < str.size(); ++s)
        {
            if('A'<=str[s] && str[s]<='Y')
            {
                str[s] = (str[s] - 'A' - 5 + 26) % 26 + 'A';
            }
        }
        cout<<str<<endl;
        getline(cin,str);
    }
    return 0;
}

4.4 统计字符

统计一个给定字符串中指定的字符出现的次数。

测试输入包含若干测试用例，每个测试用例包含2行，第1行为一个长度不超过5的字符串，第2行为一个长度不超过80的字符串。注意这里的字符串包含空格，即空格也可能是要求被统计的字符之一。当读到’#’时输入结束，相应的结果不要输出。

对每个测试用例，统计第1行中字符串的每个字符在第2行字符串中出现的次数，按如下格式输出： c0 n0 c1 n1 c2 n2 … 其中ci是第1行中第i个字符，ni是ci出现的次数。

#include<bits/stdc++.h>
#include<algorithm>
#include<string>
using namespace std;

int number[128];

int main()
{
    string str1,str2;
    while(getline(cin,str1))
    {
        if(str1 == "#")
            break;

        getline(cin,str2);
        memset(number, 0, sizeof(number)); //初始化数组
        for (int i = 0; i < str2.size(); ++i)
        {
            number[str2[i]]++;
        }
        for (int i = 0; i < str1.size(); ++i)
        {
            cout<<str1[i]<<" "<<number[str1[i]]<<endl;
        }
    }
    return 0;
}

4.5 字母统计

输入一行字符串，计算其中A-Z大写字母出现的次数。

案例可能有多组，每个案例输入为一行字符串。

对每个案例按A-Z的顺序输出其中大写字母出现的次数。

#include<bits/stdc++.h>
#include<algorithm>
#include<string>
using namespace std;

int number[128];

int main()
{
    string str,str1;
    str = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    memset(number, 0, sizeof(number));
    for (int i = 0; i < str.size(); ++i)
    {
        number[str[i]] = 0;
    }
    getline(cin,str1);
    for (int i = 0; i < str1.size(); ++i)
    {
        number[str1[i]]++;
    }
    for (int i = 0; i < str.size(); ++i)
    {
        cout<<str[i]<<":"<<number[str[i]]<<endl;
    }

    return 0;
}

4.2 字符串匹配

4.6 Number Sequence

Given two sequences of numbers : a[1], a[2], …… , a[N], and b[1], b[2], …… , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], …… , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.

input：The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], …… , a[N]. The third line contains M integers which indicate b[1], b[2], …… , b[M]. All integers are in the range of [-1000000, 1000000].

output：For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

13 5

1 2 1 2 3 1 2 3 1 3 2 1 2

1 2 3 1 3

13 5

1 2 1 2 3 1 2 3 1 3 2 1 2

1 2 3 2 1

-1

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXM = 10000 + 10;
const int MAXN = 1000000 + 10;

int nextTable[MAXM];
int pattern[MAXM];
int text[MAXN];

void GetNextTable(int m) {                      //创建next表
    int j = 0;
    nextTable[j] = -1;
    int t = nextTable[j];
    while (j < m) {
        if (t == -1 || pattern[j] == pattern[t]) {
            j++;
            t++;
            nextTable[j] = t;
        } else {
            t = nextTable[t];
        }
    }
    return ;
}

int KMP(int n, int m) {
    GetNextTable(m);
    int i = 0;
    int j = 0;
    while (i < n && j < m) {
        if (j == -1 || text[i] == pattern[j]) { //当前字符匹配成功
            i++;
            j++;
        } else {
            j = nextTable[j];                   //当前字符匹配失败
        }
    }
    if (j == m) {                               //模式串匹配成功
        return i - j + 1;
    } else {                                    //模式串匹配失败
        return -1;
    }
}

int main() {
    int caseNumber;
    scanf("%d", &caseNumber);
    while (caseNumber--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; ++i) {
            scanf("%d", &text[i]);
        }
        for (int j = 0; j < m; ++j) {
            scanf("%d", &pattern[j]);
        }
        printf("%d\n", KMP(n, m));
    }
    return 0;
}

5 数据结构

5.1 向量

5.1 完数与盈数

一个数如果恰好等于它的各因子(该数本身除外)子和，如：6=3+2+1。则称其为“完数”；若因子之和大于该数，则称其为“盈数”。求出2到60之间所有“完数”和“盈数”。

输出2到60之间所有“完数”和“盈数”，并以如下形式输出： E: e1 e2 e3 ……(ei为完数) G: g1 g2 g3 ……(gi为盈数) 其中两个数之间要有空格，行尾不加空格。

#include<bits/stdc++.h>
#include<vector>
using namespace std;

vector<int> numberE;
vector<int> numberG;

int Sum(int x)
{
    int sum = 0;
    for (int i = 1; i < x; ++i)
    {
        if(x % i == 0)
        {
            sum += i;
        }
    }
    return sum;
}

int main()
{
    for (int i = 2; i <= 60; ++i)
    {
        if(i == Sum(i))
        {
            numberE.push_back(i);
        } else if(i < Sum(i))
        {
            numberG.push_back(i);
        }
    }

    cout<<"E:";
    for (int i = 0; i < numberE.size(); ++i)
    {
        cout<<" "<<numberE[i];
    }
    cout<<endl;

    vector<int>::iterator it;
    cout<<"G:";
    for (it = numberG.begin(); it != numberG.end() ; it++)
    {
        cout<<" "<<*it;
    }
    cout<<endl;

    return  0;
}

5.2 队列

5.2 约瑟夫问题 No.2

n 个小孩围坐成一圈，并按顺时针编号为1,2,…,n，从编号为 p 的小孩顺时针依次报数，由1报到m ，当报到 m 时，该小孩从圈中出去，然后下一个再从1报数，当报到 m 时再出去。如此反复，直至所有的小孩都从圈中出去。请按出去的先后顺序输出小孩的编号。

每行是用空格分开的三个整数，第一个是n,第二个是p,第三个是m (0 < m,n < 300)。最后一行是:
0 0 0

按出圈的顺序输出编号，编号之间以逗号间隔。

```





## 6 数学问题

### 6.1 进制转换

**6.1 二进制数**

大家都知道，数据在计算机里中存储是以二进制的形式存储的。 有一天，小明学了C语言之后，他想知道一个类型为unsigned int 类型的数字，存储在计算机中的二进制串是什么样子的。 你能帮帮小明吗？并且，小明不想要二进制串中前面的没有意义的0串，即要去掉前导0。

多行，每一行表示要求的数字

输出共T行。每行输出求得的二进制串。

23
535
2624
56275
989835

10111
1000010111
101001000000
1101101111010011
11110001101010001011

```cpp
#include<bits/stdc++.h>
#include<vector>
using namespace std;

int main()
{
    unsigned int n;
    while (cin>>n)
    {
        vector<int> binary;
        while (n!=0)
        {
            binary.push_back(n % 2);
            n /= 2;
        }
        for (int i = binary.size() - 1; i >= 0; --i)
        {
            cout<<binary[i];
        }
        cout<<endl;
    }

    return 0;
}

6.2 进制转换

将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。

多组数据，每行为一个长度不超过30位的十进制非负整数。（注意是10进制数字的个数可能有30个，而非30bits的整数）

每行输出对应的二进制数。

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

string Divide(string str, int x) {                  //字符串除法
    int remainder = 0;                              //保存余数
    for (int i = 0; i < str.size(); ++i) {
        int current = remainder * 10 + str[i] - '0';
        str[i] = current / x + '0';
        remainder = current % x;
    }
    int position = 0;
    while (str[position] == '0') {                  //寻找首个非0下标
        position++;
    }
    return str.substr(position);                    //删除前置多余的0
}

int main() {
    string str;
    while (cin >> str) {
        vector<int> binary;
        while (str.size() != 0) {
            int last = str[str.size() - 1] - '0';   //最低位的值
            binary.push_back(last % 2);             //取模运算
            str = Divide(str, 2);                   //整除运算
        }
        for (int i = binary.size() - 1; i >= 0; --i) {
            printf("%d", binary[i]);
        }
        printf("\n");
    }
    return 0;
}

6.3 十进制与二进制

对于一个十进制数A，将A转换为二进制数，然后按位逆序排列，再转换为十进制数B，我们称B为A的二进制逆序数。例如对于十进制数173，它的二进制形式为10101101，逆序排列得到10110101，其十进制数为181，181即为173的二进制逆序数。

一个1000位(即10^999)以内的十进制数。

输入的十进制数的二进制逆序数。

173

181

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

string Divide(string str, int x) {                  //字符串除法
    int remainder = 0;                              //保存余数
    for (int i = 0; i < str.size(); ++i) {
        int current = remainder * 10 + str[i] - '0';
        str[i] = current / x + '0';
        remainder = current % x;
    }
    int position = 0;
    while (str[position] == '0') {                  //寻找首个非0下标
        position++;
    }
    return str.substr(position);                    //删除前置多余的0
}

string Multiple(string str, int x) {                //字符串乘法
    int carry = 0;                                  //保存进位
    for (int i = str.size() - 1; i >= 0; --i) {
        int current = x * (str[i] - '0') + carry;
        str[i] = current % 10 + '0';
        carry = current / 10;
    }
    if (carry != 0) {                               //仍有进位
        str = to_string(carry) + str;
    }
    return str;
}

string Add(string str, int x) {                     //字符串加法
    int carry = x;
    for (int i = str.size() - 1; i >= 0; --i) {
        int current = (str[i] - '0') + carry;
        str[i] = current % 10 + '0';
        carry = current / 10;
    }
    if (carry != 0) {                               //仍有进位
        str = to_string(carry) + str;
    }
    return str;
}

int main() {
    string str;
    while (cin >> str) {
        vector<int> binary;
        while (str.size() != 0) {
            int last = str[str.size() - 1] - '0';   //最低位的值
            binary.push_back(last % 2);
            str = Divide(str, 2);                   //字符串除2
        }
        string answer = "0";
        for (int i = 0; i < binary.size(); ++i) {
            answer = Multiple(answer, 2);           //字符串乘2
            answer = Add(answer, binary[i]);        //加数位值
        }
        cout << answer << endl;
    }
    return 0;
}

6.4 进制转换2

将M进制的数X转换为N进制的数输出。

输入的第一行包括两个整数：M和N(2<=M,N<=36)。
下面的一行输入一个数X，X是M进制的数，现在要求你将M进制的数X转换成N进制的数输出。

输出X的N进制表示的数。

10 2
11

1011

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

char IntToChar(int x) {                             //数字变成字符
    if (x < 10) {
        return x + '0';
    } else {
        return x - 10 + 'a';
    }
}

int CharToInt(char c) {                             //字符变成数字
    if (c >= '0' && c <= '9') {
        return c - '0';
    } else {
        return c - 'A' + 10;
    }
}

int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    string str;
    cin >> str;
    long long number = 0;
    for (int i = 0; i < str.size(); ++i) {          //从m进制变成十进制
        number *= m;
        number += CharToInt(str[i]);
    }
    vector<char> answer;
    if (number == 0) {
        answer.push_back('0');
    } else {
        while (number != 0) {                       //从十进制变成n进制
            answer.push_back(IntToChar(number % n));
            number /= n;
        }
    }
    for (int i = answer.size() - 1; i >= 0; --i) {  //逆序输出
        printf("%c", answer[i]);
    }
    printf("\n");
    return 0;

最大公约数

分解质因数

简单贪心

递归

本文作者： 李宝璐
本文链接： https://libaolu312.github.io/2023/06/26/重生之我是机试coding怪/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！