2022-3-19(洛谷)

阶乘数码（高精乘）

题目描述

求 n! 中某个数码出现的次数。

输入格式

第一行为 t (t≤10)，表示数据组数。接下来 t 行，每行一个正整数 n(n≤1000) 和数码 a。

输出格式

对于每组数据，输出一个整数，表示 n! 中 a 出现的次数。

输入 #1

2
5 2
7 0  

输出

1
2  

1000！有2568位。。。只有Python能打印出来了趴。。。

#include<iostream>
using namespace std;

//阶乘数码
#include<cstring>
int ans[3000];
int main()
{
    int t;
    cin>>t;
    while(t--){
        memset(ans,0,sizeof(ans));//清零
        ans[1]=1;//否则怎么乘都是0
        int n,i,j,k,m;
        int p=1,jw=0;//p位数，jw进位
        cin>>n>>m;
        for(int i=2;i<=n;i++){//任何数乘1等于其本身
            jw=0;
            for(j=1;j<=p;j++){//高精度*单精度
                ans[j]=ans[j]*i+jw;
                jw=ans[j]/10;//设置进位
                ans[j]=ans[j]%10;
            }
            while(jw>0){
                ans[j]=jw%10;
                jw/=10;
                j++;
            }
            p=j-1;
        }
        long long sum=0;
        for(i=p;i>=1;i--){
            if(ans[i]==m) sum++;
        }
        cout<<sum<<endl;
    }
    return 0;
}

排序、字符串、结构体 

第k小的数（快速排序或者STL）

题目描述

输入 n（1≤n<5000000 且 n 为奇数）个数字 ai​（1≤ai​<109），输出这些数字的第 k 小的数。最小的数是第 0 小。

输入 

5 1
4 3 2 1 5
  

输出 

2  

当可能输入很多数的时候，比如这道题，可能输入5000000个数据，这是用scanf("%d",&x)会缩短用时，如果用cin，洛谷最后一个测试会超时！！！

快速排序（O(n)）

#include<iostream>
using namespace std;

//第k小的数(快速排序)
int a[5000000],n,k;
void qsort(int l,int r){
  int i=l,j=r;
  int mid=a[(l+r)/2];
  while(i<=j){
    while(a[i]<mid) i++;
    while(a[j]>mid) j--;
    if(i<=j){
      swap(a[i],a[j]);
      i++;
      j--;
    }
  }
  if(k<=j) qsort(l,j);
  else if(i<=k) qsort(i,r);
  else printf("%d",a[j+1]);
}
int main()
{
  scanf("%d%d",&n,&k);
  for(int i=0;i<n;i++)
      scanf("%d",&a[i]);
  qsort(0,n-1);
  return 0;
}

nth_element(a+x,a+x+y,a+x+len) (O(n))

执行之后数组 a 下标 x 到 x+y−1 的元素都小于 a[x+y]，下标 x+y+1 到 x+len−1 的元素 都大于 a[x+y]，但不保证数组有序。此时 a[x+y] 就是数组区间 x 到 x+len−1 中第 y 小的数.

#include<iostream>
using namespace std;

//第k小的数（STL）
#include<algorithm>
int a[5000000],n,k;
int main()
{
  cin>>n>>k;
  for(int i=0;i<n;i++)
    scanf("%d",&a[i]);
  nth_element(a,a+k,a+n);
  cout<<a[k]<<endl;
  return 0;
}

奖学金（结构体+排序）

题目描述

某小学最近得到了一笔赞助，打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末，每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学 排在前面，这样，每个学生的排序是唯一确定的。

任务：先根据输入的3门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名学生的学号和总分。注意，在前5名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。例如，在某个正确答案中，如果前两行的输出数据(每行输出两个数:学号、总分) 是:

7 279
5 279

这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ，但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:

5 279
7 279

则按输出错误处理，不能得分。

输入格式

共n+1行。

第1行为一个正整数 n(≤300)，表示该校参加评选的学生人数。

第2到n+1行，每行有3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j−1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为1~n（恰好是输入数据的行号减1）。

所给的数据都是正确的，不必检验。

输出格式

