PAT_Basic_1038 统计同成绩学生

2022-01-28

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

输入格式：

输入在第 1 行给出不超过 105 的正整数 N，即学生总人数。随后一行给出 N 名学生的百分制整数成绩，中间以空格分隔。最后一行给出要查询的分数个数 K（不超过 N 的正整数），随后是 K 个分数，中间以空格分隔。

输出格式：

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

输入样例：

1
2
3

10
60 75 90 55 75 99 82 90 75 50
3 75 90 88

输出样例：

3 2 0

思路：

我自己写的测试点3超时，后知后觉发现很多题出现的超时都可以用一个通法解决。下面是我的代码。

代码：

#include<iostream>
#include<vector>
using namespace std;
#include<map>
int main(){
    int N,score,num,select_score,count=0;
    scanf("%d",&N);
    vector<int>v1,v2;
    for(int i=0;i<N;i++){
        scanf("%d",&score);
        v1.push_back(score);
    }
    cin>>num;
    for(int i=0;i<num;i++){
        scanf("%d",&select_score);
        v2.push_back(select_score);
    }
    map <int,int> m;//这样会导致没有出现的select_score不会收入m
    for(int j=0;j<num;j++){
        int cnt=0;
        for(int i=0;i<N;i++){
            if(v1[i]==v2[j]){
                m[j]++;
            }
            else{
                cnt++;
            }
        }
        if(cnt==N){
            m[j]=0;
        }
    }
    for(auto it=m.begin();it!=m.end();it++){
        if(count==0){
            printf("%d",it->second);
        }
        else{
            printf(" %d",it->second);
        }
        count++;
    }
}

我之后都采取hash散列的思想：

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int N,num,score;
    vector<int> v(101);
    cin>>N;
    for(int i=0;i<N;i++){
        scanf("%d",&score);
        v[score]++;//这种思想出现了很多次了 请务必掌握
    }
    cin>>num;
    for(int i=0;i<num;i++){
        scanf("%d",&score);
        if(i!=0){
            printf(" %d",v[score]);
        }
        else{
            printf("%d",v[score]);
        }
    }

展开全文 >>

PAT_Basic_1037 在霍格沃茨找零钱

2022-01-28

如果你是哈利·波特迷，你会知道魔法世界有它自己的货币系统 —— 就如海格告诉哈利的：“十七个银西可(Sickle)兑一个加隆(Galleon)，二十九个纳特(Knut)兑一个西可，很容易。”现在，给定哈利应付的价钱 P 和他实付的钱 A，你的任务是写一个程序来计算他应该被找的零钱。

输入格式：

输入在 1 行中分别给出 P 和 A，格式为 Galleon.Sickle.Knut，其间用 1 个空格分隔。这里 Galleon 是 [0, 107] 区间内的整数，Sickle 是 [0, 17) 区间内的整数，Knut 是 [0, 29) 区间内的整数。

输出格式：

在一行中用与输入同样的格式输出哈利应该被找的零钱。如果他没带够钱，那么输出的应该是负数。

输入样例 1：

1	10.16.27 14.1.28

输出样例 1：

3.2.1

输入样例 2：

1	14.1.28 10.16.27

输出样例 2：

-3.2.1

代码：

#include<iostream>
using namespace std;
int main(){
   int a1,b1,c1,a2,b2,c2,a3,b3,c3;
   scanf("%d.%d.%d",&a1,&b1,&c1);
   scanf("%d.%d.%d",&a2,&b2,&c2);
   if(a1>a2 || (a1==a2 && b1>b2) || (a1==a2 && b1==b2 && c1>c2)){
       swap(a1,a2);swap(b1,b2);swap(c1,c2);//确保2的总值最大
       cout<<"-";
   }
    int knut_num = c2-c1;
    if(knut_num>=0){
        c3=knut_num;//28-16=12 够找 不用向第二项借
    }else{
        b2-=1;//借1个sickle 比如1-28=-27 -27+29=2
        c3=knut_num + 29;
    }
    int sickle_num = b2-b1;
    if(sickle_num>=0){
        b3=sickle_num;
    }
    else{
        a2-=1;
        b3=sickle_num +17;
    }
   a3=a2-a1;
   printf("%d.%d.%d",a3,b3,c3);
}

展开全文 >>

PAT_Basic_1036 跟奥巴马一起编程

2022-01-28

美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014 年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！

输入格式：

输入在一行中给出正方形边长 N（3≤N≤20）和组成正方形边的某种字符 C，间隔一个空格。

输出格式：

输出由给定字符 C 画出的正方形。但是注意到行间距比列间距大，所以为了让结果看上去更像正方形，我们输出的行数实际上是列数的 50%（四舍五入取整）。

输入样例：

10 a

输出样例：

aaaaaaaaaa
a        a
a        a
a        a
aaaaaaaaaa

代码：

