今年学习的题目

第1讲 C/C++的应用训练

1.U307221 奇偶数

题目描述

输入一个正整数n，如果n是奇数，那么输出"Odd Number"；如果n是偶数，那么输出"Even Number"。

输入格式

一个正整数n（1≤n≤100000）。

输出格式

按题意输出"Odd Number"或"Even Number"。

输入输出样例

输入 #1

5

输出 #1

Odd Number

输入 #2

10

输出 #2

Even Number

参考代码：

#include<bits/stdc++.h>

using namespace std;

int main() {

    int n;

    cin>>n;

   if(n%2==0){

        cout<<"Even Number";

   } else{

        cout<<"Odd Number";

   }

   return 0;

}

2.U307243 输出整数

题目描述：输入一个正整数n，输出n行，其中第i行为从1到i的所有整数。

输入格式

一个正整数n（1≤n≤100000）。

输出格式

共n行，其中第i行为从1到i的所有正整数。整数间用一个空格隔开，行末不允许有多余的空格。

输入输出样例

输入 #1

3

输出 #1

1

1 2

1 2 3

输入 #2

4

输出 #2

1

1 2

1 2 3

1 2 3 4

参考代码：

#include <stdio.h>

int main() {

    int n;

    // 输入正整数n

    scanf("%d", &n);

    // 外层循环控制行数

    for (int i = 1; i <= n; i++) {

        // 内层循环输出从1到i的数字

        for (int j = 1; j <= i; j++) {

            printf("%d ", j); // 每个数字后跟一个空格

        }

        printf("\n"); // 每行结束后换行

    }

    return 0;

}

3.U307315 与2无关的数

题目描述

一个正整数，如果它能被2整除，或者它的十进制表示中某个位数上的数字为2，则称其为与2相关的数。求所有小于等于N的与2无关的正整数的和。 例如：N = 8，<= 8与2无关的数包括：1 3 5 7，和为：16。

输入格式

一行，一个n， 2<=n<=100。

输出格式

一行，输出一个整数，表示答案。

输入输出样例

输入 #1

8

输出 #1

16

参考代码：

#include <stdio.h>

int main() {

   int N;

   scanf("%d", &N);

   long long sum = 0; // 可能和较大，用long long

   for (int i = 1; i <= N; i++) {

        if (i % 2 == 0) continue; // 能被2整除，相关，跳过

        // 检查各位是否有2

        int temp = i;

        int hasTwo = 0;

        while (temp > 0) {

              if (temp % 10 == 2) {

                   hasTwo = 1;

                   break;

              }

              temp /= 10;

        }

        if (hasTwo) continue;

        sum += i;

   }

   printf("%lld\n", sum);

   return 0;

}

第2讲 穷举算法、迭代算法和入门模拟

1.U413399整数出现次数

给定个正整数，按从小到大的顺序输出每个整数的出现次数。

输入描述

第一行一个正整数n（1<=n<=1000）；

第二行为用空格隔开的n个正整数（每个正整数的大小均不超过100）。

输出描述

输出若干行，每行输出一个整数和它的出现次数，中间用空格隔开。

样例1

输入

4

3 1 5 3

输出

1 1

3 2

5 1

解释

1出现了1次，3出现了2次，5出现了1次

参考答案：

#include <cstdio>

int main () {

   int hashTable[101] = {0};

    int n, x;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {

        scanf("%d", &x);

        hashTable[x]++;

    }

    for (int i = 1; i <= 100; i++) {

        if (hashTable[i]) {

            printf("%d %d\n", i, hashTable[i]);

        }

    }

    return 0;

}

3.U413390日期先后

给定两个日期DAY1和DAY2，判断DAY1是否在DAY2之前。

输入描述

前两行分别为日期DAY1和DAY2（格式为YYYY-MM-DD，范围为1900-01-01≤DAY≤2199-12-31），数据保证一定合法。

输出描述

如果DAY1在DAY2之前，那么输出YES，否则输出NO。

样例1

输入

2021-05-01

2021-05-07

输出

YES

参考答案：

#include <cstdio>

int isBefore(int year1, int month1, int day1, int year2, int month2, int day2) {

    if (year1 != year2) {

        return year1 < year2;

    }

    if (month1 != month2) {

        return month1 < month2;

    }

    return day1 < day2;

}

int main() {

    int year1, month1, day1;

    int year2, month2, day2;

    scanf("%d-%d-%d", &year1, &month1, &day1);

    scanf("%d-%d-%d", &year2, &month2, &day2);

    printf(isBefore(year1, month1, day1, year2, month2, day2) ? "YES" : "NO");

    return 0;

}

4.U415278计算输入数据的和与乘积

题目描述

输入一个整型数据，计算这个数据里面所以数字的和值与乘积

输入

一个整型数字（不超过十位）

输出

这个数字里所有数字的和值乘积空格分开

样例输入

1234

样例输出

10 24

参考答案：

#include<bits/stdc++.h>

using namespace std;

int main ()

{ 

   char a[11];

   int i,sum =0,ave=1,temp;

    cin>>a;

   for(i=0;i<strlen(a);i++)

   {

        temp=a[i]-'0';//字符转换为单个数字   

        sum+=temp;    

        ave*=temp;

   }   

   cout<<sum<<" "<<ave;

   return 0;

}

算法初步

1 散列算法

1.U415270统计同成绩学生

题目描述

本题要求读入N名学生的成绩,然后将获得某一给定分数的学生人数输出。

输入格式

