Z牌题解铺子

· · 学习·文化课

Z牌题解铺子 [Z]

前言：

在很久很久以前，一个通过量还不够一百的作者励志做一百篇题解，所以经过两年半的爆肝制作，这篇题解终于没有完成。然后作者因为累个半死的原因打了个广告：

有两年半制作题解经验，使用万年珍稀键盘，天然护眼性电脑制作。 $0$ 添加剂 $0$ 蔗糖，低脂低 GI；洛谷用户新题解，美味好玩又实用。 题解，就找 $[\mathbb{Z]}$ 牌题解铺子！

食用说明：

但是因为作者太辣鸡了，所以题目难度一般在$\textcolor{red}{入门}$到$\textcolor{orange}{普及-}$之间。 在这里作者用了亿点点 $\LaTeX$,所以做的不好尽请见谅。 别问牌子为啥老是变，问就是作者感觉都好。 ### 注意事项： 屏幕前的谷友们，您**需要**： 1. 仔细观看。 1. 看完后点赞收藏。 1. 然后关闭界面。 您**不需要**： 1. 不点赞。 1. 不收藏。 1. 不关注作者。 1. 不让作者关注您。 好了，不说废话了，正文开始！ ## 正文： ### 1. P1601 A+B Problem(高精) 难度：$\textcolor{orange}{普及-}

题目

题目内容：

高精度加法，相当于 a+b problem。

注意：不用考虑负数。

题目解法：

高精度题的解法一般就是模拟一个竖式来算。但是因为会炸 long long 的原因，所以我们要用 char 数组储存。

但是如 999+1 这种算式是要进位的，而且个,十,百位上的数字都会显示为零。

众所周知要是用数组正序储存就会发生下标不够的情况，所以我们要倒序储存，输出时倒序输出就行了。

并且我们要对进位进行特判，也就是下面 jw 变量判断的东西了。

题目代码：

#include<iostream>
#include<cstring>
using namespace std;
char x[505],y[505];
int a[505],b[505],c[505];//a数组表示x,b数组表示y,c数组表示总数
int main(){
    cin>>x>>y;
    int la=strlen(x);
    int lb=strlen(y);  
  //把字符数组转换成整数类型，并倒序存储：
    for(int i=1;i<=la;i++) a[i]=x[la-i]-'0'; 
    for(int i=1;i<=lb;i++) b[i]=y[lb-i]-'0';
    int lc=max(la,lb);
    int jw=0;
    for(int i=1;i<=lc;i++){//判断进位
        c[i]=(a[i]+b[i]+jw)%10;
        jw=(a[i]+b[i]+jw)/10;
    } 
    if(jw==1) {//判断是否进位
        lc++;
        c[lc]=1;
    }
    for(int i=lc;i>=1;i--) cout<<c[i];//倒序输出
    return 0; 
}

2. P2142 高精度减法

难度：\textcolor{orange}{普及-}

题目

题目内容：

两个整数 a,b（第二个可能比第一个大）。

这就说明要考虑负数了。

题目解法：

高精度减法要考虑负数和借位，当然比高精度加法要烧脑些。

众所周知在减法中，如果减数比被减数小就会产生负数，所以我们在出现负数的情况时将两数交换相减，再加上负号即可。

借位的话只要来个特判就解决了。

其他的都跟高精度加法一样。

题目代码：

#include<iostream>
#include<cstring>
using namespace std;
char x[10088],y[10088];
int a[10088],b[10088],c[10088];
int main(){
    cin>>x>>y;
    int la=strlen(x);
    int lb=strlen(y);
    //比较两数，如果被除数比除数小就判为负数
    if(la<lb||(la==lb&&strcmp(x,y)<0)){
        cout<<'-';
        swap(x,y);
        swap(la,lb);
    } 
    for(int i=1;i<=la;i++) a[i]=x[la-i]-'0'; 
    for(int i=1;i<=lb;i++) b[i]=y[lb-i]-'0';
    //两数相减
    int lc=max(la,lb);
    for(int i=1;i<=lc;i++){
      //判断是否需要借位
        if(a[i]>=b[i]) c[i]=a[i]-b[i];
        else{
            a[i+1]--;
            c[i]=a[i]+10-b[i];
        }
    } 
    //去前导0
    while(c[lc]==0&&lc>1){ //防止差为零时把零全删去了
        lc--;
    }
    for(int i=lc;i>=1;i--) cout<<c[i];
    return 0; 
}

3.P1089 [NOIP2004 提高组] 津津的储蓄计划

难度：\textcolor{red}{入门}

题目

题目内容：

津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300 元钱，津津会预算这个月的花销，并且总能做到实际花销和预算的相同。