#include<iostream>
#include<cmath>
using namespace std;
void Head_Rail(int n,char c){
    for(int i=0;i<n;i++){
        cout<<c;
    }
    cout<<endl;
}
int main(){
    float N;
    char C;
    cin>>N>>C;
    //行是N个c 然后列是N/2 当N为奇数时 对N/2四舍五入取证 那不就是向上取整
    Head_Rail(N,C);
    int num = round(N/2);//10/2=5 num=5 
    //num-2 行  每行
    for(int i=0;i<num-2;i++){
        //每列
        for(int j=0;j<N;j++){
            if(j==0 || j==N-1){
                cout<<C;
            }
            else{
                cout<<' ';
            }
        }
        cout<<endl;
    }
    Head_Rail(N,C);

}

展开全文 >>

PAT_Basic_1035 插入与归并

2022-01-28

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：

输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：

首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例 1：

1
2
3

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例 1：

1 2	Insertion Sort 1 2 3 5 7 8 9 4 6 0

输入样例 2：

1
2
3

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

输出样例 2：

1 2	Merge Sort 1 2 3 8 4 5 7 9 0 6

代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void printArray(vector<int> a){
    cout << a[0];
    for(int i=1; i<a.size(); i++) {
        cout << " " << a[i];
    }
    cout << endl;
}

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> b(n);
    for (int i=0; i<n; i++){
        cin >> a[i];
    }
    for (int i=0; i<n; i++){
        cin >> b[i];
    }
    //找到第一个未排序元素位置
    int i = 1;
    while (i<n && b[i-1]<=b[i]){//跳出while循环是 b[i-1]>b[i] 此时从i处开始排序 
        i++;
    }// 此时i=5 未排序 
    if (equal(a.begin()+i, a.end(), b.begin()+i)){
        cout << "Insertion Sort" << endl;
        sort(b.begin(), b.begin()+i+1);
    }
    else {
        cout << "Merge Sort" << endl;
        int span = 2;
        while (!equal(a.begin(), a.end(), b.begin())){
            for (i=0; i<n/span; i++){//n=10 分为5组(0 1 2 3 4)
                sort(a.begin()+i*span, a.begin()+(i+1)*span);
            }
            sort(a.begin()+i*span, a.end());//i=5 span=2 
            span *= 2;
        }//再排一次
        for (i=0; i<n/span; i++){//10/4=2.5 0 1 
            sort(b.begin()+i*span, b.begin()+(i+1)*span);
        }
        sort(b.begin()+i*span, b.end());//i=2 span=4
    }
    printArray(b);

    return 0;
}

展开全文 >>

瓦解懦弱

2022-01-27

我是一个懦弱的人，也可以往大了说，我是一个心智不成熟的女生。在一知半解，迷迷糊糊的知道自己很垃圾、有很多低效之处，我经常做的事：浅浅地分析出我较peer的劣势，然后觉得太难太麻烦体系庞大要解决太复杂(这是一个需要长期坚持和积累才能改变的事)，我在这个时候会先去上个厕所或者找点事做，然后就麻痹自己，说太麻烦了，在chrome地址栏键入bilibili.com多爽，键入youtube.com多爽，其实我深深体验到b站、抖音、知乎、youtube带来的负面影响与无聊。这些软件和网站给我推送的视频或者问答，在我的大脑简单粗暴的归纳下，大体可以分为：(1)这事压根不需要你关心吧(比如某乎上的陈梦在东京奥运会后，为何一冠难求呢？，如何看待江歌妈妈带货卖山东农家鸽子肉的行为?，国足将在27日迎战日本，大家觉得国足会赢得比赛给全国人民拜年吗？)，我之前不就是过的行尸走肉的生活嘛，真的，打开知乎，根本刷不下去，啥问题啊，咸吃萝卜淡操心，要你管啊。(2)吓退一波不明真相菜狗的焦虑贴(如何看待2020届算法岗一片红海？，如何看待 2022 年秋招算法岗人间地狱？，如何看待2021年秋招算法岗灰飞烟灭？，如何看待2023年秋招算法岗一片红海?)我对这些问题的提问者，只能呵呵一句。你不需要用诸如“红海”、“灰飞烟灭”来形容，你tm学就是了啊，整天啥新的东西都没往脑子里灌输，全想着怎么可以省力走捷径，走过路过都要吐口口水给它们。然后抖音上的视频，我下回抖音是为了关注孙海洋的三个孩子：孙悦孙卓孙辉，但是如果以他们一天两个视频算，我1min就可以看完，但我实际会逗留几min，我归纳了下我刷到过的视频：电视剧《家有儿女》的剪辑，一些做美食的视频，一些不知道为什么要拍出来的摆拍。我虽然很想去字节跳动上班，我们都知道Byte Dance创始人张一鸣先生是一个拒绝即刻满足的人，更过分的传说是人家根本不看手机，一个在延迟满足方面做到极致的人却创造出一款消磨人麻木人的产品，我觉得抖音可以一周看一次这周你关注的人有啥更新。然后b站，也没啥看的，因为1月份我看了玲娜贝儿和《那年夏天》这部韩剧，所以b站给我推了这两个相关的视频，其余频率高的诸如减肥、健身环、分手厨房、java、python、深度学习，我都没点进去看。在得到的日报上了解到跟李沐学AI，去b站看沐神的《实用机器学习》，十几天过去了，这门很优质的课程我只看到了第2p，你说吧，我完全不能合理使用资源。

more >>

展开全文 >>