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

Chipi Chipi 2024-10-23 15:05:01 阅读 60

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

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

前言

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

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

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

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

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

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

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

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

必看

对于代码

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

如若代码粗陋，请谅解；

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

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

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

代码格式

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

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

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

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

建议

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

NOJ攻略

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

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

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

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

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

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

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

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

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

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

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

CE ：编译错误。

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

一般有两种原因：

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

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

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

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

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

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

3.代码输出：

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

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

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

良好的编程习惯

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

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

空一行

第二部分： using namespace std；

空一行

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

空一行

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

下面是示例

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

<code>#include <iostream>

using namespace std;

void fun(){

}

int main() {

return 0;//new C++ standard can ignore this

}

夹带私货

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

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

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

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

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

声明

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

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

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

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

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

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

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

总结

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

其中

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

057.字符串替换

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

三道不能AC;

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

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

第1季（001-010）

001.Hello World

Description

第一个C/C++作业，写一个Hello World吧。

Input

没有。

Output

输出Hello World，注意大小写及空格(最后换行无所谓)。

//Difficulty: 0/10

//Importance:10/10

//The place our dream begin!

//What you need:

//a good coding style(tab,enter,naming...)

//clear coding logics

#include <iostream>

using namespace std;

int main()

{

cout << "Hello World"<<endl;//printf("hello world\n");

return 0;

}//tip:no "!" here

/*

Sample input:

null

Sample output:

Hello World

*/

/*

Additional input:

null

Additional output:

Hello World

*/

002.A+B

Description

编写一个程序，输出A+B的结果。

Input

在一行中输入整型A和B，用空格间隔。

Output

输出A+B的值。

//Difficulty: 0/10

//Importance: 0/10

#include <iostream>

using namespace std;

int main()

{

int A, B;

cin >> A >> B ;

cout <<A+B<<endl;

return 0;

}

/*

Sample input:

3 4

Sample output:

7

*/

/*

Additional input:

5 6

Additional output:

11

*/

003.数据类型大小及范围

Description

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

Input

输入整数d。

Output

输出对应数据类型的内存大小及数值范围(最小值、最大值)，用逗号间隔。

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

note：

1.sizeof()函数的学习；

2.<climits>的基本运用。

<code>//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:

5

Sample output:

4,-2147483648,2147483647

*/

/*

Additional input:

1

Additional output:

1,-128,127

*/

004.平均值

Description

编写一个程序，输出整数A、B的平均值。

Input

在一行中输入整型A和B，用空格间隔。

Output

输出整数A、B的整型平均值。

note：

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

2.基础位运算；

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

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

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

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

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

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

//Difficulty: 3/10

//Importance:10/10

//Note that the data range corresponding to the type

//may be exceeded during the calculation,

//resulting in overflow

//version 1:Bitwise operations(better)

#include <iostream>

using namespace std;

int main()

{

int A, B;

cin >>A >>B;

int avg = ((A - B) >> 1) + B;

cout<<avg;

return 0;

}

//version 2:Split

#include <iostream>

using namespace std;

int main()

{

int A, B;

cin >>A >>B;

if(A<B) swap(A,B); //or：{int t=B;B=A;A=t;}

int avg = (A - B)/2 + B;

cout<<avg;

return 0;

}

/*

Sample input:

3 4

Sample output:

3

*/

/*

Additional input:

5 6

Additional output:

5

*/

005.进制转换

Description

输入一个非负整数，输出它的十六进制，八进制。

Input

输入一个非负整数。

Output

在一行里输出十六进制、八进制，用逗号间隔。十六进制A~F大写。

note：

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

%d ：即为dec，十进制；

%o ：即为oct，八进制；

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

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

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

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

在<iomanip>中：

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

showpos ：在正数前显示+号

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

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

left ：输出内容靠左

right ：输出内容靠右

scientific ：科学记数法

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

//Difficulty: 2/10

//Importance:10/10

//make use of C's good features

//printf() is very useful when you need special outputs

//version 1:printf(recommended)

#include<iostream>

using namespace std;

int main()

{

int a;

cin >> a;

printf("%X,%o",a,a);

return 0;

}

//version 2:cout

#include <iostream>

#include <iomanip>

using namespace std;

int main()

{

int a;

cin>>a;

cout<<setiosflags(ios::uppercase)<<hex<<x<<endl;

}

/*

Sample input:

10

Sample output:

A,12

*/

/*

Additional input:

12

Additional output:

C,14

*/

006.浮点数输出

Description

输出一个浮点数的3个格式结果。

Input

输入一个浮点数。

Output

输出1行，第1个小数点保留6位，第2个小数点保留2位，第3个小数点保留8位，用逗号作为间隔。

note:

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

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

//Difficulty: 1/10

//Importance:10/10

//version 1: printf(recommended)

#include<iostream>

using namespace std;

int main()

{

double a;

cin >> a;

printf("%.6f,%.2f,%.8f",a,a,a);

return 0;

}

//version 2: cout

#include<iostream>

#include<iomanip>

using namespace std;

int main()

{

double a;

cin >> a;

cout <<fixed<< setprecision(6) << a << "," << fixed <<setprecision(2) << a << "," << fixed <<setprecision(8) << a << endl;

//or: cout <<fixed<< setprecision(6) << a << "," << setprecision(2) << a << "," << setprecision(8) << a << endl;

return 0;

}

/*

Sample input:

12345567.891234567

Sample output:

12345567.891235,12345567.89,12345567.89123457

*/

/*

Additional input:

3.141592654

Additional output:

3.141593,3.14,3.14159265

*/

007.动态宽度输出

Description

输出n位宽的m，若n超出m的实际宽度，则左边填充0。

Input

输入整数m和n，用空格间隔。

Output

输出指定格式结果。

note：

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

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

//Difficulty: 1/10

//Importance:10/10

#include <iostream>

#include <iomanip>

using namespace std;

int main()

{

int m, n;

cin >> m >> n;

cout << setw(n) << setfill('0') << m << endl;

return 0;

}

/*

Sample input:

123 5

Sample output:

00123

*/

/*

Additional input:

123 7

Additional output:

0000123

*/

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

Description

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

$hav\left ( \frac{d}{r} \right )= hav\left ( \varphi _{1}-\varphi _{2}\right )+cos\left ( \varphi _{1} \right )cos\left ( \varphi _{2} \right )hav\left ( \lambda _{1}-\lambda_{2}\right )$

$hav\left ( \theta \right )=sin^{^{2}}\left ( \frac{\theta }{2} \right )=\frac{1-cos\left ( \theta \right )}{2}$

Input

输入2行数据，每行数据是点的纬度和经度，用空格间隔。例如西安(34.260958，108.942369)，莫斯科(55.755825，37.617298)。

Output

输出两点的距离，单位是km，小数点保留4位。

note：

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

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

<code>//Difficulty: 2/10

//Importance: 2/10

#include<iostream>

#include<cmath>

#include<iomanip>

#define pi 3.141592654

using 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.942369

55.755825 37.617298

Sample output:

5793.2236km

*/

/*

Additional input:

24.260958 105.942369

45.755825 31.617298

Additional output:

6917.5743km

*/

009.风寒指数

Description

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

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

Input

在一行中输入风速(公里/小时)、空气温度(摄氏温度)，用空格间隔。

Output

输出寒意指数(四舍五入整数)。

note：

<cmath>库基础：

1.pow()函数：

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

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

2.三个取整函数：

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

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

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

<code>//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 35

Sample output:

40

*/

/*

Additional input:

66 39

Additional output:

45

*/

010.颜色模型转换

Description

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

$\epsilon$

[0，1]。

Input

在一行中输入R、G、B的字节值，范围为[0，255]，用空格间隔。

Output

输出为H，S%，V%，用逗号间隔，保留4位小数。

note：

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

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

<code>//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 0

Sample output:

120.0000,100.0000%,84.3137%

*/

