西北工业大学 NOJ 2023 程序设计基础（C++）完结撒花（已停止维护）

极其感谢TA的帮助，所以下面是，爱门！

2023西工大NOJ (C语言版) 完结！！！-CSDN博客

前言

对于瓜的学生来说，noj是选了实验课之后必做的作业，占20%的分数；

但希望不要为了功利的目的写noj，理由如下：

1.编程永远是实践的过程，真正的知识只有自己打出来才能获得；更别说瓜的教材比较老，和新的C++标准有不少出入，尤其是习题册。

2.实验课也就1学分，不挂就行，你为了这点绩点功利啥。

3.瓜的实验课考试为随机抽题，最后答成什么样子主要看脸，你再功利也没啥用。

对于noj，自2023年秋开始启用新题，可以说，难度大幅提升。但质量存在极大参差，（◎_◎;）；

C的NOJ教程有很多，但是C++的这可能还是第一篇，希望对有需要的人能有所帮助;

希望是有参考、引导的作用，帮助同学能更加高效地学习C++;

必看

对于代码

本人初学者，能力有限，有幸获得一位大佬很多帮助；

如若代码粗陋，请谅解；

因为本人水平实在有限，部分代码来自各个大佬，如不希望转载，可以联系我删除；

尽量使用较新的C++17标准，而不是教材和习题册上的包浆标准（食答辩了）；

代码当然是尽可能AC的，但是由于noj的评阅比较雾，有的完全正确的也是WA，可以试试其他version，要是都不能我也没办法，饶了我罢；

代码格式

每题的代码，前两行会是难度，重要性评估，然后是该程序的一些注意点。

然后会是1+个版本，最后输入输出样例。（多版本时，后续的版本为了可读性不会注释掉，复制的时候注意）

考虑到做题方便，我会给出额外样例，以供同学检验自己的程序。

同时，考虑到中文复制之后会产生字符集问题，所以程序内部注释为纯英文（Chiglish）。

建议

1.学C++，就不要觉得自己只学C++，C的很多操作也得会。很多人C++学到最后，scanf()和printf()都不会。

NOJ攻略

1.写noj必须具有的意识：考虑极端情况，题目肯定是尽可能的恶心（划掉），考验你啦.

2.noj提交后的各种状态：

pending ：处理中，重新刷新或者重新点击NOJ作业有概率得到结果；

如果一直pending，大概率是noj服务器又崩了罢（不是你的锅）；

等服务器好了之后，可以在提交的程序上打一个空行再提交。

AC ：你醒啦，恭喜你，你已经是个女孩子了（幻视，划掉）；恭喜你，这道题通过了。

WA ：程序错误，不能在输入后台样例的情况下得到正确结果。

TE ：超时，也就是你的程序运行时间太长；