共5行，每行是两个用空格隔开的正整数，依次表示前5名学生的学号和总分。

输入 #1

6
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98
  

输出

6 265
4 264
3 258
2 244
1 237
  

输入 #2

8
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77E:\vscode\.vscode\排序.cpp
67 89 64
78 89 98  

输出 

8 265
2 264
6 264
1 258
5 258  

#include<iostream>
using namespace std;

//奖学金
#include<algorithm>
int n;
struct stu
{
  int id;
  int chinese;
  int math;
  int english;
  int sum;
};
stu a[301];
bool cmp(stu a,stu b){//从大到小排
  if(a.sum>b.sum) return true;
  else if(a.sum==b.sum&&a.chinese>b.chinese) return true;
  else if(a.sum==b.sum&&a.chinese==b.chinese&&a.id<b.id) return true;
  else return false;
}
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++){
    a[i].id=i;
    scanf("%d%d%d",&a[i].chinese,&a[i].math,&a[i].english);
    a[i].sum=a[i].chinese+a[i].math+a[i].english;
  }
  sort(a+1,a+n+1,cmp);
  for(int i=1;i<=5;i++){
    printf("%d %d\n",a[i].id,a[i].sum);
  }
  return 0;
}

宇宙总统（结构体+排序）

题目描述

地球历公元 6036 年，全宇宙准备竞选一个最贤能的人当总统，共有 n 个非凡拔尖的人竞选总统，现在票数已经统计完毕，请你算出谁能够当上总统。

输入格式

第一行为一个整数 n，代表竞选总统的人数。

接下来有 n 行，分别为第一个候选人到第 n 个候选人的票数。

输出格式

共两行，第一行是一个整数 m，为当上总统的人的号数。

第二行是当上总统的人的选票。

输入 

5
98765
12365
87954
1022356
985678
  

输出 

4
1022356  

说明/提示

票数可能会很大，可能会到 100 位数字。（用string保存）

1≤n≤20

string类型的"数字"比较大小可以像int一样直接比较！！！

#include<iostream>
using namespace std;

//宇宙总统
#include<algorithm>
int n;
struct president
{
  int id;
  string ticket;
}; president a[21];
bool cmp(president a,president b){
  if(a.ticket.size()>b.ticket.size()) return true;
  else if(a.ticket.size()==b.ticket.size()&&a.ticket>b.ticket) return true;
  else return false;
}
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++){
    cin>>a[i].ticket;
    a[i].id=i;
  }
  sort(a+1,a+n+1,cmp);
  cout<<a[1].id<<endl<<a[1].ticket<<endl;
  return 0;
}

分数线划定（结构体+排序）

题目描述

世博会志愿者的选拔工作正在 A 市如火如荼的进行。为了选拔最合适的人才，A市对所有报名的选手进行了笔试，笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取人数的150%划定，即如果计划录取m名志愿者，则面试分数线为排名第m×150%（向下取整：floor）名的选手的分数，而最终进入面试的选手为笔试成绩不低于面试分数线的所有选手。

现在就请你编写程序划定面试分数线，并输出所有进入面试的选手的报名号和笔试成绩。

输入格式

第一行，两个整数 n,m(5≤n≤5000,3≤m≤n)，中间用一个空格隔开，其中nn表示报名参加笔试的选手总数，m表示计划录取的志愿者人数。输入数据保证 m×150%向下取整后小于等于 n。

第二行到第 n+1 行，每行包括两个整数，中间用一个空格隔开，分别是选手的报名号 k(1000≤k≤9999)和该选手的笔试成绩s(1≤s≤100)。数据保证选手的报名号各不相同。

输出格式

第一行，有2个整数，用一个空格隔开，第一个整数表示面试分数线；第二个整数为进入面试的选手的实际人数。

从第二行开始，每行包含2个整数，中间用一个空格隔开，分别表示进入面试的选手的报名号和笔试成绩，按照笔试成绩从高到低输出，如果成绩相同，则按报名号由小到大的顺序输出。

输入 

6 3 
1000 90 
3239 88 
2390 95 
7231 84 
1005 95 
1001 88  

输出 