/*

Additional input:

0 0 0

Additional output:

0.0000,0.0000%,0.0000%

*/

/*

Additional input:

255 255 255

Additional output:

0.0000,0.0000%,100.0000%

*/

/*

Additional input:

123 54 45

Additional output:

6.9231,63.4146%,48.2353%

*/

第2季（011-020）

011.乘数模

Description

已知三个正整数a、b、m , 求 a*b mod m （1≤a，b，m≤

$10^{18}$

） mod表示求余运算。

Input

在一行里输入三个正整数a、b、m，用空格间隔。

Output

输出计算结果。

note：

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

2.涉及一些数论知识：

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

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

<code>//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 100000

Sample output:

56088

*/

/*

Additional input:

1244 12567 5758

Additional output:

378

*/

012.方阵

Description

编写程序，生成一个n阶正方形矩阵，其中0位于主对角线，1位于主对角线上方和下方的位置中，2位于更上方和下方，等等，依次类推。如下图所示。

Input

输入正整数n。

Output

输出指定要求的方阵。

n等于5时：

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

note:

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

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

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

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

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

<code>//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:

5

Sample output:

0 1 2 3 4

1 0 1 2 3

2 1 0 1 2

3 2 1 0 1

4 3 2 1 0

*/

/*

Additional input:

2

Additional output:

0 1

1 0

*/

013.组合数

Description

有a，b，c和d(0≤a，b，c，d≤9)四个数，求(a+b+c+d)等于n的组合数。

Input

输入n，1≤n≤50。

Output

输出组合数。

note：

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

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

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

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

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

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

//Difficulty: 2/10

//Importance: 2/10

//simple enum

#include <iostream>

using namespace std;