为了让津津学习如何储蓄，妈妈提出，津津可以随时把整百的钱存在她那里，到了年末她会加上 20\% 还给津津。因此津津制定了一个储蓄计划：每个月的月初，在得到妈妈给的零花钱后，如果她预计到这个月的月末手中还会有多于 100 元或恰好 100 元，她就会把整百的钱存在妈妈那里，剩余的钱留在自己手中。

津津发现这个储蓄计划的主要风险是，存在妈妈那里的钱在年末之前不能取出。有可能在某个月的月初，津津手中的钱加上这个月妈妈给的钱，不够这个月的原定预算。如果出现这种情况，津津将不得不在这个月省吃俭用，压缩预算。

现在请你根据 2004 年 1 月到 12 月每个月津津的预算，判断会不会出现这种情况。如果不会，计算到 2004 年年末，妈妈将津津平常存的钱加上 20\% 还给津津之后，津津手中会有多少钱。

题目解法：

此题无非就是循环判断输出的知识点。

循环，就是循环 12 个月。

判断，就是先判断是否出现了钱不够用，再判断津津手里的钱用不用存到妈妈那里去。

输出，不用说了吧。

题目代码：

#include<bits/stdc++.h>
using namespace std;
int f[15];
int main(){
  int a=0; //津津手里的钱
  double b=0; //津津存到妈妈那里的钱
  for(int i=1;i<=n;i++){
    cin>>f[i];
    a=a+300-f[i]; //妈妈给津津钱，津津减去预算
    if(a<0){
      cout<<-i;
      return 0;
    }
    else if(a>=100){
      b+=a/100*100; //有整百的就存到妈妈那里
      a=a%100; //存完了还剩多少
     }
  }
  a=b*(1+0.2); //年末妈妈给津津这些钱的120% 
  cout<<a;
  return 0;
}

4.P1093 [NOIP2007 普及组] 奖学金

难度：\textcolor{orange}{普及-}

题目

题目内容：

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

任务：先根据输入的 3 门课的成绩计算总分，然后按上述规则排序，最后按排名顺序输出前五名名学生的学号和总分。

注意，在前 5 名同学中，每个人的奖学金都不相同，因此，你必须严格按上述规则排序。

(有删改)

题目解法：

此题虽然是橙题，但是难度是比较简单的。

排序判断就可以把这个著名的大模拟题给搞定。

不过这个排序是不太一样的，它是先按总分从高到低排序，如果两个同学总分相同，再按语文成绩从高到低排序，如果两个同学总分和语文成绩都相同，那么规定学号小的同学排在前面。

判断非常的长，主要是判断总分和语文成绩的，所以在写判断时要注意别写错。

有些结构体狂热追求者就好说了：“怎么不用结构体？”

于是就：天空一声巨响，结构体闪亮登场！

当然，此题用结构体也不是不行，但是作者还是推荐大家用结构体的，因为结构体也有它自己的优势。

题目代码：

#include<iostream>
#include<cstdio>
using namespace std;
int a[305][5];
// a[][0]为学号，a[][1]为语文，a[][2]为数学，a[][3]为英语，a[][4]为总分 
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i][1]>>a[i][2]>>a[i][3];
        a[i][0]=i;//遍历学号
        a[i][4]=a[i][1]+a[i][2]+a[i][3];
    }
    //排序
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if(a[i][4]<a[j][4]||(a[i][4]==a[j][4]&&a[i][1]<a[j][1]||(a[i][4]==a[j][4]&&a[i][1]==a[j][1]&&a[i][0]>a[j][0]))){//判断总分和语文成绩
                for(int k=0;k<=4;k++) swap(a[i][k],a[j][k]);
            }
    for(int i=1;i<=5;i++)
        cout<<a[i][0]<<' '<<a[i][4]<<endl;
    return 0;
}

这是结构体代码：

#include<bits/stdc++.h>
using namespace std;
struct student{
    int xh;//学号
    int yw,sx,yy;//代表语文成绩，数学成绩，英语成绩
    int tot;//总分

};
student stu[1005]; //注：数组开小会RE
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        stu[i].xh=i;
        cin>>stu[i].yw>>stu[i].sx>>stu[i].yy;
        stu[i].tot=stu[i].yw+stu[i].sx+stu[i].yy;//现在看到的学生的总分
    }
  //排序
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(stu[i].tot<stu[j].tot||(stu[i].tot==stu[j].tot&&stu[i].yw<stu[j].yw)) swap(stu[i],stu[j]);    
        }
    } 
    for(int i=1;i<=5;i++){
        cout<<stu[i].xh<<' '<<stu[i].tot<<endl;
    }
    return 0;
}

5.P1042 [NOIP2003 普及组] 乒乓球

难度：\textcolor{orange}{普及-}

题目

题目内容：

作者的童鞋认为代码不是人写的。