第一行给出不超过105的正整数N,即学生总人数;第二行给出N名学生的百分制整数成绩，中间以空格分隔;第三行给出要查询的分数个数K(不超过N的正整数)，随后是K个分数,中间以空格分隔。

输出格式

在一行中按查询顺序给出得分等于指定分数的学生人数，中间以空格分隔，但行末不得有多余空格。

输入样例

10

60 75 90 55 75 99 82 90 75 50

3 75 90 88

输出样例

3 2 0

参考答案

#include <iostream>

using namespace std;

int hashTable[110] = {0}; //记录每个分数出现的次数

int main(){

   int n, score, k;

   cin>>n; //学生数

   for(int i=0;i<n; i++){

        scanf("%d",&score);//分数

        hashTable[score]++;//分数score出现的次数加1

   }

   cin>>k; //查询次数

   for (int i=0;i< k; i++){

        cin>>score;

        cout<<hashTable[score];//查询分数score出现的次数

        if(i<k-1){

              cout<<" ";//前K-1个结果后面输出空格

        }

   }

   return 0;

}

2.U415273集合求交

给定一个包含n个正整数的集合S1，再给定一个包含m个正整数的集合S2，求两个集合的交集。

输入描述

第一行两个正整数n、m（1<=n,m<=104），分别表示集合S1和S2的成员数；

第二行按升序给出S1的n个正整数成员（每个正整数的大小均不超过104，且互不相同）。

第三行按升序给出S2的m个正整数成员（每个正整数的大小均不超过104，且互不相同）。

输出描述

按升序输出集合S1和S2的交集。结果之间用空格隔开，行末不允许有多余的空格。

输入

5 4

1 2 5 6 8

2 4 6 7

输出

2 6

参考答案：

#include <iostream>

using namespace std;

int main(){

    int hashTable[10001] = {0};

    int n, m, x;

    cin>>n>>m;

    for (int i = 0; i < n; i++) {

        cin>>x;

        hashTable[x] = 1;

    }

    int isFirst = 1;

    for (int i = 0; i < m; i++) {

         cin>>x;

         if (hashTable[x]) {

           if(!isFirst){

              cout<<" ";

            }

            cout<<x;

            isFirst = 0; 

        }

    }

    return 0;

}

3.U417371集合求差

给定一个包含n个正整数的集合S1，再给定一个包含m个正整数的集合S2，求两个集合的差集，即S1−S2。

输入描述

第一行两个正整数n、m（1≤n≤104,1≤m≤104），分别表示集合S1和S2的成员数；

第二行按升序给出S1的n个正整数成员（每个正整数的大小均不超过103，且可能重复）。

第三行按升序给出S2的m个正整数成员（每个正整数的大小均不超过103，且可能重复）。

输出描述

按升序输出集合S1和S2的差集。结果之间用空格隔开，行末不允许有多余的空格。

样例1

输入

5 2

2 2 2 6 8

2 6

输出

2 2 8

解释

集合S1中有3个2，集合S2中有1个2，因此作差后还剩2个2；

集合S1中有1个6，集合S2中有1个6，因此作差后还剩0个6；

集合S1中有1个8，集合S2中有0个8，因此作差后还剩1个8；

因此差集为{2,2,8}

参考答案：

#include <iostream>

using namespace std;

int main () {

   int hashTable[1001] = {0};

    int n, m, x;

    cin>>n>>m;

    for (int i = 0; i < n; i++) {

        cin>>x;

        hashTable[x]++;

    }

    for (int i = 0; i < m; i++) {

         cin>>x;

        hashTable[x]--;

    }

    int isFirst = 1;

    for (int i = 1; i < 1001; i++) {

        for (int j = 0; j < hashTable[i]; j++) {

            if(!isFirst){

              cout<<" ";

            }

            cout<<i;

            isFirst = 0;

        }

    }

    return 0;

}

4.U413409单词倒序

给定一堆用空格隔开的英文单词，输出这些英文单词的倒序（单词内部保持原序）。

输入描述

一堆英文单词，每个单词不超过10个字符，且仅由大小写字母组成；每两个单词之间用一个空格隔开，整个字符串的长度不超过1000。

输出描述

输出英文单词的倒序，单词之间仍然是一个空格隔开，行末不允许有多余的空格。

样例1

输入

Hao Hao Xue Xi

输出

Xi Xue Hao Hao

参考答案

#include <cstdio>

int main() {

   char str[1000][11], num = 0;  

    while (scanf("%s", str[num]) != EOF) {

        num++;

    }

    for (int i = num - 1; i >= 0; i--) {

        printf("%s", str[i]);

        if (i > 0) {

            printf(" ");

        }

    }

    return 0;

}

3.2 递归算法

1.吓得我抱起了我的小鲤鱼

在这个定义下：

当n=0时，整个句子是“吓得我抱起了我的小鲤鱼”；

当n=1时，整个句子是“吓得我抱起了抱着我的小鲤鱼的我”；

当n=2时，整个句子是“吓得我抱起了抱着抱着我的小鲤鱼的我的我”；

当n=3时，整个句子是“吓得我抱起了抱着抱着抱着我的小鲤鱼的我的我的我”；

请根据n的大小，输出对应的句子。

输入描述

一个整数n（1<=n<=100），含义如题意所示。

输出描述

对应的表情中的完整句子。

样例1

输入

0

输出

吓得我抱起了我的小鲤鱼

样例2

输入

3

输出

吓得我抱起了抱着抱着抱着我的小鲤鱼的我的我的我

参考答案：

#include <iostream>

using namespace std;

void print(int n) {

    if (n == 0) {

        cout<<"我的小鲤鱼";

    } else {

        cout<<"抱着";

        print(n - 1);

        cout<<"的我";

    }

}