noj有的题目对时间卡的很紧，出现这种情况说明你又没动脑子 : (

解决方法很简单，抛弃你的暴力算法，用好的算法好好优化一下你的程序。

（注：对于noj来说，有的时候你的程序其实是TE，却给你显示WA，别给我犟，叉腰.jpg）

CE ：编译错误。

如果你想：我本地运行的好好的，为什么提交上去就CE呢，不是可以编译吗？

一般有两种原因：

1.头文件写漏了，本地没毛病是因为正常编译器会给你自动添加部分头

文件，而noj的编译器就像薛定谔的猫，没人知道jxf到底塞的什么。

（经典用cpp的string类不加<string>,加<cstring>）

2.孔乙己，你是不是又用了什么STL特性？

什么？你说C++如果不用STL，和C有什么区别？

可是我们noj的编译器似乎不能完全支持STL捏（有时这种情况报WA）

3.代码输出：

有人发现，很多一次输入很多组数据的题目，我提供的代码不能输出对应的样例，凭什么说能AC？

这和noj后台的评阅机制有关，你别管了，长篇大论懒得扯，反正能，就是能；（叉腰.jpg）

(实际上很多程序你直接复制粘贴我给的Input，然后敲个回车，输出会有问题，但是你自己一个数据一个数据地敲，或者分行粘贴，每行回车就好了)；

良好的编程习惯

下面是我的编程习惯（我是菜鸡，大佬轻点骂）

第一部分：预处理命令，#include,#define等

空一行

第二部分： using namespace std；

空一行

第三部分：各类函数，彼此空行

空一行

第四部分：主函数 int main()

下面是示例

合理的空行和缩进不仅美观，还可以有效提升程序可读性！

#include <iostream>using namespace std;void fun(){    }int main() {    return 0;//new C++ standard can ignore this}

夹带私货

关于电脑相关的外设，建议整一个机械键盘（一定要有素质，买线性静音轴，比如水蜜桃V2）；

更重要的是，整个无线鼠标，尤其是带两个侧键的，比如罗技G304,一个侧键定义Ctrl+C,一个定义Ctrl+V，这会极大提升你的编程体验！

如果想买一个外接显示器的话（可以显著提升电脑使用体验），建议买23.8寸左右的，27寸你瓜宿舍桌面真塞的下，但是太大了，观感很不好。最重要的是分辨率至少2k，刷新率75hz就够用，色准要好，基础HDR要有，要是支持Type-C一线连接就更好啦。（我滴SANC N50PLUS 3代完美符合捏）在这之后就可以买个侧立支架把笔记本合上了，（如果你不是很追求双屏体验，双屏瓜的桌子也不怎么塞得下吧）。（十分建议显示器在京东上买）

对了，显示器最好搭配支架使用，NB f80就挺好的，便宜好用质量好。（为了应对挡板，可以搭配某宝定制小实木木块使用）

免责声明：看了私货部分，决定要买什么是自己的事，自己的决定，在下的话只是建议，仅供参考，不负责任，请自己思考判断自己是否需要，以及是否自愿承担相应风险。

声明

note只会在前几季有，用于引导新手，才不是因为懒呢；

前四季题目提供 Description , Input, Output ;（也许未入学的xdx可以看一看？）

但是放心，后面的难题，或者复杂的题一般都会带注释，甚至可能中文注释；

后期会逐渐添加题目截图，有的可能不含Sample Input和Sample Output部分，但是代码最后肯定有；

如果Additional Input和Additional Output 是NULL，说明这题没必要搞额外样例，或者是太麻烦，我已经懒死了；（要是实在想要额外样例，拿我的代码随便跑几个不就行了）

有的题目，我说无人AC，是基于我的认知，可能有真的大佬，可能题目又被修改过了，反正是我这个小垃圾肯定AC不了酱紫；

严正声明：该篇Blog仅作引导作用，绝不鼓励抄袭，若因其他用途产生不良后果与本人无关。

总结

2023年秋-2024年春的C++ noj 一共100道，应该是最多AC97道的亚子；

其中

042.【专业融合：航空】飞机起飞速度

057.字符串替换

074.【专业融合：天文】日出日落时间

三道不能AC;

距离首次发布已过去1年，该blog预计不会继续维护，存在的问题大概修复完了（吧？），完结撒花！?

所以如果有任何相关问题建议评论区留言，等待好心人经过，为你解答。（博主包指望不上的?）

第1季（001-010）

001.Hello World

Description
第一个C/C++作业，写一个Hello World吧。
Input
没有。
Output
输出Hello World，注意大小写及空格(最后换行无所谓)。

//Difficulty: 0/10//Importance:10/10//The place our dream begin!//What you need://a good coding style(tab,enter,naming...)//clear coding logics#include <iostream>using namespace std;int main(){    cout << "Hello World"<<endl;//printf("hello world\n");    return 0;}//tip:no "!" here/*Sample input:nullSample output:Hello World*//*Additional input:nullAdditional output:Hello World*/

002.A+B

Description
编写一个程序，输出A+B的结果。
Input
在一行中输入整型A和B，用空格间隔。
Output
输出A+B的值。

//Difficulty: 0/10//Importance: 0/10#include <iostream>using namespace std;int main(){    int A, B;    cin >> A >> B ;    cout <<A+B<<endl;    return 0;}/*Sample input:3 4Sample output:7*//*Additional input:5 6Additional output:11*/

003.数据类型大小及范围

Description
每一个C/C++整型，都有一个内存大小和数值范围。例如:int，内存大小为4，数值范围为(-2147483648,2147483647)。如下表，输入选择d，输出对应数据类型的大小及范围。
Input
输入整数d。
Output
输出对应数据类型的内存大小及数值范围(最小值、最大值)，用逗号间隔。

d	输出类型	d	输出类型
1	char	2	unsigned char
3	short	4	unsigned short
5	int	6	unsigned int
7	long	8	unsigned long
9	long long	10	unsigned long long

note：

1.sizeof()函数的学习；

2.<climits>的基本运用。

//Difficulty: 1/10//Importance: 1/10//make use of <climits> (<limits.h>) to get min and max sizes//sizeof(),return memory size(bit)#include <iostream>#include <climits>using namespace std;int main(){    int n;    cin >> n;    switch (n) {        case 1: cout << sizeof(char) << "," << CHAR_MIN << "," << CHAR_MAX; break;        case 2: cout << sizeof(unsigned char) << "," << 0<< "," << UCHAR_MAX; break;        case 3: cout << sizeof(short) << "," << SHRT_MIN << "," << SHRT_MAX; break;        case 4: cout << sizeof(unsigned short) << "," << 0<< "," << USHRT_MAX; break;        case 5: cout << sizeof(int) << "," << INT_MIN << "," << INT_MAX; break;        case 6: cout << sizeof(unsigned int) << "," << 0<< "," << UINT_MAX; break;        case 7: cout << sizeof(long) << "," << LONG_MIN << "," << LONG_MAX; break;        case 8: cout << sizeof(unsigned long) << "," << 0 << "," << ULONG_MAX; break;        case 9: cout << sizeof(long long) << "," << LLONG_MIN << "," << LLONG_MAX; break;        case 10: cout << sizeof(unsigned long long) << "," << 0 << "," << ULLONG_MAX; break;    }    return 0;}/*Sample input:5Sample output:4,-2147483648,2147483647*//*Additional input:1Additional output:1,-128,127*/

004.平均值

Description
编写一个程序，输出整数A、B的平均值。
Input
在一行中输入整型A和B，用空格间隔。
Output
输出整数A、B的整型平均值。

note：

1.数据容量“溢出”的概念；

2.基础位运算；

a>>i 为：将二进制数据a右移i位，即a/(2^i);

a<<i 为：将二进制数据a左移i位，即a*(2^i);

3.注：C++ 中int类型除法，正数向下取整（即floor（）），负数向上取整（即ceil（））

eg: 1/2=0; -1/2=0;

4.因此version 2 需要保证A>B才能实现一直使用向下取整，或者人为添加floor();(A=B不用考虑)

5.swap()函数用于交换两个变量的值，基于指针实现，不仅限于int类型；（无需头文件，C++内置）

//Difficulty: 3/10//Importance:10/10//Note that the data range corresponding to the type//may be exceeded during the calculation,//resulting in overflow//version 1:Bitwise operations(better)#include <iostream>using namespace std;int main(){    int A, B;    cin >>A >>B;    int avg = ((A - B) >> 1) + B;    cout<<avg;    return 0;}//version 2:Split#include <iostream>using namespace std;int main(){    int A, B;    cin >>A >>B;    if(A<B) swap(A,B);  //or：{int t=B;B=A;A=t;}    int avg = (A - B)/2 + B;    cout<<avg;       return 0;}/*Sample input:3 4Sample output:3*//*Additional input:5 6Additional output:5*/

005.进制转换

Description
输入一个非负整数，输出它的十六进制，八进制。
Input
输入一个非负整数。
Output
在一行里输出十六进制、八进制，用逗号间隔。十六进制A~F大写。

note：

1.printf()的基础运用（数字输出）：

%d ：即为dec，十进制；

%o ：即为oct，八进制；

%x ：即为hex，十六进制（小写）；

%X ：即为hex，十六进制（大写）；

2.cout与格式输入输出库<iomanip>基础：

对于cout，默认输出dec，每次使用hex等修改时，此后均为hex，除非重新修改。

在<iomanip>中：

uppercase ：十六进制格式字母变大写

showpos ：在正数前显示+号

showbase ：十六进制前显示 0x，八进制前显示0

boolalpha ：逻辑值1和0用ture和false 输出

left ：输出内容靠左

right ：输出内容靠右

scientific ：科学记数法

showpoint ：即使小数后面都是0，也输出小数点。

//Difficulty: 2/10//Importance:10/10//make use of C's good features//printf() is very useful when you need special outputs//version 1:printf(recommended)#include<iostream>using namespace std;int main(){    int a;    cin >> a;    printf("%X,%o",a,a);    return 0;}//version 2:cout#include <iostream>#include <iomanip> using namespace std; int main(){    int a;    cin>>a;    cout<<setiosflags(ios::uppercase)<<hex<<x<<endl;}/*Sample input:10Sample output:A,12*//*Additional input:12Additional output:C,14*/

006.浮点数输出

Description
输出一个浮点数的3个格式结果。
Input
输入一个浮点数。
Output
输出1行，第1个小数点保留6位，第2个小数点保留2位，第3个小数点保留8位，用逗号作为间隔。

note:

1:在cin或cout中指明数制后，该数制将一直有效，直到重新指明使用其他数制。

2:为什么很多时候我喜欢用printf：不用头文件，使用简洁方便。

//Difficulty: 1/10//Importance:10/10//version 1: printf(recommended)#include<iostream>using namespace std;int main(){    double a;    cin >> a;    printf("%.6f,%.2f,%.8f",a,a,a);     return 0; }//version 2: cout#include<iostream>#include<iomanip>using namespace std;int main(){    double a;    cin >> a;    cout <<fixed<< setprecision(6) << a << "," << fixed <<setprecision(2) << a << "," << fixed <<setprecision(8) << a << endl;    //or: cout <<fixed<< setprecision(6) << a << "," << setprecision(2) << a << "," << setprecision(8) << a << endl;    return 0;}/*Sample input:12345567.891234567Sample output:12345567.891235,12345567.89,12345567.89123457*//*Additional input:3.141592654Additional output:3.141593,3.14,3.14159265*/

007.动态宽度输出

Description
输出n位宽的m，若n超出m的实际宽度，则左边填充0。
Input
输入整数m和n，用空格间隔。
Output
输出指定格式结果。

note：

1.cout、iomanip和printf各有各的好，要灵活使用；

2.setw()和setfill()的先后顺序无所谓。

//Difficulty: 1/10//Importance:10/10#include <iostream>#include <iomanip>using namespace std;int main(){    int m, n;    cin >> m >> n;    cout << setw(n) << setfill('0') << m << endl;    return 0;}/*Sample input:123 5Sample output:00123*//*Additional input:123 7Additional output:0000123*/

008.计算地球上两点之间的距离

Description
依据Haversine公式。对于任何球面上的两点，圆心角的半正矢值可以通过hav(d/r)公式计算，其中hav(0)是半正矢函数，d是两点之间的距离，r是地球半径(6371km)，φ1和中2是点1的纬度和点2的纬度，以弧度为单位，入1和入2是点1的经度和点2的经宴，以弧度为单位。如下:
$hav\left ( \frac{d}{r} \right )= hav\left ( \varphi _{1}-\varphi _{2}\right )+cos\left ( \varphi _{1} \right )cos\left ( \varphi _{2} \right )hav\left ( \lambda _{1}-\lambda_{2}\right )$

$hav\left ( \theta \right )=sin^{^{2}}\left ( \frac{\theta }{2} \right )=\frac{1-cos\left ( \theta \right )}{2}$
Input
输入2行数据，每行数据是点的纬度和经度，用空格间隔。例如西安(34.260958，108.942369)，莫斯科(55.755825，37.617298)。
Output
输出两点的距离，单位是km，小数点保留4位。

note：

1.使用宏#define的时候注意最后加不加分号；宏是简单的符号替换；

2.变量名写的时候最好可以代表具体意义，不要脸滚键盘；

//Difficulty: 2/10//Importance: 2/10#include<iostream>#include<cmath>#include<iomanip>#define pi 3.141592654using namespace std;double hav(double x) {    double result = (1 - cos(x)) * 0.5;    return result;}double trans(double e) {    double m;    m = (e / 180) * pi;    return m;}int main(){    double x1, y1, x2, y2,s,m,d;    cin >> x1 >> y1;    cin >> x2 >> y2;    x1 = trans(x1), y1 = trans(y1), x2 = trans(x2), y2 = trans(y2);    s = hav(x2 - x1) + cos(x1) * cos(x2) * hav(y2 - y1);    m = acos(1 - 2*s);    d = m * 6371;    cout <<fixed<<setprecision(4)<< d <<"km"<< endl;}/*Sample input:34.260958 108.94236955.755825 37.617298Sample output:5793.2236km*//*Additional input:24.260958 105.94236945.755825 31.617298Additional output:6917.5743km*/

009.风寒指数

Description
已知风速和空气温度计算寒意指数。公式如下：

$Wind Chill =13.12+0.6215T_{a}-11.37v^{+0.16}+0.3965T_{a}v^{+0.16}$

Input
在一行中输入风速(公里/小时)、空气温度(摄氏温度)，用空格间隔。
Output
输出寒意指数(四舍五入整数)。

note：

<cmath>库基础：

1.pow()函数：

原型double pow(double x, double y);

求x的y次方，注意参数与返回值均为double类型，因此有时搭配取整函数食用更佳；

2.三个取整函数：

double floor(doube x); floor为地板的意思，所以是向下取整；

double ceil(doube x); ceiling为天花板的意思，所以是向上取整；

double round(doube x); round为左右、四周的意思，所以是四舍五入；

//Difficulty: 2/10//Importance: 2/10#include<iostream>#include<cmath>using namespace std;int main(){    double  v, t;    double chilldegree;    cin >> v >> t;    double a = pow(v, 0.16);    chilldegree = 13.12 + 0.6215 * t - 11.37 * a+ 0.3965* t * a;    chilldegree = round(chilldegree);    cout << chilldegree;}/*Sample input:120 35Sample output:40*//*Additional input:66 39Additional output:45*/

010.颜色模型转换

Description
RGB是一种颜色空间，R是红色分量，C是绿色分量，B是蓝色分量。RGB是图像处理中最基本、最常用、面向硬件的颜色空间，适合于显示系统，却并不适合于图像处理。HSV是另一种颜色空间，H是色调，S是饱和度，V是明度，它比RGB更接近人们对彩色的感知经验，方便进行颜色的对比。RGB转换成HSV的算法如下图，其中R,G,B $\epsilon$ [0，1]。

Input
在一行中输入R、G、B的字节值，范围为[0，255]，用空格间隔。
Output
输出为H，S%，V%，用逗号间隔，保留4位小数。

note：

1.注意逻辑顺序，考虑极端情况；

2.涉及浮点数精度问题，当判断一个浮点数x是否为0，应使用 x-0<1e-9等类似方式；

//Difficulty: 3/10//Importance: 3/10//given types of float,double have precision problem//(a - b < 1e-9) is used to judge whether it is 0#include<iostream>#include<iomanip>using namespace std;int main() {    int R, G, B;    cin >> R >> G >> B;    double r, g, b, h, s, v;    double MAX, MIN, d;    r = R / 255.0;    g = G / 255.0;    b = B / 255.0;    MAX = max(r,max(g,b) );    MIN = min(r,min(g,b));    d = MAX - MIN;    v = MAX;    if (MAX - 0 < 1e-9) {        s = 0;    }    else {        s = d / MAX;    }    if (d - 0 < 1e-9) {        h = 0;    }    else {        s = d / MAX;        if (MAX - r < 1e-9) {            h = 60 * ((g - b) / d);        }        else if (MAX - g < 1e-9) {            h = 60 * (2 + (b - r) / d);        }        else if (MAX - b < 1e-9) {            h = 60 * (4 + (r - g) / d);        }        if (h - 0 < 1e-9) {            h = h + 360;        }    }    cout << fixed << setprecision(4) << h << ","    << fixed << setprecision(4) << s * 100 << "%,"    << fixed << setprecision(4) << v * 100 << "%";}/*Sample input:0 215 0Sample output:120.0000,100.0000%,84.3137%*//*Additional input:0 0 0Additional output:0.0000,0.0000%,0.0000%*//*Additional input:255 255 255Additional output:0.0000,0.0000%,100.0000%*//*Additional input:123 54 45Additional output:6.9231,63.4146%,48.2353%*/

第2季（011-020）

011.乘数模

Description
已知三个正整数a、b、m , 求 a*b mod m （1≤a，b，m≤ $10^{18}$ ） mod表示求余运算。
Input
在一行里输入三个正整数a、b、m，用空格间隔。
Output
输出计算结果。

note：

1.依旧是溢出问题，程序里运用数学工具解决；

2.涉及一些数论知识：

模的乘法性质：对于任意整数a、b和n，有(a * b) mod n = (（a mod n） *（ b mod n）) mod n；

3.用了上面一条性质，可以优化程序，有效缩减运行时间，防止TE；

//Difficulty: 2/10//Importance:10/10//learn some formulas for mod//to prevent exceeding and TE#include <iostream>using namespace std;int main(){    unsigned long long a, b, m, r;    cin >> a >> b >> m;    r = ((a % m) * (b % m)) % m;    cout << r;}/*Sample input:123 456 100000Sample output:56088 *//*Additional input:1244 12567 5758Additional output:378*/

012.方阵

Description
编写程序，生成一个n阶正方形矩阵，其中0位于主对角线，1位于主对角线上方和下方的位置中，2位于更上方和下方，等等，依次类推。如下图所示。
Input
输入正整数n。
Output
输出指定要求的方阵。

n等于5时：

0	1	2	3	4
1	0	1	2	3
2	1	0	1	2
3	2	1	0	1
4	3	2	1	0

note:

1.小小的数学转化罢了；

2.这里用abs()只是方便熟悉<cmath>库，三目运算更简便，abs()为绝对值函数；

3.有的老师讲三目运算符的时候不太强调，简单说一下：

假设有表达式a，b，c；那么三目运算符

a ? b : c ; 代表 a为真，得到b；a为假，得到c；

//Difficulty: 2/10//Importance: 4/10//discover some wonderful functions in cmath!#include <iostream>#include <cmath>using namespace std;void generatematrix(int n) {    for (int i = 1; i <= n; i++) {        for (int j = 1; j <= n; j++) {            int v = abs(i - j);//or : int v = (i-j)>0 ? i-j : j-i ;            cout << v << "  ";        }        cout << endl;    }}int main(){    int m;    cin >> m;    generatematrix(m);}/*Sample input:5Sample output:0  1  2  3  41  0  1  2  32  1  0  1  23  2  1  0  14  3  2  1  0*//*Additional input:2Additional output:0  11  0*/

013.组合数

Description
有a，b，c和d(0≤a，b，c，d≤9)四个数，求(a+b+c+d)等于n的组合数。
Input
输入n，1≤n≤50。
Output
输出组合数。

note：

1.关于 while，if，for等循环语句的格式：

当循环内只有一个语句时，可以不加{ }；

至于空行和缩进，都不影响编译器的扫描；

但是建议一句时，循环内语句直接写在 while，if，for后面，不要随便换行，保证优秀的可阅读性；

理论上，你把所有语句全换成逗号间隔，那算起来只有一句，也不用{ }；你最好不要这么干，考虑逗号表达式和可读性；分号该加就加，换行该打就打，要有美感。

多语句使用{ }时，建议 while，if，for后面跟 { 空一行之后，与 while，if，for的开头对齐，打 } （这是大部分主流编程软件的自动格式，然鹅破破又烂烂的CodeBlocks，根本不会给自动格式，导致有的人写的程序不忍直视）

//Difficulty: 2/10//Importance: 2/10//simple enum#include <iostream>using namespace std;int main() {    int a,b,c,d,n,sum=0;    cin>>n;    for (a=0;a<=9;++a){        for(b=0;b<=9;++b){            for(c=0;c<=9;++c){                for(d=0;d<=9;++d){                    if (n==a+b+c+d) sum++;                    else sum=sum+0;                }            }        }    }    cout<<sum;}/*Sample input:15Sample output:592*//*Additional input:37Additional output:0*/

014.比率

Description
编写一个程序将浮点数转换为比率。
Input
输入一个浮点数。
Output
输出它对应的比率(按最简分数形式)。

note：

1.gcd，为求最大公因数的算法，也称辗转相除法，非常有用，必须记忆；作为函数时，可以进行递归调用；

2.floor函数前面 009.风寒指数的note已经介绍过；

//Difficulty: 3/10//Importance:10/10//memorize gcd!#include <iostream>#include <cmath>using namespace std;int gcd(int a,int b){    if(b==0){return a;}    return gcd(b,a%b);}int main(){    double fz;    int fm=1,m;    cin>>fz;    for(fz;fz!=floor(fz);fz=fz*10,fm=fm*10);    m=gcd((int)(fz),fm);    fz=fz/m;    fm=fm/m;    cout<<fz<<"/"<<fm;}/*Sample input:4.2Sample output:21/5*//*Additional input:3.33333Additional output:333333/100000*/

015.分数的加、减、乘、除法

Description
输入两个分数，计算它们的加、减、乘、除。
Input
输入为2行，每行分别是分数的分子和分母，采用分数形式(参考输入样例)。输入的数据保证运算结果合理。
Output
输出为4行，分别是两个分数的加、减、乘、除式子和结果，用最简分数形式表示。

note：

1.相信你肯定为函数如何带回多个数据发愁，这涉及参数传递的概念，然鹅很可能还没讲到这；

2.解决方法（此处仅列出两个）

数组带回：数组作为函数参数时，传入的是数组地址，因而函数内对数组的修改可以保存下来；

tuple元组：在C++中，元组(tuple)是一种用于组合多个不同类型的值的数据结构。元组可以将不同类型的数据打包在一起，类似于一个容器，可以按照索引顺序访问其中的元素。

把函数的返回类型设置成元组tuple，即可返回含有多个数据的tuple;

3.非常实用的C语言函数一例：

getchar()函数，用于从缓冲区得到一个字符；

在这个程序里用来去掉不想要的符号‘/’ ，然而在各种程序里，getchar()也可以用来使你的console控制台（没错就是那个大黑框）在程序运行到最后的时候保持显示，直至你有输入（只需在程序的最后加上一行getchar();）

当你获得的字符对你没有作用，你就可以直接写getchar();而不需要定义一个变量，把getchar()赋进去；

//Difficulty: 3/10//Importance: 3/10//I don't think tuple necessary//you can use point to replace//more acceptable way is using Global variables//plus,getchar() is very useful//version 1:use array to pass values(recommended)#include <iostream>using namespace std;int gcd(int x,int y){    if(y==0)return x;    else return gcd(y,x%y);}void add(int fz1,int fm1,int fz2,int fm2,int arr[4][2]){    int nfz,nfm,d;    nfz=fz1*fm2+fz2*fm1;    nfm=fm1*fm2;    d=gcd(nfz,nfm);    nfz=nfz/d;    nfm=nfm/d;    arr[0][0]=nfz;    arr[0][1]=nfm;}void sub(int fz1,int fm1,int fz2,int fm2,int arr[4][2]){    int nfz,nfm,d;    nfz=fz1*fm2-fz2*fm1;    nfm=fm1*fm2;    d=gcd(nfz,nfm);    nfz=nfz/d;    nfm=nfm/d;    arr[1][0]=nfz;    arr[1][1]=nfm;}void multi(int fz1,int fm1,int fz2,int fm2,int arr[4][2]){    int nfz,nfm,d;    nfz=fz1*fz2;    nfm=fm1*fm2;    d=gcd(nfz,nfm);    nfz=nfz/d;    nfm=nfm/d;    arr[2][0]=nfz;    arr[2][1]=nfm;}void divi(int fz1,int fm1,int fz2,int fm2,int arr[4][2]){    int nfz,nfm,d;    nfz=fz1*fm2;    nfm=fm1*fz2;    d=gcd(nfz,nfm);    nfz=nfz/d;    nfm=nfm/d;    arr[3][0]=nfz;    arr[3][1]=nfm;}int main() {    int fz1,fm1,fz2,fm2;    cin>>fz1;    getchar();    cin>>fm1;    cin>>fz2;    getchar();    cin>>fm2;    int arr[4][2];    add(fz1,fm1,fz2,fm2,arr);    sub(fz1,fm1,fz2,fm2,arr);    multi(fz1,fm1,fz2,fm2,arr);    divi(fz1,fm1,fz2,fm2,arr);    char symbol[4]={'+','-','*','/'};    for(int i=0;i<4;++i){        cout<<'('<<fz1<<'/'<<fm1<<')'<<symbol[i]<<'('<<fz2<<'/'<<fm2<<')'            <<'='<<arr[i][0]<<'/'<<arr[i][1]<<endl;    }    return 0;}//version 2:use tuple#include <iostream>#include <tuple>using namespace std;int gcd(int x,int y){    if(y==0)return x;    else return gcd(y,x%y);}tuple<int,int> add(int fz1,int fm1,int fz2,int fm2){    int nfz,nfm,d;    nfz=fz1*fm2+fz2*fm1;    nfm=fm1*fm2;    d=gcd(nfz,nfm);    nfz=nfz/d;    nfm=nfm/d;    return make_tuple(nfz,nfm);}tuple<int,int> sub(int fz1,int fm1,int fz2,int fm2){    int nfz,nfm,d;    nfz=fz1*fm2-fz2*fm1;    nfm=fm1*fm2;    d=gcd(nfz,nfm);    nfz=nfz/d;    nfm=nfm/d;    return make_tuple(nfz,nfm);}tuple<int,int> multi(int fz1,int fm1,int fz2,int fm2){    int nfz,nfm,d;    nfz=fz1*fz2;    nfm=fm1*fm2;    d=gcd(nfz,nfm);    nfz=nfz/d;    nfm=nfm/d;    return make_tuple(nfz,nfm);}tuple<int,int> divi(int fz1,int fm1,int fz2,int fm2){    int nfz,nfm,d;    nfz=fz1*fm2;    nfm=fm1*fz2;    d=gcd(nfz,nfm);    nfz=nfz/d;    nfm=nfm/d;    return make_tuple(nfz,nfm);}int main() {    int fz1,fm1,fz2,fm2;    cin>>fz1;    getchar();    cin>>fm1;    cin>>fz2;    getchar();    cin>>fm2;    tuple<int,int> result0=add(fz1,fm1,fz2,fm2);    cout<<'('<<fz1<<'/'<<fm1<<')'<<'+'<<'('<<fz2<<'/'<<fm2<<')'    <<'='<<get<0>(result0)<<'/'<<get<1>(result0)<<endl;    tuple<int,int> result1=sub(fz1,fm1,fz2,fm2);    cout<<'('<<fz1<<'/'<<fm1<<')'<<'-'<<'('<<fz2<<'/'<<fm2<<')'    <<'='<<get<0>(result1)<<'/'<<get<1>(result1)<<endl;    tuple<int,int> result2=multi(fz1,fm1,fz2,fm2);    cout<<'('<<fz1<<'/'<<fm1<<')'<<'*'<<'('<<fz2<<'/'<<fm2<<')'    <<'='<<get<0>(result2)<<'/'<<get<1>(result2)<<endl;    tuple<int,int> result3=divi(fz1,fm1,fz2,fm2);    cout<<'('<<fz1<<'/'<<fm1<<')'<<'/'<<'('<<fz2<<'/'<<fm2<<')'    <<'='<<get<0>(result3)<<'/'<<get<1>(result3)<<endl;}/*Sample input:2/33/7Sample output:(2/3)+(3/7)=23/21(2/3)-(3/7)=5/21(2/3)*(3/7)=2/7(2/3)/(3/7)=14/9*//*Additional input:1/21/2Additional output:(1/2)+(1/2)=1/1(1/2)-(1/2)=0/1(1/2)*(1/2)=1/4(1/2)/(1/2)=1/1*/

016.幂数模

Description
已知三个正整数a、b、m，求 $a^{b}\: \: mod\, \, \, m$ , 1≤ a,b,m≤ $2^{63}$ , mod表示求余运算。
Input
在一行里输入三个正整数a、b、m，用空格间隔。
Output
输出计算结果。

note：

1.常用的一个位运算：a&1

当a（默认dec）为奇数，a&1得到1（真）；a为偶数，a&1得到0（假）；

因而用来快速判断数的奇偶性；

2.对 typedef unsigned long long(或者long long) ll;的操作是常见的编程实践；

3.同样运用了模的乘法性质来优化，防止TE;

//Difficulty: 3/10//Importance: 10/10//learn fast mod algorithm!//you can use Bitwise operations//but fast mod is better#include<iostream>typedef unsigned long long ll;using namespace std;int main(){    ll a,b,m,ans=1;    cin>>a>>b>>m;    while(b){        if(b&1){            ans=(ans*a)%m;        }        a=(a*a)%m;        b>>=1;    }    cout<<ans;}/*Sample input:2 10 9Sample output:7*//*Additional input:2 63 1314Additional output:512*/

017.对称数

Description
一个对称数是指该数字经过360度旋转以后，依然是该数字。如916->916。编写程序判断一个数是否是对称数。
Input
输入一个整数n。
Output
如果是对称数输出Yes，否则输出No。

note：

1.使用C++更多的特性；

2.<unordered_map> 无序关联容器和map一样，十分好用；

3.迭代器，掌握.begin() .end() .rbegin() .rend()

迭代器在遍历等应用时非常常见且好用；一般命名为it，使用auto自动类型；

//Difficulty: 5/10//Importance: 5/10//there must be longer,but stupider ways//why not take C++'s unique advantages?//such as map/unordered_map,iterator(which is easier to use)#include<iostream>#include<string>#include<unordered_map>using namespace std;int main(){    string ori,inver;    cin>>ori;    unordered_map<char,char> table{{'0','0'},{'1','1'},{'6','9'},{'9','6'},{'8','8'}};    for(auto it=ori.rbegin();it!=ori.rend();++it){        inver.push_back(table[*it]);}// or: inver+=table[*it];    if(inver==ori)cout<<"Yes";    else cout<<"No";}/*Sample input:916Sample output:Yes*//*Additional input:1000081800001Additional output:Yes*/

018.操作数

Description
任意一个整数n，每次操作用n减去它的各位数字之和，直到n小于等于0，统计操作的次数。例如21， 21-3=18-9=9-9=0，所以操作数为3。
Input
输入正数n。
Output
输出操作次数。

note：

1.理清楚逻辑就行；

//Difficulty: 3/10//Importance: 3/10//version 1: no func#include<iostream>using namespace std;int main(){    int n,n1,d,sum,k;    cin>>n;    sum=0;    n1=n;    for(k=0;n1>0;++k){        while(n>0){            d=n%10;            sum+=d;            n=n/10;        }        n1-=sum;        n=n1;        sum=0;    }    cout<<k;}//version 2: func#include<iostream> int sumPerDig(int n){    int sum = 0;    while(n){        sum += n%10;        n /= 10;    }    return sum; } int main(){    int n,cnt=0;    cin>>n;     while(n){        n -= sumPerDig(n);        ++cnt;    }     cout<<cnt;     return 0;}/*Sample input:21Sample output:3*//*Additional input:164Additional output:17*/

019.倍数和

Description
小于10的自然数中，3或5的倍数有3、5、6和9，这些数之和是23。求小于n的自然数中所有3或5的倍数之和。
Input
第一行输入整数T，表示接下来有T行数据需要处理。接下来的T行，每行输入一个正整数n(称为一个测试用例)。T和n的范围如下：1≤T≤ $10^{5}$ ， 1≤N≤ $10^{9}$
Output
对于每一个测试用例，输出倍数之和，一行一个。

note：

1.没啥东西，简单的枚举；

//Difficulty: 3/10//Importance: 3/10#include<iostream>using namespace std;int main(){    int T;    cin>>T;    int num[T];    for(int i=0;i<T;++i){        int n;        cin>>n;        int sum=0;        for(int j=1;j<n;j++){            if (j%3==0||j%5==0){                sum+=j;            }        }        num[i]=sum;    }    for(int k=0;k<T;++k){        cout<<num[k]<<endl;    }}/*Sample input:210100Sample output:232318*//*Additional input:25415115Additional output:683106102195*/

020.级数和

Description
编写程序来计算n项级数:1.2+2.3+3.4+4.5+5.6+......的和
Input
输入n(在1到99之间)。
Output
输出计算结果。

note：

1.没啥东西，注意一下输出的格式就行；

2.关于wid()函数

返回int类型的位数，简单，常用，某种程度上，最好有肌肉记忆；

//Difficulty: 2/10//Importance: 2/10#include<iostream>using namespace std;int wid(int n){    int i=0;    if(n==0)return 1;    else{        while(n){            n=n/10;            i++;        }        return i;    }}double decimal(double n){    int w;    w=wid(n);    for(int i=0;i<w;++i){        n=n/10.0;    }    return n;}int main(){    int n;    cin>>n;    int z[n];    for(int i=0;i<n;++i){        z[i]=i+1;    }    int x[n];    for(int j=0;j<n;++j){        x[j]=j+2;    }    double sum=0.0,s;    for(int k=0;k<n;++k){        s=(double)z[k]+decimal((double)x[k]);        sum+=s;    }    cout<<z[0]+decimal(x[0]);    for(int k=0;k<n-1;++k){        cout<<'+'<<z[k+1]+decimal((double)x[k+1]);    }    cout<<'='<<sum;}/*Sample input:10Sample output:1.2+2.3+3.4+4.5+5.6+6.7+7.8+8.9+9.1+10.11=59.61*//*Additional input:5Additional output:1.2+2.3+3.4+4.5+5.6=17*/

第3季（021-030）

021.竖式乘法

Description
输入两个整数，输出它们的竖式乘法的结果。如下图。
Input
在一行里输入2个整数a、b，用空格间隔，输入数据保证有意义。
Output
输出a*b的竖式乘法，参见输出样例。注意乘号x、加号+的位置，算式隔行用减号“-”制作。

//Difficulty: 2/10//Importance: 2/10//You can use setfill('?') before setw(n) to control//the character used for filling setw (default is space).#include <iostream>#include <iomanip>using namespace std;int wid(int n){    int i=0;    if(n==0)return 1;    else{        while(n){            n=n/10;            i++;        }        return i;    }}int main() {    int a,b,b0,i=0,ans,n,n0;    cin>>a>>b;    int z[wid(b)];    b0=b;    while(b0>0){        int c=b0%10;        z[i]=c*a;        b0=b0/10;        ++i;    }    ans=a*b;    n=wid(ans);    n0=n;    cout<<setw(n+1)<<a<<endl<<'x'<<setw(n)<<b<<endl;    for(int j=0;j<n+1;++j){        cout<<'-';    }cout<<endl;    for(int j=0;j<wid(b)-1;++j){        cout<<setw(n0+1)<<z[j]<<endl;        n0=n0-1;    }    cout<<'+'<<z[wid(b)-1]<<endl;    for(int j=0;j<n+1;++j){        cout<<'-';    }    cout<<endl<<setw(n+1)<<ans;}/*Sample input:12345 120Sample output:   12345x    120--------       0  24690+12345-------- 1481400*//*Additional input:12479 9347Additional output:     12479x     9347----------     87353    49916   37437+112311---------- 116641213*/

022.查找数列

Description
有一个数列1、1、2、1、2、3、1、2、3、4、1、2、3、4、5.…..其规律是:首先是数字1，然后是1到2，然后是1到3，依此类推。求这个数列中第n个数字。
Input
输入整数n。
Output
输出数列中第n个数字。

note:

1.此处使用元组tuple传参，也可以使用数组（更推荐）。

2.实际上是子数列问题，先数学上化简问题。

//Difficulty: 2/10//Importance: 2/10#include<iostream>#include<tuple>using namespace std;tuple<int,int> sum(int n){    int i=1,k;    while(((i*(i+1))/2)<n){        ++i;    }    i=i-1;    k=(i*(i+1))/2;    return make_tuple(i+1,k);}int main(){    int n,k;    cin>>n;    tuple<int,int> result=sum(n);    int a[get<0>(result)];    for(int j=0;j<get<0>(result);++j){        a[j]=j+1;    }    k=get<1>(result);    cout<<a[n-k-1];}/*Sample input:14Sample output:4*//*Additional input:45Additional output:9*/

023.毕达哥拉斯三元组

Description
毕达哥拉斯三元组由三个自然数a<b<c组成，满足 $a^{2}+b^{2}=c^{2}$ ；
有一个特殊三元组还满足a+b+c=n，求它的abc乘积。
Input
输入n。
Output
输出三元组的乘积。

note:

1.通过数学的不等式以及几何关系，尽量缩小穷举范围，实现高效。

//Difficulty: 1/10//Importance: 1/10#include<iostream>using namespace std;int main(){    int n,a,b,c;    cin>>n;    for(a=0;a<n/4;a++){        for(b=n/4+1;b>n/4&&b<n/2;b++){            c=n-a-b;            if(a*a+b*b==c*c&&c>b){                cout<<a*b*c;            }        }    }}/*Sample input:1000Sample output:31875000*//*Additional input:42360Additional output:1101603584441138216*/

024.余数和

Description
给定正整数n和k，计算 $G\left ( n,k \right )=\sum_{i=1}^{n}\left ( k \, \, mod\, \, i\right )$ 其中k mod i表示k除以i的余数。
Input
在一行里输入2个整数n、k，用空格间隔。
Output
输出G函数的结果。

//Difficulty: 1/10//Importance: 1/10#include<iostream>using namespace std;int main(){    int n,k,s,sum=0;    cin>>n>>k;    for(int i=0;i<n;++i){        s=k%(i+1);        sum+=s;    }    cout<<sum;}/*Sample input:10 5Sample output:29*//*Additional input:45 2Additional output:86*/

025.最大数字

Description
给定一个正整数N，找到一个最大的数字，使这个数字小于或等于N，且该数字的顺序不递减。
Inpute
输入N。
Output
输出找到的数字。

note:

1."不递减"即每相邻两位数字，左边≤右边。

//Difficulty: 2/10//Importance: 2/10#include<iostream>using namespace std;int wid(int n){    int i=0;    if(n==0)return 1;    else{        while(n){            n=n/10;            i++;        }        return i;    }}int main(){    int n,m,m0,f,l,w;    cin>>n;    m=n;    m0=m;    for(;m0>=0;--m0){        int sum=0;        m=m0;        w=wid(m);        for(int i=0;i<w-1;++i){            l=m%10;            m=m/10;            f=m%10;            if (f<=l) sum++;        }        if (sum==w-1){            cout<<m0;            break;        }    }}/*Sample input:200Sample output:199*//*Additional input:246545Additional output:245999*/

026.倒水

Description
有两个杯子，容积分别是m升和n升，其中0<m<n。两个杯子最初都是空的，且杯子上没有任何标记，无法进行测量。现在利用两个杯子操作得到d 升水，d<n，水源不限。求得到d升水所需要的最少操作次数。
可以执行的操作有:
(1)倒空一个杯子；
(2)装满一个杯子;
(3)将水从一个杯子倒入另一个杯子，直到其中一个杯子为空或满。
例如m=3、n=5、d=4时，可以有(括号为m升和n升的杯子状况)
倒法1:
(0,0)→(3,0)→(0,3)→(3,3)→(1,5)→(1,0)→(0,1)→(3,1)→(0,4)，需要执行操作次数是8. 倒法2:
(0,0)→(0,5)→(3,2)→(0,2)→(2,0)→(2,5)→(3,4)，需要执行操作次数是6.
因此，最少操作次数为6。
Input
在一行里输入3个整数m、n、d，用空格间隔。输入数据保证有意义。
Output
输出最少操作次数。

note：

1.很重要，对于真正想学好编程的人来说，而不是只为了那点学分对应的绩点；

2.非常经典的BFS（广度优先遍历）算法题，思路建议直接CSDN搜索C++倒水，好好了解；

//Difficulty: 5/10//Importance:10/10//a classic BFS#include <iostream>#include <queue>#include <set>#include <array>using namespace std;int main(){    int m,n,d;    cin>>m>>n>>d;    queue<array<int,2>> q;    set<array<int,2>>visited;    q.push({0,0});    visited.insert({0,0});    int minop=0;    while(!q.empty()){        int size=q.size();        for(int i=0;i<size;++i){            array<int,2> curr=q.front();            q.pop();            int x = curr[0];            int y = curr[1];            if (x == d || y == d) {                cout <<minop<<endl;                return 0;            }            array<int, 2> next;            //fill m            next = {m, y};            if (visited.find(next) == visited.end()) {                q.push(next);                visited.insert(next);            }            //fill n            next = {x, n};            if (visited.find(next) == visited.end()) {                q.push(next);                visited.insert(next);            }            //empty m            next={0,y};            if(visited.find(next)==visited.end()){                q.push(next);                visited.insert(next);            }            //empty n            next={x,0};            if(visited.find(next)==visited.end()){                q.push(next);                visited.insert(next);            }            //m to n            int pourAmount1 = std::min(x, n - y);            next = {x - pourAmount1, y + pourAmount1};            if (visited.find(next) == visited.end()) {                q.push(next);                visited.insert(next);            }            //n to m            int pourAmount2 = std::min(y, m-x);            next = {x + pourAmount2, y - pourAmount2};            if (visited.find(next) == visited.end()) {                q.push(next);                visited.insert(next);            }        }minop++;    }}/*Sample input:3 5 4Sample output:6*//*Additional input:5 9 7Additional output:12*//*Additional input:28 17 13Additional output:26*/

027.好数字

Description
一个数字字符串是由数字0到9组成的，其中可能包含前导零。如果在偶数位置上(第1个字符位置为0)是偶数，奇数位置上是素数(2、3、5或7)，则称该字符串是“好数字”。
例如，4562是好数字，因为它的偶数位置(4和6)是偶数，奇数位置(5和2)是素数。而3245不是好数字。
给定整数N，1≤N≤10^15，返回长度为N的好数字的总数。由于结果可能太大，以10^9+7为模。
Input
输入N。
Output
输出好数字的总数 mod 10^9+7。

//Difficulty: 3/10//Importance: 3/10//fastmod algorithm#include<iostream>typedef long long ll;using namespace std;ll fastmod(ll base,ll power){    ll m=1000000007,res=1;    while(power){        if(power&1){            res=(res*base)%m;        }        base=(base*base)%m;        power>>=1;    }    return res;}int main(){    ll n,evenCount,oddCount,ans,m=1000000007;    cin>>n;    evenCount=fastmod(5,(n+1)/2);    //each even point corresponds to 5 possibilities(5 even numbers:0,2,4,6,8)    //occurtimes=(n+1)/2    oddCount=fastmod(4,n/2);    //each odd point corresponds to 4 possibilities(4 prime numbers:2,3,5,7)    //occurtimes=n/2    ans=(evenCount*oddCount)%m;    cout<<ans;}/*Sample input:1Sample output:5*//*Additional input:4Additional output:400*/

028.俄罗斯农夫算法

Description
俄罗斯农夫乘法具体是:在纸上，左边写下被乘数，右边写下乘数;被乘数的下方写下被乘数反复除二(且无条件舍去小数)的结果，乘数下方写上乘数反复乘二的结果，一直到被乘数那一栏为1为止。将乘数那一列的数字相加，若被乘数那一列为偶数，则跳过此数不累加。所得结果即为乘法的结果。如下图所示。

Input
在一行里输入2个整数a、b，用空格间隔。输入数据保证有意义。
Output
输出农夫乘法的过程，被乘数和乘数列用空格间隔，最后一行输出累加结果。参见输出样例。

//Difficulty: 2/10//Importance: 2/10#include<iostream>using namespace std;int main(){    int a,b,sum=0;    cin>>a>>b;    while(a>0) {        cout << a << ' ' << b<<endl;        if (a&1) {            sum += b;        }        a /= 2;        b *= 2;    }    cout<<sum;}/*Sample input:11 3Sample output:11 35 62 121 2433*//*Additional input:54 67Additional output:54 6727 13413 2686 5363 10721 21443618*/

029.阶乘倍数

Description
已知K是一个大于或等于2的整数，求最小正整数N，使得N!是K的倍数。在问题约束条件下，可以证明这样的N总是存在的
Input
输入K。
Output
输出N。

note：

1.很重要；

2.二分查找+线性筛优化，防止TE;

//Difficulty: 5/10//Importance:10/10//TE warning!//use binary search and transformation//never simply use violent factorial(too slow)#include<iostream>#include<vector>using namespace std;bool check(long long mid, const vector<long long>& primes, const vector<long long>& powers) {    for (int i = 0; i < primes.size(); i++) {        long long cnt = 0, p = primes[i];        while (mid >= p) {            cnt += mid / p;            p *= primes[i];        }        if (cnt < powers[i]) {            return false;        }    }    return true;}int main() {    long long k;    cin >> k;    vector<long long> primes, powers;    for (long long i = 2; i * i <= k; i++) {        if (k % i == 0) {            long long cnt = 0;            while (k % i == 0) {                k /= i;                cnt++;            }            primes.push_back(i);            powers.push_back(cnt);        }    }    if (k > 1) {        primes.push_back(k);        powers.push_back(1);    }    long long left = 1, right = 1e18, ans = -1;    while (left <= right) {        long long mid = (left + right) / 2;        if (check(mid, primes, powers)) {            ans = mid;            right = mid - 1;        }        else {            left = mid + 1;        }    }    cout << ans << endl;}/*Sample input:30Sample output:5*//*Additional input:5195Additional output:1039*//*Additional input:1455Additional output:97*/

030.方案数

Description
给定一个数字N，把它展开成连续正整数之和的式子，求有多少种方案。例如N=9时，有9=4+5=2+3+4三种，其中N自身为一种。
Input
输入N。
Output
输出方案数。

//Difficulty: 2/10//Importance: 2/10#include<iostream>using namespace std;int main() {    int n, sum = 0;    cin >> n;    int m;    double a;    for (m = 1; m * m< 2 * n; ++m) {        a = (double)n / (double)m - (double)m * 0.5 + 0.5;        if (a - (int)a == 0) {            sum++;        }    }    cout << sum;}/*Sample input:9Sample output:3*//*Additional input:757Additional output:2*/

第4季（031-040）

031.素数

Description
素数(Prime number)又称质数，指在大于1的自然数中，除了1和该数外，无法被其他自然数整除的数。大于1的自然数若不是素数，则称之为合数。确认一个数n是否为素数有许多种方法，最基本的是试除法。
(1)从2至n-1逐一整除n判定。
(2)一个数如果不是素数，则一定能被一个小于它自己的数整除。假设一个数a能整除n，那么n/a也必定能整除n，不妨设 a≤n/a，则有a^2≤n，因此判定素数可以不用到n-1，而是根号n。
(3)一个大于1的整数如果不是素数，那么一定有素因子，因此在枚举时只需要考虑可能为素数的因子即可。可以枚举kn+i的数，例如取k=6，那么6n+2、6n+3、6n+4、6n+6都不可能为素数，因此我们只需要枚举6n+1、6n+5的数即可，这样整体的时间复杂度就会降低2/3，也就是立方根n。调整k值，可以进一步加快计算速度。
Input
输入整数a、b，用空格间隔。
Output
输出a和b之间(包含a和b)的素数个数。

note：

1.很重要；

2.线性筛最好要会，多看点B站介绍，CSDN文章，把它搞懂；

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <cstring>using namespace std;int primecount(int n){    bool isprime[n+1];    int prime[n+1];    int cnt=0;    memset(isprime,true,sizeof(isprime));    isprime[1]=false;    for(int i=2;i<=n;++i){        if(isprime[i]) prime[++cnt]=i;        for(int j=1;j<=cnt && i*prime[j]<=n;++j){            isprime[i*prime[j]]=false;            if(i%prime[j]==0) break;        }    }    return cnt;}int main() {    int a,b;    cin>>a>>b;    int cnt1=primecount(a-1);    int cnt2=primecount(b);    cout<<cnt2-cnt1;}/*Sample input:10 100Sample output:21*//*Additional input:19 41455Additional output:4329*/

032.基思数

Description
数学中，基思数(Keith number)又称Repfigit (REPetitive Flbonacci-like diGIT)数，它是一个用特定起始项的线性递推关系数列来定义的整数。假定有一个b进位制的n位数
$N=\sum_{i=0}^{n-1}b^{i}d_{i}$ 序列 $S_{N}$ 以 $d_{n-1},d_{n-2},......,d_{1},d_{0}$ 为初始项开始
每一项都由前面n项和产生，如果N出现在序列S中，那么N就是基思数。
是否存在无穷多个基思数仍然是个有待论证的问题，但10^19以下的基思数只有71个，比素数还稀有。
例如197，以十进制按照上面的方法建立一个序列:
1
9
7
1+9+7=17
9+7+17=33
7+17+33=57
17+33+57=107
33+57+107=197
因此197为基思数。
编写一个内联函数inline lsKeith(int N)，判断N是否为基思数，若是返回1，否则返回0。
Input
输入N(10≤N≤99999999)。
Output
调用lsKeith函数，如果是基思数输出Yes，否则输出No。

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <vector>#include<algorithm>using namespace std;inline bool IsKeith(int N){    int tmp=N;    vector<int>sequence;    while(tmp){        sequence.push_back(tmp%10);        tmp/=10;    }    reverse(sequence.begin(),sequence.end());    int num=sequence.size()-1;    int sum = 0;    while(sum<N){        sum=0;        for(int i=num;i>=0;--i){            sum+=sequence[i];        }        sequence.erase(sequence.begin());        sequence.push_back(sum);        if(sum==N) return true;    }    return false;}int main(){    int N;    cin>>N;    if(IsKeith(N)) cout<<"Yes"<<endl;    else cout<<"No"<<endl;}/*Sample input:197Sample output:Yes*//*Additional input:891Additional output:No*/

033.幂函数【C++】

Description
编写一个默认参数函数:
double pow(double base, int exp=2); 计算base的exp次幂。
Input
在一行里输入两个数base、exp，用空格间隔。
Output
第一行输出调用pow(base)的结果。
第二行输出调用pow(base,exp)的结果。

//Difficulty: 2/10//Importance: 2/10#include<iostream>#include<iomanip>using namespace std;double pow(double base,int exp=2){    double n=base;    for(;exp>1;--exp){        base*=n;    }    return base;}int main(){    double base;    int exp;    cin>>base>>exp;    cout<<fixed<<setprecision(6)<<pow(base)<<endl    <<fixed<<setprecision(6)<<pow(base,exp);}/*Sample input:1.23 5Sample output:1.5129002.815306*//*Additional input:1.01 365Additional output:1.02010037.783434*/

034.体积计算器【C++】

Description
NPU大作业要开发一个体积计算器，求几种常见形状的体积，如下图所示设计了它们的用户界面UI，输入相应的参数，单击“计算”按钮进行计算。
现在你负责开发体积计算器的算法部分(在专业软件开发中称为逻辑或业务部分)，采用C++函数重载技术，函数名称必须是VolCalc。这样，就可以用一个名称计算多种形状体积，其函数原型如下:
double VolCalc(double r); //球体
double VolCalc(double r,double h);                                //圆锥体
double VolCalc(long a); //立方体
double VolCalc(double r,long h), ; //圆柱体
double VolCalc(long l,long w,long h); //长方体
double VolCalc(double r,double R,double h); //球盖
double VolCalc(double r,double R,double h,double l); //胶囊
double VolCalc(long r,double R,double h);                    //圆锥体
double VolCalc(double a,double b,long c); //椭球体
double VolCalc(long a,long h);                                      //四棱锥
double VolCalc(long d1,long d2,double l);                    //管件

Input
在第一行里输入整数T，表示有T个测试用例。
在接下来的T行里，每行先是n，表示是什么形状，参考上图，接着是若干个参数，不同的n有不同数目的参数，而且参数的顺序由图中所列决定。中间用空格间隔。
Output
针对每行测试样例，输出相应形状的体积，每行一个。
需要注意:球盖和胶囊由于h计算的问题，体积是两个结果(h先计算加，再计算减)，中间用空格间隔。

note：

1.一切尽在注释中，好吧；

2.题目里的顺序都有问题，直接参考我的代码就行；

3.不喜欢else if ？可以用switch代替。

//Difficulty: 2/10//Importance: 2/10#include<iostream>#include<cmath>#include<tuple>#include<cstring>#include<iomanip>#define pi 3.1415926/*    pay attention!!! here noj define pi as 3.1415926    instead of 3.141592654(which is more precise),    you MUST define it exactly 3.1415926!!!*/using namespace std;/*  noj is likely to pay no attention to return type "double",    so don't add ".0" after the int data in your calculation either,    even actually this is important(obviously this is his fault,    clion would even give you warnings if you don't do so,    this make me thought: is noj using a rubbish compiler?)*/double v(double r){    return 4*pi*r*r*r/3;}double v(double r,double h){    return pi*r*r*h/3;}double v(long a){    return a*a*a/1;}double v(double r,long h){    return pi*r*r*h/1;}double v(long l,long w,long h){    return l*w*h;}/*    if you are careful enough,you may find that the     following two examples are in reverse order in     the stem and in the chart, this is also noj's mistake.*/tuple <double,double> v(double r,double R,double h){    double m=sqrt(R*R-r*r);    double v1,v2;    double h1=R+m;    v1=(pi/3.0)*(3.0*R-h1)*h1*h1;    double h2=R-m;    v2=(pi/3.0)*(3.0*R-h2)*h2*h2;    return make_tuple(v1,v2);}tuple <double,double> v(double r,double R,double h,double l){    double m=sqrt(R*R-r*r);    double v0,v1,v2;    v0=pi*r*r*l;    double h1=R+m;    v1=v0+(pi/3.0)*(3.0*R-h1)*h1*h1*2;    double h2=R-m;    v2=v0+(pi/3.0)*(3.0*R-h2)*h2*h2*2;    return make_tuple(v1,v2);}double v(long r,double R,double h){    return pi*h*(r*r+R*R+R*r)/3;}double v(double a,double b,long c){    return 4*pi*a*b*c/3;}double v(long a,long h){    return a*a*h/3;}double v(long d1,long d2,double l){    return pi*(d1*d1-d2*d2)*l/4;}int main(){    bool z[12];    memset(z, false, sizeof(z));    double s[12],six[2],seven[2];    int t;    cin>>t;    for(int i=0;i<t;++i) {        int n;        cin>>n;        z[n]=true;        if(n==1){            double r;            cin>>r;            s[n]=v(r);        }        else if(n==2){            double r,h;            cin>>r>>h;            s[n]=v(r,h);        }        else if(n==3){            long a;            cin>>a;            s[n]=v(a);        }        else if(n==4){            double r;            long h;            cin>>r>>h;            s[n]=v(r,h);        }        else if(n==5){            long l,w,h;            cin>>l>>w>>h;            s[n]=v(l,w,h);        }        else if(n==6){            double r,R,h=0,l;            cin>>r>>R>>l;            tuple <double,double>result=v(r,R,h,l);            six[0]=get<0>(result);            six[1]=get<1>(result);        }        else if(n==7){            double r,R,h=0;            cin>>r>>R;            tuple <double,double>result=v(r,R,h);            seven[0]=get<0>(result);            seven[1]=get<1>(result);        }        else if(n==8){            long r;            double R,h;            cin>>r>>R>>h;            s[n]=v(r,R,h);        }        else if(n==9){            double a,b;            long c;            cin>>a>>b>>c;            s[n]=v(a,b,c);        }        else if(n==10){            long a,h;            cin>>a>>h;            s[n]=v(a,h);        }        else if(n==11){            long d1,d2;            double l;            cin>>d1>>d2>>l;            s[n]=v(d1,d2,l);        }    }    /*        in fact,you need all you outcomes outcome together,        but not beyond my imagination,noj STILL had no description of it...    */    for(int j=1;j<=5;++j){        if(z[j]) cout<<fixed<<setprecision(6)<<s[j]<<endl;    }    if(z[6]) cout<<six[0]<<' '<<six[1]<<endl;    if(z[7]) cout<<seven[0]<<' '<<seven[1]<<endl;    for(int j=8;j<=11;++j){        if(z[j]) cout<<s[j]<<endl;    }/*    noj had no description of demand on precision,    but noj had it in fact,I'm tired from bottom heart...*/}/*Sample input:111 32 3 53 64 5 125 1 2 36 5 7 127 5 78 3 4 59 6 7 810 5 1011 12 8 6Sample output:113.09733447.123889216.000000942.4777806.0000003641.261807 1117.2037841349.392014 87.363002193.7315441407.43348583.000000376.991112*//*Additional input:111 82 7 43 94 7 115 1 5 66 5 6 137 5 98 3 5 59 6 9 810 5 1311 12 5 4Additional output:113.09733447.123889216.000000942.4777806.0000003641.261807 1117.2037841349.392014 87.363002193.7315441407.43348583.00000038390.261572*/

035.可变参数平均

Description
stdarg.h头文件提供了一组宏和函数，允许可变参数函数(Variadic function)访问变量参数列表。这些宏和函数是:
va_list:声明将保存变量参数列表的变量的类型。
va_start:一个宏，用于初始化va_list变量以指向变量参数列表中的第一个参数。
va_arg:检索变量参数列表中指定类型的下一个参数的宏。
va_copy:将va_list 变量复制到另一个变量的宏。
va_end:一个宏，用于在使用 va list 变量后清除该变量。
编写一个可变函数double avg(int n,...),，计算n个可变参数的平均值。
Input
在一行里输入5个double型数a、b、c、d、e，用空格间隔。
Output
两次调用函数并且做减法:avg(2,a,b)-avg(3,c,d,e)，输出减法结果，小数点保留四位。

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <cstdarg>#include <iomanip>using namespace std;double avg(int cnt,...){    va_list nums;    double sum=0;    va_start(nums,cnt);    for(int i=0;i<cnt;++i){        sum+=va_arg(nums,double);    }    va_end(nums);    double result=sum/cnt;    return result;}int main(){    double a,b,c,d,e;    cin>>a>>b>>c>>d>>e;    cout<<fixed<<setprecision(4)<<avg(2,a,b)-avg(3,c,d,e);}/*Sample input:1 2 3 4 5 6Sample output:-2.5000*//*Additional input:3 645 14 662 7Additional output:96.3333*/

036.可变参数累加

Description
stdarg.h头文件提供了一组宏和函数，允许可变参数函数(Variadic function)访问变量参数列表。这些宏和函数是
va_list:声明将保存变量参数列表的变量的类型。
va_start:一个宏，用于初始化va_list变量以指向变量参数列表中的第一个参数。
va_arg:检索变量参数列表中指定类型的下一个参数的宏。
va_copy:将va_list 变量复制到另一个变量的宏。
va_end:一个宏，用于在使用 va_list 变量后清除该变量。
编写一个可变函数int sum(int first..);，计算多个可变参数的累加，该函数以参数小于等于0结尾。
Input
在一行里输入6个整数a、b、c、d、e、f，用空格间隔，保证输入数据大于0。
Output
两次调用函数并且做减法:sum(a,b,0)-sum(c,d,e,f,0)，输出减法结果。

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <cstdarg>using namespace std;int pl(int first,...){    va_list nums;    va_start(nums,first);    int cnt=1;    while(va_arg(nums,int)){        cnt++;    }    va_end(nums);    int sum=first;    va_start(nums,first);    for(int i=1;i<cnt;++i){        sum+=va_arg(nums,int);    }    va_end(nums);    return sum;}int main(){    int a,b,c,d,e,f;    cin>>a>>b>>c>>d>>e>>f;    cout<<pl(a,b,0)-pl(c,d,e,f,0);}/*Sample input:1 2 3 4 5 6Sample output:-15*//*Additional input:123 5624 2645 167 3427 12354Additional output:-12846*/

037.运动会

Description
学校运动会即将开始，ACM基地组成了一个NXN的仪仗队方阵。为了保证队伍在行进中整齐划一，队长会跟在仪仗队的左后方根据其视线所及的学生人数来判断队伍是否整齐，如下图所示。

（蓝色即为可见的人）

Input
输入整数N(1≤N≤40000)。
Output
输出队长在NxN的方阵中看到的人数。

note：

1.突破口：建立平面直角坐标系，利用斜率的唯一性；

2.又用到了线性筛（aka欧拉筛），我说啥来着？

3.本题实际为 [SDOI2008]仪仗队。

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;int phiEuler(int n){    int phi[n+1],prime[n+1];    bool isSieved[n+1];    int sum = 0,cnt = 1, comp;    prime[0] = 1;    phi[1] = 1;    for (int i = 2; i < n; ++i){        if (!isSieved[i]){            prime[cnt++] = i;            phi[i] = i-1;        }        for (int j = 1; i*prime[j] <= n; ++j){            comp = i*prime[j];            isSieved[comp] = true;            if (i%prime[j] == 0){                phi[comp] = prime[j]*phi[i];                break;            } else{                phi[comp] = (prime[j]-1)*phi[i];            }        }    }    for (int i = 1; i <= n-1; ++i) {        sum += phi[i];    }    return sum;}int main() {    int n, num;    cin>>n;    num = n == 1 ? 0 : (2 * phiEuler(n) + 1);    cout<<num;}/*Sample input:4Sample output:9*//*Additional input:99Additional output:71315*/

038.光线追踪

Description
用三面长度为N的镜子组成一个等边三角形 $\Delta$ abc，如下图所示:

在ab边上任取一点p，ap长度为X。从该点水平方向向右射入一束红光，接下来它遇到镜子或者自己的轨迹，都会反射。可以证明，光最后是从p点射出的。编程求光线轨迹的总长度。

Input
在一行里输入整数N、X，用空格间隔。其中，2≤N≤10^12，1≤X≤N-1。
Output
输出光线轨迹的总长度。
样例解释:当N=5，X=2时，如图中红线，光线轨迹的总长度=2+3+2+2+1+1+1=12。

note：

1.作为小fw，我搞懂真正逻辑花了很久，甚至现在已经忘了，彻底搞不明白了；

2.我能告诉你的只有：得到每一步的结果和辗转相除法的过程极其相似，这就是用gcd的原因；同时正三角形三条边的对称性使得最后乘3；

3.真优美啊，一辈子也永远理解不了的优美;（类目.jpg）

//Difficulty: 2/10//Importance: 2/10#include<iostream>using namespace std;unsigned int gcd(unsigned int a, unsigned int b){    if (b == 0) return a;    return gcd(b,a%b);}int main(){    unsigned int n,x,l;    cin>>n>>x;    l = 3*(n-gcd(n,x));    cout<<l;}/*Sample input:5 2Sample output:12*//*Additional input:5 3Additional output:12*//*Additional input:199 31Additional output:594*/

039.佩尔数

Description
佩尔数由以下关系定义:

$P_{n}=\left\{\begin{matrix} 0& & \ n=0 & & \\1 & & \, \, n=1\\2P_{n-1}+P_{n-2}& &else \end{matrix}\right.$

下面分别给出使用递归方法和递推方法的佩尔函数PA或PB，求解佩尔数。

int PA(int n){//递归方法    if(n==0) return 0;    else if(n==1) return 1;    return 2*PA(n-1)+PA(n-2);}int PB(int n){ //递推方法    int p0=0,p1=1,pn,i;    for(i=0;i<=n;i++)        if(i==0)pn=p0;        else if(i==1)pn=p1;        else {            pn=2*p1+p0;            p0=p1;            p1=pn;        }    return pn;}

Input
输入n。
Output
当n为奇数调用递归方法PA函数，当n为偶数调用递归方法PB函数，输出佩尔数。

//Difficulty: 2/10//Importance: 2/10#include<iostream>using namespace std;int PA(int n){    if(n==0) return 0;    else if(n==1) return 1;    return 2*PA(n-1)+PA(n-2);}int PB(int n){    int p0=0,p1=1,pn,i;    for (i=0;i<=n;++i){        if (i==0) pn=p0;        else if (i==1) pn=p1;        else{            pn=2*p1+p0;            p0=p1;            p1=pn;        }    }    return pn;}int main(){    int n;    cin>>n;    if(n&1) cout<<PA(n);    else cout<<PB(n);}/*Sample input:10Sample output:2378*//*Additional input:42Additional output:339564650*/

040.哈沙德数

Description

inline int HarshadNumber(int n){    int t=n,s=0;    while (t){        s+=t%10;        t/=10;    }    if (s && n%s==0) return n/s;    return 0;}

上述代码用来求哈沙德数，函数返回0表示n不是哈沙德数，返回其他表示n是哈沙德数且返回值为整除结果。
Input
输入n。
Output
调用上述函数，输出n是几重哈沙德数，为0表示它不是哈沙德数，为1表示它是一重哈沙德数，依此类推。

//Difficulty: 2/10//Importance: 2/10#include<iostream>using namespace std;inline int hn(int n){    int t=n,s=0;    while (t){        s+=t%10;        t/=10;    }    if ((s == 0) || (n%s != 0)) return 0;    if (s == 1) return 1;    return n/s;}int main(){    int cnt = 0, n;    cin>>n;    if (n == 1) cnt = 1;    while ((n != 0) && (n != 1)) {        n = hn(n);        if (n) ++cnt;    }    cout<<cnt;}/*Sample input:6804Sample output:4*//*Additional input:1048Additional output:0*/

第5季（041-050）

041.完美矩阵

note：

1.别看noj题目里面矩阵矩阵的，实际上就是装，蒙骗你；最后就是判断方阵，正方形，懂么；

2.前缀和基础；

//Difficulty: 2/10//Importance: 2/10//这道题用正常方法暴力判断逻辑上成立，但是肯定超时；//下面的程序做了一点优化，实测34ms(再改改细节说不定能到30ms)；//修正题目：子矩阵必须是方阵（noj又错了，气死）；//规定1：一个矩阵的记号为[(x1,y1),(x2,y2)],即左上角和右下角的两个值；//规定2：记号s[(x1,y1),(x2,y2)]为矩阵[(x1,y1),(x2,y2)]内所有元素的和；//翻译题目：首先对要输入的矩阵进行处理，将所有0换成-1，简化运算；//简化之后：条件（2）转化成  s[(x1,y1),(x2,y2)]-s[(x1+1,y1+1),(x2-1,y2-1)]=2(y2-y1+x2-x1) 可类比矩形周长理解；//        上面一条仅针对 行数>=3且列数>=3//简化之后：条件（3）转化成  s[(x1,y1),(x2,y2)]=-1，0，1；//注意程序里面有多个函数需要传多个相同参数，因此最好确保顺序统一；#include <iostream>using namespace std;static int arr[301][301];       //arr为转换之后的矩阵；static int preSum[301][301];    //preSum为前缀和运算后得到的矩阵；//此处两个数组要用static修饰并在main外部定义，作为全局静态参量，便于调用；void prefixSum(int n,int m) {    for (int i = 1; i <= n; ++i) {        for (int j = 1; j <= m; ++j) {            preSum[i][j] = arr[i][j] + preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1];        }    }}//prefixSum为前缀和算法，用于快速计算某个二维数列子矩阵的s[(1，1),(x2,y2)]，结果存储在preSum中；int getSum(int x1, int y1, int x2, int y2) {    return preSum[x2][y2]-preSum[x1-1][y2]-preSum[x2][y1-1]           +preSum[x1-1][y1-1];}//getSum利用prefixSum和容斥原理得到任意的s[(x1，y1),(x2,y2)];bool isPerfectMatrix(int x1,int y1,int x2,int y2){    int sum1=getSum(x1,y1,x2,y2);               //sum1用来存整个子矩阵之和，sum2用来存子矩阵内层之和；    if((x2-x1)==1||(y2-y1)==1){                 //即2x2的情况，必须单独考虑，        if(sum1==4) return true;                //因为这种情况下getSum里的参数实际上会相等，        else return false;                      //导致getSum的运算失去意义；    }    else{        int sum2=getSum(x1+1,y1+1,x2-1,y2-1);        if (sum2==-1||sum2==0||sum2==1){        //先判断简单的条件(3)，优化一下；            int c=2*(y2-y1+x2-x1);            if(sum1-sum2==c) return true;       //判断条件(2)；            else return false;        }        else return false;    }}int PerfectMatrixCount(int n,int m){    int cnt=0;    for(int i=1;i<=n;++i){        for(int j=1;j<=m;++j){            for(int k=1;i+k<=n&&j+k<=m;++k){    //记得开头说的子矩阵必须是方阵；                if (arr[i][k + j] == -1 || arr[k + i][j] == -1) break;                //此处为优化部分，发现扩展遍历时遇到元素为0，那么该方向的扩展均不可能为完美矩阵，                //因为扩展的最外圈总会包含这个0，至于为什么是==-1，因为矩阵转换过了；                if (isPerfectMatrix(i,j,i+k,j+k)) {                    ++cnt;                }            }        }    }    return cnt;}int main(){    int n,m;    cin>>n>>m;    for(int i=1;i<=n;++i){        for(int j=1;j<=m;++j){            int tmp;            cin>>tmp;            if (tmp==1) arr[i][j]=1;            else arr[i][j]=-1;      //此处完成0-1矩阵到(-1)-1矩阵的转换；        }    }    prefixSum(n,m);    if(n<2||m<2) cout<<0;           //其实多余，但是为了完整，还是放在这边；    else cout<<PerfectMatrixCount(n,m);}/*Sample input:4 41 1 1 11 0 1 11 1 0 11 1 1 1Sample output:3*//*Additional input:5 51 0 1 0 11 1 0 1 11 1 1 1 10 1 1 0 01 0 1 1 1Additional output:3*/

042.【专业融合：航空】飞机起飞速度

note：

1.这是第一道无人AC的题；

2.给出一个版本的代码，不能AC的，样例都跑不出来；但这题的样例似乎就有问题；

//Difficulty:??/10//Importance: 0/10//1st none AC you meet#include <iostream>#include <cmath>using namespace std;double calculateSpeed(double temperature, double pressure, int elevation, int runway, int weight, int flaps, int wet) {    // 检查输入是否在有效范围内    if (flaps != 1 && flaps != 5 && flaps != 15) {        return -1;    }    if (weight < 41413 || weight > 65000 || runway <= 6900) {        return -1;    }    // 计算温度档和气压档    int tempRange = floor(temperature / 10);    int pressureRange = ceil(pressure);    // 检查操纵参考表是否存在    if (tempRange < 0 || tempRange > 7 || pressureRange < 0 || pressureRange > 9) {        return -1;    }    // 根据温度档和气压档查找操纵参考值    char referenceTable[8][10] = {            {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K'},            {'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V'},            {'W', 'X', 'Y', 'Z', 'A', 'B', 'C', 'D', 'E', 'F'},            {'G', 'H', 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R'},            {'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'A', 'B'},            {'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K', 'L', 'M'},            {'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X'},            {'Y', 'Z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}    };    char reference = referenceTable[tempRange][pressureRange];    // 检查操纵参考表是否存在V1、Vr和V2    if (reference != 'A' && reference != 'B' && reference != 'C' && reference != 'D' && reference != 'E') {        return -1;    }    // 根据襟翼位置、起飞重量和操纵参考值查找V1、Vr和V2    int speedTable[3][5] = {            {117, 126, 134, 142, 151},            {122, 131, 139, 147, 156},            {127, 136, 145, 153, 162}    };    int speedIndex = (flaps - 1) / 7;    int* speedRow = speedTable[speedIndex];    int v1 = speedRow[weight / 13000];    int vr = speedRow[weight / 13000] + 11;    int v2 = speedRow[weight / 13000] + 18;    // 如果是湿跑道，根据跑道长度和襟翼位置查找折扣值    if (wet == 1) {        int discountTable[3][3] = {                {0, 0, 0},                {0, 0, 0},                {0, 0, 0}        };        int discountIndex = (flaps - 1) / 7;        int* discountRow = discountTable[discountIndex];        int discount = discountRow[runway / 1000];        v1 -= discount;    }    printf("V1=%dkts Vr=%dkts V2=%dkts\n", v1, vr, v2);    return 0;}int main() {    double temperature, pressure;    int elevation, runway, weight, flaps, wet;    cin>>temperature>>pressure>>elevation>>runway>>weight>>flaps>>wet;    int result = calculateSpeed(temperature, pressure, elevation, runway, weight, flaps, wet);    if (result == -1) {        cout<<"Flight not possible!\n";    }    return 0;}/*Sample input:23,8 28.67 1200 7250 52600 5 1Sample output:V1=128kts Vr=139kts V2=146kts*//*Additional input:NULLAdditional output:NULL*/

043.【专业融合：数学】行列式值

//Difficulty: 2/10//Importance: 2/10#include <iostream>#define MAXSIZE 10using namespace std;void swap(double arr[MAXSIZE][MAXSIZE], int r1, int r2, int n) {    for (int i = 0; i < n; i++) {        double temp = arr[r1][i];        arr[r1][i] = arr[r2][i];        arr[r2][i] = temp;    }}double calDet(double arr[MAXSIZE][MAXSIZE], int n) {    int i, j, k;    double det = 1.0;    for (i = 0; i < n; i++) {        if (arr[i][i] == 0.0) {            for (j = i + 1; j < n; j++) {                if (arr[j][i] != 0.0) {                    swap(arr, i, j, n);                    det *= -1.0;                    break;                }            }        }        if (arr[i][i] == 0.0) {            return 0.0;        }        double v = arr[i][i];        det *= v;        for (j = i; j < n; j++) {            arr[i][j] /= v;        }        for (j = i + 1; j < n; j++) {            double e = arr[j][i];            for (k = i; k < n; k++) {                arr[j][k] -= e * arr[i][k];            }        }    }    return det;}int main() {    int n;    cin>>n;    double arr[MAXSIZE][MAXSIZE];    for (int i = 0; i < n; i++) {        for (int j = 0; j < n; j++) {            cin>>arr[i][j];        }    }    double det = calDet(arr, n);    cout<<det;    return 0;}/*Sample input:32 6 31 0 25 8 4Sample output:28*//*Additional input:38 91 14 15 1561 237 16Additional output:50954*/

044.稀疏矩阵

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;int main () {    int raw, col, n, num = 0;    cin>>raw>>col;    for (int i = 0; i < raw; ++i) {        for (int j = 0; j < col; ++j) {            cin>>n;            if (n) ++num;        }    }    double ratio = (double)num / (raw * col);    if (num == raw || num == col || (ratio - 0.05) <= 1e-9)        cout<<"Yes"<<endl;    else cout<<"No"<<endl;    return 0;}/*Sample input:4 45 0 0 00 8 0 00 0 3 00 6 0 0Sample output:Yes*//*Additional input:4 45 5 0 00 1 0 00 0 3 00 6 0 2Additional output:No*/

045.【专业融合：管理】航空旅行

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;void pass(int a, int b, int c, int d, int e) {    bool flag = false;    if (a <= e && (b + c) <= d) flag = true;    if (b <= e && (a + c) <= d) flag = true;    if (c <= e && (a + b) <= d) flag = true;    if (flag) cout<<"YES"<<endl;    else cout<<"NO"<<endl;}int main() {    int n, a, b, c, d, e;    cin>>n;    while (n--){        cin>>a>>b>>c>>d>>e;        pass(a, b, c, d, e);    }    return 0;}/*Sample input:31 1 1 15 58 7 6 15 58 5 7 15 6Sample output:YESNOYES*//*Additional input:31 4 5 5 1615 51 16 15 1515 61 16 16 16Additional output:YESNONO*/

046.【专业融合：管理】货运优化

note：

1.这么喜欢管理？都融合俩了；

2.这题使用贪心算法，必须掌握；

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;int main() {    int l3s2[4] = {0, 5, 3, 1};    int n, x1, x2, x3, x4, x5, x6, s2, s1;    while (1) {        cin>>x1>>x2>>x3>>x4>>x5>>x6;        if ((x1 + x2 + x3 + x4 + x5 + x6) == 0) break;        n = (x3 + 3) / 4 + x4 + x5 + x6;        s2 = 5 * x4 + l3s2[x3 % 4];        if (x2 > s2) n += (x2 - s2 + 8) / 9;        s1 = 36 * n - 36 * x6 - 25 * x5 - 16 * x4 - 9 * x3 - 4 * x2;        if (x1 > s1) n += (x1 - s1 + 35) / 36;        cout<<n<<endl;    }    return 0;}/*Sample input:1 1 1 1 1 12 2 2 2 2 21 2 3 4 5 60 0 0 0 0 0Sample output:4716*//*Additional input:1 5 6 2 1 61 6 7 1 2 71 2 7 19 8 60 0 0 0 0 0Additional output:111235*/

047.回文数之和

note:

1.回文数，实验考试挺喜欢考的（似乎）；

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;int dec0[10] , kSys[32] ;bool isPalindrome(int arr[], int cnt){    int head = 0, tail = cnt - 1;    while (head < tail) {        if (arr[head] != arr[tail]) return false;        ++head, --tail;    }    return true;}bool isBiPalindrome(int n, int k){    int tmp = n, cnt = 0;    while (tmp) {        dec0[cnt++] = tmp % 10;        tmp /= 10;    }    if (!isPalindrome(dec0, cnt)) return false;    tmp = n, cnt = 0;    while (tmp) {        kSys[cnt++] = tmp % k;        tmp /= k;    }    if (!isPalindrome(kSys, cnt)) return false;    return true;}int main() {    int n, k, sum = 0;    cin>>n>>k;    for (int i = 1; i <= n; ++i) {        if (isBiPalindrome(i, k)) sum += i;    }    cout<<sum;    return 0;}/*Sample input:100 2Sample output:157*//*Additional input:1000 3Additional output:2638*/

048.【专业融合：物理】蒙特卡罗方法求积分

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <cmath>#include <cstdlib>using namespace std;double func1(double x) {    return pow(x, 4) * exp(-x);}double func2(double x) {    return x * x + 1;}double func3(double x) {    return cos(x);}double func4(double x) {    return sqrt(x) * (x - 2);}double func5(double x) {    return 2 * sin(x) - 5 * cos(x);}double func(int m, double x) {    switch (m) {        case 1: return func1(x);        case 2: return func2(x);        case 3: return func3(x);        case 4: return func4(x);        case 5: return func5(x);        default: return 0;    }}double mtk(int m, double a, double b, int n) {    srand(RAND_MAX);    double w = b - a, sum = 0;    for (int i = 1; i < n; ++i) {        double x = ((double)rand() / RAND_MAX) * w + a;        sum += func(m, x);    }    sum *= w / n;    return sum;}int main() {    int m, n;    double a, b;    cin>>m>>a>>b>>n;    printf("%.6lf", mtk(m, a, b, n));    return 0;}/*Sample input:1 1 5 2000Sample output:13.317870*//*Additional input:3 8 7 1292Additional output:-0.331019*/

049.【专业融合：计算机】波士顿房价预测

note：

1.这到底哪里融合计算机了，我真看不出来，实在扯不上能不能直接不扯关系，看着怪尴尬的；

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;double nAvg(double arr[], int n) {    double sum = 0;    for (int i = 0; i < n; ++i) {        sum += arr[i];    }    return sum / n;}int main() {    int n;    cin>>n;    double x[n], y[n];    for (int i = 0; i < n; ++i) {        cin>>x[i]>>y[i];    }    double xBar = nAvg(x, n), yBar = nAvg(y, n);    double sumUp = 0, sumDown = 0;    for (int i = 0; i < n; ++i) {        sumUp += (x[i] - xBar) * (y[i] - yBar);    }    for (int i = 0; i < n; ++i) {        sumDown += (x[i] - xBar) * (x[i] - xBar);    }    double b = sumUp / sumDown;    double a = yBar - b * xBar;    printf("Y=%.4lf+%.4lf*X",a,b);    return 0;}/*Sample input:7150 6450200 7450250 8445300 9450350 11450400 15450600 18450Sample output:Y=1770.2394+28.7793*X*//*Additional input:51 12 23 34 45 5Additional output:Y=0.0000+1.0000*X*/

050.素数筛选法

note：

1.这题出现的也太迟了，应该塞第2季，线性筛都用烂了；

2.下面代码我记得没用埃氏筛，直接上的欧拉筛；

//Difficulty: 2/10//Importance: 2/10#include<iostream>using namespace std;#define NUM (int)1e7+1static bool isSieved[NUM];static int prime[NUM];int main() {    int n, k = 0;    cin>>n;    isSieved[1] = true;    for (int i = 2; i <= n; ++i) {        if (!isSieved[i]) prime[++k] = i;        for (int j = 1; prime[j] * i <= n; ++j) {            isSieved[prime[j] * i] = true;            if (i % prime[j] == 0) break;        }    }    cout<<k;}/*Sample input:100Sample output:25*//*Additional input:1590Additional output:250*/

第6季（051-060）

051.分离字符串

note：

1.字符串的好好搞懂吧，实验的期末抽到概率不小；

2.对string类的各种函数（原型，参数，返回值）要牢牢把握，随便列几个常用的：

str.substr(); str.find(); str.erase(); str.find(); str.append();

str.size(); str.length(); str.insery(); str.compare(); str.replace();

atoi(); stoi(); tolower(); toupper(); ......

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <vector>using namespace std;vector<string> split(string str, string pattern){    string::size_type pos;    vector<string> result;    str += pattern;    int size = str.size();    for (int i = 0; i < size; i++)    {        pos = str.find(pattern, i);        if (pos < size)        {            string s = str.substr(i, pos - i);            result.push_back(s);            i = pos + pattern.size() - 1;        }    }    return result;}int main(){    string str;    getline(cin,str);    string pattern;    getline(cin,pattern);    vector<string> result=split(str,pattern);    for(int i=0; i<result.size(); i++)    {        cout<<result[i]<<endl;    }    return 0;}/*Sample input:www.nwpu.edu.cn.Sample output:wwwnwpueducn*//*Additional input:https://www.bh3.com/.Additional output:https://wwwbh3com/*/

052.Kids A+B

note:

1.这题真没意思，优化也优化不到哪里去，所以直接让GPT生成map了；（别以为我是慢慢敲的，叉腰.jpg）

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <map>#include <vector>using namespace std;vector<string> split(string str, string pattern){    string::size_type pos;    vector<string> result;    str += pattern;    int size = str.size();    for (int i = 0; i < size; i++)    {        pos = str.find(pattern, i);        if (pos < size)        {            string s = str.substr(i, pos - i);            result.push_back(s);            i = pos + pattern.size() - 1;        }    }    return result;}int stringToInt(vector<string> str){    map<string, int> stringToIntMap;    //个位映射    stringToIntMap["zero"] = 0;    stringToIntMap["one"] = 1;    stringToIntMap["two"] = 2;    stringToIntMap["three"] = 3;    stringToIntMap["four"] = 4;    stringToIntMap["five"] = 5;    stringToIntMap["six"] = 6;    stringToIntMap["seven"] = 7;    stringToIntMap["eight"] = 8;    stringToIntMap["nine"] = 9;    //十位映射    stringToIntMap["twenty"] = 20;    stringToIntMap["thirty"] = 30;    stringToIntMap["forty"] = 40;    stringToIntMap["fifty"] = 50;    stringToIntMap["sixty"] = 60;    stringToIntMap["seventy"] = 70;    stringToIntMap["eighty"] = 80;    stringToIntMap["ninety"] = 90;    //特殊映射（其实包含十位映射）    stringToIntMap["ten"] = 10;    stringToIntMap["eleven"] = 11;    stringToIntMap["twelve"] = 12;    stringToIntMap["thirteen"] = 13;    stringToIntMap["fourteen"] = 14;    stringToIntMap["fifteen"] = 15;    stringToIntMap["sixteen"] = 16;    stringToIntMap["seventeen"] = 17;    stringToIntMap["eighteen"] = 18;    stringToIntMap["nineteen"] = 19;    //使用映射    int result=0;    if(str.size()==1){        result=stringToIntMap[str[0]];    }    if(str.size()==2){        result=stringToIntMap[str[0]]+stringToIntMap[str[1]];    }    return result;}int intNumWidth(int x){    string str = to_string(x);    return str.size();}string intToString(int num){    // 肯定有好的方法，但是下面的map可以直接让ai生成，也不费时间    map<int,string> intToStringMap;    intToStringMap[0] = "zero";    intToStringMap[1] = "one";    intToStringMap[2] = "two";    intToStringMap[3] = "three";    intToStringMap[4] = "four";    intToStringMap[5] = "five";    intToStringMap[6] = "six";    intToStringMap[7] = "seven";    intToStringMap[8] = "eight";    intToStringMap[9] = "nine";    intToStringMap[10] = "ten";    intToStringMap[11] = "eleven";    intToStringMap[12] = "twelve";    intToStringMap[13] = "thirteen";    intToStringMap[14] = "fourteen";    intToStringMap[15] = "fifteen";    intToStringMap[16] = "sixteen";    intToStringMap[17] = "seventeen";    intToStringMap[18] = "eighteen";    intToStringMap[19] = "nineteen";    intToStringMap[20] = "twenty";    intToStringMap[21] = "twenty-one";    intToStringMap[22] = "twenty-two";    intToStringMap[23] = "twenty-three";    intToStringMap[24] = "twenty-four";    intToStringMap[25] = "twenty-five";    intToStringMap[26] = "twenty-six";    intToStringMap[27] = "twenty-seven";    intToStringMap[28] = "twenty-eight";    intToStringMap[29] = "twenty-nine";    intToStringMap[30] = "thirty";    intToStringMap[31] = "thirty-one";    intToStringMap[32] = "thirty-two";    intToStringMap[33] = "thirty-three";    intToStringMap[34] = "thirty-four";    intToStringMap[35] = "thirty-five";    intToStringMap[36] = "thirty-six";    intToStringMap[37] = "thirty-seven";    intToStringMap[38] = "thirty-eight";    intToStringMap[39] = "thirty-nine";    intToStringMap[40] = "forty";    intToStringMap[41] = "forty-one";    intToStringMap[42] = "forty-two";    intToStringMap[43] = "forty-three";    intToStringMap[44] = "forty-four";    intToStringMap[45] = "forty-five";    intToStringMap[46] = "forty-six";    intToStringMap[47] = "forty-seven";    intToStringMap[48] = "forty-eight";    intToStringMap[49] = "forty-nine";    intToStringMap[50] = "fifty";    intToStringMap[51] = "fifty-one";    intToStringMap[52] = "fifty-two";    intToStringMap[53] = "fifty-three";    intToStringMap[54] = "fifty-four";    intToStringMap[55] = "fifty-five";    intToStringMap[56] = "fifty-six";    intToStringMap[57] = "fifty-seven";    intToStringMap[58] = "fifty-eight";    intToStringMap[59] = "fifty-nine";    intToStringMap[60] = "sixty";    intToStringMap[61] = "sixty-one";    intToStringMap[62] = "sixty-two";    intToStringMap[63] = "sixty-three";    intToStringMap[64] = "sixty-four";    intToStringMap[65] = "sixty-five";    intToStringMap[66] = "sixty-six";    intToStringMap[67] = "sixty-seven";    intToStringMap[68] = "sixty-eight";    intToStringMap[69] = "sixty-nine";    intToStringMap[70] = "seventy";    intToStringMap[71] = "seventy-one";    intToStringMap[72] = "seventy-two";    intToStringMap[73] = "seventy-three";    intToStringMap[74] = "seventy-four";    intToStringMap[75] = "seventy-five";    intToStringMap[76] = "seventy-six";    intToStringMap[77] = "seventy-seven";    intToStringMap[78] = "seventy-eight";    intToStringMap[79] = "seventy-nine";    intToStringMap[80] = "eighty";    intToStringMap[81] = "eighty-one";    intToStringMap[82] = "eighty-two";    intToStringMap[83] = "eighty-three";    intToStringMap[84] = "eighty-four";    intToStringMap[85] = "eighty-five";    intToStringMap[86] = "eighty-six";    intToStringMap[87] = "eighty-seven";    intToStringMap[88] = "eighty-eight";    intToStringMap[89] = "eighty-nine";    intToStringMap[90] = "ninety";    intToStringMap[91] = "ninety-one";    intToStringMap[92] = "ninety-two";    intToStringMap[93] = "ninety-three";    intToStringMap[94] = "ninety-four";    intToStringMap[95] = "ninety-five";    intToStringMap[96] = "ninety-six";    intToStringMap[97] = "ninety-seven";    intToStringMap[98] = "ninety-eight";    intToStringMap[99] = "ninety-nine";    return intToStringMap[num];}int main() {    string num1,num2;    cin>>num1>>num2;    vector<string> str1=split(num1,"-");    vector<string> str2=split(num2,"-");    int ans=0;    ans=stringToInt(str1)+stringToInt(str2);    cout<<intToString(ans);    return 0;}/*Sample input:twenty-seven fifty-fourSample output:eighty-one*//*Additional input:zero zeroAdditional output:zero*/

053.前后缀移除

note：

1.题目不说人话也是noj一大特色，你得好好理解到底说的什么意思；

2.遍历到chars，也就是子字符串中不含的字符，遍历终止；

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;string removePre(string input, const string& std) {    int pos = 0;    for (auto it = input.begin(); it != input.end(); ++it) {        if (std.find(*it) != string::npos) ++pos;        else break;    }    if (pos) input.erase(0, pos);    return input;}string removeSuf(string input, const string& std) {    int pos = 0;    for (auto it = input.rbegin(); it != input.rend(); ++it) {        if (std.find(*it) != string::npos) ++pos;        else break;    }    if (pos) input.erase(input.size()-pos, pos);    return input;}int main() {    string input,std;    getline(cin,input);    getline(cin,std);    cout<<removePre(input,std)<<endl<<removeSuf(input,std)<<endl<<removeSuf(removePre(input,std),std);    return 0;}/*Sample input:www.example.comcmowz.Sample output:example.comwww.exampleexample*//*Additional input:https://www.bh3.com/pthsocm/:w.Additional output:bh3.com/https://www.bh3bh3*/

054.删除前后缀

note：

1.名字整的和上一题那么像，这一题更简单，但更实用；

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;string removePre(string input, const string& std) {    int base=0;    for (auto it = input.begin(); it != input.end(); ) {        if (input.substr(distance(input.begin(), it),std.size())== std){            ++base;            it+=std.size();        }        else break;    }    int pos=std.size()*base;    if (base) input.erase(0, pos);    return input;}string removeSuf(string input, const string& std) {    int base=0;    for (auto it = input.rbegin(); it != input.rend(); ) {        if (input.substr(distance(input.rbegin(), it),std.size()) == std){            ++base;            it+=std.size();        }        else break;    }    int pos=std.size()*base;    if (base) input.erase(input.size()-pos, pos);    return input;}int main() {    string input,std;    getline(cin,input);    getline(cin,std);    cout<<removePre(input,std)<<endl<<removeSuf(input,std);    return 0;}/*Sample input:antiantianwartiantiantiantiSample output:anwartiantiantiantiantianwarti*//*Additional input:yuanshenyuanshenyuanshengyuanshenshenshenyuanAdditional output:shenyuanshenyuanshengyuanshenshenshenyuanshenyuanshenyuanshengyuanshenshen*/

055.AtoI转换

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <climits>using namespace std;int ATOI(string str) {    auto it = str.begin();    int sgn = 1;    long long tmp = 0;    if (*it == '+') ++it;    else if (*it == '-') sgn = -1, ++it;    while (it != str.end()) {        if (*it == ' ') ;        else if ('0' <= *it && *it <= '9') {            tmp = (*it - '0') + tmp * 10;            if ((tmp * sgn) >= INT_MAX) return INT_MAX;            else if ((tmp * sgn) <= INT_MIN) return INT_MIN;        }        else break;        ++it;    }    return tmp * sgn;}int main() {    string str;    cin>>str;    cout<<ATOI(str);    return 0;}/*Sample input:-123x+123Sample output:-123*//*Additional input:00519Additional output:519*/

056.大小写交换

note:

1.ASCII码表的简单运用罢了；

2.ASCII码表建议记忆的如下：

Dec（十进制值）	字符
0	NUL
32	空格
48	0
65	a
97	A

上面的就够用了，实在不行直接cout<<(int)(char); 让编译器告诉你；

3.这题的本质是实现string类的str.toUpperCase()，所以你可以用这个秒杀；

有str.toUpperCase()，那自然也有str.toLowerCase()；

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <string>using namespace std;string trans(string str){    for(int i=0;i<str.size();++i){        if(str[i]>64&&str[i]<91){            str[i]+=32;        }        else if(str[i]>96&&str[i]<123){            str[i]-=32;        }    }    return str;}int main() {    string str;    getline(cin,str);    cout<<trans(str);}/*Sample input:Hello worldSample output:hELLO WORLD*//*Additional input:eLYSIA tRUeAdditional output:Elysia TruE*/

057.字符串替换

note：

1.第二道无人AC的题；

2.肯定是noj后台样例又出什么毛病了呗；

3.本质是实现string类的str.replace()，可以用这个直接解决；

//Difficulty: 3/10//Importance: 3/10//2nd none AC you meet#include <iostream>#include <string>using namespace std;void subreplace(string &str,string olds,string news){    size_t pos=0;    while((pos=str.find(olds))!=string::npos){        str.replace(pos,olds.length(),news);    }}int main() {    string str,olds,news;    getline(cin,str);    getline(cin,olds);    getline(cin,news);    subreplace(str,olds,news);    cout<<str;}/*Sample input:xxforxx xx for xxxxnwpuSample output:nwpufornwpu nwpu for nwpu*//*Additional input:xx for xx is xxxxGenshin ImpactAdditional output:Genshin Impact for Genshin Impact is Genshin Impact*/

058.字符串切片

note：

1.本质是模拟python的slice，这下不能像上面几题直接来了，悲；

2.但是还可以用string类的str.substr()取出特点位置的字符串，进行曲线救国；

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <string>using namespace std;int len;string string_slice(string str, int start,int stop,int step){    string res;    if (stop < 0) stop += len;    if (start < 0) start += len;    if(start>stop&&step<0){        for (int i = start; i >stop; i+=step) {            res += str[i];        }        return res;    }    if(start<=stop&&step>0){        for (int i = start; i<stop; i+=step) {            res += str[i];        }        return res;    }}int main() {    string str;    getline(cin,str);    len=str.size();    int T;    cin>>T;    for(int i=0;i<T;++i){        int n,a,b,c;        cin>>n;        switch (n) {            case 1:                cin>>a;                cout<<string_slice(str,a,len,1)<<endl;break;            case 2:                cin>>a>>b;                cout<<string_slice(str,a,b,1)<<endl;break;            case 3:                cin>>a>>b>>c;                cout<<string_slice(str,a,b,c)<<endl;break;        }    }}/*Sample input:ABCDEFGHI82 2 72 -7 -22 2 -53 2 7 23 6 1 -22 0 31 63 -1 -10 -1Sample output:CDEFGCDEFGCDCEGGECABCGHIIHGFEDCBA*//*Additional input:NULLAdditional output:NULL*/

059.元宇宙A+B

note：

1.不觉得decToMeta的数组很妙吗，也符合进制的概念；

2.在C++中，gets()函数由于具有极大安全性风险，已经被废弃，不建议使用；（就这样你瓜教材里还是它）

3.针对上一点，使用C++新标准的编译器依旧为了兼容C考虑，允许使用gets()，但是必定警告；如果你的编程工具啥也没说，这提醒你，该换啦，参考“必看”中的“推荐工具”；

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <cstring>using namespace std;const static char decToMeta[37] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";static char c[100] = "", a[100] = "", b[100] = "";static int C[100] = {0}, A[100] = {0}, B[100] = {0};int metaToDec(char m) {    if ('0' <= m && m <= '9') return m - '0';    return m - 'A' + 10;}void add(void) {    int lenA = strlen(a), lenB = strlen(b);    for (int i = 0; i < lenA; ++i) A[i] = metaToDec(a[lenA - i - 1]);    for (int i = 0; i < lenB; ++i) B[i] = metaToDec(b[lenB - i - 1]);    int carry = 0;    int lenC = lenA > lenB ? lenA : lenB;    for (int i = 0; i < lenC; ++i) {        C[i] = A[i] + B[i] + carry;        carry = C[i] / 36;        C[i] %= 36;    }    if (carry != 0) {        C[lenC] = carry;        ++lenC;    }    for (int i = lenC - 1; i >= 0; --i) c[i] = decToMeta[C[lenC - i - 1]];    c[lenC] = '\0';}int main() {    cin>>a>>b;    add();    cout<<c;    return 0;}/*Sample input:ZZ 321Sample output:420*//*Additional input:ac 42Additional output:1BA*/

060.字符串后缀

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;bool findSuf(string input, const string& std) {    int pos = 0;    if(input.substr(input.size()-std.size(),std.size()) == std) return true;    return false;}int main(){    string input,std;    getline(cin,input);    getline(cin,std);    if (findSuf(input,std)) cout<<"Yes";    else cout<<"No";}/*Sample input:hello world!world!Sample output:Yes*//*Additional input:Genshin Impact! Impact!Additional output:Yes*/

第7季（061-070）

061.有效表达式

note：

1.回忆起来一点点高中时期的排列组合知识就够了，考虑顺序与匹配问题；

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;int main() {    long long n;    cin>>n;    long long cnt = 1;    for (long long i = n + 2; i <= 2 * n; ++i) cnt *= i;    for (long long i = 1; i <= n; ++i) cnt /= i;    cout<<cnt;    return 0;}/*Sample input:6Sample output:132*//*Additional input:14Additional output:2674440*/

062.【专业融合：生物】DNA双螺旋结构

note：

1.不是我说，这融合得也太生硬了吧，这题也没有任何意义；

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;void displayDNA1(){    cout<<"   AT   \n";    cout<<"  T--A  \n";    cout<<" A----T \n";    cout<<"T------A\n";    cout<<"T------A\n";    cout<<" G----C \n";    cout<<"  T--A  \n";    cout<<"   GC   \n";}void displayDNA2(){    cout<<"   CG   \n";    cout<<"  C--G  \n";    cout<<" A----T \n";    cout<<"A------T\n";    cout<<"T------A\n";    cout<<" A----T \n";    cout<<"  A--T  \n";    cout<<"   GC   \n";}void displayDNA3(){    cout<<"   AT   \n";    cout<<"  C--G  \n";    cout<<" T----A \n";    cout<<"C------G\n";    cout<<"C------G\n";    cout<<" T----A \n";    cout<<"  G--C  \n";    cout<<"   AT   \n";}int main() {    int n;    cin>>n;    for (int i = 1; i <= n/2; ++i) {        if (i % 3 == 1) displayDNA1();        else if (i % 3 == 2) displayDNA2();        else displayDNA3();    }    return 0;}/*Sample input:8Sample output:   AT  T--A A----TT------AT------A G----C  T--A   GC   CG  C--G A----TA------TT------A A----T  A--T   GC   AT  C--G T----AC------GC------G T----A  G--C   AT   AT  T--A A----TT------AT------A G----C  T--A   GC*//*Additional input:2Additional output:   AT  T--A A----TT------AT------A G----C  T--A   GC*/

063.【专业融合：通信】GPS通信协议

note：

1.不是我说，这题完全可以算是极其重磅的了，在noj的一众卧龙凤雏里面也算得上是鹤立鸡群；

2.光这逆天Sample input，要是没有OCR，我得打到天荒地老；

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <string>using namespace std;string out[100];int k=0;int check(string str){    int i,result;    for(result=str[1],i=2;str[i]!='*';i++)    {        result^=str[i];    }    return result;}int convert(string str){    int res=0;    res=stoi(str,0,16);    return res;}void convert_BeingTime(string utcTime){    int  hour=stoi(utcTime.substr(0,2));    int  B_hour=(hour+8)%24;    if(B_hour/10==0)        out[k++]="0"+to_string(B_hour)+":"+utcTime.substr(2,2)+":"+utcTime.substr(4,2);    else        out[k++]=to_string(B_hour)+":"+utcTime.substr(2,2)+":"+utcTime.substr(4,2);}int main(){    string str;    while(cin>>str){        if(str=="END") break;        if(str.compare(0,6,"$GPRMC")==0){            size_t asteriskPos = str.find('*');            if(asteriskPos!=string::npos){                int checksum=check(str);                int senchecksum=convert(str.substr(asteriskPos + 1, 2));                if(checksum!=senchecksum) {                    out[k++]="error";                }                else{                    string utcTime = str.substr(7, 6);                    convert_BeingTime(utcTime);                }            }        }    }    for(int i=0;i<k;i++){        cout<<out[i]<<endl;    }}/*Sample input:$GPRMC,024813.640,A,3158.4608,N,11848.3737,E,10.05 ,324.27,150706,,,A*50$GPGSV,3,1,11,10,63,137,17,07,61,098,15,05,59,290,20,08,54,157,30*70$GPRMC,194548.127,A,5230.657,N,01325.713,E,3968.7,122.8,200220,000.0,W*44$GPGGA,092750.000,5321.6802,N,00630.3372,W,1,8,1.03,61.7,M,55.2,M,,*76$GPRMC,111724.681,A,5231.801,N,01329.267,E,1289.3,000.0,291123,000.0,W*48$GNVTG,112.99,T,109.99,M,0.15,N,0.08,K,A*3BENDSample output:10:48:13error19:17:24*//*Additional input:NULLAdditional output:NULL*/

064.循环排序

note：

1.在那么多种类的算法里，排序算是基础而又十分重要的；

2.无论你有多摆，请至少学会冒泡和选择排序；

3.我会在后期更新一个排序算法的blog，七种排序算法的代码+演示；

（真别小瞧这个，中文互联网上能搜到的排序算法大部分甚至不能编译成功，剩下的又有一大半是错的，正确的寥寥无几）

4.不行了，我抑制不住了，咕咕咕~

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;void swap(int *a, int *b) {    int tmp = *a;    *a = *b, *b = tmp;}void CycleSort(int arr[], int n) {    for (int i = 0; i < n - 1; ++i) {        int item = arr[i], pos = i;        for (int j = i + 1; j < n; ++j) if (arr[j] < item) ++pos;        if (pos == i) continue;        swap(&arr[pos], &item);        while(pos != i) {            pos = i;            for (int j = i + 1; j < n; ++j) if (arr[j] < item) ++pos;            while (item == arr[pos]) ++pos;            swap(&arr[pos], &item);        }    }}int main() {    int n;    cin>>n;    int arr[n];    for (int i = 0; i < n; ++i) cin>>arr[i];    CycleSort(arr, n);    for (int i = 0; i < n; ++i) cout<<arr[i]<<' ';    return 0;}/*Sample input:81 8 3 9 10 10 2 4Sample output:1 2 3 4 8 9 10 10*//*Additional input:101 1 1 1 2 6 2 6 2 7Additional output:1 1 1 1 2 2 2 6 6 7*/

065.长安

note：

1.实际上可以用简单的排列组合解决，但是我写的WA了，似乎是cmath里一些函数在noj里不能用？反正代码对的，我也懒得自己写函数代替那个函数了；

2.仔细读题，你会发现，noj连平面直角坐标系标点都不会标，请默认把所有除了（0，0）的坐标的x，y值减1，还原成正确坐标；

//Difficulty: 2/10//Importance: 2/10//version 1:simple combination//but noj doesn't fully support cmath(seemly), so it's WA//of course you can write functions to fully replace cmath to ensure AC#include <iostream>#include <cmath>using namespace std;int combination(int n, int k) {    if (k > n) {        return 0;    }    return tgamma(n + 1) / (tgamma(k + 1) * tgamma(n - k + 1));}int ways(int bx,int by,int px, int py){    bx-=1;by-=1;px-=1;py-=1;    if(bx>=px&&by>=py){        int nx=bx-px,ny=by-py;        return combination(bx+by,bx<by?bx:by)-combination(px+py,px<py?px:py)* combination(nx+ny,nx<ny?nx:ny);    }    else return combination(bx+by,bx<by?bx:by);}int main() {    int bx,by,px,py,cnt=0;    while (1) {        cin.sync();        cin>>bx>>by>>px>>py;        if (bx <= 0 || by <= 0 || px <= 0 || py <= 0) break;        cnt=ways(bx,by,px,py);        cout<<cnt<<endl;    }}//version 2:DFS#include <iostream>using namespace std;int bx, by, px, py, cnt;void dfs(int x, int y) {    if ((x == px && y == py) || x > bx || y > by) return;    if (x == bx && y == by) {        ++cnt;        return;    }    dfs(x + 1, y);    dfs(x, y + 1);}int main() {    while (1) {        fflush(stdin);        cin>>bx>>by>>px>>py;        if (bx <= 0 || by <= 0 || px <= 0 || py <= 0) break;        cnt = 0;        dfs(1, 1);        cout<<cnt<<endl;    }    return 0;}/*Sample input:8 6 5 38 6 8 68 6 9 60 0 0 0Sample output:4920792*//*Additional input:8 5 6 11 6 1 61 6 3 70 0 0 0Additional output:31501*/

066.时钟A-B

note：

1.<ctime>是得学着用用，挺有用的；你甚至可以用ctime生成随机数，比rand()的假随机要好；

2.然鹅，很多情况下，<ctime>的计时并不准确，尤其是ms尺度，这个时候建议改用<chrono>；

3.某种程度上，你可以用chrono全面代替ctime,因为chrono是C++11标准库的一部分，更现代，更易用，更好；

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <ctime>#include <iomanip>using namespace std;int main(){    tm begin = {0}, end = {0};    cin >> end.tm_year >> end.tm_mon >> end.tm_mday;    cin >> begin.tm_year >> begin.tm_mon >> begin.tm_mday;    begin.tm_year -= 1900;    begin.tm_mon -= 1;    end.tm_year -= 1900;    end.tm_mon -= 1;    time_t tmBegin =  mktime(&begin);    time_t tmEnd = mktime(&end);    double difference = difftime(tmEnd, tmBegin);    cout << fixed<<setprecision(6)<<difference << endl;    return 0;}/*Sample input:2021 1 22021 1 1Sample output:86400.000000*//*Additional input:2024 1 12024 1 2Additional output:-86400.000000*/

067.Arduino显示

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;static const int digit[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};int getUnit(int num) {    int cnt = 0;    do {        cnt += digit[num % 10];        num /= 10;    } while (num);    return cnt;}int main() {    int n;    cin>>n;    n -= 4;    if (n <= 0) cout<<0;    else {        int cnt = 0;        for (int i = 0; i <= 1111; ++i) {            for (int j = 0; j <= 1111; ++j) {                if (getUnit(i) + getUnit(j) + getUnit(i + j) == n) ++cnt;            }        }        cout<<cnt;    }    return 0;}/*Sample input:14Sample output:2*//*Additional input:23Additional output:88*/

068.【专业融合：网安】加密字串

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;static int freq[26] = {0};int main() {    char plain[8000] = "";    int x;    cin>>plain>>x;    for (int i = 0; plain[i]; ++i) ++freq[plain[i] - 'a'];    char cipher[8000] = "";    for (int i = 0; plain[i]; ++i) {        if (freq[plain[i] - 'a'] & 1)            cipher[i] = (char) (((plain[i] - 'a' - x) % 26 + 26) % 26 + 'a');        else            cipher[i] = (char) ((plain[i] - 'a' + x) % 26 + 'a');    }    cout<<cipher;    return 0;}/*Sample input:abcda3Sample output:dyzad*//*Additional input:fdmrghm1Additional output:ecnqfgn*/

069.【专业融合：自动化】PID控制

note：

1.你别说，你还真别说，这Sample output 也忒长了吧；

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;struct PIDData {    double Kp, Ki, Kd;    double preError, integral;} ;double PIDCalculate(PIDData *pid, double setPoint, double measuredValue) {    double error = setPoint - measuredValue;    pid->integral += error;    double differential = error - pid->preError;    double output = pid->Kp * error + pid->Ki * pid->integral + pid->Kd * differential;    pid->preError = error;    return output;}int main() {    double setPoint, measuredValue;    int time;    PIDData pid = {0};    cin>>pid.Kp>>pid.Ki>>pid.Kd;    cin>>setPoint>>measuredValue>>time;    for (int i = 1; i <= time; ++i) {        double output = PIDCalculate(&pid, setPoint, measuredValue);        measuredValue += output;        printf("%d %.6lf\n", i, measuredValue);    }    return 0;}/*Sample input:0.1 0.01 0.05100 0100Sample output:1 16.0000002 25.4400003 35.0096004 44.2656645 53.1691426 61.6682107 69.7209098 77.2934489 84.35980710 90.90124011 96.90576412 102.36762413 107.28675414 111.66824115 115.52177816 118.86114217 121.70366618 124.06974419 125.98233820 127.46652421 128.54904622 129.25790923 129.62198924 129.67068125 129.43356626 128.94011727 128.21942928 127.29997729 126.20940930 124.97435931 123.62029532 122.17138533 120.65039534 119.07860335 117.47574536 115.85996837 114.24781638 112.65421939 111.09251240 109.57445641 108.11027842 106.70872243 105.37710344 104.12137845 102.94621746 101.85508147 100.85030748 99.93319049 99.10406950 98.36242051 97.70693852 97.13562753 96.64588254 96.23457455 95.89812956 95.63260557 95.43376158 95.29712959 95.21807960 95.19187461 95.21372962 95.27885763 95.38252164 95.52006665 95.68696266 95.87883267 96.09147768 96.32090469 96.56334170 96.81524971 97.07334172 97.33458273 97.59619474 97.85566575 98.11074076 98.35941977 98.59995678 98.83084779 99.05082380 99.25883881 99.45406282 99.63586283 99.80379584 99.95759085 100.09713686 100.22246987 100.33375488 100.43127689 100.51542190 100.58666791 100.64556692 100.69273693 100.72884994 100.75461595 100.77077596 100.77809297 100.77733998 100.76929199 100.754719100 100.734384*//*Additional input:NULLAdditional output:NULL*/

070.三元搜索

note：

1.三元搜索可能在一些优化的排序算法中使用到；

2.但是没有那么必要去掌握，但二分查找得会吧；

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;int terSearch(int arr[], int n, int k) {    int left = 0, right = n - 1, mid1 = (n - 1) / 3, mid2 = n - mid1;    while(mid1 != mid2) {        if (k > arr[right] || k < arr[left]) return -1;        if (k == arr[mid1]) return mid1;        if (k == arr[mid2]) return mid2;        if (mid1 == mid2) break;        if (k < arr[mid1]) right = mid1 - 1;        else if (k > arr[mid2]) left = mid2 + 1;        else left = mid1 + 1, right = mid2 - 1;        mid1 = left + (right - left) / 3, mid2 = right - (right - left) / 3;    }    return -1;}int main() {    int n, k;    cin>>n;    int arr[n];    for (int i = 0; i < n; ++i) cin>>arr[i];    cin>>k;    printf("%d in [%d]", k, terSearch(arr, n, k));    return 0;}/*Sample input:101 2 3 4 5 6 7 8 9 105Sample output:5 in [4]*//*Additional input:1011 16 18 19 21 34 53 55 69 7055Additional output:55 in [7]*/

第8季（071-080）

071.【专业融合：数学】中位数

note：

1.实质上就是排序，试着使用STL里的vector容器，体验一把C++的力量吧；

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <vector>#include <iomanip>using namespace std;int main() {    vector<int> arr;    int tmp;    int cnt=0;    int count[100]={0};    cin>>tmp;    while(tmp>=0) {        arr.push_back(tmp);        if (tmp == 0) {            cnt++;        }else{            count[cnt]++;        }        cin >> tmp;    }    vector<int> print;    for(int i=0;i<arr.size();++i){        if(arr[i]>0){            print.push_back(arr[i]);        }    }    int sum[100]={0};    for(int k=0;k<cnt;++k){        for(int l=0;l<=k;++l)        {            sum[k]+=count[l];        }    }    for(int k=0;k<cnt;++k){        for(int i=0;i<sum[k];++i){            cout<<print[i]<<' ';        }        double ans;        if(sum[k]%2==0){            ans=(print[sum[k]/2]+print[sum[k]/2-1])/2.0;        }        else ans=print[sum[k]/2];        cout<<fixed<<setprecision(6)<<ans<<endl;    }}/*Sample input:1 2 3 4 5 07 8 9 0-1Sample output:1 2 3 4 5 3.0000001 2 3 4 5 7 8 9 4.500000*//*Additional input:145 15 163 13609 135 015 3614 16345 13051 16349 14 0-1Additional output:145 15 163 13609 135 163.000000145 15 163 13609 135 15 3614 16345 13051 16349 14 15.000000*/

072.【专业融合：航天】卫星定位

note：

1.不是我说，这俩卫星的题目（另一道GPS），主打一个人间不值得；

//Difficulty:??/10//Importance: 0/10#include <iostream>#include <cmath>#define N 11#define c 299792.458using namespace std;double X[N],A[N],B[N],C[N],T[N];void scanf1(double A[N],int n){    for(int i=0;i<n;i++) {        cin >> A[i];    }}void print1(double A[N],int n) { //输出一个矢量    int i,tmp;    double a;    for (i=0; i<n-1; i++){        tmp=(int)(A[i]*10000);        a=(double)tmp/10000.0;        printf("%.4lf,",a);    }    tmp=(int)(A[n-1]*10000);    a=(double)tmp/10000.0;    printf("%.4lf",a);}void print2(double A[N][N],int n) { //输出一个矩阵    int i, j;    for (i=0; i<n; i++) {        for (j=0; j<n; j++)            printf("%.7lf ", A[i][j]);        printf("\n");    }}// 计算代数余子式函数，结果=destint GetCoFactor(double dest[N][N], double src[N][N], int row, int col, int n){    int i, j;    int colCount=0,rowCount=0;    for(i=0; i<n; i++ ) {        if( i!=row ) {            colCount = 0;            for(j=0; j<n; j++ )                if( j != col ) { //当j不是元素时                    dest[rowCount][colCount] = src[i][j];                    colCount++;                }            rowCount++;        }    }    return 1;}// 递归计算行列式，结果=返回值double CalcDeterminant(double mat[N][N], int n){    int i,j;    double det = 0; //行列式值    double minor[N][N]; // allocate 余子式矩阵    // n 必须 >= 0，当矩阵是单个元素时停止递归    if( n == 1 ) return mat[0][0];    for(i = 0; i < n; i++ ) {        GetCoFactor(minor, mat, 0, i , n);        det += ( i%2==1 ? -1.0 : 1.0 ) * mat[0][i] * CalcDeterminant(minor,n-1);    }    return det;}// 伴随矩阵法矩阵求逆 , 结果存放到 inv 数组void MatrixInversion(double J[N][N], int n){    int i,j;    double det, temp [N][N], minor[N][N];    double inv[N][N];    det = 1.0/CalcDeterminant(J,n); //计算行列式    for(j=0; j<n; j++)        for(i=0; i<n; i++) {            // 得到矩阵A(j,i)的代数余子式            GetCoFactor(minor,J,j,i,n);            inv[i][j] = det*CalcDeterminant(minor,n-1);            if( (i+j)%2 == 1)                inv[i][j] = -inv[i][j];        }    //结果存回J矩阵    for(j=0; j<n; j++)        for(i=0; i<n; i++)            J[i][j] = inv[i][j];}// 由Xn计算函数Fn，结果存放到 Fvoid CalcF(double F[N],double X[N],int n) {    double f;    int i;    for (i=0; i<n; i++) {        switch (i+1) {            case 1:                f=X[0]*X[0]+X[1]*X[1]-2*X[0]-X[2]+1; //x^2+y^2-2x-z+1                break;            case 2:                f=X[0]*X[1]*X[1]-X[0]-3*X[1]+X[1]*X[2]+2; //xy^2-x-3y+yz+2                break;            case 3:                f=X[0]*X[2]*X[2]-3*X[2]+X[1]*X[2]*X[2]+X[0]*X[1]; //xz^2-3z+yz^2+xy                break;        }        F[i]=f;    }}void CalcF_re(double F[N],double X[N],int n) {    double f;    int i;    for (i=0; i<n; i++) {        switch (i+1) {            case 1:                f=(X[0]-A[0])*(X[0]-A[0])+(X[1]-B[0])*(X[1]-B[0])+(X[2]-C[0])*(X[2]-C[0])-(c*(T[0]-X[3]))*(c*(T[0]-X[3]));                break;            case 2:                f=(X[0]-A[1])*(X[0]-A[1])+(X[1]-B[1])*(X[1]-B[1])+(X[2]-C[1])*(X[2]-C[1])-(c*(T[1]-X[3]))*(c*(T[1]-X[3]));                break;            case 3:                f=(X[0]-A[2])*(X[0]-A[2])+(X[1]-B[2])*(X[1]-B[2])+(X[2]-C[2])*(X[2]-C[2])-(c*(T[2]-X[3]))*(c*(T[2]-X[3]));                break;            case 4:                f=(X[0]-A[3])*(X[0]-A[3])+(X[1]-B[3])*(X[1]-B[3])+(X[2]-C[3])*(X[2]-C[3])-(c*(T[3]-X[3]))*(c*(T[3]-X[3]));        }        F[i]=f;    }}// 由Xn计算偏导数Jacobian矩阵F'n，结果存放到 Jvoid CalcJ(double J[N][N],double X[N],int n) {    double f;    int i,j;    for (i=0; i<n; i++)        switch (i+1) {            case 1:                for (j=0; j<n; j++) {                    switch (j+1) {                        case 1: f=2*X[0]-2;break; // J1.1=2x-2                        case 2: f=2*X[1];break; // J1.2=2y                        case 3: f=-1;break;  // J1.3=-1                    }                    J[i][j]=f;                }                break;            case 2:                for (j=0; j<n; j++) {                    switch (j+1) {                        case 1: f=X[1]*X[1]-1;break; // J2.1=y^2-1                        case 2: f=2*X[0]*X[1]-3+X[2];break; // J2.2=2xy-3+z                        case 3: f=X[1];break; // J2.3=y                    }                    J[i][j]=f;                }                break;            case 3:                for (j=0; j<n; j++) {                    switch (j+1) {                        case 1: f=X[2]*X[2]+X[1];break; // J3.1=z^2+y                        case 2: f=X[2]*X[2]+X[0];break; // J3.2=z^2+x                        case 3: f=2*X[0]*X[2]-3+2*X[1]*X[2];break; // J3.3=2xz-3+2yz                    }                    J[i][j]=f;                }                break;        }}// 由Xn计算偏导数Jacobian矩阵F'n，结果存放到 Jvoid CalcJ_re(double J[N][N],double X[N],int n) {    double f;    int i,j;    for (i=0; i<n; i++)        switch (i+1) {            case 1:                for (j=0; j<n; j++) {                    switch (j+1) {                        case 1: f=2*(X[0]-A[0]);break; // J1.1=2(x-A1)                        case 2: f=2*(X[1]-B[0]);break; // J1.2=2(y-B1)                        case 3: f=2*(X[2]-C[0]);break;  // J1.3=2(z-C1)                        case 4: f=2*c*c*(T[0]-X[3]);break;//J1.4=2*c^2(t1-d)                    }                    J[i][j]=f;                }                break;            case 2:                for (j=0; j<n; j++) {                    switch (j+1) {                        case 1: f=2*(X[0]-A[1]);break; // J1.1=2(x-A1)                        case 2: f=2*(X[1]-B[1]);break; // J1.2=2(y-B1)                        case 3: f=2*(X[2]-C[1]);break;  // J1.3=2(z-C1)                        case 4: f=2*c*c*(T[1]-X[3]);break;//J1.4=2*c^2(t1-d)                    }                    J[i][j]=f;                }                break;            case 3:                for (j=0; j<n; j++) {                    switch (j+1) {                        case 1: f=2*(X[0]-A[2]);break; // J1.1=2(x-A1)                        case 2: f=2*(X[1]-B[2]);break; // J1.2=2(y-B1)                        case 3: f=2*(X[2]-C[2]);break;  // J1.3=2(z-C1)                        case 4: f=2*c*c*(T[2]-X[3]);break;//J1.4=2*c^2(t1-d)                    }                    J[i][j]=f;                }                break;            case 4:                for (j=0; j<n; j++) {                    switch (j+1) {                        case 1: f=2*(X[0]-A[3]);break; // J1.1=2(x-A1)                        case 2: f=2*(X[1]-B[3]);break; // J1.2=2(y-B1)                        case 3: f=2*(X[2]-C[3]);break;  // J1.3=2(z-C1)                        case 4: f=2*c*c*(T[3]-X[3]);break;//J1.4=2*c^2(t1-d)                    }                    J[i][j]=f;                }                break;        }}// 计算 J^-1* F，结果存放到 Rvoid CalcJF(double R[N], double J[N][N], double F[N], int n) {    int i,j,k;    for (i=0; i<n; i++) {        R[i]=0.0;        for (j=0; j<n; j++)            R[i] = R[i] + J[i][j]*F[j];    }}// 计算 X=X0-R，结果存放到 Xvoid CalcX(double X[N],double X0[N],double R[N],int n) {    int i;    for (i=0; i<n; i++)        X[i]=X0[i]-R[i];}// 计算 A=B，结果存放到 Avoid AequB(double A[N],double B[N],int n) {    int i;    for (i=0; i<n; i++)        A[i]=B[i];}// 计算 F-double Ferror(double F[N], int n) {    double m=0;    int i;    for (i=0; i<n; i++) {        double t=fabs(F[i]);        if (m<t) m = t;    }    return m;}// Newton–Raphson method 牛顿迭代法求非线性方程组的根，存放到X0void mvNewtons(double X0[N], int n, double e) {    // Guess为初始猜测值 e为迭代精度要求    int k;    double J[N][N],Y[N][N];    double X[N],R[N],F[N];    //X0一开始为初始猜测值    for (k=1; k<=20; k++) { //限定20次迭代        /*printf("-------------- n=%d\n",k);printf("X\n");print1(X0,n); //输出X0        */        CalcF_re(F,X0,n); //计算F矩阵        /*printf("F\n"); //观察 Fprint1(F,n); //输出F        */        CalcJ_re(J,X0,n); //计算Jacobian矩阵F'n(x0)        /*printf("J\n");print2(J,n); //观察 J        */        MatrixInversion(J, n); // 求J的逆矩阵 J^-1        CalcJF(R,J,F,n); // R=J^-1 * F        CalcX(X,X0,R,n); // X=X0-R        AequB(X0,X,n); // X0=X 下次迭代        if (Ferror(F,n)<e) break; //达到精度要求，终止迭代    }}int main() {    int n=4;    cin>>A[0]>>B[0]>>C[0];    cin>>A[1]>>B[1]>>C[1];    cin>>A[2]>>B[2]>>C[2];    cin>>A[3]>>B[3]>>C[3];    scanf1(T,n);    scanf1(X,n);    mvNewtons(X,n,1e-6); //根存放在X    print1(X,3);    return 0;}/*Sample input:15600 7540 2014018760 2750 1861017610 14630 1348019170 610 183900.07074 0.07220 0.07690 0.072420 0 6370 0Sample output:-41.7727,-16.7891,6370.0595*//*Additional input:NULLAdditional output:NULL*/

073.【专业融合：机械】几何约束

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;int maxi(int a, int b) {    return a > b ? a : b;}int mini(int a, int b) {    return a < b ? a : b;}int cross(int x1, int y1, int x2, int y2) {    return x1 * y2 - y1 * x2;}bool insert(int line1[4], int line2[4]) {    if (maxi(line2[0], line2[2]) < mini(line1[0], line1[2]) ||        maxi(line1[0],line1[2]) < mini(line2[0], line2[2]) ||        maxi(line2[1], line2[3]) < mini(line1[1], line1[3]) ||        maxi(line1[1], line2[3]) < mini(line2[1],line2[3])) return false;    if (cross(line1[2] - line1[0], line1[3] - line1[1], line2[0] - line1[0], line2[1] - line1[1]) *        cross(line1[2] - line1[0], line1[3] - line1[1], line2[2] - line1[0], line2[3] - line1[1]) > 0 ||        cross(line2[2] - line2[0], line2[3] - line2[1], line1[0] - line2[0], line1[1] - line2[1]) *        cross(line2[2] - line2[0], line2[3] - line2[1], line1[2] - line2[0], line1[3] - line2[1]) > 0) return false;    return true;}int main() {    int n;    cin>>n;    int line[n][4];    for (int i = 0; i < n; ++i)        for (int j = 0; j < 4; ++j) cin>>line[i][j];    int cnt = 0;    for (int i = 0; i < n; ++i) {        for (int j = i + 1; j < n; ++j) {            if (insert(line[i], line[j])) {                cout<<"X: #"<<i + 1<<" #"<<j + 1<<endl;                ++cnt;            }        }    }    cout<<"n="<<cnt;    return 0;}/*Sample input:51 5 4 52 5 10 13 2 10 36 4 9 47 1 8 1Sample output:X: #1 #2X: #2 #3n=2*//*Additional input:51 5 4 92 5 10 33 2 10 66 4 9 457 1 8 0Additional output:X: #2 #3X: #2 #4n=2*/

074.【专业融合：天文】日出日落时间

note：

1.你瓜甚至没有天文专业，这整的多生硬；你甚至还要输出正午的时间，为啥要叫“日出日落时间”；

2.第三个无人AC的题目；

3.主要问题在于，题目里给的链接根本打不开，不知道他用的是什么样的NOAA算法，就不知道算法的每一步的精度、误差是如何产生的；所以就算自己写一个NOAA算法，也势必得不到和题目里一样的结果；

4.所以，下面的代码只是一个例子，只能WA，图一乐；

//Difficulty:??/10//Importance: 0/10//3th none AC you meet#include <cmath>#include <iostream>#include <iomanip>#define M_PI 3.14159265358979323846using namespace std;double degToRad(double deg) {    return deg * M_PI / 180.0;}double calcSolarDeclination(int dayOfYear) {    return 0.4093 *  sin((2.0 * M_PI / 365.0) * dayOfYear - 1.405);}double calcTime(int year, int month, int day, double longitude, double latitude, bool sunrise, int timezone) {    int dayOfYear = (month - 1) * 30 + day;    double declination = calcSolarDeclination(dayOfYear);    double time = 12.0 + (sunrise ? -1 : 1) *  acos(( sin(degToRad(-0.83)) -  sin(degToRad(latitude)) *  sin(declination)) / ( cos(degToRad(latitude)) *  cos(declination))) / M_PI * 180.0 / 15.0;    return time - 4.0 * longitude / 60.0 + timezone;}int main() {    int year, month, day, timezone;    double longitude, latitude;    cin >> year >> month >> day ;    cin >> longitude >> latitude ;    cin >> timezone;    double sunrise = calcTime(year, month, day, longitude, latitude, true, timezone);    double sunset = calcTime(year, month, day, longitude, latitude, false, timezone);    double noon = calcTime(year, month, day, longitude, latitude, false, timezone) - (sunset - sunrise) / 2;    cout <<"Solar Noon="<<  setfill('0') <<  setw(2) << int(noon) << ":" <<  setw(2) << int((noon - int(noon)) * 60) << ":" <<  setw(2) << int(((noon - int(noon)) * 60 - int((noon - int(noon)) * 60)) * 60) <<  endl;    cout <<"   Sunrise="<<  setfill('0') <<  setw(2) << int(sunrise) << ":" << setw(2) << int((sunrise - int(sunrise)) * 60) << ":" <<  setw(2) << int(((sunrise - int(sunrise)) * 60 - int((sunrise - int(sunrise)) * 60)) * 60) <<  endl;    cout <<"    Sunset="<<  setfill('0') <<  setw(2) << int(sunset) << ":" <<  setw(2) << int((sunset - int(sunset)) * 60) << ":" <<  setw(2) << int(((sunset - int(sunset)) * 60 - int((sunset - int(sunset)) * 60)) * 60) <<  endl;    return 0;}/*Sample input:2022 8 15108.760064 34.035672Sample output:*//*Additional input:NULLAdditional output:NULL*/

075.成绩单

1.结构体是一定要会滴，尽管这题题干让用C的方式写结构体，但是最好直接用C++风格的方式；

2.最好还要掌握结构体写入写出文件；

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;typedef struct tag {    long long id;    char name[31];    int score;} ST;void load(ST* arr[], int n) {    for (int i = 0; i < n; ++i) {        arr[i] = (ST*) malloc(sizeof(ST));        cin>>arr[i]->id>>arr[i]->name>>arr[i]->score;    }}void sort(ST* arr[], int n) {    ST* tmp = NULL;    for (int i = 0; i < n; ++i) {        bool isSwapped = false;        for (int j = 0; j < n - 1 - i; ++j)            if ((arr[j]->score < arr[j + 1]->score) ||                (arr[j]->score == arr[j + 1]->score && arr[j]->id > arr[j + 1]->id))                tmp = arr[j], arr[j] = arr[j + 1], arr[j + 1] = tmp, isSwapped = true;        if (!isSwapped) break;    }}void traverse(ST* arr[], int n) {    for (int i = 0; i < n; ++i)        cout<<arr[i]->id<<' '<<arr[i]->name<<' '<<arr[i]->score<<endl;}int main() {    int n;    cin>>n;    ST* grade[n];    load(grade, n);    sort(grade, n);    traverse(grade, n);    return 0;}/*Sample input:62001900001 Jerry 882001900005 Tom 922001900006 Milla 852001900002 Alice 802001900003 Mickey 852001900004 Aladdin 83Sample output:2001900005 Tom 922001900001 Jerry 882001900003 Mickey 852001900006 Milla 852001900004 Aladdin 832001900002 Alice 80*//*Additional input:NULLAdditional output:NULL*/

076.【专业融合：材料】晶体结构

note：

1.专业融合真是一锅乱炖啊，什么都融只会害了你！

2.这题目整的多牵强；

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <string>#include <iomanip>#include <cmath>using namespace std;struct Atom{    string name;    double mass;    double APF;    double r;};Atom elemList[] =        {                { "Po",   208.998, 0.52360, 1.68 },                { "Li",     6.941, 0.68017, 1.52 },                { "Na", 22.989770, 0.68017, 1.86 },                { "Cr",   51.9961, 0.68017, 1.28 },                { "Mn", 54.938049, 0.68017, 1.27 },                { "Fe",    55.845, 0.68017, 1.26 },                { "Mo",     95.94, 0.68017, 1.39 },                { "Ta",  180.9749, 0.68017, 1.46 },                { "Al", 26.981538, 0.74048, 1.43 },                { "Ca",    40.078, 0.74048, 1.97 },                { "Ni",   58.6934, 0.74048, 1.24 },                { "Cu",    63.546, 0.74048, 1.28 },                { "Ge",     72.64, 0.74048, 1.22 },                { "Ag",  107.8682, 0.74048, 1.44 },                { "Pt",   195.078, 0.74048, 1.39 },                { "Au", 196.96655, 0.74048, 1.44 },                { "Pb",     207.2, 0.74048, 1.75 }        };template <int N> double pow(double a) { return a * pow<N - 1>(a); }template <> double pow<0>(double a) { return 1; }int main(){    int n;    cin >> n;    for (int i = 0; i < n; ++i)    {        string in;        cin >> in;        for(const auto& e : elemList)        {            if(e.name == in)            {                double V = 4.0 * M_PI * pow<3>(e.r) / 3.0;                cout << fixed << setprecision(2) << 10.0 * e.mass * e.APF / 6.022 / V << endl;                break;            }        }    }    return 0;}/*Sample input:3PoMoCuSample output:9.159.638.89*//*Additional input:NULLAdditional output:NULL*/

077.【专业融合：化学】原子计数

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <map>using namespace std;string s;int getnum(int x){    int res = 0;    while (true)    {        char ch = s[x];        if(ch >='0'&& ch<='9' && s[x])        {            res = res * 10 + ch - '0';            ++ x;        }        else return res;    }    return res;}int main(){    getline(cin, s);    map<string, int> ump;    for (int i = 0; s[i]; i ++)    {        char ch = s[i];        if(!(ch>='A' && ch<='Z'))continue;        char ch1 = s[i+1];        if (ch1>='a' && ch1<='z')        {            string ele = "";            ele.append(1, ch);            ele.append(1, ch1);            int num = getnum(i+2);            if(num)            {                if(!ump.count(ele)) ump[ele] = num;                else ump[ele] += num;            }            else            {                if(!ump.count(ele)) ump[ele] = 1;                else ump[ele] += 1;            }        }        else        {            int num = getnum(i+1);            string ele = "";            ele.append(1, ch);            if(num)            {                if(!ump.count(ele)) ump[ele] = num;                else ump[ele] += num;            }            else            {                if(!ump.count(ele)) ump[ele] = 1;                else ump[ele] += 1;            }        }    }    for (auto& p : ump)    {        cout << p.first << " " << p.second << endl;    }}/*Sample input:Fe2H3OHSample output:Fe 2H 4*//*Additional input:H2OAdditional output:H 2O 1*/

078.【专业融合：动能】热能计算

note：

1.写到这题就好好笑吧，毕竟表示百分数的这种写法真没见过?，绷不住了；

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;int main() {    int Ti, Tf, cL, cV;    double mL, mV;    cin>>Ti>>Tf>>mL>>cL>>mV>>cV;    double QL = cL * mL * (Tf - Ti);    double QV = cV * mV * (Tf - Ti);    double Q = QL + QV;    printf("%.2lfkJ,%.2lf%%,%.2lf%%\n", Q / 1000, QV / Q, QL / Q);    return 0;}/*Sample input:20 800.250 41860.500 900Sample output:89.79kJ,0.30%,0.70%*//*Additional input:NULLAdditional output:NULL*/

079.【专业融合：力学】火箭发射模拟

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <iomanip>using namespace std;const double timeStep = 0.1;int main(){    double totalMass, rocketMass, burnTime, cE, g;    cin >> totalMass >> rocketMass >> burnTime >> cE >> g;    double propellantMass = totalMass - rocketMass;    double massFlow = propellantMass / burnTime;    double T = massFlow * cE;    double altitude = 0, V = 0;    double timeLeft = burnTime + timeStep;    while(timeLeft >= 0)    {        double a = T / totalMass;        double deltaV = a * timeStep;        double deltaAltitude = V * timeStep;        double deltaM = massFlow * timeStep;        V += deltaV;        altitude += deltaAltitude;        totalMass -= deltaM;        timeLeft -= timeStep;    }    cout << fixed << setprecision(3) << altitude / 1000 << "km" << endl;    return 0;}/*Sample input:100000 10000 100 4000 9.81Sample output:298.766km*//*Additional input:NULLAdditional output:NULL*/

080.【专业融合：航海】水下声学定位

note：

1.自此和【专业融合】告别了，doge；

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <cmath>#define PI 3.1415926using namespace std;double area(double AB,double BC,double CD,double DA,double diagonal){    double s1= (AB + BC + diagonal)/2;    double s2 = (CD + DA + diagonal)/2;    double area1 = sqrt(s1 * (s1 - AB) * (s1 - BC) * (s1 - diagonal));    double area2 = sqrt(s2 * (s2 - CD) * (s2 - DA) * (s2 - diagonal));    return area1 +area2;}double angle(double AB,double BC,double CD,double DA,double diagonal,double area){    double angle=(4 *area )/(BC * BC + DA * DA - AB * AB - CD * CD);    return atan(angle)*180.0/PI;}int main(){    double ab,bc,cd,da,ac;    cin>>ab>>bc>>cd>>da>>ac;    double areaout=area(ab,bc,cd,da,ac);    double angleout=angle(ab,bc,cd,da,ac,areaout);    printf("%.6lf %.1lf",areaout,angleout);}/*Sample input:7 5 5 7 6Sample output:29.293877 90.0*//*Additional input:NULLAdditional output:NULL*/

第9季（081-090）

081.【算法策略：动态规划】上楼梯

note：

1.这一季都是算法，挺重要的，好好掌握；

//Difficulty: 2/10//Importance: 2/10//version 1:better#include <iostream>#include <cstring>using namespace std;int main() {    int n, m;    cin>>n>>m;    long long dp[n + 1];    memset(dp, -1, (n + 1) * sizeof(long long));    for (int i = 0; i < m; ++i) {        int tmp;        cin>>tmp;        dp[tmp] = 0;    }    dp[1] = dp[1] ? 1 : 0;    dp[2] = dp[2] ? (dp[1] ? 2 : 1) : 0;    for (int i = 3; i <= n; ++i)        if(dp[i]) dp[i] = (dp[i - 1] + dp [i - 2]) % (long long) (1e9 + 7);    cout<<dp[n]<<endl;    return 0;}//version 2:#include <iostream>#include <vector>#include <algorithm>using namespace std;int main() {    int N, M;    cin >> N >> M;    vector<int> badSteps(M);    for (int i = 0; i < M; i++) {        cin >> badSteps[i];    }    vector<long long> dp(N + 1, 0);    dp[0] = 1;    dp[1] = (find(badSteps.begin(), badSteps.end(), 1) == badSteps.end()) ? 1 : 0;    for (int i = 2; i <= N; i++) {        if (find(badSteps.begin(), badSteps.end(), i) == badSteps.end()) {            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;        }    }    cout << dp[N] << endl;    return 0;}/*Sample input:6 13Sample output:4*//*Additional input:6 15Additional output:5*/

082.【算法策略：贪心】三角形

//Difficulty: 2/10//Importance: 2/10//version 1:#include <iostream>#include <vector>#include <algorithm>using namespace std;int main() {    int n;    cin >> n;    vector<int> sticks(n);    for (int i = 0; i < n; i++) {        cin >> sticks[i];    }    sort(sticks.begin(), sticks.end(), greater<int>());    for (int i = 0; i < n - 2; i++) {        if (sticks[i] < sticks[i + 1] + sticks[i + 2]) {            vector<int> sides = {sticks[i], sticks[i + 1], sticks[i + 2]};            sort(sides.begin(), sides.end());            cout << sides[0] << " " << sides[1] << " " << sides[2] << endl;            return 0;        }    }    cout << -1 << endl;    return 0;}//version 2:more basic#include <iostream>#include <ctime>using namespace std;void quickSort(int arr[], int left, int right) {    if (left >= right) return;    srand(time(NULL));    int idx = rand() % (left - right) + left;    int flag = arr[idx], head = left - 1, tail = right + 1;    while (head < tail) {        do head++; while(arr[head] < flag);        do tail--; while(arr[tail] > flag);        if (head < tail) {            int tmp = arr[head];            arr[head] = arr[tail];            arr[tail] = tmp;        }    }    quickSort(arr, left, tail);    quickSort(arr, tail + 1, right);}void findTri(int arr[], int n) {    for (int i = n - 1; i > 1; --i)        if (arr[i] < arr[i - 1] + arr[i - 2]) {            cout<<arr[i - 2]<<arr[i - 1]<<arr[i]<<endl;            return;        }    cout<<-1<<endl;}int main() {    int n;    cin>>n;    int arr[n];    for (int i = 0; i < n; ++i) cin>>arr[i];    quickSort(arr, 0, n - 1);    findTri(arr, n);    return 0;}/*Sample input:61 8 5 2 4 3Sample output:4 5 8*//*Additional input:NULLAdditional output:NULL*/

083.【算法策略：优雅的策略】危险的组合（递推、动态规划、打表）

note:

1.什么叫打表？就是先把每种情况对应的结果都算出来，存好，要的时候直接用，不用再算了；

2.那一开始怎么算捏？由于最后程序是直接打表的，你只需要先写个程序把每种结果给算出来，然后搬到第二个程序里；所以，算法再暴力，再无脑也没事，算得出来就行。

//Difficulty: 2/10//Importance: 2/10//version 1:#include <iostream>#include <cmath>using namespace std;int count(int n) {    if (n < 3) {        return 0;    } else if (n == 3) {        return 1;    } else if (n == 4) {        return 3;    } else {        return 2 * count(n - 1) + pow(2, n - 4) - count(n - 4);    }}int main() {    int n;    while (cin >> n && n > 0) {        cout << count(n) << endl;    }}//version 2:violent,then table lookup//calculate by -> tmp & (tmp >> 1) & (tmp >> 1)#include <iostream>using namespace std;long long w[] = {0, 0, 0, 1, 3, 8, 20, 47, 107, 238, 520, 1121,2391, 5056, 10616, 22159, 46023, 95182, 196132, 402873, 825259,1686408, 3438828, 6999071, 14221459, 28853662, 58462800,118315137, 239186031, 483072832, 974791728};int main(){    int n;    while (cin >> n, n)    {        if (n <= 0) exit(0);        cout << w[n] << endl;    }    return 0;}/*Sample input:123450Sample output:00138*//*Additional input:NULLAdditional output:NULL*/

084.【算法策略：贪心】汤包

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <ctime>using namespace std;struct Tag {    int guest;    int end;};void quickSort(Tag* arr[], int left, int right) {    if (left >= right) return;    srand(time(NULL));    int idx = rand() % (left - right) + left;    int flag = arr[idx]->end, head = left - 1, tail = right + 1;    while (head < tail) {        do head++; while(arr[head]->end < flag);        do tail--; while(arr[tail]->end > flag);        if (head < tail) {            Tag *tmp = arr[head];            arr[head] = arr[tail];            arr[tail] = tmp;        }    }    quickSort(arr, left, tail);    quickSort(arr, tail + 1, right);}void traverse(Tag *arr[], int n) {    for (int i = 0; i < n; ++i)        cout<<arr[i]->guest<<' ';}int main() {    int n;    cin>>n;    Tag *arr[n];    for (int i = 0; i < n; ++i) {        arr[i] = (Tag*)malloc(sizeof(Tag));        arr[i]->guest = i + 1;        int begin, duration;        cin>>begin>>duration;        arr[i]->end = begin + duration;    }    quickSort(arr, 0, n -1);    traverse(arr, n);    return 0;}/*Sample input:33 31 32 3Sample output:2 3 1*//*Additional input:NULLAdditional output:NULL*/

085.【算法策略：回溯】和字符串

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <cstring>using namespace std;long long substrToNum(char str[], int pos, int len) {    long long num = 0;    for (int i = 0; i < len; ++i)        num = num * 10 + str[pos + i] - '0';    return num;}long long getLen(long long n) {    int cnt = 0;    do ++cnt, n /= 10; while(n);    return cnt;}bool backTracking(char str[], int strLen, int begin, int len1, int len2) {    if (begin + len1 + len2 >= strLen) return true;    long long num1 = substrToNum(str, begin, len1);    long long num2 = substrToNum(str, begin + len1, len2);    long long num3 = substrToNum(str, begin + len1 + len2, getLen(num1 + num2));    if (num1 + num2 == num3) return backTracking(str, strLen, begin + getLen(num1), getLen(num2), getLen(num3));    return false;}void partition(char str[]) {    int strLen = strlen(str);    for (int i = 1; i <= strLen / 2; ++i) {        if (backTracking (str, strLen, 0, i, i)) {            cout<<"true\n";            return;        }    }    cout<<"false\n";}int main() {    char str[1000] = "";    cin>>str;    partition(str);    return 0;}/*Sample input:1212243660Sample output:true*//*Additional input:NULLAdditional output:NULL*/

086.【算法策略：贪心】绝对差

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <ctime>#include <climits>#include <cstdlib>using namespace std;void quickSort(int arr[], int left, int right) {    if (left >= right) return;    srand(time(NULL));    int idx = rand() % (left - right) + left;    int flag = arr[idx], head = left - 1, tail = right + 1;    while (head < tail) {        do head++; while(arr[head] < flag);        do tail--; while(arr[tail] > flag);        if (head < tail) {            int tmp = arr[head];            arr[head] = arr[tail];            arr[tail] = tmp;        }    }    quickSort(arr, left, tail);    quickSort(arr, tail + 1, right);}int minAbsSub(int arr[], int n) {    int min = INT_MAX;    for (int i = 0; i < n - 1; ++i) {        int tmp = arr[i + 1] - arr[i];        if (tmp < min) min = tmp;    }    return min;}int main() {    int n;    cin>>n;    int arr[n];    for (int i = 0; i < n; ++i) cin>>arr[i];    quickSort(arr, 0, n - 1);    cout<<minAbsSub(arr, n);    return 0;}/*Sample input:33 -7 0Sample output:3*//*Additional input:NULLAdditional output:NULL*/

087.【算法策略：分治】子数列最大和

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <cstring>using namespace std;int maxSum(int arr[], int n) {    int dp[n];    memset(dp, 0, n * sizeof(int));    int maxi = arr[0];    dp[0] = arr[0];    for (int i = 1; i < n; ++i) {        dp[i] = arr[i] > (dp[i - 1] + arr[i]) ? arr[i] : (dp[i - 1] + arr[i]);        maxi = dp[i] > maxi ? dp[i] : maxi;    }    return maxi;}int main() {    int n;    cin>>n;    int arr[n];    for (int i = 0; i < n; ++i) cin>>arr[i];    cout<<maxSum(arr, n)<<endl;    return 0;}/*Sample input:72 -4 1 9 -6 7 -3Sample output:11*//*Additional input:NULLAdditional output:MULL*/

088.【算法策略：动态规划】挑选

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <climits>#include <cstdlib>#include <ctime>using namespace std;void quickSort(long long arr[], long long left, long long right) {    if (left >= right) return;    srand(time(NULL));    long long idx = rand() % (left - right) + left;    long long flag = arr[idx], head = left - 1, tail = right + 1;    while (head < tail) {        do head++; while(arr[head] < flag);        do tail--; while(arr[tail] > flag);        if (head < tail) {            long long tmp = arr[head];            arr[head] = arr[tail];            arr[tail] = tmp;        }    }    quickSort(arr, left, tail);    quickSort(arr, tail + 1, right);}long long maxi(long long arr[], long long n) {    long long max = LLONG_MIN;    for (long long i = 0; i < n; ++i)        if (max < arr[i]) max = arr[i];    return max;}long long sumMax(long long arr[], long long n) {    long long dp[n];    dp[0] = arr[0];    for (long long i = 1; i < n; ++i) {        if (arr[i] == arr[i - 1])            dp[i] = dp[i - 1] > (arr[i] + dp[i - 1]) ? dp[i - 1] : (arr[i] + dp[i - 1]);        else {            long long j = i - 1;            while (j >= 0 && arr[j] >= arr[i] - 1) --j;            dp[i] = arr[i] + (j >= 0 ? dp[j] : 0);        }    }    return maxi(dp, n);}int main() {    long long n;    cin>>n;    long long arr[n];    for (long long i = 0; i < n; ++i) cin>>arr[i];    quickSort(arr, 0, n - 1);    cout<<sumMax(arr, n)<<endl;    return 0;}/*Sample input:31 2 3Sample output:4*//*Additional input:NULLAdditional output:NULL*/

089.【算法策略：动态规划】打字机

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <cstring>using namespace std;long long dp[100];long long seg[100] = {0};long long method(char str[]) {    memset(dp, -1, 100 * sizeof(long long));    char *iter = str;    int part = 0, ans = 1;    seg[part] = 1;    while (*iter) {        if (*iter == 'm' || *iter == 'w') return 0;        if (*iter == 'n' && *(iter + 1) == 'n') {            int cnt = 1;            dp[0] = 1, dp[1] = 2, iter += 2;            while(*iter == 'n') {                ++cnt, ++iter;                dp[cnt] = dp[cnt - 1] + dp[cnt - 2];            }            seg[++part] = dp[cnt];        }        else if (*iter == 'u' && *(iter + 1) == 'u') {            int cnt = 1;            dp[0] = 1, dp[1] = 2, iter += 2;            while(*iter == 'u') {                ++cnt, ++iter;                dp[cnt] = dp[cnt - 1] + dp[cnt - 2];            }            seg[++part] = dp[cnt];        }        else ++iter;    }    for (int i = 0; seg[i] ; ++i) ans *= seg[i];    return ans;}int main() {    char str[1000];    cin>>str;    cout<<method(str);    return 0;}/*Sample input:ennkuuSample output:4*//*Additional input:NULLAdditional output:NULL*/

090.【算法策略：回溯】游乐园

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <cstring>using namespace std;int dist[12][12];int n, m;bool pass[12];int ans = -1;bool check(int v, int u) {    return !pass[u] && dist[v][u] != 0x3f3f3f3f;}bool noway(int v) {    for (int i = 0; i < n; ++i)        if (check(v, i)) return false;    return true;}void backTracking(int v, int l) {    if (noway(v)) {        ans = ans > l ? ans : l;        return;    }    for (int i = 0; i < n; ++i) {        if (check(v, i) && i != v) {            pass[i] = true;            backTracking(i, l + dist[v][i]);            pass[i] = false;        }    }}int main() {    cin>>n>>m;    memset(dist, 0x3f, sizeof(dist));    for (int i = 0; i < n; ++i) dist[i][i] = 0;    while (m) {        int v, u, l;        cin>>v>>u>>l;        v -= 1, u -= 1;        dist[v][u] = dist[v][u] < l ? dist[v][u] : l;        dist[u][v] = dist[v][u], --m;    }    for (int i = 0; i < n; ++i) {        memset(pass, 0, sizeof(pass));        pass[i] = true;        backTracking(i, 0);    }    cout<<ans<<endl;    return 0;}/*Sample input:4 41 2 12 3 101 3 1001 4 1000Sample output:1110*//*Additional input:NULLAdditional output:NULL*/

第10季（091-100）

091.【考试题型：字符串】左右操作

//Difficulty: 2/10//Importance: 2/10//version 1:lots of string#include <iostream>#include <string>using namespace std;string fropro(string fron){    int num=fron.size();    for(int i=0;i<num-1;++i){        for(int j=0;j<num-1;++j){            if(fron[j]<fron[j+1]){                swap(fron[j],fron[j+1]);            }        }    }    return fron;}int main(){    string str,ans,fron,lat;    cin>>str;    int len=str.size();    for(int i=0;i<len/2;++i){        fron+=str[i];    }    if(len&1){        for(int i=len-1;i>len/2;--i){            lat+=str[i];        }        ans=fropro(fron)+str[len/2]+lat;    }    else{        for(int i=len-1;i>=len/2;--i){            lat+=str[i];        }        ans=fropro(fron)+lat;    }    cout<<ans;    return 0;}//version 2:single string#include <iostream>#include<string>using namespace std;void sort(string &p,int n){    int pos=n/2-1;    for(int i=0;i<pos-1;++i){        for(int j=0;j<pos-1-i;++j){            if(p[j]<p[j+1]){                char tmp=p[j];                p[j]=p[j+1];                p[j+1]=tmp;            }        }    }}void rev(string &p,int n){    int pos=0;    if(n&1) pos=n/2+1;    else pos=n/2;    for(int i=pos,j=n-1;i<j;++i,--j){        char tmp=p[i];p[i]=p[j];p[j]=tmp;    }}int main(){    string str;    cin>>str;    int n=str.size();    sort(str,n);    rev(str,n);    cout<<str;    return 0;}/*Sample input:abcdefX181292Sample output:fedcbaX292181*//*Additional input:NULLAdditional output:NULL*/

092.【考试题型：函数（递归）】阿克曼函数

note：

1.注意给的公式有的是m+1，n+1；而不是m，n；

//Difficulty: 2/10//Importance: 2/10#include <iostream>using namespace std;int Ackermann(int m,int n){    if(m==0) return n+1;    else if(n==0) return Ackermann(m-1,1);     return Ackermann(m-1,Ackermann(m,n-1));}int main(){    int m,n;    cin>>m>>n;    cout<<Ackermann(m,n);    return 0;}/*Sample input:2 3Sample output:9*//*Additional input:NULLAdditional output:NULL*/

093.【考试题型：循环（迭代）】圆周率Π

//Difficulty: 2/10//Importance: 2/10//version 1#include <iostream>#include <iomanip>using namespace std;double an(int i){    if(i==1) return 3.0;    else if(i&1) return -4.0/(2.0*i*(2.0*i-1)*(2.0*i-2));    return 4.0/(2.0*i*(2.0*i-1.0)*(2.0*i-2.0));}int main(){    int n;    cin>>n;    double ans=0;    for(int i=1;i<n+1;++i) ans+=an(i);    cout<<fixed<<setprecision(7)<<ans;    //printf("%.7f",ans);    return 0;}//version 2:standarded answer#include <iostream>#include <iomanip>#include <cmath>using namespace std;int main() {    int n, i, d;    double pi = 0.0, t = 1.0;    cin >> n;    for (i = 2; i <= n; i++) {        d = 2 * (i - 1);        pi = pi + t / (d * (d + 1) * (d + 2));        t = -t;    }    cout << setiosflags(ios::fixed) << setprecision(7) << 3 + 4 * pi;}/*Sample input:100Sample output:3.1415929*//*Additional input:NULLAdditional output:NULL*/

094.【考试题型：输入输出】气体扩散

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <cmath>#include <iomanip>using namespace std;int main(){    double m1,m2;    cin>>m1>>m2;    cout<<fixed<<setprecision(4)<<sqrt(m2/m1);    //printf("%.4f",sqrt(m2/m1));    return 0;}/*Sample input:349.03 352.04Sample output:1.0043*//*Additional input:NULLAdditional output:NULL*/

095.【考试题型文件】平方根

//Difficulty: 2/10//Importance: 2/10//version 1#include <iostream>#include <fstream>#include <cmath>#include <iomanip>using namespace std;int main(){    int n;    cin>>n;    ofstream writef("rr.dat",ios_base::out);    if(writef.is_open()){        for(int i=1;i<n+1;++i){            writef<<fixed<<setprecision(6)<<sqrt((double)i)<<endl;//endl is must        }        writef.close();    }    ifstream oputf("rr.dat",ios_base::in);    if(oputf.is_open()){        double num;        while(oputf>>num){            cout<<fixed<<setprecision(6)<<num<<' ';        }    }    oputf.close();    return 0;}//version 2:clearer#include<iostream>#include<fstream>#include<cmath>#include<iomanip>using namespace std;int main(){    int n;    cin>>n;    ofstream ofs;    ofs.open("rr.dat",ios::out);    if(ofs.is_open()){        for(int i=1;i<n+1;++i){            ofs<<fixed<<setprecision(6)<<sqrt(i)<<endl;        }    }    ofs.close();    ifstream ifs;    ifs.open("rr.dat",ios::in);    if(ifs.is_open()){        for(int i=1;i<n+1;++i){            double x;            ifs>>x;            cout<<fixed<<setprecision(6)<<x<<' ';        }    }    ifs.close();}/*Sample input:5Sample output:1.000000 1.414214 1.732051 2.000000 2.236068*//*Additional input:NULLAdditional output:NULL*/

096.【考试题型：算法策略（递推分治贪心动态规划）】零钞

//Difficulty: 2/10//Importance: 2/10//version 1:common#include <iostream>using namespace std;int main() {    int s;    cin>>s;    int cnt[4], r = s;    cnt[0] = r / 10, r -= cnt[0] * 10;    cnt[1] = r / 5, r -= cnt[1] * 5;    cnt[2] = r / 2, cnt[3] = r - cnt[2] * 2;    if (cnt[3]) cout<<"1="<<cnt[3]<<endl;    if (cnt[2]) cout<<"2="<<cnt[2]<<endl;    if (cnt[1]) cout<<"5="<<cnt[1]<<endl;    if (cnt[0]) cout<<"10="<<cnt[0]<<endl;    return 0;}//version 2:better#include<iostream>using namespace std;int main(){    int cash[4][2]={{1,0},{2,0},{5,0},{10,0}};    int cost;    cin>>cost;    for(int i=3;i>=0;--i){        while(cost>=cash[i][0]){        cost-=cash[i][0];        cash[i][1]++;        }    }    for(int i=0;i<4;++i){        printf("%d=%d\n",cash[i][0],cash[i][1]);    }}/*Sample input:25Sample output:5=110=2*//*Additional input:NULLAdditional output:NULL*/

097.【考试题型：分支选择】马赫数

//Difficulty: 2/10//Importance: 2/10#include <iostream>#include <cmath>#include <iomanip>using namespace std;int main() {    double m,v,c,t;    cin>>v>>t;    c=331.3*sqrt(1.0+t/273.15);    m=v/(c*3.6);    string a;    if(m<0.8) a="subsonic";    else if(m<1.2) a="transonic";    else if(m<5.0) a="supersonic";    else if(m<=10.0) a="hypersonic";    cout<<fixed<<setprecision(3)<<m<<' '<<a;    return 0;}/*Sample input:920 -49.90Sample output:0.853 transonic*//*Additional input:NULLAdditional output:NULL*/

098.【考试题型：枚举】机场翻牌显示

//Difficulty: 2/10//Importance: 2/10//version 1#include <iostream>#include <string>using namespace std;int sum=0;int cha(char a,char b){    char c='Z';    char d='A';    if(a<b) return (int)b-(int)a;    else if(a==b) return 0;    else return (int)c-(int)a+1+(int)b-(int)d;}int num(char a,char b){    char d='0';    char c='9';    if(a<b) return (int)b-(int)a;    else if(a==b) return 0;    else return (int)c-(int)a+1+(int)b-(int)d;}void cal(string a,string b){    for(int i=0;i<2;++i){        sum+=cha(a[i],b[i]);    }    for(int i=2;i<6;++i){        sum+=num(a[i],b[i]);    }}int main() {    string a,b;    cin>>a>>b;    cal(a,b);    cout<<sum;    return 0;}//version 2:kind of better#include<iostream>using namespace std;int flaps(char a,char b){    if(a>='A'){        if(a<=b) return b-a;        return b-'A'+1+'Z'-a;    }    if(a<=b) return b-a;    return b-'0'+1+'9'-a;}int main(){  string sta,des;  cin>>sta>>des;  int cnt=0;  for(int i=0;i<6;++i){    cnt+=flaps(sta[i],des[i]);  }  cout<<cnt;}/*Sample input:MU2103CA8326Sample output:35*//*Additional input:MU2103MU2103Additional output:0*/

099.【考试题型：结构体】空中交通管制

//Difficulty: 2/10//Importance: 2/10//version 1:advanced std#include <iostream>#include <cmath>#include <vector>#include <string>#include <iomanip>using namespace std;struct Plane {    string id;    int x;    int y;};int main() {    int n;    cin >> n;    vector<Plane*> planes;    for (int i = 0; i < n; ++i) {        Plane* p = new Plane();        cin >> p->id >> p->x >> p->y;        planes.push_back(p);    }    double minDist = 1e9;    int idx1, idx2;    for (int i = 0; i < n - 1; ++i) {        for (int j = i + 1; j < n; ++j) {            double dist = sqrt(pow(planes[i]->x - planes[j]->x, 2) +                               pow(planes[i]->y - planes[j]->y, 2));            if (dist < minDist) {                idx1 = i;                idx2 = j;                minDist = dist;            }        }    }    cout << planes[idx1]->id << "-" << planes[idx2]->id << " " << fixed <<setprecision(4) << minDist;    // Free memory allocated for Plane objects    for (auto p : planes) {        delete p;    }    return 0;}//version 2:more common#include<iostream>#include<string>#include<cmath>using namespace std;struct Plane{ string id; int x,y;};double dis(int x1,int y1,int x2,int y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}int main(){  int n;  cin>>n;  Plane airs[n];  for(int i=0;i<n;++i){    cin>>airs[i].id>>airs[i].x>>airs[i].y;  }  double mdis=1e9;  int id0=0,id1=1;  for(int i=0;i<n;++i){    for(int j=i+1;j<n;++j){        if(mdis>=dis(airs[i].x,airs[i].y,airs[j].x,airs[j].y)){            id0=i;id1=j;mdis=dis(airs[i].x,airs[i].y,airs[j].x,airs[j].y);        }    }  }  cout<<airs[id0].id<<'-'<<airs[id1].id<<' ';  printf("%.4f",mdis);}/*Sample input:6UA057 2 3AA044 12 30BA1534 40 50DL262 5 1AF001 12 10SK837 3 4Sample output:UA057-SK837 1.4142*//*Additional input:NULLAdditional output:NULL*/

100.【考试题型：数组】重复元素

//Difficulty:??/10//Importance: 0/10//total: 97 AC, 3 WA//that's the end//hope you have properly used all these codes//otherwise all my efforts would be useless//Fight for all the beauty in this world!//May all the beauty be blessed.//version 1:dull,but straight and simple#include <iostream>#include <unordered_map>using namespace std;int main() {    int n;    cin>>n;    int arr[n];    for(int i=0;i<n;++i){        cin>>arr[i];    }    int cnt=0;    unordered_map<int, bool> countMap;    for (int i = 0; i < n; i++) {        countMap[arr[i]]=1;    }    for (int i = 0; i < n; i++) {        if(countMap[arr[i]]=1){            cnt++;        }    }    cout<<cnt-countMap.size();    return 0;}//version 2: a brilliant break#include<iostream>using namespace std;int main(){  int n;  cin>>n;  int arr[n];  for(int i=0;i<n;++i) cin>>arr[i];  int cnt=0;  for(int i=0;i<n;++i){    for(int j=i+1;j<n;++j){        if(arr[i]==arr[j]) {        cnt++;        break;        }    }  }  cout<<cnt;}/*Sample input:101 10 20 1 25 1 10 30 25 1Sample output:5*//*Additional input:NULLAdditional output:NULL*/

张士玉小黑屋

当前位置：首页 » 《关于电脑》 » 正文

西北工业大学 NOJ 2023 程序设计基础（C++） 完结撒花（已停止维护）

13 人参与 2024年11月18日 13:21 分类 : 《关于电脑》 评论

前言

必看

对于代码

代码格式

推荐工具

建议

NOJ攻略

良好的编程习惯

夹带私货

声明

总结

第1季（001-010）

001.Hello World

002.A+B

003.数据类型大小及范围

004.平均值

005.进制转换

006.浮点数输出

007.动态宽度输出

008.计算地球上两点之间的距离

009.风寒指数

010.颜色模型转换

第2季（011-020）

011.乘数模

012.方阵

013.组合数

014.比率

015.分数的加、减、乘、除法

016.幂数模

017.对称数

018.操作数

019.倍数和

020.级数和

第3季（021-030）

021.竖式乘法

022.查找数列

023.毕达哥拉斯三元组

024.余数和

025.最大数字

026.倒水

027.好数字

028.俄罗斯农夫算法

029.阶乘倍数

030.方案数

第4季（031-040）

031.素数

032.基思数

033.幂函数【C++】

034.体积计算器【C++】

035.可变参数平均

036.可变参数累加

037.运动会

038.光线追踪

039.佩尔数

040.哈沙德数

第5季（041-050）

041.完美矩阵

042.【专业融合：航空】飞机起飞速度

043.【专业融合：数学】行列式值

044.稀疏矩阵

045.【专业融合：管理】航空旅行

046.【专业融合：管理】货运优化

047.回文数之和

048.【专业融合：物理】蒙特卡罗方法求积分

049.【专业融合：计算机】波士顿房价预测

050.素数筛选法

第6季（051-060）

051.分离字符串

052.Kids A+B

053.前后缀移除

054.删除前后缀

055.AtoI转换

056.大小写交换

057.字符串替换

058.字符串切片

059.元宇宙A+B

西北工业大学 NOJ 2023 程序设计基础（C++）完结撒花（已停止维护）

13 人参与 2024年11月18日 13:21 分类 : 《关于电脑》评论

092.【考试题型：函数（递归）】阿克曼函数

评论（0）

赞助本站