国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革，以推动乒乓球运动在全球的普及。其中 11 分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白 11 分制和 21 分制对选手的不同影响。在开展他的研究之前，他首先需要对他多年比赛的统计数据进行一些分析，所以需要你的帮忙。

华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在 11 分制和 21 分制下，双方的比赛结果（截至记录末尾）。

比如现在有这么一份记录，（其中 W 表示华华获得一分，L 表示华华对手获得一分）：

WWWWWWWWWWWWWWWWWWWWWWLW

在 11 分制下，此时比赛的结果是华华第一局 11 比 0 获胜，第二局 11 比 0 获胜，正在进行第三局，当前比分 1 比 1。而在 21 分制下，此时比赛结果是华华第一局 11 比 0 获胜，正在进行第二局，比分 2 比 1。如果一局比赛刚开始，则此时比分为 0 比 0。直到分差大于或者等于 2，才一局结束。

(有删改)

题目解法：

对作者这位超级大蒟蒻来说，此题当然是比较恶心的。

但是此题实际上 并不 难，只需要对输入的内容进行统计就可以了。我们可以看见底下代码有一个数组 a，它是用来记录得分情况的，如果华华赢了就记 1，对手赢了记 0，读到 E 时就结束。

两种赛制的计算也是比较简单的，首先计分板上华华和对手都是 0 分,华华赢了W就加 1，反之L加 1。再判断是否达到了符合要求的分数，且分差足够，就输出得分，同时计分板清零开始下一局。

注：要记录他们一共打了几局，且最后要输出正在进行的比赛的得分。

题目代码：

#include<bits/stdc++.h> 
using namespace std;
int f[2] = {11,21}; //两种赛制分别的获胜得分
int a[25*2500+20], n=0;
int main(){
    char tmp;
    while(1){
        cin>>tmp;
        if(tmp=='E') break;
        else if(tmp=='W') a[n++]=1; //判断华华是否赢了
        else if(tmp=='L') a[n++]=0; //判断对手是否赢了
    }
    for(int i=0;i<2;i++){
        int w=0,l=0;
        for(int k=0;k<n;k++){
            w+=a[k];
            l+=(a[k]==0);
            if((max(w,l)>=f[i])&&abs(w-l) >= 2){ //判断是否达到了符合要求的分数，且分差足够
                cout<<w<<":"<<l<<endl;
                w=0;l=0; //计分板清零
            }
        }
        cout<<w<<":"<<l<<endl;
        cout<<endl;
    }
    return 0;
}

6.P5732 【深基5.习7】杨辉三角

难度：\textcolor{red}{入门}

题目

题目内容：

给出 n(n \le 20)，输出杨辉三角的前 n 行。

如果你不知道什么是杨辉三角，可以观察样例找找规律。

在这里作者大方地给出了样例：

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

题目解法：

作者认为这题不简单。

实际上输入循环相加就可以解决，但是代码容易写错。

先循环，计算 i 数是多少，再按照格式输出就可以了。

题目代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[20][20];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        a[i][1]=a[i][i]=1; //第一行一定是1
        for(int j=2;j<=i-1;j++){
            a[i][j]=a[i-1][j-1]+a[i-1][j];//此数为这个数的上一行和此数的左上方相加
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            printf("%d ",a[i][j]);
        cout<<endl;
    }
    return 0;
}

7.P2669 [NOIP2015 普及组] 金币

难度：\textcolor{red}{入门}

题目

题目内容：

国王将金币作为工资，发放给忠诚的骑士。第一天，骑士收到一枚金币；之后两天（第二天和第三天），每天收到两枚金币；之后三天（第四、五、六天），每天收到三枚金币；之后四天（第七、八、九、十天），每天收到四枚金币……；这种工资发放模式会一直这样延续下去：当连续 n 天每天收到 n 枚金币后，骑士会在之后的连续 n+1 天里，每天收到 n+1 枚金币。

请计算在前 k 天里，骑士一共获得了多少金币。

题目解法：

这题也太简单了。

只需要来个循环嵌套，一直循环到对应的天数，把金币都加进 ans 这个变量里就可以了。

题目代码:

#include<bits/stdc++.h>
using namespace std;
int day=0,ans,k;
int main(){
    cin>>k;
    for(int i=1;;i++){
        for(int j=1;j<=i;j++){//循环
            ans+=i;
            day=day+1;
            if(day==k){//循环至到达对应的天数
                cout<<ans<<endl;
                return 0;
            }
        }
    }
    return 0;
} 
//注:此题太水了所以没怎么加注释

8.P1553 数字反转（升级版）

难度：\textcolor{orange}{普及-}

题目

题目内容：

给定一个数，请将该数各个位上数字反转得到一个新数。

注：这个数可以是小数，分数，百分数，整数。

（有删改）

