极其感谢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.建议使用CLion作为编程工具，别惦记那CodeBlocks，Dev-C++了，一个太简陋，一个太老，不具有现代化工具的特点，都4202年啦，大人，时代变啦！
实在不行也得用Visual Studio，community版本免费，官网链接如下
Visual Studio 2022 IDE - 适用于软件开发人员的编程工具 (microsoft.com)
你说你只会CodeBlocks？甚至CodeBlocks都配置不明白？能不能有点学习意识，
B站上手把手教你安装配置Clion，Visual Studio的视频一抓一大把，学不会就洗洗睡吧。
你说Visual Studio下载太慢？我滴IDM可是一眨眼就下好了，你也可以试试梯子。
至于最推荐的CLion的安装、配置、使用，我就直接放大佬的文章了
CLion安装、配置、使用、调试（完全小白向）-CSDN博客
2.不会吧，不会吧，不会有人写noj是网页看一眼，切个界面再打一句代码吧，或者是每次一忘就要切回头看一眼，烦不烦呐。
什么，你说你是小机灵鬼，直接分屏，可是如果你不是外接显示器，那么点大的屏幕还分屏，折磨自己捏。
所以，在下隆重推荐Snipatse，可以直接把noj上面的题目截下来，悬浮显示在最上层，而且还可以白嫖！
官网链接Snipaste - 截图 + 贴图，不过建议直接在微软商店下载，体验更友好。至于使用方法，当然是自己去B站大学自学啦。
注：上述建议均基于Windows电脑，MacOS我真不道啊。
建议
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只会在前几季有，用于引导新手，才不是因为懒呢；
但是放心，后面的难题，或者复杂的题一般都会带注释，甚至可能中文注释；
后期会逐渐添加题目截图，有的可能不含Sample Input和Sample Output部分，但是代码最后肯定有；
如果Additional Input和Additional Output 是NULL，说明这题没必要搞额外样例，或者是太麻烦，我已经懒死了；（要是实在想要额外样例，拿我的代码随便跑几个不就行了）
有的题目，我说无人AC，是基于我的认知，可能有真的大佬，可能题目又被修改过了，反正是我这个小垃圾肯定AC不了酱紫；
严正声明：该篇Blog仅作引导作用，绝不鼓励抄袭，若因其他用途产生不良后果与本人无关。
总结
2023年秋-2024年春的C++ noj 一共100道，应该是最多AC97道的亚子；
其中 042.【专业融合：航空】飞机起飞速度
057.字符串替换
074.【专业融合：天文】日出日落时间
三道不能AC;
第1季（001-010）
001.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
//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.数据类型大小及范围
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.平均值
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.进制转换
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.浮点数输出
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.动态宽度输出
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.计算地球上两点之间的距离
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.风寒指数
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.颜色模型转换
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.乘数模
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.方阵
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.组合数
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.比率
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.分数的加、减、乘、除法
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.幂数模
note：
1.常用的一个位运算：a&1
当a（默认dec）为奇数，a&1得到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.对称数
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.操作数
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.倍数和
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.级数和
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.竖式乘法
//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.查找数列
//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.毕达哥拉斯三元组
//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.余数和
//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.最大数字
//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.倒水
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.好数字
//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.俄罗斯农夫算法
//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.阶乘倍数
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.方案数
//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.素数
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.基思数
//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++】
//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++】
note：
1.一切尽在注释中，好吧；
2.题目里的顺序都有问题，直接参考我的代码就行；
//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 IDE?)*/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 fing 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.可变参数平均
//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.可变参数累加
//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.运动会
note：
1.突破口：建立平面直角坐标系，利用斜率的唯一性；
2.又用到了线性筛（aka欧拉筛），我说啥来着？
//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.光线追踪
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.佩尔数
//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.哈沙德数
//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#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;}/*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: 96 AC, 3 WA, 1 NC//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*/