88 5 
1005 95 
2390 95 
1000 90 
1001 88 
3239 88   

说明/提示

m×150%=3×150%=4.5，向下取整后为4。保证4个人进入面试的分数线为88，但因为88有重分，所以所有成绩大于等于88 的选手都可以进入面试，故最终有5个人进入面试。

#include<iostream>
using namespace std;

//分数线划定
#include<algorithm>
#include<cmath>
int n,m;
struct people
{
  int id;
  int score;
};
people a[5000];
bool cmp(people a,people b){
  if(a.score>b.score) return true;
  else if(a.score==b.score){
    if(a.id<b.id) return true;
    else return false;
  }else return false;
}
int main()
{
  cin>>n>>m;
  m=floor(m*1.5);
  for(int i=0;i<n;i++)
    scanf("%d%d",&a[i].id,&a[i].score);
  sort(a,a+n,cmp);
  int line=a[m-1].score;//分数线,过分数线的人数
  for(int i=m;i<n;i++){
    if(a[i].score==line) m++;
    else break;
  }
  cout<<line<<" "<<m<<endl;
  for(int i=0;i<m;i++){
    printf("%d %d\n",a[i].id,a[i].score);
  }
  return 0;
}

生日（结构体+排序）

题目描述

cjf 君想调查学校 OI 组每个同学的生日，并按照年龄从大到小的顺序排序。但cjf君最近作业很多，没有时间，所以请你帮她排序。

输入格式

有2行，

第1行为OI组总人数n；

第2行至第n+1行分别是每人的姓名s、出生年y、月m、日d。

输出格式

有n行，

即n个生日从大到小同学的姓名。(如果有两个同学生日相同,输入靠后的同学先输出)

输入 

3
Yangchu 1992 4 23
Qiujingya 1993 10 13
Luowen 1991 8 1
  

输出 

Luowen
Yangchu
Qiujingya
  

说明/提示

数据规模：1<n<100， length(s)<20

C语言——printf&scanf格式字符串【占位符】_刘鑫磊up的博客-CSDN博客_scanf 占位符目录:一：printf格式字符串1.一般形式2.类型字符3.标志字符4.使用printf函数时注意的问题二：scanf格式字符串1.一般形式2.类型字符3.标志字符4.使用scanf函数时注意的问题三：double 和 float 对于——%lf和%f 的用法1.printf输出2.scanf 输入一：printf格式字符串函数原型在...https://blog.csdn.net/liu17234050/article/details/103935791

#include<iostream>
using namespace std;

//生日
#include<algorithm>
int n;
struct stu
{
  int id;//输入顺序
  int year,mon,day;
  string name;
};
stu a[100];
bool cmp(stu a,stu b){
  if(a.year<b.year) return true;
  else if(a.year==b.year&&a.mon<b.mon) return true;
  else if(a.year==b.year&&a.mon==b.mon&&a.day<b.day)return true;
  else if(a.year==b.year&&a.mon==b.mon&&a.day==b.day){
    if(a.id>b.id) return true;
    else return false;
  }
  else return false;
}
int main()
{
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i].name>>a[i].year>>a[i].mon>>a[i].day;
    a[i].id=i;
  }
  sort(a,a+n,cmp);
  for(int i=0;i<n;i++)
    cout<<a[i].name<<endl;
  return 0;
}

拼数（字符串+排序）

题目描述

设有 n 个正整数 a1​…an​，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 n。

第二行有 n 个整数，表示给出的 n 个整数 ai​。

输出格式

一个正整数，表示最大的整数

输入 #1

3
13 312 343
  

输出 

34331213
  

输入 #2

4
7 13 4 246  

输出 

7424613  

说明/提示

对于全部的测试点，保证 1≤n≤20，1≤ai​≤10^9。

#include<iostream>
using namespace std;

//拼数
#include<algorithm>
int n;
string a[20];
bool cmp(string a,string b){
  return a+b>b+a;
}
int main()
{
  cin>>n;
  for(int i=0;i<n;i++) cin>>a[i];
  sort(a,a+n,cmp);
  for(int i=0;i<n;i++) cout<<a[i];
  return 0;
}