题目解法：

此题用作者推荐定义一个反转函数，可以适当减少代码量，非常不戳。

我们可以定义一个 void 类型的无返回值函数(底下代码的 rev)用来反转数字，并且进行去前导 0，去后导 0 的操作。

为什么要去前导 0 和后导 0 呢？

比如样例输入了个 000123000, 因为这个数不合理，所以要去前导 0，变成了 123000，反转后变成了 000123。但是众所周知 000123 也是不合理的所以又去前导 0，所以为了方便，就把前导 0 和后导 0 一起去了，还可以少写一个循环。

然后看看输入的数是整数，百分数还是小数分数，整数就直接反转，百分数就先不看百分号再反转，小数分数也反转再输出就 OK 了。

题目代码：

#include<bits/stdc++.h>
using namespace std;
char s[25];
void rev(int l,int r){//定义一个反转函数
    while(s[l]=='0'&&l<r) l++;//去前导0
    while(s[r]=='0'&&l<r) r--;//去后导0
    for(int i=r;i>=l;i--) cout<<s[i];
}
int main(){
    cin>>s+1;
    int len=strlen(s+1);
    int p=0;
    for(int i=1;i<=len;i++)
        if(s[i]<'0'||s[i]>'9') p=i;//判断P是否为字符
    if(p==0) rev(1,len); //整数 
    else if(p==len){
        rev(1,len-1);
        cout<<'%';
    }//百分数
    else {
        rev(1,p-1);
        cout<<s[p];
        rev(p+1,len);
    } //小数或分数
    return 0;
}

9.P1217 [USACO1.5] 回文质数 Prime Palindromes

难度：\textcolor{orange}{普及-}

题目

题目内容：

因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。

写一个程序来找出范围 [a,b](5 \le a < b \le 100,000,000)（一亿）间的所有回文质数。

注：如果你还不知道啥是回文质数，那就看看作者 抄来 的回文质数吧：

5
7
11
101
131
151
181
191
313
353
373
383
......

题目解法：

作者强力推荐用函数！

既然是回文质数，那就定义两个函数，一个判断是否是素数，一个判断是否是回文数，再做个循环判断调用函数三件套就可以判断出这个数是不是回文质数了，代码也瞬间变简单了。

但是大家在看底下代码时可能会疑惑：为什么要写这两行呢：

if(b>=10000000) b=9999999;
if(a%2==0) a=a+1;

众所周知，位数为偶数的回文质数只有 11 ，而一亿虽然是九位数，但它自己就不是回文质数，所以我们只需要遍历到七位数 9999999 就可以了，还可以减少TLE的概率。

第二行的话众所周知既是偶数又是质数的数只有 2，但是数据又提示最小为 5，所以就不必要再多算一遍输入的偶数了。

题目代码：

#include<iostream>
using namespace std;
//函数s:判断一个数是否为素数
bool s(int x){
    if(x<=1) return false;
    if(x==2) return true;
    for(int i=2;i*i<=x;i++)//i*i<=x 也可以写成 i<=sqrt(x)
        if(x%i==0) return false;
    return true;
} 
//函数h:判断一个数是否为回文数
bool h(int x) {
    int y=0;
    int t=x;
    while(t){
        y=y*10+t%10;
        t=t/10;
    }
    if(x==y) return true;
    else return false;
}
int main(){
    int a,b;
    cin>>a>>b;
    if(b>=10000000) b=9999999;//只需遍历到七位数 9999999
    if(a%2==0) a=a+1;//不必要在多算一个偶数
    for(int i=a;i<=b;i+=2)
        if(h(i)&&s(i)) cout<<i<<endl;       
    return 0;
}

10.B2104 矩阵加法

难度：\textcolor{red}{入门}

题目

题目内容：

输入两个 n 行 m 列的矩阵 A 和 B，输出它们的和 A+B，矩阵加法的规则是两个矩阵中对应位置的值进行加和，具体参照样例。

样例：

输入：

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

输出：

2 4 6
5 7 9
8 10 12

题目解法：

好简单的题哦！

只需要循环输入，循环相加再循环输出就可以了。

但是有一点要注意，A 数组和 B 数组一定要是一样的，并且最后一定要加换行符！！！

（不要问为什么）

看着题解区大家都写这个那我也写个吧：

C_{i,j} = A_{i,j} + B_{i,j}

但是我们这里为了节省空间，就把 C 数组和 A 数组共用了一下，避免不必要的MLE。

其实本来就不会 MLE，所以大家可以放心地开个 C 数组。

题目代码：

#include<bits/stdc++.h>
using namespace std;
int a[105][105];
int b[105][105];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];//输入
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>b[i][j];
            a[i][j]+=b[i][j];//相加
        }       
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<a[i][j]<<' ';//输出
        cout<<endl;//要加换行符！！！
    }
    return 0;
}//这种水题很适合蒟蒻们去切

