【題解】Luogu P1125 【笨小猴】

给出一种半(maybe更少)面向对象的写法,这种写法的好处就是灰常好写,是以人为中心的而不是以算法(顺便提一下几乎所有老师都说面向对象在竞赛中用不到,但实际上却很有用,虽然不用也可以,只是对于我这种Java转行的人来说很麻烦),跑题了 咳咳(听说ACM可用Java提交诶)再次跑题233

此题如下坑点:

  1. 题干中所述min是出现次数最少的词,那么意味着首先得出现,min才有意义(这告诉我们语文or审题or严谨态度的重要性)

  2. 忘了

伪码(《head first java》告诉我们,想写程序先得写出(or想出)程序的伪码,然后是测试码,最后是真实码,也就是说看到题也别急先写)

数据结构:

用一个名叫Word的类,来储存字母的出现次数和该字母是否出现,即开一个Word w[26]。

算法:

判断质数

类排序(类似于结构体排序)

逻辑:

读入
统计字母出现次数

排序
取最大(小)次数

判断输出即可

您的点赞和评论是咱前进的动力qwq(商界互吹)

qwq管理员求通过了(再不过就被连拒n片题解了)

    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    class Word{
    public:
        int cnt;
        bool isAppear;
    };
    Word w[26];
    bool compare(Word w1,Word w2){
        return w1.cnt > w2.cnt;
    }
    bool isPrime(int n){
        int sqr = sqrt(n * 1.0);
        if(n <= 1){
            return false;
        }
        for(int i = 2;i < sqr;i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
    int main(){
        char word[101];
        scanf("%s",word);
        char c = 'a';
        for(int i = 0;i < 26;i++){
            for(int j = 0;j < strlen(word);j++){
                if(c == word[j]){
                    w[i].isAppear = true;
                    w[i].cnt++;
                }
            }
            c++;
        }
        sort(w,w + 26,compare);
        int max = 0,min = 9999;
        max = w[0].cnt;
        for(int i = 0;i < 26;i++){
            if(w[i].isAppear){
                min = w[i].cnt;
            }
        }
        if(isPrime(max - min)){
            printf("Lucky Word\n");
            printf("%d",max - min);
        }else{
            printf("No Answer\n");
            printf("0\n");
        }
        return 0;
}

【題解】Luogu P1208 【[USACO1.3]混合牛奶 Mixing Milk】

(伪)面向对象

C++用类来解题

sort() + class + 贪心思想

设计一个类来保存每个奶农的信息(奶量和单价),然后定义compare函数用于比较,最后贪心求解即可。

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    class Farmer{

    public:

            int price;
            int milk;
    };
    bool compare(Farmer f1,Farmer f2){
        return f1.price < f2.price;
    }
    Farmer f[2000000];
    int main(){
        int n,m;//N是需要牛奶的总数;M是提供牛奶的农民个数。
        scanf("%d %d",&n,&m);
        for(int i = 0;i < m;i++){
            scanf("%d %d",&f[i].price,&f[i].milk);
        }
        sort(f,f + m,compare);//按单价从小到大排序
        int total = n;
        int min = 0;
        for(int i = 0;i < m;i++){
            if(total == 0) break;//当前需求量为0就退出
            if(total >= f[i].milk){//当前需求量大于奶农f[i]的奶量时,就全部买下来
                total -= f[i].milk;//当前需求量减去购买量
                min += (f[i].milk * f[i].price);//计算当前价格
            }else if(total < f[i].milk){//如果不够,能买多少买多少
                min += total * f[i].price;
                total = 0;
            }
        }
        printf("%d",min);
        return 0;
}

【題解】Luogu P1003 【铺地毯】

首先看题被分类迷惑了,以为可以直接暴力模拟,创一个一百万乘一百万的二维数组。然后发现。。。不用想128MB绝对放不下,128MB大概开5700×5700的二维int数组,就算是short也不够。

所以这题就不能陷入思维怪圈。

然后我们就可以想一个数学方法,即判断一个点是否在一个正方形内(不妨令点坐标为(px,py),正方形左下角坐标(a,b),大小为s),则有

px >= a
px <= a + s
py >= b
py <= b + s

恒成立
然后我们就只需倒着遍历地毯(如果你是顺着读入的话),然后判断即可

如何输入就在此不述了

    #include<cstdio>
    using namespace std;
    int carpet[10000][5] = {};
    int main(){
        int n;
        scanf("%d",&n);
        for(int i = 0;i < n;i++){
            scanf("%d %d %d %d",&carpet[i][0],&carpet[i][1],&carpet[i][2],&carpet[i][3]);
            carpet[i][4] = i + 1;
        }
        int px,py;
        scanf("%d %d",&px,&py);
        int result = -1;
        for(int i = n - 1;i >= 0;i--){
            if(px >= carpet[i][0] && px <= carpet[i][0] + carpet[i][3] && py >= carpet[i][1] && py <= carpet[i][1] + carpet[i][3]){
                result = carpet[i][4];
                break;
            }
        }
        printf("%d",result);
        return 0;
}

【題解】Luogu P1051 【谁拿了最多奖学金】

再来一波面向对象(C++版)

注意看题注意看题注意看题这题注意看题注意看题注意看题

本题:第三行是这N个学生获得的奖学金的总数。

然后就创一个学生类,包含所需信息,然后再创对象数组储存每一个学生信息。

然后按题意模拟即可

最后输出

    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<iostream>
    using namespace std;
    //设计类
    class Student{
        public:
            string name;//名字
            int number;//序号(用于判断输入顺序)
            int aveScore;//期末平均成绩
            int classScore;//班级议评成绩
            char isCadre;//是否干部
            char isWest;//是否西部
            int paper;//论文数
            int money;//个人钱数
    };
    //比较函数:钱多的在前,相同钱数比序号,序号小的在前
    bool compare(Student s1,Student s2){
        if(s1.money == s2.money){
            return s1.number < s2.number;
        }else{
            return s1.money > s2.money;
        }
    }
    int main(){
        int n;
        scanf("%d",&n);
        Student s[100];//对象数组
        int delta1,delta2;//辅助输入,能不用cin/cout就不用
        char delta3,delta4;//同上
        int delta5,total = 0;//前二者同上,最后一个total为总钱数
        //输入,预处理
        for(int i = 0;i < n;i++){
            cin >> s[i].name;
            //cin >> delta1 >> delta2 >> delta3 >> delta4 >> delta5;
            scanf("%d %d %c %c %d",&delta1,&delta2,&delta3,&delta4,&delta5);
            s[i].aveScore = delta1;
            s[i].classScore = delta2;
            s[i].isCadre = delta3;
            s[i].isWest = delta4;
            s[i].paper = delta5;
            s[i].money = 0;
            s[i].number = i + 1;//序号
        }
        //模拟判断钱数
        for(int i = 0;i < n;i++){
            if(s[i].aveScore > 80 && s[i].paper > 0){
                s[i].money += 8000;
            }
            if(s[i].aveScore > 85 && s[i].classScore > 80){
                s[i].money += 4000;
            }
            if(s[i].aveScore > 90){
                s[i].money += 2000;
            }
            if(s[i].aveScore > 85 && s[i].isWest == 'Y'){
                s[i].money += 1000;
            }
            if(s[i].classScore > 80 && s[i].isCadre == 'Y'){
                s[i].money += 850;
            }
        }
        //真·sort排序
        sort(s,s + n,compare);
        cout << s[0].name << endl;
        cout << s[0].money << endl;
        //计算总钱数
        for(int i = 0;i < n;i++){
            delta6 += s[i].money;
        }
        cout << delta6 << endl;
        return 0;
}

【題解】Luogu P1093 【奖学金】

面向对象大法好(C++版)
结构体什么的就是水(误,毕竟是Java过来的难民)
重点是比较函数的书写
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    //类的定义
    class Student{
    public:
        int number;
        int chinese;
        int math;
        int english;
        int total;
    };
    //用于语文成绩的比较
    bool cmp1(int a,int b){
        return a > b;
    }
    //用于学号的比较
    bool cmp2(int a,int b){
        return a < b;
    }
    //之所以要分开,是因为不分开有一个点过不去
    //真·迷之比较函数
    bool compare(Student s1,Student s2){
        if(s1.total == s2.total && s1.chinese != s2.chinese){//如果总分相同而语文成绩不同
            return cmp1(s1.chinese,s2.chinese) > 0;//语文成绩高的在前
        }else if(s1.total == s2.total && s1.chinese == s2.chinese){//如果总分相同且语文成绩相同
            return cmp2(s1.number,s2.number) > 0;//学号小的在前
        }else{//如果总分在前
            return s1.total > s2.total;//总分大的在前
        }
    }
    int main(){
        int n;
        scanf("%d",&n);
        Student s[300];//对象数组,如果不会面向对象的就去问度娘吧
        //输入,预处理
        int delta1,delta2,delta3;
        for(int i = 0;i < n;i++){
            s[i].number = i + 1;
            scanf("%d %d %d",&delta1,&delta2,&delta3);
            s[i].chinese = delta1;
            s[i].math = delta2;
            s[i].english = delta3;
            s[i].total = s[i].chinese + s[i].math + s[i].english;
        }
        //真·sort排序
        sort(s,s + n,compare);
        //输出
        int delta4,delta5;
        for(int i = 0;i < 5;i++){
            delta4 = s[i].number;
            delta5 = s[i].total;
            printf("%d %d\n",delta4,delta5);
        }
        //优雅的结束
        return 0;
}

【題解】Luogu P1067 【多项式输出】

这题坑点略多,居然花了我两次数据下载

坑点如下:

  • 第一项前无‘+’号

  • 常数项与一次项是不同的概念

  • 注意系数为1,-1和0的情况

然后直接模拟即可,当然,为了方便模拟

分三步:

第一步:单独判号输出第一项

第二步:循环输出第二到倒数第三项

第三步:单独判号输出一次项(这个别漏了)

第四步:输出常数项


程序如下:(想抄就复制吧,反正OI是自己的事)

    #include<cstdio>
    using namespace std;
    int main(){
        int time;//次数
        scanf("%d",&time);
        int coefficient[101];//系数
        for(int i = 0;i < time + 1;i++){
            scanf("%d",&coefficient[i]);//其中第i个整数表示第time - i + 1次项的系数
        }
        //先判最高此项,分0,1,-1的情况
        if(coefficient[0] == 1){
            printf("x^%d",time);
        }else if(coefficient[0] == -1){
            printf("-x^%d",time);
        }else if(coefficient[0] == 0){
            printf("");
        }else{
            printf("%dx^%d",coefficient[0],time);
        }
        //循环判次高项~二次项,分0,1,-1,和正负数的情况
        for(int i = 1;i < time - 1;i++){
            if(coefficient[i] == -1){
                printf("-x^%d",time - i);
            }else if(coefficient[i] == 1){
                printf("+x^%d",time - i);
            }else if(coefficient[i] == 0){
                printf("");
            }else{
                if(coefficient[i] > 0){
                    printf("+%dx^%d",coefficient[i],time - i);
                }else{
                    printf("%dx^%d",coefficient[i],time - i);
                }
            }
        }
        //再判一次项分0,1,-1,和正负数的情况
        if(coefficient[time - 1] == -1){
                printf("-x");
        }else if(coefficient[time - 1] == 1){
                printf("+x");
        }else if(coefficient[time - 1] == 0){
                printf("");
        }else{
            if(coefficient[time - 1] > 0){
                printf("+%dx",coefficient[time - 1]);
            }else{
                printf("%dx",coefficient[time - 1]);
            }
        }
        //最后判常数项,分正负和0
        if(coefficient[time] > 0){
            printf("+%d",coefficient[time]);
        }else if(coefficient[time] == 0){
            printf("");
        }else if(coefficient[time] < 0){;
            printf("%d",coefficient[time]);
        }
        return 0;
    }

【題解】Luogu P1307 【数字反转】

这题如果会字符串相关的处理将会非常简单

为何一大堆人的题解都这么麻烦

首先我们得知道几个关于字符串的函数

See Also https://www.luogu.org/blog/Cinema/sscanf-sprintf

reverse(),位于STL中,是一个用于反转数组的函数
ssprintf() & sscanf(),位于cstdio/stdio.h中,用于将变量输入到char[]或将char[]转换为相应变量

strlen()/reverse()/ssprintf()/sscanf()

首先写一个函数

int change(int number);

/*
*@author Cinema 17-12-29

*@version 1.1

*@description change函数用于对int类型的数字进行反转,会自动处理掉前导0,

*@args int number,需要反转的数

*@return 反转后的数,会处理前导0和负数

*/

int change(int number){

    bool isMinus = false;//判断是否是负数 

/*
*@description 若number<0,则将其转化成正数处理,并将isMinus设为true,若为0,直接return 0

*/

        if(number < 0){
            number = -number;
            isMinus = true;
        }else if(number == 0){
            return 0;
        }

/*
*@description delta[]用于接收number,changedNumber是return的值

*/

    char delta[100];

    int changedNumber = 0;

/*
*@description 将number转化为char[]

     \*@see-also sprintf() reverse() sscanf()

*/

    sprintf(delta,"%d",number);

/*
*@description reverse()用于反转delta[]

*/

    reverse(delta,delta + strlen(delta));

/*
*@description 将反转后的数输出到changedNumber中,sscanf()会自动处理前导0

*/

    sscanf(delta,"%d",&changedNumber);

/*
*@description 判断正负并return

*/

        if(isMinus){
            return -changedNumber;
        }else{
            return changedNumber;
        }
    }

这个是1.1的版本,原来1.0的时候还不知道有reverse()这么好用的函数,所以1.0就写的很烦琐,故就不献丑了。

完整程序(已去除注释):

    #include<cstdio>
    #include<cstring>
    #include<algorithm> 
    using namespace std;
    int change(int number){
        bool isMinus = false;
        if(number < 0){
            number = -number;
            isMinus = true;
        }else if(number == 0){
            return 0;
        }
        char delta[100];
        int changedNumber = 0;
        sprintf(delta,"%d",number);
        reverse(delta,delta + strlen(delta));
        sscanf(delta,"%d",&changedNumber);
        if(isMinus){
            return -changedNumber;
        }else{
            return changedNumber;
        }
    }
    int main(){
        int number;
        scanf("%d",&number);
        printf("%d",change(number));
        return 0;
}

【題解】Luogu P1618【三连击(升级版)】

这题和普通版三连击差不多,只是倍数改了。

首先有一个数学规律:

这个三个数的每一位之积一定等于9的阶乘

且每一位都不相同

思路:

先枚举a,bc两数用比例乘上去,a最小为123,且很显然小于333,然后裂解出每一位,再根据数学规律判断即可。


#include<cstdio>
using namespace std;
int main(){
    int a,b,c,count = 0;//a,b,c为所给数,count为是否存在的个数
    //以下三行均为a,b,c的每一位
    int a100,a10,a1;
    int b100,b10,b1;
    int c100,c10,c1;
    float x,y,z;//比例
    scanf("%f %f %f",&x,&y,&z);
    //开始迭代
    for(a = 123;a <= 329;a++){
        //裂解a,其实这里的裂解方式是最菜的,不要学我23333
        a100 = a / 100;
        a10 = (a - (a100 * 100)) / 10;
        a1 = (a % 100) % 10;
        //计算b,c
        b = a * (y / x);
        c = a * (z / x);
        //裂解b
        b100 = b / 100;
        b10 = (b - (b100 * 100)) / 10;
        b1 = (b % 100) % 10;;
        //裂解c
        c100 = c / 100;
        c10 = (c - (c100 * 100)) / 10;
        c1 = (c % 100) % 10;
        //按照数学规律判断,简单明了,不过字多了点就是
        if(((a100 * a10 * a1 * b100 * b10 * b * c100 * c10 * c1) == (1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9)) && (a100 != a10) && (a100 != a1) && (a100 != b100) && (a100 != b10) && (a100 != b1) && (a100 != c100) && (a100 != c10) && (a100 != c1) && (a10 != a1) && (a10 != b100) && (a10 != b10) && (a10 != b1) && (a10 != c100) && (a10 != c10) && (a10 != c1) && (a1 != b100) && (a1 != b10) && (a1 != b1) && (a1 != c100) && (a1 != c10) && (a1 != c1) && (b100 != b10) && (b100 != b1) && (b100 != c100) && (b100 != c10) && (b100 != c1) && (b10 != b1) && (b10 != c100) && (b10 != c10) && (b10 != c1) && (b1 != c100) && (b1 != c10) && (b1 != c1) && (c100 != c10) && (c100 != c1) && (c10 != c1) ){
            count++;//存在就自加,不存在则为0
            printf("%d %d %d\n",a,b,c);
        }
    }
    //不存在就输出
    if(count == 0){
        printf("No!!!");
    }
    return 0;
}

Windows下的程序對拍-fc命令詳解

在競賽中,我們常常需要比較我們寫的程序的輸出與樣例的差別,通常情況下是可以用肉眼觀察的到結果的。但是如果輸出極其之多或者是差一個空格回車之類的那咱們不就沒招了。

不,我們有fc命令,這是微軟給我們留下的不錯的東西,使用簡單方便快捷,還可以用來裝逼

這裡是它的APIs:
Compares two files or sets of files and displays the differences between them

FC [/A] [/C] [/L] [/LBn] [/N] [/OFF[LINE]] [/T] [/U] [/W] [/nnnn]
  [drive1:][path1]filename1 [drive2:][path2]filename2
FC /B [drive1:][path1]filename1 [drive2:][path2]filename2
  /A         Displays only first and last lines for each set of differences.
  /B         Performs a binary comparison.
  /C         Disregards the case of letters.
  /L         Compares files as ASCII text.
  /LBn       Sets the maximum consecutive mismatches to the specified
             number of lines.
  /N         Displays the line numbers on an ASCII comparison.
  /OFF[LINE] Do not skip files with offline attribute set.
  /T         Does not expand tabs to spaces.
  /U         Compare files as UNICODE text files.
  /W         Compresses white space (tabs and spaces) for comparison.
  /nnnn      Specifies the number of consecutive lines that must match
             after a mismatch.
  [drive1:][path1]filename1        Specifies the first file or set of files to compare.
  [drive2:][path2]filename2        Specifies the second file or set of files to compare.

然後咱們準備兩個內容有點不同的txt文檔
輸入fc out1.txt out2.txt
這時在終端上就可以看到結果了

如果比對信息太多了,還能輸出到文件里
輸入fc out1.txt out2.txt > isAC.txt

easy