int main() {

int a,b,c,d,n,sum=0;

cin>>n;

for (a=0;a<=9;++a){

for(b=0;b<=9;++b){

for(c=0;c<=9;++c){

for(d=0;d<=9;++d){

if (n==a+b+c+d) sum++;

else sum=sum+0;

}

cout<<sum;

}

/*

Sample input:

15

Sample output:

592

*/

/*

Additional input:

37

Additional output:

0

*/

014.比率

Description

编写一个程序将浮点数转换为比率。

Input

输入一个浮点数。

Output

输出它对应的比率(按最简分数形式)。

note：

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

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

//Difficulty: 3/10

//Importance:10/10

//memorize gcd!

#include <iostream>

#include <cmath>

using namespace std;

int gcd(int a,int b){

if(b==0){return a;}

return gcd(b,a%b);

}

int main(){

double fz;

int fm=1,m;

cin>>fz;

for(fz;fz!=floor(fz);fz=fz*10,fm=fm*10);

m=gcd((int)(fz),fm);

fz=fz/m;

fm=fm/m;

cout<<fz<<"/"<<fm;

}

/*

Sample input:

4.2

Sample output:

21/5

*/

/*

Additional input:

3.33333

Additional output:

333333/100000

*/

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

Description

输入两个分数，计算它们的加、减、乘、除。

Input

输入为2行，每行分别是分数的分子和分母，采用分数形式(参考输入样例)。输入的数据保证运算结果合理。

Output

输出为4行，分别是两个分数的加、减、乘、除式子和结果，用最简分数形式表示。

note：

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

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

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

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

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

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

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

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

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

//Difficulty: 3/10

//Importance: 3/10

//I don't think tuple necessary

//you can use point to replace

//more acceptable way is using Global variables

//plus,getchar() is very useful

//version 1:use array to pass values(recommended)

#include <iostream>

using namespace std;

int gcd(int x,int y){

if(y==0)return x;

else return gcd(y,x%y);

}

void add(int fz1,int fm1,int fz2,int fm2,int arr[4][2]){

int nfz,nfm,d;

nfz=fz1*fm2+fz2*fm1;

nfm=fm1*fm2;

d=gcd(nfz,nfm);

nfz=nfz/d;

nfm=nfm/d;

arr[0][0]=nfz;

arr[0][1]=nfm;

}

void sub(int fz1,int fm1,int fz2,int fm2,int arr[4][2]){

int nfz,nfm,d;

nfz=fz1*fm2-fz2*fm1;

nfm=fm1*fm2;

d=gcd(nfz,nfm);

nfz=nfz/d;

nfm=nfm/d;

arr[1][0]=nfz;

arr[1][1]=nfm;

}

void multi(int fz1,int fm1,int fz2,int fm2,int arr[4][2]){

int nfz,nfm,d;

nfz=fz1*fz2;

nfm=fm1*fm2;

d=gcd(nfz,nfm);

nfz=nfz/d;

nfm=nfm/d;

arr[2][0]=nfz;

arr[2][1]=nfm;

}

void divi(int fz1,int fm1,int fz2,int fm2,int arr[4][2]){

int nfz,nfm,d;

nfz=fz1*fm2;

nfm=fm1*fz2;

d=gcd(nfz,nfm);

nfz=nfz/d;

nfm=nfm/d;

arr[3][0]=nfz;

arr[3][1]=nfm;

}

int main() {

int fz1,fm1,fz2,fm2;

cin>>fz1;

getchar();

cin>>fm1;

cin>>fz2;

getchar();

cin>>fm2;

int arr[4][2];

add(fz1,fm1,fz2,fm2,arr);

sub(fz1,fm1,fz2,fm2,arr);

multi(fz1,fm1,fz2,fm2,arr);

divi(fz1,fm1,fz2,fm2,arr);

char symbol[4]={'+','-','*','/'};

for(int i=0;i<4;++i){

cout<<'('<<fz1<<'/'<<fm1<<')'<<symbol[i]<<'('<<fz2<<'/'<<fm2<<')'

<<'='<<arr[i][0]<<'/'<<arr[i][1]<<endl;

}

return 0;

}

//version 2:use tuple

#include <iostream>

#include <tuple>

using namespace std;

int gcd(int x,int y){

if(y==0)return x;

else return gcd(y,x%y);

}

tuple<int,int> add(int fz1,int fm1,int fz2,int fm2){

int nfz,nfm,d;

nfz=fz1*fm2+fz2*fm1;

nfm=fm1*fm2;

d=gcd(nfz,nfm);

nfz=nfz/d;

nfm=nfm/d;

return make_tuple(nfz,nfm);

}

tuple<int,int> sub(int fz1,int fm1,int fz2,int fm2){

int nfz,nfm,d;

nfz=fz1*fm2-fz2*fm1;

nfm=fm1*fm2;

d=gcd(nfz,nfm);

nfz=nfz/d;

nfm=nfm/d;

return make_tuple(nfz,nfm);

}

tuple<int,int> multi(int fz1,int fm1,int fz2,int fm2){

int nfz,nfm,d;

nfz=fz1*fz2;

nfm=fm1*fm2;

d=gcd(nfz,nfm);

nfz=nfz/d;

nfm=nfm/d;

return make_tuple(nfz,nfm);

}

tuple<int,int> divi(int fz1,int fm1,int fz2,int fm2){

int nfz,nfm,d;

nfz=fz1*fm2;

nfm=fm1*fz2;

d=gcd(nfz,nfm);

nfz=nfz/d;

nfm=nfm/d;

return make_tuple(nfz,nfm);

}

int main() {

int fz1,fm1,fz2,fm2;

cin>>fz1;

getchar();

cin>>fm1;

cin>>fz2;

getchar();

cin>>fm2;

tuple<int,int> result0=add(fz1,fm1,fz2,fm2);

cout<<'('<<fz1<<'/'<<fm1<<')'<<'+'<<'('<<fz2<<'/'<<fm2<<')'

<<'='<<get<0>(result0)<<'/'<<get<1>(result0)<<endl;

tuple<int,int> result1=sub(fz1,fm1,fz2,fm2);

cout<<'('<<fz1<<'/'<<fm1<<')'<<'-'<<'('<<fz2<<'/'<<fm2<<')'

<<'='<<get<0>(result1)<<'/'<<get<1>(result1)<<endl;

tuple<int,int> result2=multi(fz1,fm1,fz2,fm2);

cout<<'('<<fz1<<'/'<<fm1<<')'<<'*'<<'('<<fz2<<'/'<<fm2<<')'

<<'='<<get<0>(result2)<<'/'<<get<1>(result2)<<endl;

tuple<int,int> result3=divi(fz1,fm1,fz2,fm2);

cout<<'('<<fz1<<'/'<<fm1<<')'<<'/'<<'('<<fz2<<'/'<<fm2<<')'

<<'='<<get<0>(result3)<<'/'<<get<1>(result3)<<endl;

}

/*

Sample input:

2/3

3/7

Sample 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/2

Additional output:

(1/2)+(1/2)=1/1

(1/2)-(1/2)=0/1

(1/2)*(1/2)=1/4

(1/2)/(1/2)=1/1

*/

016.幂数模

Description

已知三个正整数a、b、m，求

$a^{b}\: \: mod\, \, \, m$

, 1≤ a,b,m≤

$2^{63}$

, mod表示求余运算。

Input

在一行里输入三个正整数a、b、m，用空格间隔。

Output

输出计算结果。

note：

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

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

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

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

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

<code>//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 9

Sample output:

7

*/

/*

Additional input:

2 63 1314

Additional output:

512

*/

017.对称数

Description

一个对称数是指该数字经过360度旋转以后，依然是该数字。如916->916。编写程序判断一个数是否是对称数。

Input

输入一个整数n。

Output

如果是对称数输出Yes，否则输出No。

note：

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

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

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

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

//Difficulty: 5/10

//Importance: 5/10

//there must be longer,but stupider ways

//why not take C++'s unique advantages?

//such as map/unordered_map,iterator(which is easier to use)

#include<iostream>

#include<string>

#include<unordered_map>

using namespace std;

int main()

{

string ori,inver;

cin>>ori;

unordered_map<char,char> table{ {'0','0'},{'1','1'},{'6','9'},{'9','6'},{'8','8'}};

for(auto it=ori.rbegin();it!=ori.rend();++it){

inver.push_back(table[*it]);}// or: inver+=table[*it];

if(inver==ori)cout<<"Yes";

else cout<<"No";

}

/*

Sample input:

916

Sample output:

Yes

*/

/*

Additional input:

1000081800001

Additional output:

Yes

*/

018.操作数

Description

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

Input

输入正数n。

Output

输出操作次数。

note：

1.理清楚逻辑就行；

//Difficulty: 3/10

//Importance: 3/10

//version 1: no func

#include<iostream>

using namespace std;

int main()

{

int n,n1,d,sum,k;

cin>>n;

sum=0;

n1=n;

for(k=0;n1>0;++k){

while(n>0){

d=n%10;

sum+=d;

n=n/10;

}

n1-=sum;

n=n1;

sum=0;

}

cout<<k;

}

//version 2: func

#include<iostream>

int sumPerDig(int n){

int sum = 0;

while(n){

sum += n%10;

n /= 10;

}

return sum;

}

int main(){

int n,cnt=0;

cin>>n;

while(n){

n -= sumPerDig(n);

++cnt;

}

cout<<cnt;

return 0;

}

/*

Sample input:

21

Sample output:

3

*/

/*

Additional input:

164

Additional output:

17

*/

019.倍数和

Description

小于10的自然数中，3或5的倍数有3、5、6和9，这些数之和是23。求小于n的自然数中所有3或5的倍数之和。

Input

第一行输入整数T，表示接下来有T行数据需要处理。接下来的T行，每行输入一个正整数n(称为一个测试用例)。T和n的范围如下：1≤T≤

$10^{5}$

， 1≤N≤

$10^{9}$

Output

对于每一个测试用例，输出倍数之和，一行一个。

note：

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

<code>//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:

2

10

100

Sample output:

23

2318

*/

/*

Additional input:

2

541

5115

Additional output:

68310

6102195

*/

020.级数和

Description

编写程序来计算n项级数:1.2+2.3+3.4+4.5+5.6+......的和

Input

输入n(在1到99之间)。

Output

输出计算结果。

note：

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

2.关于wid()函数

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

//Difficulty: 2/10

//Importance: 2/10

#include<iostream>

using namespace std;

int wid(int n){

int i=0;

if(n==0)return 1;

else{

while(n){

n=n/10;

i++;

}

return i;

}

double decimal(double n){

int w;

w=wid(n);

for(int i=0;i<w;++i){

n=n/10.0;

}

return n;

}

int main()

{

int n;

cin>>n;

int z[n];

for(int i=0;i<n;++i){

z[i]=i+1;

}

int x[n];

for(int j=0;j<n;++j){

x[j]=j+2;

}

double sum=0.0,s;

for(int k=0;k<n;++k){

s=(double)z[k]+decimal((double)x[k]);

sum+=s;

}

cout<<z[0]+decimal(x[0]);

for(int k=0;k<n-1;++k){

cout<<'+'<<z[k+1]+decimal((double)x[k+1]);

}

cout<<'='<<sum;

}

/*

Sample input:

10

Sample 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:

5

Additional output:

1.2+2.3+3.4+4.5+5.6=17

*/

第3季（021-030）

021.竖式乘法

Description

输入两个整数，输出它们的竖式乘法的结果。如下图。

Input

在一行里输入2个整数a、b，用空格间隔，输入数据保证有意义。

Output

输出a*b的竖式乘法，参见输出样例。注意乘号x、加号+的位置，算式隔行用减号“-”制作。

<code>//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 120

Sample output:

12345

x 120

--------

0

24690

+12345

--------

1481400

*/

/*

Additional input:

12479 9347

Additional output:

12479

x 9347

----------

87353

49916

37437

+112311

----------

116641213

*/

022.查找数列

Description

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

Input

输入整数n。

Output

输出数列中第n个数字。

note:

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

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

//Difficulty: 2/10

//Importance: 2/10

#include<iostream>

#include<tuple>

using namespace std;

tuple<int,int> sum(int n){

int i=1,k;

while(((i*(i+1))/2)<n){

++i;

}

i=i-1;

k=(i*(i+1))/2;

return make_tuple(i+1,k);

}

int main(){

int n,k;

cin>>n;

tuple<int,int> result=sum(n);

int a[get<0>(result)];

for(int j=0;j<get<0>(result);++j){

a[j]=j+1;

}

k=get<1>(result);

cout<<a[n-k-1];

}

/*

Sample input:

14

Sample output:

4

*/

/*

Additional input:

45

Additional output:

9

*/

023.毕达哥拉斯三元组

Description

毕达哥拉斯三元组由三个自然数a<b<c组成，满足

$a^{2}+b^{2}=c^{2}$

；

有一个特殊三元组还满足a+b+c=n，求它的abc乘积。

Input

输入n。

Output

输出三元组的乘积。

note:

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

<code>//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:

1000

Sample output:

31875000

*/

/*

Additional input:

42360

Additional output:

1101603584441138216

*/

024.余数和

Description

给定正整数n和k，计算

$G\left ( n,k \right )=\sum_{i=1}^{n}\left ( k \, \, mod\, \, i\right )$

其中k mod i表示k除以i的余数。

Input

在一行里输入2个整数n、k，用空格间隔。

Output

输出G函数的结果。

<code>//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 5

Sample output:

29

*/

/*

Additional input:

45 2

Additional output:

86

*/

025.最大数字

Description

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

Inpute

输入N。

Output

输出找到的数字。

note:

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

//Difficulty: 2/10

//Importance: 2/10

#include<iostream>

using namespace std;

int wid(int n){

int i=0;

if(n==0)return 1;

else{

while(n){

n=n/10;

i++;

}

return i;

}

int main(){

int n,m,m0,f,l,w;

cin>>n;

m=n;

m0=m;

for(;m0>=0;--m0){

int sum=0;

m=m0;

w=wid(m);

for(int i=0;i<w-1;++i){

l=m%10;

m=m/10;

f=m%10;

if (f<=l) sum++;

}

if (sum==w-1){

cout<<m0;

break;

}

/*

Sample input:

200

Sample output:

199

*/

/*

Additional input:

246545

Additional output:

245999

*/

026.倒水

Description

有两个杯子，容积分别是m升和n升，其中0<m<n。两个杯子最初都是空的，且杯子上没有任何标记，无法进行测量。现在利用两个杯子操作得到d 升水，d<n，水源不限。求得到d升水所需要的最少操作次数。

可以执行的操作有:

(1)倒空一个杯子；

(2)装满一个杯子;

(3)将水从一个杯子倒入另一个杯子，直到其中一个杯子为空或满。

例如m=3、n=5、d=4时，可以有(括号为m升和n升的杯子状况)

倒法1:

(0,0)→(3,0)→(0,3)→(3,3)→(1,5)→(1,0)→(0,1)→(3,1)→(0,4)，需要执行操作次数是8. 倒法2:

(0,0)→(0,5)→(3,2)→(0,2)→(2,0)→(2,5)→(3,4)，需要执行操作次数是6.

因此，最少操作次数为6。

Input

在一行里输入3个整数m、n、d，用空格间隔。输入数据保证有意义。

Output

输出最少操作次数。

note：

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

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

//Difficulty: 5/10

//Importance:10/10

//a classic BFS

#include <iostream>

#include <queue>

#include <set>

#include <array>

using namespace std;

int main(){

int m,n,d;

cin>>m>>n>>d;

queue<array<int,2>> q;

set<array<int,2>>visited;

q.push({0,0});

visited.insert({0,0});

int minop=0;

while(!q.empty()){

int size=q.size();

for(int i=0;i<size;++i){

array<int,2> curr=q.front();

q.pop();

int x = curr[0];

int y = curr[1];

if (x == d || y == d) {

cout <<minop<<endl;

return 0;

}

array<int, 2> next;

//fill m

next = {m, y};

if (visited.find(next) == visited.end()) {

q.push(next);

visited.insert(next);

}

//fill n

next = {x, n};

if (visited.find(next) == visited.end()) {

q.push(next);

visited.insert(next);

}

//empty m

next={0,y};

if(visited.find(next)==visited.end()){

q.push(next);

visited.insert(next);

}

//empty n

next={x,0};

if(visited.find(next)==visited.end()){

q.push(next);

visited.insert(next);

}

//m to n

int pourAmount1 = std::min(x, n - y);

next = {x - pourAmount1, y + pourAmount1};

if (visited.find(next) == visited.end()) {

q.push(next);

visited.insert(next);

}

//n to m

int pourAmount2 = std::min(y, m-x);

next = {x + pourAmount2, y - pourAmount2};

if (visited.find(next) == visited.end()) {

q.push(next);

visited.insert(next);

}

}minop++;

}

/*

Sample input:

3 5 4

Sample output:

6

*/

/*

Additional input:

5 9 7

Additional output:

12

*/

/*

Additional input:

28 17 13

Additional output:

26

*/

027.好数字

Description

一个数字字符串是由数字0到9组成的，其中可能包含前导零。如果在偶数位置上(第1个字符位置为0)是偶数，奇数位置上是素数(2、3、5或7)，则称该字符串是“好数字”。

例如，4562是好数字，因为它的偶数位置(4和6)是偶数，奇数位置(5和2)是素数。而3245不是好数字。

给定整数N，1≤N≤10^15，返回长度为N的好数字的总数。由于结果可能太大，以10^9+7为模。

Input

输入N。

Output

输出好数字的总数 mod 10^9+7。

//Difficulty: 3/10

//Importance: 3/10

//fastmod algorithm

#include<iostream>

typedef long long ll;

using namespace std;

ll fastmod(ll base,ll power){

ll m=1000000007,res=1;

while(power){

if(power&1){

res=(res*base)%m;

}

base=(base*base)%m;

power>>=1;

}

return res;

}

int main(){

ll n,evenCount,oddCount,ans,m=1000000007;

cin>>n;

evenCount=fastmod(5,(n+1)/2);

//each even point corresponds to 5 possibilities(5 even numbers:0,2,4,6,8)

//occurtimes=(n+1)/2

oddCount=fastmod(4,n/2);

//each odd point corresponds to 4 possibilities(4 prime numbers:2,3,5,7)

//occurtimes=n/2

ans=(evenCount*oddCount)%m;

cout<<ans;

}

/*

Sample input:

1

Sample output:

5

*/

/*

Additional input:

4

Additional output:

400

*/

028.俄罗斯农夫算法

Description

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

Input

在一行里输入2个整数a、b，用空格间隔。输入数据保证有意义。

Output

输出农夫乘法的过程，被乘数和乘数列用空格间隔，最后一行输出累加结果。参见输出样例。

<code>//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 3

Sample output:

11 3

5 6

2 12

1 24

33

*/

/*

Additional input:

54 67

Additional output:

54 67

27 134

13 268

6 536

3 1072

1 2144

3618

*/

029.阶乘倍数

Description

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

Input

输入K。

Output

输出N。

note：

1.很重要；

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

//Difficulty: 5/10

//Importance:10/10

//TE warning!

//use binary search and transformation

//never simply use violent factorial(too slow)

#include<iostream>

#include<vector>

using namespace std;

bool check(long long mid, const vector<long long>& primes, const vector<long long>& powers) {

for (int i = 0; i < primes.size(); i++) {

long long cnt = 0, p = primes[i];

while (mid >= p) {

cnt += mid / p;

p *= primes[i];

}

if (cnt < powers[i]) {

return false;

}

return true;

}

int main() {

long long k;

cin >> k;

vector<long long> primes, powers;

for (long long i = 2; i * i <= k; i++) {

if (k % i == 0) {

long long cnt = 0;

while (k % i == 0) {

k /= i;

cnt++;

}

primes.push_back(i);

powers.push_back(cnt);

}

if (k > 1) {

primes.push_back(k);

powers.push_back(1);

}

long long left = 1, right = 1e18, ans = -1;

while (left <= right) {

long long mid = (left + right) / 2;

if (check(mid, primes, powers)) {

ans = mid;

right = mid - 1;

}

else {

left = mid + 1;

}

cout << ans << endl;

}

/*

Sample input:

30

Sample output:

5

*/

/*

Additional input:

5195

Additional output:

1039

*/

/*

Additional input:

1455

Additional output:

97

*/

030.方案数

Description

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

Input

输入N。

Output

输出方案数。

//Difficulty: 2/10

//Importance: 2/10

#include<iostream>

using namespace std;

int main() {

int n, sum = 0;

cin >> n;

int m;

double a;

for (m = 1; m * m< 2 * n; ++m) {

a = (double)n / (double)m - (double)m * 0.5 + 0.5;

if (a - (int)a == 0) {

sum++;

}

cout << sum;

}

/*

Sample input:

9

Sample output:

3

*/

/*

Additional input:

757

Additional output:

2

*/

第4季（031-040）

031.素数

Description

素数(Prime number)又称质数，指在大于1的自然数中，除了1和该数外，无法被其他自然数整除的数。大于1的自然数若不是素数，则称之为合数。确认一个数n是否为素数有许多种方法，最基本的是试除法。

(1)从2至n-1逐一整除n判定。

(2)一个数如果不是素数，则一定能被一个小于它自己的数整除。假设一个数a能整除n，那么n/a也必定能整除n，不妨设 a≤n/a，则有a^2≤n，因此判定素数可以不用到n-1，而是根号n。

(3)一个大于1的整数如果不是素数，那么一定有素因子，因此在枚举时只需要考虑可能为素数的因子即可。可以枚举kn+i的数，例如取k=6，那么6n+2、6n+3、6n+4、6n+6都不可能为素数，因此我们只需要枚举6n+1、6n+5的数即可，这样整体的时间复杂度就会降低2/3，也就是立方根n。调整k值，可以进一步加快计算速度。

Input

输入整数a、b，用空格间隔。

Output

输出a和b之间(包含a和b)的素数个数。

note：

1.很重要；

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

//Difficulty: 2/10

//Importance: 2/10

#include <iostream>

#include <cstring>

using namespace std;

int primecount(int n){

bool isprime[n+1];

int prime[n+1];

int cnt=0;

memset(isprime,true,sizeof(isprime));

isprime[1]=false;

for(int i=2;i<=n;++i){

if(isprime[i]) prime[++cnt]=i;

for(int j=1;j<=cnt && i*prime[j]<=n;++j){

isprime[i*prime[j]]=false;

if(i%prime[j]==0) break;

}

return cnt;

}

int main() {

int a,b;

cin>>a>>b;

int cnt1=primecount(a-1);

int cnt2=primecount(b);

cout<<cnt2-cnt1;

}

/*

Sample input:

10 100

Sample output:

21

*/

/*

Additional input:

19 41455

Additional output:

4329

*/

032.基思数

Description

数学中，基思数(Keith number)又称Repfigit (REPetitive Flbonacci-like diGIT)数，它是一个用特定起始项的线性递推关系数列来定义的整数。假定有一个b进位制的n位数

$N=\sum_{i=0}^{n-1}b^{i}d_{i}$

序列

$S_{N}$

以

$d_{n-1},d_{n-2},......,d_{1},d_{0}$

为初始项开始

每一项都由前面n项和产生，如果N出现在序列S中，那么N就是基思数。

是否存在无穷多个基思数仍然是个有待论证的问题，但10^19以下的基思数只有71个，比素数还稀有。

例如197，以十进制按照上面的方法建立一个序列:

1+9+7=17

9+7+17=33

7+17+33=57

17+33+57=107

33+57+107=197

因此197为基思数。

编写一个内联函数inline lsKeith(int N)，判断N是否为基思数，若是返回1，否则返回0。

Input

输入N(10≤N≤99999999)。

Output

调用lsKeith函数，如果是基思数输出Yes，否则输出No。

<code>//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:

197

Sample output:

Yes

*/

/*

Additional input:

891

Additional output:

No

*/

033.幂函数【C++】

Description

编写一个默认参数函数:

double pow(double base, int exp=2); 计算base的exp次幂。

Input

在一行里输入两个数base、exp，用空格间隔。

Output

第一行输出调用pow(base)的结果。

第二行输出调用pow(base,exp)的结果。

//Difficulty: 2/10

//Importance: 2/10

#include<iostream>

#include<iomanip>

using namespace std;

double pow(double base,int exp=2){

double n=base;

for(;exp>1;--exp){

base*=n;

}

return base;

}

int main(){

double base;

int exp;

cin>>base>>exp;

cout<<fixed<<setprecision(6)<<pow(base)<<endl

<<fixed<<setprecision(6)<<pow(base,exp);

}

/*

Sample input:

1.23 5

Sample output:

1.512900

2.815306

*/

/*

Additional input:

1.01 365

Additional output:

1.020100

37.783434

*/

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

Description

NPU大作业要开发一个体积计算器，求几种常见形状的体积，如下图所示设计了它们的用户界面UI，输入相应的参数，单击“计算”按钮进行计算。

现在你负责开发体积计算器的算法部分(在专业软件开发中称为逻辑或业务部分)，采用C++函数重载技术，函数名称必须是VolCalc。这样，就可以用一个名称计算多种形状体积，其函数原型如下:

double VolCalc(double r); //球体

double VolCalc(double r,double h); //圆锥体

double VolCalc(long a); //立方体

double VolCalc(double r,long h), ; //圆柱体

double VolCalc(long l,long w,long h); //长方体

double VolCalc(double r,double R,double h); //球盖

double VolCalc(double r,double R,double h,double l); //胶囊

double VolCalc(long r,double R,double h); //圆锥体

double VolCalc(double a,double b,long c); //椭球体

double VolCalc(long a,long h); //四棱锥

double VolCalc(long d1,long d2,double l); //管件

Input

在第一行里输入整数T，表示有T个测试用例。

在接下来的T行里，每行先是n，表示是什么形状，参考上图，接着是若干个参数，不同的n有不同数目的参数，而且参数的顺序由图中所列决定。中间用空格间隔。

Output

针对每行测试样例，输出相应形状的体积，每行一个。

需要注意:球盖和胶囊由于h计算的问题，体积是两个结果(h先计算加，再计算减)，中间用空格间隔。

note：

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

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

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

//Difficulty: 2/10

//Importance: 2/10

#include<iostream>

#include<cmath>

#include<tuple>

#include<cstring>

#include<iomanip>

#define pi 3.1415926

/*

pay attention!!! here noj define pi as 3.1415926

instead of 3.141592654(which is more precise),

you MUST define it exactly 3.1415926!!!

*/

using namespace std;

/* noj is likely to pay no attention to return type "double",

so don't add ".0" after the int data in your calculation either,

even actually this is important(obviously this is his fault,

clion would even give you warnings if you don't do so,

this make me thought: is noj using a rubbish compiler?)

*/

double v(double r){

return 4*pi*r*r*r/3;

}

double v(double r,double h){

return pi*r*r*h/3;

}

double v(long a){

return a*a*a/1;

}

double v(double r,long h){

return pi*r*r*h/1;

}

double v(long l,long w,long h){

return l*w*h;

}

/*

if you are careful enough,you may find that the

following two examples are in reverse order in

the stem and in the chart, this is also noj's mistake.

*/

tuple <double,double> v(double r,double R,double h){

double m=sqrt(R*R-r*r);

double v1,v2;

double h1=R+m;

v1=(pi/3.0)*(3.0*R-h1)*h1*h1;

double h2=R-m;

v2=(pi/3.0)*(3.0*R-h2)*h2*h2;

return make_tuple(v1,v2);

}

tuple <double,double> v(double r,double R,double h,double l){

double m=sqrt(R*R-r*r);

double v0,v1,v2;

v0=pi*r*r*l;

double h1=R+m;

v1=v0+(pi/3.0)*(3.0*R-h1)*h1*h1*2;

double h2=R-m;

v2=v0+(pi/3.0)*(3.0*R-h2)*h2*h2*2;

return make_tuple(v1,v2);

}

double v(long r,double R,double h){

return pi*h*(r*r+R*R+R*r)/3;

}

double v(double a,double b,long c){

return 4*pi*a*b*c/3;

}

double v(long a,long h){

return a*a*h/3;

}

double v(long d1,long d2,double l){

return pi*(d1*d1-d2*d2)*l/4;

}

int main(){

bool z[12];

memset(z, false, sizeof(z));

double s[12],six[2],seven[2];

int t;

cin>>t;

for(int i=0;i<t;++i) {

int n;

cin>>n;

z[n]=true;

if(n==1){

double r;

cin>>r;

s[n]=v(r);

}

else if(n==2){

double r,h;

cin>>r>>h;

s[n]=v(r,h);

}

else if(n==3){

long a;

cin>>a;

s[n]=v(a);

}

else if(n==4){

double r;

long h;

cin>>r>>h;

s[n]=v(r,h);

}

else if(n==5){

long l,w,h;

cin>>l>>w>>h;

s[n]=v(l,w,h);

}

else if(n==6){

double r,R,h=0,l;

cin>>r>>R>>l;

tuple <double,double>result=v(r,R,h,l);

six[0]=get<0>(result);

six[1]=get<1>(result);

}

else if(n==7){

double r,R,h=0;

cin>>r>>R;

tuple <double,double>result=v(r,R,h);

seven[0]=get<0>(result);

seven[1]=get<1>(result);

}

else if(n==8){

long r;

double R,h;

cin>>r>>R>>h;

s[n]=v(r,R,h);

}

else if(n==9){

double a,b;

long c;

cin>>a>>b>>c;

s[n]=v(a,b,c);

}

else if(n==10){

long a,h;

cin>>a>>h;

s[n]=v(a,h);

}

else if(n==11){

long d1,d2;

double l;

cin>>d1>>d2>>l;

s[n]=v(d1,d2,l);

}

/*

in fact,you need all you outcomes outcome together,

but not beyond my imagination,noj STILL had no description of it...

*/

for(int j=1;j<=5;++j){

if(z[j]) cout<<fixed<<setprecision(6)<<s[j]<<endl;

}

if(z[6]) cout<<six[0]<<' '<<six[1]<<endl;

if(z[7]) cout<<seven[0]<<' '<<seven[1]<<endl;

for(int j=8;j<=11;++j){

if(z[j]) cout<<s[j]<<endl;

}

/*

noj had no description of demand on precision,

but noj had it in fact,I'm tired from bottom heart...

*/

}

/*

Sample input:

11

1 3

2 3 5

3 6

4 5 12

5 1 2 3

6 5 7 12

7 5 7

8 3 4 5

9 6 7 8

10 5 10

11 12 8 6

Sample output:

113.097334

47.123889

216.000000

942.477780

6.000000

3641.261807 1117.203784

1349.392014 87.363002

193.731544

1407.433485

83.000000

376.991112

*/

/*

Additional input:

11

1 8

2 7 4

3 9

4 7 11

5 1 5 6

6 5 6 13

7 5 9

8 3 5 5

9 6 9 8

10 5 13

11 12 5 4

Additional output:

113.097334

47.123889

216.000000

942.477780

6.000000

3641.261807 1117.203784

1349.392014 87.363002

193.731544

1407.433485

83.000000

38390.261572

*/

035.可变参数平均

Description

stdarg.h头文件提供了一组宏和函数，允许可变参数函数(Variadic function)访问变量参数列表。这些宏和函数是:

va_list:声明将保存变量参数列表的变量的类型。

va_start:一个宏，用于初始化va_list变量以指向变量参数列表中的第一个参数。

va_arg:检索变量参数列表中指定类型的下一个参数的宏。

va_copy:将va_list 变量复制到另一个变量的宏。

va_end:一个宏，用于在使用 va list 变量后清除该变量。

编写一个可变函数double avg(int n,...),，计算n个可变参数的平均值。

Input

在一行里输入5个double型数a、b、c、d、e，用空格间隔。

Output

两次调用函数并且做减法:avg(2,a,b)-avg(3,c,d,e)，输出减法结果，小数点保留四位。

//Difficulty: 2/10

//Importance: 2/10

#include <iostream>

#include <cstdarg>

#include <iomanip>

using namespace std;

double avg(int cnt,...){

va_list nums;

double sum=0;

va_start(nums,cnt);

for(int i=0;i<cnt;++i){

sum+=va_arg(nums,double);

}

va_end(nums);

double result=sum/cnt;

return result;

}

int main(){

double a,b,c,d,e;

cin>>a>>b>>c>>d>>e;

cout<<fixed<<setprecision(4)<<avg(2,a,b)-avg(3,c,d,e);

}

/*

Sample input:

1 2 3 4 5 6

Sample output:

-2.5000

*/

/*

Additional input:

3 645 14 662 7

Additional output:

96.3333

*/

036.可变参数累加

Description

stdarg.h头文件提供了一组宏和函数，允许可变参数函数(Variadic function)访问变量参数列表。这些宏和函数是

va_list:声明将保存变量参数列表的变量的类型。

va_start:一个宏，用于初始化va_list变量以指向变量参数列表中的第一个参数。

va_arg:检索变量参数列表中指定类型的下一个参数的宏。

va_copy:将va_list 变量复制到另一个变量的宏。

va_end:一个宏，用于在使用 va_list 变量后清除该变量。

编写一个可变函数int sum(int first..);，计算多个可变参数的累加，该函数以参数小于等于0结尾。

Input

在一行里输入6个整数a、b、c、d、e、f，用空格间隔，保证输入数据大于0。

Output

两次调用函数并且做减法:sum(a,b,0)-sum(c,d,e,f,0)，输出减法结果。

//Difficulty: 2/10

//Importance: 2/10

#include <iostream>

#include <cstdarg>

using namespace std;

int pl(int first,...){

va_list nums;

va_start(nums,first);

int cnt=1;

while(va_arg(nums,int)){

cnt++;

}

va_end(nums);

int sum=first;

va_start(nums,first);

for(int i=1;i<cnt;++i){

sum+=va_arg(nums,int);

}

va_end(nums);

return sum;

}

int main(){

int a,b,c,d,e,f;

cin>>a>>b>>c>>d>>e>>f;

cout<<pl(a,b,0)-pl(c,d,e,f,0);

}

/*

Sample input:

1 2 3 4 5 6

Sample output:

-15

*/

/*

Additional input:

123 5624 2645 167 3427 12354

Additional output:

-12846

*/

037.运动会

Description

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

（蓝色即为可见的人）

Input

输入整数N(1≤N≤40000)。

Output

输出队长在NxN的方阵中看到的人数。

note：

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

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

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

<code>//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:

4

Sample output:

9

*/

/*

Additional input:

99

Additional output:

71315

*/

038.光线追踪

Description

用三面长度为N的镜子组成一个等边三角形

$\Delta$

abc，如下图所示:

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

Input

在一行里输入整数N、X，用空格间隔。其中，2≤N≤10^12，1≤X≤N-1。

Output

输出光线轨迹的总长度。

样例解释:当N=5，X=2时，如图中红线，光线轨迹的总长度=2+3+2+2+1+1+1=12。

note：

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

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

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

<code>//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 2

Sample output:

12

*/

/*

Additional input:

5 3

Additional output:

12

*/

/*

Additional input:

199 31

Additional output:

594

*/

039.佩尔数

Description

佩尔数由以下关系定义:

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

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

<code>int PA(int n)

{//递归方法

if(n==0) return 0;

else if(n==1) return 1;

return 2*PA(n-1)+PA(n-2);

}

int PB(int n)

{ //递推方法

int p0=0,p1=1,pn,i;

for(i=0;i<=n;i++)

if(i==0)pn=p0;

else if(i==1)pn=p1;

else {

pn=2*p1+p0;

p0=p1;

p1=pn;

}

return pn;

}

Input

输入n。

Output

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

//Difficulty: 2/10

//Importance: 2/10

#include<iostream>

using namespace std;

int PA(int n){

if(n==0) return 0;

else if(n==1) return 1;

return 2*PA(n-1)+PA(n-2);

}

int PB(int n){

int p0=0,p1=1,pn,i;

for (i=0;i<=n;++i){

if (i==0) pn=p0;

else if (i==1) pn=p1;

else{

pn=2*p1+p0;

p0=p1;

p1=pn;

}

return pn;

}

int main(){

int n;

cin>>n;

if(n&1) cout<<PA(n);

else cout<<PB(n);

}

/*

Sample input:

10

Sample output:

2378

*/

/*

Additional input:

42

Additional output:

339564650

*/

040.哈沙德数

Description

inline int HarshadNumber(int n){

int t=n,s=0;

while (t){

s+=t%10;

t/=10;

}

if (s && n%s==0) return n/s;

return 0;

}

上述代码用来求哈沙德数，函数返回0表示n不是哈沙德数，返回其他表示n是哈沙德数且返回值为整除结果。

Input

输入n。

Output

调用上述函数，输出n是几重哈沙德数，为0表示它不是哈沙德数，为1表示它是一重哈沙德数，依此类推。

//Difficulty: 2/10

//Importance: 2/10

#include<iostream>

using namespace std;

inline int hn(int n){

int t=n,s=0;

while (t){

s+=t%10;

t/=10;

}

if ((s == 0) || (n%s != 0)) return 0;

if (s == 1) return 1;

return n/s;

}

int main(){

int cnt = 0, n;

cin>>n;

if (n == 1) cnt = 1;

while ((n != 0) && (n != 1)) {

n = hn(n);

if (n) ++cnt;

}

cout<<cnt;

}

/*

Sample input:

6804

Sample output:

4

*/

/*

Additional input:

1048

Additional 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 4

1 1 1 1

1 0 1 1

1 1 0 1

1 1 1 1

Sample output:

3

*/

/*

Additional input:

5 5

1 0 1 0 1

1 1 0 1 1

1 1 1 1 1

0 1 1 0 0

1 0 1 1 1

Additional 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}

};

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 1

Sample output:

V1=128kts Vr=139kts V2=146kts

*/

/*

Additional input:

NULL

Additional output:

NULL

*/

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

//Difficulty: 2/10

//Importance: 2/10

#include <iostream>

#define MAXSIZE 10

using 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:

3

2 6 3

1 0 2

5 8 4

Sample output:

28

*/

/*

Additional input:

3

8 91 1

4 15 15

61 237 16

Additional 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 4

5 0 0 0

0 8 0 0

0 0 3 0

0 6 0 0

Sample output:

Yes

*/

/*

Additional input:

4 4

5 5 0 0

0 1 0 0

0 0 3 0

0 6 0 2

Additional 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:

3

1 1 1 15 5

8 7 6 15 5

8 5 7 15 6

Sample output:

YES

NO

YES

*/

/*

Additional input:

3

1 4 5 5 16

15 51 16 15 15

15 61 16 16 16

Additional output:

YES

NO

*/

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 1

2 2 2 2 2 2

1 2 3 4 5 6

0 0 0 0 0 0

Sample output:

4

7

16

*/

/*

Additional input:

1 5 6 2 1 6

1 6 7 1 2 7

1 2 7 19 8 6

0 0 0 0 0 0

Additional output:

11

12

35

*/

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 2

Sample output:

157

*/

/*

Additional input:

1000 3

Additional 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 2000

Sample output:

13.317870

*/

/*

Additional input:

3 8 7 1292

Additional 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:

7

150 6450

200 7450

250 8445

300 9450

350 11450

400 15450

600 18450

Sample output:

Y=1770.2394+28.7793*X

*/

/*

Additional input:

5

1 1

2 2

3 3

4 4

5 5

Additional 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+1

static 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:

100

Sample output:

25

*/

/*

Additional input:

1590

Additional 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:

www

nwpu

edu

cn

*/

/*

Additional input:

https://www.bh3.com/

.

Additional output:

https://www

bh3

com/

*/

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-four

Sample output:

eighty-one

*/

/*

Additional input:

zero zero

Additional 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.com

cmowz.

Sample output:

example.com

www.example

example

*/

/*

Additional input:

https://www.bh3.com/

pthsocm/:w.

Additional output:

bh3.com/

https://www.bh3

bh3

*/

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:

antiantianwartiantianti

anti

Sample output:

anwartiantianti

antiantianwarti

*/

/*

Additional input:

yuanshenyuanshenyuanshengyuanshenshenshen

yuan

Additional output:

shenyuanshenyuanshengyuanshenshenshen

yuanshenyuanshenyuanshengyuanshenshen

*/

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+123

Sample output:

-123

*/

/*

Additional input:

00519

Additional 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()；

<code>//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 world

Sample output:

hELLO WORLD

*/

/*

Additional input:

eLYSIA tRUe

Additional 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 xx

xx

nwpu

Sample output:

nwpufornwpu nwpu for nwpu

*/

/*

Additional input:

xx for xx is xx

xx

Genshin Impact

Additional 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:

ABCDEFGHI

8

2 2 7

2 -7 -2

2 2 -5

3 2 7 2

3 6 1 -2

2 0 3

1 6

3 -1 -10 -1

Sample output:

CDEFG

CD

CEG

GEC

ABC

GHI

IHGFEDCBA

*/

/*

Additional input:

NULL

Additional 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 321

Sample output:

420

*/

/*

Additional input:

ac 42

Additional 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:

6

Sample output:

132

*/

/*

Additional input:

14

Additional 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<<" 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<<" 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:

8

Sample output:

AT

T--A

A----T

T------A

G----C

T--A

GC

CG

C--G

A----T

A------T

T------A

A----T

A--T

GC

AT

C--G

T----A

C------G

T----A

G--C

AT

T--A

A----T

T------A

G----C

T--A

GC

*/

/*

Additional input:

2

Additional output:

AT

T--A

A----T

T------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*3B

END

Sample output:

10:48:13

error

19:17:24

*/

/*

Additional input:

NULL

Additional 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:

8

1 8 3 9 10 10 2 4

Sample output:

1 2 3 4 8 9 10 10

*/

/*

Additional input:

10

1 1 1 1 2 6 2 6 2 7

Additional 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 3

8 6 8 6

8 6 9 6

0 0 0 0

Sample output:

492

0

792

*/

/*

Additional input:

8 5 6 1

1 6 1 6

1 6 3 7

0 0 0 0

Additional output:

315

0

1

*/

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 2

2021 1 1

Sample output:

86400.000000

*/

/*

Additional input:

2024 1 1

2024 1 2

Additional 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:

14

Sample output:

2

*/

/*

Additional input:

23

Additional 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:

abcda

3

Sample output:

dyzad

*/

/*

Additional input:

fdmrghm

1

Additional 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.05

100 0

100

Sample output:

1 16.000000

2 25.440000

3 35.009600

4 44.265664

5 53.169142

6 61.668210

7 69.720909

8 77.293448

9 84.359807

10 90.901240

11 96.905764

12 102.367624

13 107.286754

14 111.668241

15 115.521778

16 118.861142

17 121.703666

18 124.069744

19 125.982338

20 127.466524

21 128.549046

22 129.257909

23 129.621989

24 129.670681

25 129.433566

26 128.940117

27 128.219429

28 127.299977

29 126.209409

30 124.974359

31 123.620295

32 122.171385

33 120.650395

34 119.078603

35 117.475745

36 115.859968

37 114.247816

38 112.654219

39 111.092512

40 109.574456

41 108.110278

42 106.708722

43 105.377103

44 104.121378

45 102.946217

46 101.855081

47 100.850307

48 99.933190

49 99.104069

50 98.362420

51 97.706938

52 97.135627

53 96.645882

54 96.234574

55 95.898129

56 95.632605

57 95.433761

58 95.297129

59 95.218079

60 95.191874

61 95.213729

62 95.278857

63 95.382521

64 95.520066

65 95.686962

66 95.878832

67 96.091477

68 96.320904

69 96.563341

70 96.815249

71 97.073341

72 97.334582

73 97.596194

74 97.855665

75 98.110740

76 98.359419

77 98.599956

78 98.830847

79 99.050823

80 99.258838

81 99.454062

82 99.635862

83 99.803795

84 99.957590

85 100.097136

86 100.222469

87 100.333754

88 100.431276

89 100.515421

90 100.586667

91 100.645566

92 100.692736

93 100.728849

94 100.754615

95 100.770775

96 100.778092

97 100.777339

98 100.769291

99 100.754719

100 100.734384

*/

/*

Additional input:

NULL

Additional 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:

10

1 2 3 4 5 6 7 8 9 10

5

Sample output:

5 in [4]

*/

/*

Additional input:

10

11 16 18 19 21 34 53 55 69 70

55

Additional 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 0

7 8 9 0

-1

Sample output:

1 2 3 4 5 3.000000

1 2 3 4 5 7 8 9 4.500000

*/

/*

Additional input:

145 15 163 13609 135 0

15 3614 16345 13051 16349 14 0

-1

Additional output:

145 15 163 13609 135 163.000000

145 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.458

using 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");

}

// 计算代数余子式函数，结果=dest

int 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，结果存放到 F

void 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，结果存放到 J

void 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，结果存放到 J

void 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，结果存放到 R

void 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，结果存放到 X

void 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，结果存放到 A

void 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 牛顿迭代法求非线性方程组的根，存放到X0

void 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"); //观察 F

print1(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 20140

18760 2750 18610

17610 14630 13480

19170 610 18390

0.07074 0.07220 0.07690 0.07242

0 0 6370 0

Sample output:

-41.7727,-16.7891,6370.0595

*/

/*

Additional input:

NULL

Additional 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:

5

1 5 4 5

2 5 10 1

3 2 10 3

6 4 9 4

7 1 8 1

Sample output:

X: #1 #2

X: #2 #3

n=2

*/

/*

Additional input:

5

1 5 4 9

2 5 10 3

3 2 10 6

6 4 9 45

7 1 8 0

Additional output:

X: #2 #3

X: #2 #4

n=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.14159265358979323846

using 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;code>

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;code>

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;code>

return 0;

}

/*

Sample input:

2022 8 15

108.760064 34.035672

Sample output:

*/

/*

Additional input:

NULL

Additional 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:
6
2001900001 Jerry 88
2001900005 Tom 92
2001900006 Milla 85
2001900002 Alice 80
2001900003 Mickey 85
2001900004 Aladdin 83
Sample output:
2001900005 Tom 92
2001900001 Jerry 88
2001900003 Mickey 85
2001900006 Milla 85
2001900004 Aladdin 83
2001900002 Alice 80
*/
/*
Additional input:
NULL
Additional 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:
3
Po
Mo
Cu
Sample output:
9.15
9.63
8.89
*/
/*
Additional input:
NULL
Additional 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:
Fe2H3OH
Sample output:
Fe 2
H 4
*/
/*
Additional input:
H2O
Additional output:
H 2
O 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 80
0.250 4186
0.500 900
Sample output:
89.79kJ,0.30%,0.70%
*/
/*
Additional input:
NULL
Additional 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.81
Sample output:
298.766km
*/
/*
Additional input:
NULL
Additional output:
NULL
*/ 
080.【专业融合：航海】水下声学定位
 note：
 
1.自此和【专业融合】告别了，doge；
 
//Difficulty: 2/10
//Importance: 2/10
#include <iostream>
#include <cmath>
#define PI 3.1415926
using 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 6
Sample output:
29.293877 90.0
*/
/*
Additional input:
NULL
Additional 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 1
3
Sample output:
4
*/
/*
Additional input:
6 1
5
Additional 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:
6
1 8 5 2 4 3
Sample output:
4 5 8
*/
/*
Additional input:
NULL
Additional 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:
1
2
3
4
5
0
Sample output:
0
0
1
3
8
*/
/*
Additional input:
NULL
Additional 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:
3
3 3
1 3
2 3
Sample output:
2 3 1
*/
/*
Additional input:
NULL
Additional 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:
1212243660
Sample output:
true
*/
/*
Additional input:
NULL
Additional 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:
3
3 -7 0
Sample output:
3
*/
/*
Additional input:
NULL
Additional 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:
7
2 -4 1 9 -6 7 -3
Sample output:
11
*/
/*
Additional input:
NULL
Additional 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:
3
1 2 3
Sample output:
4
*/
/*
Additional input:
NULL
Additional 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:
ennkuu
Sample output:
4
*/
/*
Additional input:
NULL
Additional 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 4
1 2 1
2 3 10
1 3 100
1 4 1000
Sample output:
1110
*/
/*
Additional input:
NULL
Additional 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:
abcdefX181292
Sample output:
fedcbaX292181
*/
/*
Additional input:
NULL
Additional 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 3
Sample output:
9
*/
/*
Additional input:
NULL
Additional output:
NULL
*/ 
093.【考试题型：循环（迭代）】圆周率Π
 //Difficulty: 2/10
//Importance: 2/10
//version 1
#include <iostream>
#include <iomanip>
using namespace std;
double an(int i){
 if(i==1) return 3.0;
 else if(i&1) return -4.0/(2.0*i*(2.0*i-1)*(2.0*i-2));
 return 4.0/(2.0*i*(2.0*i-1.0)*(2.0*i-2.0));
}
int main()
{
 int n;
 cin>>n;
 double ans=0;
 for(int i=1;i<n+1;++i) ans+=an(i);
 cout<<fixed<<setprecision(7)<<ans;
 //printf("%.7f",ans);
 return 0;
}
//version 2:standarded answer
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main() {
 int n, i, d;
 double pi = 0.0, t = 1.0;
 cin >> n;
 for (i = 2; i <= n; i++) {
 d = 2 * (i - 1);
 pi = pi + t / (d * (d + 1) * (d + 2));
 t = -t;
 }
 cout << setiosflags(ios::fixed) << setprecision(7) << 3 + 4 * pi;
}
/*
Sample input:
100
Sample output:
3.1415929
*/
/*
Additional input:
NULL
Additional 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.04
Sample output:
1.0043
*/
/*
Additional input:
NULL
Additional 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:
5
Sample output:
1.000000 1.414214 1.732051 2.000000 2.236068
*/
/*
Additional input:
NULL
Additional 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]);code>
 }
}
/*
Sample input:
25
Sample output:
5=1
10=2
*/
/*
Additional input:
NULL
Additional 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";code>
 else if(m<1.2) a="transonic";code>
 else if(m<5.0) a="supersonic";code>
 else if(m<=10.0) a="hypersonic";code>
 cout<<fixed<<setprecision(3)<<m<<' '<<a;
 return 0;
}
/*
Sample input:
920 -49.90
Sample output:
0.853 transonic
*/
/*
Additional input:
NULL
Additional 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';code>
 char d='A';code>
 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';code>
 char c='9';code>
 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:
MU2103
CA8326
Sample output:
35
*/
/*
Additional input:
MU2103
MU2103
Additional 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:
6
UA057 2 3
AA044 12 30
BA1534 40 50
DL262 5 1
AF001 12 10
SK837 3 4
Sample output:
UA057-SK837 1.4142
*/
/*
Additional input:
NULL
Additional output:
NULL
*/ 
100.【考试题型：数组】重复元素
 //Difficulty:??/10
//Importance: 0/10
//total: 97 AC, 3 WA
//that's the end
//hope you have properly used all these codes
//otherwise all my efforts would be useless
//Fight for all the beauty in this world!
//May all the beauty be blessed.
//version 1:dull,but straight and simple
#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
 int n;
 cin>>n;
 int arr[n];
 for(int i=0;i<n;++i){
 cin>>arr[i];
 }
 int cnt=0;
 unordered_map<int, bool> countMap;
 for (int i = 0; i < n; i++) {
 countMap[arr[i]]=1;
 }
 for (int i = 0; i < n; i++) {
 if(countMap[arr[i]]=1){
 cnt++;
 }
 }
 cout<<cnt-countMap.size();
 return 0;
}
//version 2: a brilliant break
#include<iostream>
using namespace std;
int main(){
 int n;
 cin>>n;
 int arr[n];
 for(int i=0;i<n;++i) cin>>arr[i];
 int cnt=0;
 for(int i=0;i<n;++i){
 for(int j=i+1;j<n;++j){
 if(arr[i]==arr[j]) {
 cnt++;
 break;
 }
 }
 }
 cout<<cnt;
}
/*
Sample input:
10
1 10 20 1 25 1 10 30 25 1
Sample output:
5
*/
/*
Additional input:
NULL
Additional output:
NULL
*/

 
 
   上一篇： 基于大数据爬虫数据挖掘技术+Python的网络用户购物行为分析与可视化平台(源码+论文+PPT+部署文档教程等) 
  下一篇： Python——图片文字识别与提取 
  本文标签 
  西北工业大学 NOJ 2023 程序设计基础（C++） 完结撒花（已停止维护）    
 
  
  声明
  本文内容仅代表作者观点，或转载于其他网站，本站不以此文作为商业用途
 如有涉及侵权，请联系本站进行删除
 转载本站原创文章，请注明来源及作者。