里程碑：10篇！

11.B2105 矩阵乘法

难度：\textcolor{orange}{普及-}

题目

题目内容：

计算两个矩阵的乘法。n \times m 阶的矩阵 A 乘以 m \times k 阶的矩阵 B 得到的矩阵 C 是 m \times k 阶的，且C[i][j]=A[i][0] × B[0][j] + A[i][1]×B[1][j]+ ......+A[i][m−1]×B[m−1][j] （C[i][j] 表示 C 矩阵中第 i 行第 j 列元素）。

题目解法：

难度高了，但是难不倒本蒟蒻。

首先矩阵乘法也有前提条件，就是 a 的列数和 b 的行数必须相同。

作者认为此题有枚举的思想，所以枚举闪亮登场：

我是先枚举 c 的每一行和 a 的每一行，再枚举的 c 的每一列，b 的每一列，还有 a_i 的每一列，b_j 的每一行再相乘的，这样就差不多能看懂了。

注意换行！！！

题目代码：

#include<iostream>
using namespace std;
int a[105][105];
int b[105][105];
int c[105][105];
int main(){
    int n,k,m;
    cin>>n>>k>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++)
            cin>>a[i][j];
    for(int i=1;i<=k;i++)
        for(int j=1;j<=m;j++)
            cin>>b[i][j];   
    for(int i=1;i<=n;i++)//枚举c的每一行 a的每一行 
        for(int j=1;j<=m;j++)//枚举的c的每一列 b的每一列 
            for(int l=1;l<=k;l++)//a[i]的每一列 b[j]的每一行 
                c[i][j]+=a[i][l]*b[l][j];//将新矩阵的每一个点都看作计数器来计算           
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
            cout<<c[i][j]<<' ';
        cout<<endl;
    }
    return 0;
}

12.P1055 [NOIP2008 普及组] ISBN 号码

难度：\textcolor{orange}{普及-}

题目

题目内容：

每一本正式出版的图书都有一个 ISBN 号码与之对应，ISBN 码包括 9 位数字、1 位识别码和 3 位分隔符，其规定格式如 x-xxx-xxxxx-x，其中符号 - 就是分隔符（键盘上的减号），最后一位是识别码，例如 0-670-82162-4 就是一个标准的 ISBN 码。ISBN 码的首位数字表示书籍的出版语言，例如 0 代表英语；第一个分隔符 - 之后的三位数字代表出版社，例如 670 代表维京出版社；第二个分隔符后的五位数字代表该书在该出版社的编号；最后一位为识别码。

识别码的计算方法如下：

首位数字乘以 1 加上次位数字乘以 2......以此类推，用所得的结果 \mod 11 ，所得的余数即为识别码，如果余数为 10，则识别码为大写字母 X。例如 ISBN 号码 0-670-82162-4 中的识别码 4 是这样得到的：对 067082162 这 9 个数字，从左至右，分别乘以 1,2,...,9 再求和，即 0×1+6×2+……+2×9=158，然后取 158 \mod 11 的结果 4 作为识别码。

你的任务是编写程序判断输入的 ISBN 号码中识别码是否正确，如果正确，则仅输出 Right；如果错误，则输出你认为是正确的 ISBN 号码。

题目解法：

这道题简直就不能被称为橙题！

做这个题有这几个步骤：

  1. 输入。

  2. 定义变量 ins，代表 ISBN 号码加起来。

  3. 把 ins\mod 11，得出正确的识别码。

  4. 判断识别码是否正确，正确就输出Right，否则输出正确的 ISBN 号码。

然后就没了，就是这么简单。

题目代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c,d,e,f,g,h,i,j;
    scanf("%c-%c%c%c-%c%c%c%c%c-%c",&a,&b,&c,&d,&e,&f,&g,&h,&i,&j);
    int ins=(a-'0')*1+(b-'0')*2+(c-'0')*3+(d-'0')*4+(e-'0')*5+(f-'0')*6+(g-'0')*7+(h-'0')*8+(i-'0')*9;//把ISBN 号码都加起来
    ins=ins%11;//进行模运算
    if((ins==j-'0')||(ins==10&&j=='X')) cout<<"Right";
    else printf("%c-%c%c%c-%c%c%c%c%c-%c",a,b,c,d,e,f,g,h,i,ins==10?'X':ins+'0');//用了三目运算符来判断是否正确
    return 0;
}

13.P1002 [NOIP2002 普及组] 过河卒

难度：\textcolor{orange}{普及-}

题目

题目内容：

棋盘上 A 点有一个过河卒，需要走到目标 B 点。卒行走的规则：可以向下,或者向右。同时在棋盘上 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 棋盘用坐标表示， A 点 (0,0)，B 点 (n,m)，同样马的位置坐标是需要给出的。