int main() {

    int n;

    cin>>n;

    cout<<"吓得我抱起了";

    print(n);

    return 0;

}

2.从前有座山

很多人都知道从前有座山的故事，它是这样的：

从前有座山，山上有座庙

庙里有一个老和尚和一个小和尚

睡前老和尚给小和尚讲故事：

……

然后老和尚和小和尚就睡觉啦

对本题来说，整个故事是下面的严格定义。

当n=0时，故事A(n)是

讲你妹的故事啊！快点去睡觉！！！

当n>0时，故事A(n)是

从前有座山，山上有座庙

庙里有一个老和尚和一个小和尚

睡前老和尚给小和尚讲故事：

A(n-1)

然后老和尚和小和尚就睡觉啦

请根据n的大小，输出对应的故事。

输入描述

一个整数n（1≤n≤100），含义如题意所示。

输出描述

故事A(n)。

样例1

输入

0

输出

讲你妹的故事啊！快点去睡觉！！！

样例2

输入

1

输出

从前有座山，山上有座庙

庙里有一个老和尚和一个小和尚

睡前老和尚给小和尚讲故事：

讲你妹的故事啊！快点去睡觉！！！

然后老和尚和小和尚就睡觉啦

样例3

输入

2

输出

从前有座山，山上有座庙

庙里有一个老和尚和一个小和尚

睡前老和尚给小和尚讲故事：

从前有座山，山上有座庙

庙里有一个老和尚和一个小和尚

睡前老和尚给小和尚讲故事：

讲你妹的故事啊！快点去睡觉！！！

然后老和尚和小和尚就睡觉啦

然后老和尚和小和尚就睡觉啦

参考答案：

#include <iostream>

using namespace std;

void print(int n) {

    if (n == 0) {

        cout<<"讲你妹的故事啊！快点去睡觉！！！\n";

    } else {

        cout<<"从前有座山，山上有座庙\n";

        cout<<"庙里有一个老和尚和一个小和尚\n";

        cout<<"睡前老和尚给小和尚讲故事：\n";

        print(n - 1);

        cout<<"然后老和尚和小和尚就睡觉啦\n";

    }

}

int main() {

    int n;

    cin>>n;

    print(n);

    return 0;

}

4.U417383猴子吃桃的问题

题目描述

猴子吃桃问题。猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个。 第二天早上又将剩下的桃子吃掉一半，又多吃一个。以后每天早上都吃了前一天剩下的一半零一个。 到第N天早上想再吃时，见只剩下一个桃子了。求第一天共摘多少桃子。

输入

N

输出

桃子总数

样例输入

10

样例输出

1534

参考答案

#include<stdio.h>

int fruit(int n){

   if(n==1) return 1;

   return (fruit(n-1)+1)*2;

}

int main(){

   int N;

   scanf("%d",&N);

   printf("%d",fruit(N));

   return 0;

}

3.U417393莲花池

题目描述

有个莲花池里起初有一只莲花，每过一天莲花的数量就会翻一倍。假设莲花永远不凋谢，30天的时候莲花池全部长满了莲花， 请问第n(5<=n<=30)天的莲花占莲花池的几分之几.

输入格式

n

输出格式

百分比，保留8位小数

输入

23

输出

0.00781250

参考答案:

#include<stdio.h>

int fn(int a);

int main(){

   long long aa,bb;

   double cc;

   int n;

   scanf("%d",&n);

   aa = fn(30);

   bb = fn(n);

   cc = (double)bb/aa;

   printf("%.8f\n", cc);

   return 0;

}

int fn(int n){

   if(n == 1){

        return 1;

   }

   else{

        return  fn(n-1)*2;

   }

}

3.3 贪心算法

1.U421343最优装箱

题目描述

有n个箱子需要装上一艘轮船，已知第i个箱子的重量为wi，轮船的载重为W。问在不超过轮船载重的前提下，最多能把多少个箱子装上轮船。

输入描述

第一行两个正整数n、W（1≤n≤105、1≤W≤107），分别表示箱子个数和轮船载重。

第二行n个正整数wi（1≤wi≤107），表示n个箱子的重量。

输出描述

输出两个整数，分别表示能装上轮船的箱子个数和总重量，用空格隔开。

样例1

输入

5 11

7 2 9 1 11

输出

3 10

样例1

输入

4 80

54 89 45 12

输出

2 57

样例1解释

能将重量分别为7、2、1的箱子装上轮船（此时箱子个数最多），总重量为10。

样例2解释

能将重量分别为45、12的箱子装上轮船（此时箱子个数最多），总重量为57。（注意，优先把重量值小的箱子搬上轮船）

参考答案：

#include <bits/stdc++.h>

//#include <algorithm>

using namespace std;

int main() {

   int a[100001];

    int n, maxW;

    cin>>n>>maxW;

    for (int i = 0; i < n; i++) {

        cin>>a[i];

    }

    sort(a, a + n);

    int num = 0, sum = 0;

    for (int i = 0; i < n; i++) {

        if (sum + a[i] <= maxW) {

            num++;

            sum += a[i];

        } else {

            break;

        }

    }

    cout<<num<<" "<<sum ;

    return 0;

}

2.U422123最大组合整数

题目描述

现有0~9中各个数的个数，将它们组合成一个整数，求能组合出的最大整数。

输入描述

在一行中依次给出0~9中各个数的个数（所有个数均在0~100之间）。数据保证至少有一个数的个数大于0。

输出描述

输出一个整数，表示能组合出的最大整数。

样例1

输入

1 0 2 0 0 0 0 0 0 1

输出

9220

解释

存在1个0、2个2、1个9，因此能组合出的最大整数是9220

参考答案：

#include <bits/stdc++.h>

//#include <algorithm>

using namespace std;

int main() {

   int cnt[10];

    for (int i = 0; i < 10; i++) {

        cin>>cnt[i];

    }

    int isZero = 1;

    for (int i = 9; i >= 0; i--) {

        if (i > 0 && cnt[i] > 0) {

            isZero = 0;

        }

        if (!isZero) {

            for (int j = 0; j < cnt[i]; j++) {

               cout<<i;

            }

        }

    }

    if (isZero) {

       cout<<"0";

    }

    return 0;

}

3.U422129同学的等待

题目描述

同学们下课后去食堂，每个人都需要一段时间去点菜。

然而，某些同学点菜时间太长了。同学们对于等待很烦躁：他们希望，能尽量少的花时间等待。

(同学数<=100000)，(0<=点菜耗时<=10000)

他们希望在点菜时，能排成一个次序，使得总等待时间最短(即不包括点菜人的其他所有人的等待时间)。

输入

第一行是一个数字n，表示同学的个数

接下来n个数，表示点菜的耗时

输出

一个数，表示总等待时间。

样例输入

6

9 1 3 5 4 2

样例输出

35

参考答案

#include <bits/stdc++.h>

//#include <algorithm>

using namespace std;

int main() {

   int a[100001];

    int n;

    cin>>n;

    for(int i = 1;i<=n;i++)

        scanf("%d",&a[i]);

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

    long long sum = 0;

    for(int i = 1; i<=n;i++) {

        sum += a[i]*(n-i);

    }

    cout<<sum<<endl;

    return 0;

}

3.4 二分算法

1.U423603寻找指定元素II

在一个严格递减序列A中寻找一个指定元素x，如果能找到，那么输出它的下标；如果不能找到，那么输出−1。

注：使用二分法实现。

输入描述

第一行为两个正整数n（1≤n≤105）、x（1≤x≤106），分别表示严格递减序列A中元素的个数、需要寻找的元素；

第二行按顺序给出n个严格递减的正整数，表示序列A中的元素（1≤每个元素≤106）。假设序列的下标从0开始。

输出描述

如果能找到x，那么输出它的下标；否则输出−1。

样例1

输入

5 3

8 5 3 2 1

输出

2

样例2

输入

5 6

8 5 3 2 1

输出

-1

参考答案：

#include <iostream>

using namespace  std;

const int MAXN = 100000;

int n, a[MAXN], target;

int binarySearch() {

    int l = 0, r = n - 1;

    while (l <= r) {

        int mid = (l+r) / 2;

        if (a[mid] == target) {

            return mid;

        } else if (a[mid] > target) {

            l = mid + 1;

        } else if (a[mid] < target) {

            r = mid - 1;

        }

    }

    return -1;

}

int main() {

    cin>>n>>target;

    for (int i = 0; i < n; i++) {

        cin>>a[i];

    }

    cout<<binarySearch();

    return 0;

}

3.U425603日期排序

有一些日期，日期格式为“MM/DD/YYYY”。编程将其按日期大小排列。

输入

无

输出

无

样例输入

05/12/1999

10/21/2003

10/22/2003

02/12/2004

11/30/2005

12/31/2005

样例输出

05/12/1999

10/21/2003

10/22/2003

02/12/2004

11/30/2005

12/31/2005

参考答案：

#include<bits/stdc++.h>

using namespace std;

struct date{

    int year,month,day;

}dd[100];

int cmp(date a,date b){

    if(a.year!=b.year)

        return a.year<b.year;

    else if(a.month!=b.month)

        return a.month<b.month;

    else

        return a.day<b.day;     

}

int main(){

    int i=0;

    while(scanf("%d/%d/%d",&dd[i].month,&dd[i].day,&dd[i].year)!=EOF){

        i++;

    }

    sort(dd,dd+i,cmp);

    for(int j=0;j<i;j++)

        printf("%02d/%02d/%04d\n",dd[j].month,dd[j].day,dd[j].year);

    return 0;

 }

4.U680528首字母大写

给定一堆用空格隔开的英文单词，将每个单词的首字母改为大写后输出。

输入描述

一堆英文单词，每个单词不超过10个字符，且仅由小写字母组成；每两个单词之间用一个空格隔开，整个字符串的长度不超过1000。

输出描述

输出每个单词首字母大写后的结果，单词之间仍然是一个空格隔开，行末不允许有多余的空格。

样例1

输入

good good study

输出

Good Good Study

参考答案：

#include <bits/stdc++.h>

using namespace std;

int main() {

   int i=0;

   char str[1000];

    while (scanf("%s", str) != EOF) {    

       if(i!=0) printf(" "); 

        int len = strlen(str);

        printf("%c", str[0] -32);

        for (int j = 1; j < len; j++) {

            printf("%c", str[j]);

        }

        i=1;

    }

    return 0;

}

  数学问题

1.U425809组合数

给定两个非负整数n和m，求Cnm的值。

输入描述

两个非负整数n、m（1≤n≤50,0≤m≤50,m≤n），含义如题意所述。

输出描述

输出一个整数，表示Cnm的值。

样例1

输入

6 2

输出

15

解释

C62=6*5/2*1=15

参考答案：

#include <cstdio>

typedef long long LL;

LL C(LL n, LL m) {

    LL ans = 1;

    for (LL i = 1; i <= m; i++) {

        ans = ans * (n - m + i) / i;

    }

    return ans;

}