图：

作者太蒻了，弄不出图来，你还是看这里吧。

----> P1002 [NOIP2002 普及组] 过河卒

现在要求你计算出卒从 A 点能够到达 B 点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。

题目解法：

你考虑时可以先把马给屏蔽。

这是一道很显然的 DP 题。我们得知道马能控制的点都是哪，然后再标记，当发现有马能控制的点时就绕过去。

然后再判断一下如果小卒走到了马能控制的点上，就直接跳过去。

这里还有个递推公式：

dp[i][j]=dp[i-1][j]+dp[i][j-1]

题目代码：

#include<bits/stdc++.h>
bool f[105][105];
int dx[]={0,2,1,-1,-2,-2,-1,1,2};
int dy[]={0,1,2,2,1,-1,-2,-2,-1};
//这里是马能控制的八个点
long long dp[105][105];//十年OI一场空，不开 long long 见祖宗
using namespace std;
int main(){
    int n,m,x1,y2;
    cin>>n>>m>>x1>>y2;
    for(int i=0;i<=8;i++){//标记马能控制的坐标
        int ii=x1+dx[i];
        int jj=x2+dy[i];
        if(ii>=0&&ii<=n&&jj>=0&&jj<=m)f[ii][jj]=1;
    }
    dp[0][0]=1;//在起点的话方案数只有一个
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++){
            if(i==0&&j==0)continue;
            if(f[i][j]==0){//判断坐标是否没被标记
                if(i==0)dp[i][j]=dp[i][j-1];
                else if(j==0)dp[i][j]=dp[i-1][j];
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
    cout<<dp[n][m]<<endl;
    return 0;
}

14.P1080 [NOIP2012 提高组] 国王游戏

难度：\textcolor{green}{普及+/提高}

题目

题目内容：

蒟蒻做出的第一道绿题！（庆祝）

恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

题目解法：

这题又是贪心又是高精度的，对我这位超级大蒟蒻来说，超纲了。

我们需要定义一个结构体，在结构体内定义大臣左手上的数和右手上的数。

这里我们用函数来搞这个高精度会简单一些。所以要在函数里写高精，注意不要写错。高精在这里就不说了。详细请看注释。

接着我们要用贪心来判断怎样才能让大臣得到的金币最少，所以我们要使用 sort 进行排序，要使用 cmp 自定义排序函数。接着求出最优的方案即可。

虽说这是道绿题（作者一看就没思路的那种），可是最终的解法倒不多。代码长的原因主要还是高精度。

去了高精度就成橙题了。

题目代码：

#include<bits/stdc++.h>
using namespace std;
int n;//大臣总数 
struct node{
    int l,r;
};
node a[10005];
bool cmp(node i,node j){//比较i大臣和j大臣的顺序 
    //同时乘上i.r*j.r
    return max(j.r,i.l*i.r) <max(i.r,j.l*j.r);
}
int s[4500],t[4500],ans[4500];
//s:积 t:商 ans:最大值 
int Len=4005; //字符数组的长度 
void c1(int d){//高精度*int 
    for(int i=1;i<=Len;i++) s[i]*=d;
    for(int i=1;i<=Len;i++){
        s[i+1]+=s[i]/10;//进位 
        s[i]=s[i]%10;//保留个位 
    }
}
void c2(int d){//高精度/int 
    memset(t,0,sizeof(t));
    int r=0;
    for(int i=Len;i>=1;i--){
        r=r*10+s[i];
        t[i]=r/d;//借位
        r=r%d;
    }
}
bool f(){
    for(int i=Len;i>=1;i--){
        if(t[i]>ans[i]) return true;
        if(t[i]<ans[i]) return false;
    }
    return false;
}
void cpy(){
    for(int i=1;i<=Len;i++) ans[i]=t[i];
}
void p(){
    //去前导0 
    while(ans[Len]==0&&Len>1) Len--;
    for(int i=Len;i>=1;i--) cout<<ans[i];
}
int main(){
    cin>>n;
    //p[0]=国王 
    for(int i=0;i<=n;i++) cin>>a[i].l>>a[i].r;
    sort(a+1,a+n+1,cmp);
    //枚举每个大臣获得的奖励并且找到获得最大的奖励 
    s[1]=1;
    for(int i=1;i<=n;i++){
        c1(a[i-1].l);//高精度乘法 
        c2(a[i].r);//高精度除法 
        if(f()) cpy();//高精度赋值 
    } 
    p();//高精度输出 
    return 0;
}

15.P2249 【深基13.例1】查找

难度：\textcolor{orange}{普及-}

题目

题目内容：

输入 n 个不超过 10^9 的单调不减的（就是后面的数字不小于前面的数字）非负整数 a_1,a_2,...,a_n ，然后进行 m 次询问。对于每次询问，给出一个整数 q，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出 −1 。

题目解法：

这次是九点整。

这道题主要要用二分的算法。

二分查找是一个很方便的查找方法。二分查找，就是在一个数列中找中间的数（假设它是 mid），如果正好是要找的数，那就结束；如果这个数大了，就去找 1 到 mid - 1 之间的数，反之就去找 mid + 1 到结尾之间的数，直到找到为止。

这道题有多种解法。蒟蒻作者当然想的是暴力枚举。如果你不幸使用了暴力枚举，那你就喜提 TLE 了。

所以我们给他改成了二分算法。用了 for 循环和 while 循环，首先遍历 m（查询次数），然后再找到答案。但是这题是求最前面的数的地址，所以我们要先保存答案，再向左区间找，直到找到了为止。

第二种就是递归函数了。在这里我们定义了一个 binsearch 递归函数，但是这里我们调用函数时不能直接调用，需要用一下 cout 才可以。

第三种就是使用二分自带（现有）的函数了。众所周知，C++ 是非常良心的，给了我们三个二分自带函数：

在这个代码中我们就可以使用 lower_bound() 这个函数，在原来代码的基础上改一改就可以 AC，亿分好用。

这个写的的确是有那么亿点点多了。

题目代码：

第一种代码（循环）：

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[10000050];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];//有序的
    for(int i=1;i<=m;i++){
        int k;
        cin>>k;
        int l=1;
        int r=n;
        int ans=-1;//没找到就是-1 
        while(l<=r){
            int mid=l+(r-l)/2;
            if(a[mid]==k){//mid不一定是第一个出现的 
                ans=mid;
                r=mid-1;//先保存答案，再向左区间找 
            }
            if(a[mid]>k) r=mid-1;//如果a[mid]比这个数大了右区间就改为mid-1 
            if(a[mid]<k) l=mid+1;//如果a[mid]比这个数小了左区间就改为mid+1 
        } 
        cout<<ans<<" "; 
    }
    return 0;
}