int main() {

    LL n, m;

    scanf("%lld%lld", &n, &m);

    printf("%lld", C(n, m));

    return 0;

}

2.U428209 左小数

给定由n个正整数组成的序列，问在序列中有多少个数，满足在它左边的所有数都比它小。

输入描述

第一行一个整数n（1≤n≤105），表示序列中正整数的个数；

第二行按顺序给出序列中的n个正整数（每个正整数均不超过106且互不相同）。

输出描述

输出满足条件的整数个数。

样例1

输入

4

1 3 2 4

输出

3

解释

1的左边没有数，满足条件；

3的左边所有数都比3小，满足条件；

2的左边存在不小于2的数，不满足条件；

4的左边所有数都比4小，满足条件；

因此共3个数满足条件。

参考答案：

#include<bits/stdc++.h>

using namespace std;

int main() {

    int n, x, leftMax = 0;

    scanf("%d", &n);

    int result = 0;

    for (int i = 0; i < n; i++) {

        cin>>x;

        if (x > leftMax) {

            result++;

        }

        leftMax = max(leftMax, x);

    }

    cout<<result;

    return 0;

}

3.U427935前缀和

给定由n个正整数组成的序列，接下来给出k个查询，每个查询指定一个正整数m，计算序列前m个正整数之和。

输入描述

第一行一个整数n（1≤n≤104），表示序列中正整数的个数；

第二行按顺序给出序列中的n个正整数（每个正整数均不超过104）；

第三行一个整数k（1≤k≤104），表示查询的个数；

接下来k行，每行一个整数m（1≤m≤n），表示需要计算序列前m个正整数之和。

输出描述

输出k行，每行一个查询结果，表示序列前m个正整数之和。

样例1

输入

5

2 8 5 1 3

3

1

3

5

输出

2

15

19

解释

前1个正整数之和是2；

前3个正整数之和是2+8+5=15；

前5个正整数之和是2+8+5+1+3=19。

参考答案：

#include<bits/stdc++.h>

using namespace std;

int main() {

   int n, a[10000];

   int sum[10000] = {0};

    cin>>n;

    for (int i = 0; i < n; i++) {

        cin>>a[i];

        if (i == 0) {

            sum[i] = a[i];

        } else {

            sum[i] = sum[i - 1] + a[i];

        }

    }

    int k, m;

    cin>>k;

    for (int i = 0; i < k; i++) {

       cin>>m;

       cout<<sum[m - 1]<<endl;

    }

    return 0;

} 

4.B3866 [GESP202309 二级] 数字黑洞

题目描述

给定一个三位数，要求各位不能相同。例如，352是符合要求的，112是不符合要求的。将这个三位数的三个数字重新排列，得到的最大的数，减去得到的最小的数，形成一个新的三位数。对这个新的三位数可以重复上述过程。神奇的是，最终一定会得到495！

试试看，重新排列352，得到的最大数为532，最小数为235，它们的差是297；变换297，得到972−279=693；变换693，963−369=594；变换594，954−459=495。因此，经过4次变换得到了495。

现在，输入的三位数，你能通过编程得出，这个三位数经过多少次变换能够得到495吗？

输入格式

输入一行，包含一个符合要求的三位数N。

输出格式

输出一行，包含一个整数C，表示经过C次变换得到495。

输入输出样例

输入 #1

352

输出 #1

4

参考答案：

#include <cstdio>

#include <algorithm>

using namespace std;

bool cmp(int a,int b) { //递减排序 cmp

   return a > b;

}

//将 n的每一位存到num数组中

void to_array(int n, int num[]) {

    for(int i=0;i<3;i++){

   num[i] = n % 10;

   n /= 10;

    }

}

//将num数组转换为数字

int to_number(int num[]) { 

     int sum = 0;

     for(int i =0; i< 3; i++) {

   sum = sum * 10+ num[i] ;

     }

     return sum;

}

int main() {

   //MIN和MAX分别表示递增排序和递减排序后得到的最小值和最大值

   int n, MIN, MAX,result=0;

   scanf("%d", &n) ;

   int num[4] ;

   while (1) {

        to_array(n, num) ;

        //将n转换为数组

        sort(num, num + 3) ;

        //对 num数组中元素从小到大排序

        MIN = to_number (num); //获取最小值

        sort(num, num + 3,cmp) ;

        //对num数组中元素从大到小排序

        MAX = to_number (num) ;

        //获取最大值

        n = MAX- MIN; //得到下一个数

        result++;

        if(n==495) break;// 下一个数如果是495则退出

   }

   printf("%d",result);

   return 0;

}

C++ STL标准库

1.U429878数列排序

将一个有n（n<=100000）个元素组成的正整数序列{K1,K2,K3,K4,K5,......}重新排列成一个新的序列。新序列中，比K1小的数都在K1的前面(左面)，比K1大的数都在K1的后面(右面)。

输入

输入有两行,第一行为n表示正整数个数,第二行是n个正整数。

输出

输出一行,按要求进行排序的结果。

样例输入

10

60 88 90 10 22 55 40 70 30 150

样例输出

30 40 55 22 10 60 88 90 70 150

参考答案

#include<iostream>

#include<vector>

using namespace std;

int main(){

   vector<int>  xyz;

   int n,k1,temp;

   cin>>n;

   cin>>k1;

   xyz.push_back(k1);

   for(int i=0;i<n-1;i++){

        cin>>temp;

        if(temp<k1){

              xyz.insert(xyz.begin(),temp);

        }else{

              xyz.push_back(temp);

        }   

   }

   vector<int>::iterator iiiiiii;

   for(iiiiiii=xyz.begin();iiiiiii!=xyz.end();iiiiiii++){

        cout<<*iiiiiii<<" ";

   }         

}