第二种代码（递归函数）：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int a[10000005];
int ans; 
int binsearch(int l,int r,int k){
    int mid=l+(r-l)/2;
    if(l>r) return ans;
    if(a[mid]==k){
        ans=mid;
        return binsearch(l,mid-1,k);
    }
    if(a[mid]<k) return binsearch(mid+1,r,k);
    if(a[mid]>k) return binsearch(l,mid-1,k);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];//有序的
    for(int i=1;i<=m;i++){
        int k;
        cin>>k;
        ans=-1;//初始化ans 
        cout<<binsearch(1,n,k)<<" ";
    }

    return 0;
}

第三种代码（二分自带函数）：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int a[10000005];
int ans; 
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];//有序的
    for(int i=1;i<=m;i++){
        int k;
        cin>>k;
        int p=lower_bound(a+1,a+n+1,k)-a;//因为返回的是迭代器所以要减a
        if(a[p]==k) cout<<p<<" ";
        else cout<<-1<<" ";
    }

    return 0;
}

16.P2240 【深基12.例1】部分背包问题

难度：\textcolor{orange}{普及-}

题目

题目内容：

阿里巴巴走进了装满宝藏的藏宝洞。藏宝洞里面有 N(N \le 100) 堆金币，第 i 堆金币的总重量和总价值分别是 m_i,v_i(1 \le m_i,v_i \le 100)。阿里巴巴有一个承重量为 T(T \le 1000) 的背包，但并不一定有办法将全部的金币都装进去。他想装走尽可能多价值的金币。所有金币都可以随意分割，分割完的金币重量价值比（也就是单位价格）不变。请问阿里巴巴最多可以拿走多少价值的金币？

题目解法：

北京时间，十点整。

这题看似是个背包问题，实际上是个贪心。

首先我们把金币按照性价比来从高到低排序，接着再依次遍历，判断。如果背包内有足够多的空间，就可以全部抢走。就可以从最贵的开始拿，直到装不下。

题目代码：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int g,v;//分别表示重量和价值
}a[150];
int read(){//运用一下快读
    int x=0,f=1;
    char s=getchar();
    while(s<'0'||s>'9'){
        if(s=='-'){
            f=-1;
        }
        s=getchar();
    }
    while(s>='0'&&s<='9'){
        x=x*10+s-'0';
        s=getchar();
    }
    return x*f;
}
bool cmp(node as,node b){//自定义函数cmp，表示要按性价比从大到小排序。
    return as.v*b.g>as.g*b.v;
}
double ans=0;
int main(){
    int n=read();
    int m=read();
    for(int i=1;i<=n;i++){
        a[i].g=read();
        a[i].v=read();
    }
    sort(a+1,a+n+1,cmp);//排序
    for(int i=1;i<=n;i++){//如果有足够多的空间就全拿走
        if(a[i].g<=m){
            ans+=a[i].v;
            m-=a[i].g;
        } 
        else {//没有足够多的空间就尽量拿走性价比高的
            ans+=a[i].v*m*1.0/(a[i].g*1.0);
            break;//退出循环
        }
    }
    printf("%.2lf",ans);
    return 0;
}