2.U429875 :C语言网：1605: 蓝桥杯算法训练VIP-阿尔法乘积

题目描述

 计算一个整数的阿尔法乘积。对于一个整数x来说，它的阿尔法乘积是这样来计算的：如果x是一个个位数，那么它的阿尔法乘积就是它本身；否则的话，x的阿尔法乘积就等于它的各位非0的数字相乘所得到的那个整数的阿尔法乘积。例如：4018224312的阿尔法乘积等于8，它是按照以下的步骤来计算的：

4018224312  →  4*1*8*2*2*4*3*1*2  →  3072  →  3*7*2  →  42  →  4*2  →  8

编写一个程序，输入一个正整数（该整数不会超过6,000,000,000），输出它的阿尔法乘积。

输入

输入只有一行，即一个正整数。 

输出

输出相应的阿尔法乘积。 

样例输入

4018224312

样例输出

8

参考答案

#include <iostream>

#include <vector>

using namespace std;

int main(){

    vector<int>a;

    long long  num;

    cin >> num;

    for(; num > 0 ; num /= 10){   

        a.push_back(num % 10);

    }

    while(a.size() != 1){

        long long  sum = 1;

        for(int i = 0; i < a.size(); i++){

            if(a[i] == 0){

                continue;

            }else{

                sum *= a[i];

            }

        }

        a.clear();

        for(; sum > 0 ; sum /= 10){

            a.push_back(sum % 10);

        }

    }

    cout << a[0] << endl;

    return 0;

}

3.U430127 :C语言网：[2065]{A} + {B}

题目描述

给你两个集合，要求{A} + {B}.

注:同一个集合中不会有两个相同的元素.

输入

每组输入数据分为三行,第一行有两个数字n,m(0<n,m<=10000),

分别表示集合A和集合B的元素个数.后两行分别表示集合A和集合B.    

每个元素为不超出int范围的整数,每个元素之间有一个空格隔开.

输出

针对每组数据输出一行数据,表示合并后的集合,要求从小到大输出,   

每个元素之间有一个空格隔开.

样例输入

1 2

1

2 3

1 2

1

1 2

样例输出

1 2 3

1 2

参考答案：

#include <iostream>

#include <set>

using namespace std;

int main()

{

   set<int> myset;

   int n,m,temp;

   while(cin>>n>>m){

       while(n--&&cin>>temp){

           myset.insert(temp);

       }

       while(m--&&cin>>temp){

           myset.insert(temp);

       }

      for(set<int>::iterator i=myset.begin();i!=myset.end();i++){

           cout<<*i<<" ";

       }

       myset.clear();

       cout<<endl;

   }

   return 0;

}

4.U432033统计输入的不同单词个数

题目描述

输入若干个单词，输出不用单词个数

输入

若干行，第一行为n,表示输入单词的个数。

接下来为n行，每一行一个单词。

输出

一个整数,表示不用单词个数

样例输入

8

he

you

student

you

she

he

you

student

样例输出

4

参考答案：

#include <iostream>

#include<set>

#include<string>

using namespace std;

int main() {

    set<string> s;

    string str;

    int n;

    cin>>n;

    while(n--){

        cin >> str;

        s.insert(str);

    }

    cout << s.size();

    return 0;

}

5.P15799 [GESP202603 五级] 找数

题目描述

给定一个包含n个互不相同的正整数的数组A与一个包含m个互不相同的正整数的数组B，请你帮忙计算有多少个数在数组A与数组B中均出现。

输入格式

第一行包含两个整数n,m。

第二行包含n个正整数a1,a2,⋯,an表示数组A。

第三行包含m个正整数b1,b2,⋯,bm表示数组B。

输出格式

输出一个整数，表示在数组 A与数组B中均出现的数的个数。

输入输出样例

输入 #1复制

3 5

4 2 3

3 1 5 4 6

输出 #1复制

2

说明/提示

样例解释

样例1中，4、3在数组A与B中均出现。

数据范围

对于40%的数据，保证1≤n,m≤1000。

对于100%的数据，保证1≤n,m≤105，1≤ai,bi≤109。

参考答案：

#include <iostream>

#include <set>

using namespace std;

int main() {

    int n, m;

    cin >> n>>m;

    set<int> setA;

    for (int i = 0; i < n; i++) {

        int x;

        cin >> x;

        setA.insert(x);

    }

    int count = 0;

    for (int i = 0; i < m; i++) {

        int x;

        cin >> x;

        if (setA.find(x) != setA.end()) {

            count++;

        }

    }

    cout << count << endl;

    return 0;

}

6.U432038 STL训练 壮志难酬

给你一个小数x，让你算出小数点后第n位是什么，(1 <= n <= 6)  

输入

包含多组测试数据。

首先输入一个t,表示有t组数据，跟着t行：

每行输入一个小数（输入数据保证一定是a.b的形式,为了简单化问题，没有循环小数的情况）.然后跟一个n,表示小数点后第几位

输出

输出一个数表示小数点后第n位的数

样例输入

3

1.234 1

2.345 2

3.456 3

样例输出

2

4

6

参考答案：

#include <iostream>

#include <string>

using namespace std;

int main(){

    int n,index,c;

    string s;

    while(cin>>n){

        while(n--){

            cin>>s>>index;

            c=s.find(".");

            cout<<s[c+index]<<endl;

        }

    }

    return 0;

}