17.P1226 【模板】快速幂：

难度：\textcolor{orange}{普及-}

题目

题目内容：

给你三个整数 a,b,p，求 a^b \bmod p。

题目解法：

所谓的快速幂是个啥呢？

作者告诉你：就是快速计算幂次。（我蒙的）。

首先看看这道题的数据范围：保证 0\le a,b < 2^{31}，a+b>0，2 \leq p \lt 2^{31}。

那么我们就可以得出一个结论：a^b 会爆 long long。

那么我们就可以得出一个公式(假设 b = 3)：

a^b \bmod p=(a \bmod p + a \bmod p + a \bmod p) \bmod p

所以我们就可以用函数来解决这个问题。也是很简单的。

题目代码：

#include<bits/stdc++.h>
using namespace std;
int a,b,p;
long long qmi(int a,int b,int p){
    if(b==0) return 1%p;
    if(b==1) return a%p;
    long long ans=qmi(a,b/2,p);
    ans=ans*ans%p;
    if(b%2) ans=ans*a%p;
    return ans%p;
}
int main(){
    cin>>a>>b>>p;
    printf("%d^%d mod %d=%d",a,b,p,qmi(a,b,p));
    return 0;
}

18.P1449 后缀表达式：

难度：\textcolor{orange}{普及-}

题目

题目内容：

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

本题中运算符仅包含 \texttt{+-*/}。保证对于 \texttt{/} 运算除数不为 0。特别地，其中 \texttt{/} 运算的结果需要向 0 取整（即与 C++ / 运算的规则一致）。

如：\texttt{3*(5-2)+7} 对应的后缀表达式为：\texttt{3.5.2.-*7.+@}。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。

题目解法：

这道题呢我们要用到‘栈’这个东西。

所谓“栈”，就相当于一个（怎么说呢？）类似管子或者小桶的东西，也就是一个单向的东西，元素要进，出都只能从一段进或出，所以栈也被称为“先进后出表”。可以看图：

抄的图片就是好用。

but：作者不是那么会用栈（以后会学会用的），所以作者用数组来模拟了一下栈。

题目代码：

#include<bits/stdc++.h>
using namespace std;
int st[55];
int top;//栈顶 
int main(){
    char ch;
    while((ch=getchar())&&ch!='@'){//赋值的优先级很低 
        if(ch>='0'&&ch<='9'){
            //把数字字符转换成整数
            int num=0;
            while(ch>='0'&&ch<='9') {
                num=num*10+ch-'0';
                ch=getchar();
            }
            st[++top]=num;
        }
        else if(ch=='.') continue;
        else{
            //把st[top-1]和st[top]进行运算
            //结果存在st[top-1]里
            if(ch=='+') st[top-1]=st[top-1]+st[top];
            else if(ch=='-') st[top-1]=st[top-1]-st[top];
            else if(ch=='*') st[top-1]=st[top-1]*st[top];
            else st[top-1]=st[top-1]/st[top];
            top--;//减少了一个数 
        }
    }
    cout<<st[1]; 
    return 0;

}

19.P1102 A-B 数对

难度：\textcolor{orange}{普及-}

题目

题目内容：

给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A - B = C 的数对的个数（不同位置的数字一样的数对算不同的数对）。

题目解法：

首先，我们想到的就是：枚举 A ，那么 B 就是 A-C 。所以我们只要找到与 A-C 相同的数就可以了。

But 暴力会 T！（#3#4#5 TLE，76 pts）。

所以我们需要用较快的方法——二分。这种思想其实就是二分找 B 而已。

这题我扣了三个月终于是听课听出来了...

题目代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[10005];
int c;
long long ans=0;
int main(){
    cin>>n>>c;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){//枚举A=a[i]，找B(B=A-C=a[i]-c) 
        //找第一个B 
        int p=lower_bound(a+1,a+n+1,a[i]-c)-a;
        //找最后一个B 
        int q=upper_bound(a+1,a+n+1,a[i]-c)-a;//不用减一，因为如果减一后面还要加回来 
        ans+=q-p;
    }
    cout<<ans<<endl;
    return 0;
}

日常复制粘贴是一个很好的习惯


### 20.
难度：$\textcolor{}{}$

[题目](https://www.luogu.com.cn/problem/)

#### 题目内容：
#### 题目解法：
#### 题目代码：