7.U432056:C语言1536: 蓝桥杯算法提高VIP-最长单词

题目描述

编写一个函数，输入一行字符，将此字符串中最长的单词输出。

输入仅一行，多个单词，每个单词间用一个空格隔开。单词仅由小写字母组成。所有单词的长度和不超过100000。如有多个最长单词，输出最先出现的。

样例输入

I am a student

样例输出

student

参考答案

#include<iostream>

#include<string>

using namespace std;

int main(){

         string s, m;

         int mmax = -1, num = 0;

         while (cin >> s){

               num = s.size();

               if (num > mmax){

                    mmax = num;

                           m = s;

                }

          }

          cout << m;

          return 0;

}

8.U432041 美国大选：C语言网 2060: 美国大选

题目描述

美国大选是按各州的投票结果来确定最终的结果的，如果得到超过一半的州的支持就可以当选，而每个州的投票结果又是由该州选民投票产生的，如果某个州超过一半的选民支持希拉里，则她将赢得该州的支持。现在给出每个州的选民人数，请问希拉里至少需要赢得多少选民的支持才能当选？

输入

多组输入数据

每组数据的第一行包括一个整数N（1<=N<=101）,表示美国的州数，N=0表示输入结束。接下来一行包括N个正整数，分别表示每个州的选民数，每个州的选民数不超过100。

输出

对于每组数据输出一行，表示希拉里至少需要赢得支持的选民数

样例输入

3

5 7 5

0

样例输出

6

参考答案

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

int main()

{

    int n;

    while(cin>>n&&n!=0){

        vector<int> vi;

        int num=0,temp;

        for(int i=0;i<n;i++){

         cin>>temp;

              vi.push_back(temp);

        }

        sort(vi.begin(),vi.end());

        for(int i=0;i<n/2+1;i++){

            num+=vi[i]/2+1;

        }

        cout<<num<<endl;

    }

    return 0;

}

7.U432039 :C语言网：[2162]信息学奥赛一本通-统计数字

题目描述

某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5∗10^9）。已知不相同的数不超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

输入

第一行是整数 n，表示自然数的个数；

第2~n+1每行一个自然数。

输出

包含m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。

样例输入

8

2

4

2

4

5

100

2

100

样例输出

2 3

4 2

5 1

100 2

参考答案：

#include<iostream>

#include <string>

#include <map>

using namespace std;

int main(){

   map<long long,int> mymap;

    long long num;

    int n;

    cin>>n;

   while(n--){

   //find(key)在 map 容器中查找键为 key 的键值对，如果成功找到，则返回

   //指向该键值对的迭代器；反之，则返回和 end() 方法一样的迭代器。

       cin>>num;

        if(mymap.find(num)!=mymap.end()){

              ++mymap[num];

        }else{

              mymap[num]=1;

        }

    }

    map<long long,int>::iterator  iter;

    for(iter=mymap.begin();iter!=mymap.end();iter++){

        cout<<iter->first<<" "<<iter->second<<endl;

    }

    return 0;

}

9.U432058字符串比较

题目描述

给出了n(n<=100000)个由数字和字母组成的字符串（长度小于1000），求与给出字符串相同字符串的个数。

输入

第一行是一个数n。

接下来n行，每行都是一个字符串。

接下来一行，是待查询的字符串。

输出

输出一行，一个数。表示与待查询字符串相同的字符串个数。

样例输入

6

ase

eet

ase

see3

awqol

sss

ase

样例输出

2

参考答案：

#include<bits/stdc++.h>

using namespace std;

int main(){

    int n;

    string str;

    cin>>n;

    map<string,int> mp;

    for(int i=1;i<=n;i++){

        cin>>str;

//find(key)查找以key为键的键值对，如果找到，则返回一个指向该键值对的迭代器,

//反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（end() 方法返回的迭代器）。

        if(mp.find(str)!=mp.end()){

          mp[str]+=1;

        }

        else{

          mp[str]=1;

       }         

    }

    cin>>str;

    cout<<mp[str];

    return 0;

}

10.U432060删除字符串中的重复元素

题目描述

本程序的功能是删除输入字符串中所有的重复元素。不连续的重复元素也要删除。

输入

一个字符串（不包含空格）

输出

删除重复元素之后的字符串。

样例输入

love2423445e1e96767878

样例输出

lov3519

参考答案：

#include <iostream>

#include <map>

using namespace std;

int main(){

    map<char, int> mp;

    string str;

    cin >> str;

    //当对map进行下标索引时,如果元素不存在,会自动创建,并赋默认0

    for (string::iterator it = str.begin(); it !=str.end(); it++)

        mp[*it] += 1;

    for (string::iterator it = str.begin(); it !=str.end();){

        if (mp[*it] > 1)

   //s.erase( const_interator pos )

   //删除 pos 迭代器所指的元素，返回值为下一个元素的迭代器

        it = str.erase(it);

        else

            it++;

    }

    cout << str << endl;

    return 0;

}

第8讲 并查集

1.P3367[模板]并查集

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入格式

第一行包含两个整数 N,M表示共有 N个元素和 M个操作。

接下来 M 行，每行包含三个整数 Zi,Xi,Yi。

当 Zi=1 时，将 Xi与 Yi所在的集合合并。

当 Zi=2 时，输出 Xi与Yi是否在同一集合内，是的输出 Y ；否则输出 N 。

输出格式

对于每一个 Zi=2 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。

输入

4 7

2 1 2

1 1 2

2 1 2

1 3 4

2 1 4

1 2 3

2 1 4

输出

N

Y

N

Y

参考答案

#include<bits/stdc++.h>

using namespace std;

int father[1000010];

int findFather(int x){

   int a = x;

   while(x !=father[x]){

        x=father[x];

   }

   while(a!=father[a]){

        int z=a; 

        a = father[a];

        father[z] =x;

   }

   return x;

}

void Union(int a,int b)

{

    int faA=findFather(a);

    int fbB=findFather(b);

    if(faA!=fbB)

    {

        father[faA]=fbB;

    }

}

int main(){

   int i,p1,p2,p3,n,m;

    cin>>n>>m;

    for(i=1;i<=n;i++)

        father[i]=i;

    for(i=1;i<=m;i++){

        cin>>p1>>p2>>p3;

        if(p1==1)

            Union(p2,p3);

        else

            if(findFather(p2)==findFather(p3))

                printf("Y\n");

            else

                printf("N\n");

    }

    return 0;

}

2. P8654 [蓝桥杯201国C]合根植物

w星球的一个种植园，被分成 m×n 个小格子（东西方向 m行，南北方向 n列）。每个格子里种了一株合根植物。

这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

输入格式

第一行，两个整m,n用空格分开，表示格子的行数、列数（1<m,n<1000）。

接下来一行，一个整数 k，表示下面还有 k行数据 (0<k<10^5)。

接下来 k 行，第k行两个整数 a，b，表示编号为 a 的小格子和编号为 b 的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。

比如：5×4 的小格子，编号：

1  2  3  4 

5  6  7  8

9  10 11  12 

13  14  15  16 

17  18  19  20

输出格式

一行一个整数，表示答案

输入

5 4

16

2 3

1 5

5 9

4 8

7 8

9 10

10 11

11 12

10 14

12 16

14 18

17 18

15 19

19 20

9 13

13 17

输出

5

参考答案：

#include<bits/stdc++.h>

using namespace std;

int father[10000000];

//递归写法

/*int findFather(int v)

{

   if(v==father[v]) return v;

   else {

            int F=findFather(father[v]);

            father[v]=F;

            return F;

        }

}

*/

int findFather(int x){

   int a = x;

   while(x !=father[x]){

        x=father[x];

   }

   while(a!=father[a]){

        int z=a; 

        a = father[a];

        father[z] =x;

   }

   return x;

}

void Union(int a,int b){

    int faA=findFather(a);

    int fbB=findFather(b);

    if(faA!=fbB)

    {

        father[faA]=fbB;

    }

}

int main(){

   int i,a,b,n,m,k,sum=0;

    cin>>n>>m;

    for(i=1;i<=n*m;i++)

        father[i]=i;//初始化i的老大为自己

    cin>>k;

    for(i=0;i<k;i++){

        cin>>a>>b;  

        Union(a,b);

    }

    for(i=1;i<=n*m;i++){

         if(i==father[i])

             sum++;

    }

    cout<<sum;

    return 0;

}

3.U437610班级最高分

现有一个学校，学校中有若干个班级，每个班级中有若干个学生，每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级，学生B和学生C处于一个班级，那么我们称学生A和学生C也处于一个班级。

现已知学校中共n个学生（编号为从1到n），每个学生有一个考试分数，再给出m组学生关系（指定两个学生处于一个班级），问总共有多少个班级，并按降序给出每个班级的最高考试分数。

输入描述

第一行两个整数n、m（1≤n≤100,1≤m≤100），分别表示学生个数、学生关系个数；

第二行为用空格隔开的n个整数（0≤每个整数≤100），表示n学生的考试分数；

接下来m行，每行两个整数a和b（1≤a≤n,1≤b≤n），表示编号为a的学生和编号为b的学生处于一个班级。

输出描述

第一行输出一个整数，表示班级个数；

第二行若干个整数，按降序给出每个班级的最高考试分数。整数之间用空格隔开，行末不允许有多余的空格。

样例1

输入

5 3

88 90 86 92 95

4 2

1 3

2 5

输出

2

95 88

解释

编号2、4、5的学生在同一个班级，编号1、3的学生在同一个班级，因此共有两个班级，最高分数分别是编号1的学生的88分、编号5的学生的95分。

参考答案：

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 100;

int father[MAXN];

int score[MAXN];

vector<int> classes;

int findFather(int x){

   int a = x;

   while(x !=father[x]){

        x=father[x];

   }   

   while(a!=father[a]){

        int z=a; 

        a = father[a];

        father[z] =x;

   }

   return x;

}

void Union(int a, int b) {

    int faA = findFather(a);

    int faB = findFather(b);

    if (faA != faB) {

        if (score[faA] < score[faB]) {

            father[faA] = faB;

        } else {

            father[faB] = faA;

        }

    }

}

void init(int n) {

    for (int i = 1; i <=n; i++) {

        father[i] = i;

    }

}

int cmp(int a,int b){

   return a>b;   

}

int main() {

    int n, m, a, b;

    scanf("%d%d", &n, &m);

    init(n);

    for (int i = 1; i <=n; i++) {

        scanf("%d", &score[i]);

    }

    for (int i = 1; i <=m; i++) {

        scanf("%d%d", &a, &b);

        Union(a, b );

    }

    for (int i = 1; i <=n; i++) {

       if (father[i] == i) {           

classes.push_back(score[i]);

        }

    }

    sort(classes.begin(), classes.end(),cmp);

    printf("%d\n", classes.size());

    for (int i = 0; i < classes.size(); i++) {

        printf("%d", classes[i]);

        if (i < (int)classes.size() - 1) {

            printf(" ");

        }

    }

    return 0;

}