devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2023 西北工业大学 NOJ 程序设计基础（C++） 100道完结版

作者：小小林熬夜学编程 | 2024-02-09 13:25:31

赞

踩

2023 西北工业大学 NOJ 程序设计基础（C++） 100道完结版

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

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

前言

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

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

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

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

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

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

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

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

必看

对于代码

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

如若代码粗陋，请谅解；

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

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

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

代码格式

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

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

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

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

推荐工具

1.建议使用CLion作为编程工具，别惦记那CodeBlocks，Dev-C++了，一个太简陋，一个太老，不具有现代化工具的特点，都4202年啦，大人，时代变啦！

   实在不行也得用Visual Studio，community版本免费，官网链接如下

   Visual Studio 2022 IDE - 适用于软件开发人员的编程工具 (microsoft.com)

   你说你只会CodeBlocks？甚至CodeBlocks都配置不明白？能不能有点学习意识，

   B站上手把手教你安装配置Clion，Visual Studio的视频一抓一大把，学不会就洗洗睡吧。

   你说Visual Studio下载太慢？我滴IDM可是一眨眼就下好了，你也可以试试梯子。

   至于最推荐的CLion的安装、配置、使用，我就直接放大佬的文章了

   CLion安装、配置、使用、调试（完全小白向）-CSDN博客

2.不会吧，不会吧，不会有人写noj是网页看一眼，切个界面再打一句代码吧，或者是每次一忘就要切回头看一眼，烦不烦呐。

   什么，你说你是小机灵鬼，直接分屏，可是如果你不是外接显示器，那么点大的屏幕还分屏，折磨自己捏。

   所以，在下隆重推荐Snipatse，可以直接把noj上面的题目截下来，悬浮显示在最上层，而且还可以白嫖！

   官网链接Snipaste - 截图 + 贴图，不过建议直接在微软商店下载，体验更友好。至于使用方法，当然是自己去B站大学自学啦。

注：上述建议均基于Windows电脑，MacOS我真不道啊。

建议

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

NOJ攻略

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

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

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

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

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

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

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

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

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

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

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

        CE                ：编译错误。

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

                               一般有两种原因：

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

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

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

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

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

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

3.代码输出：

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

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

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

良好的编程习惯

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

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

空一行

第二部分： using namespace std；

空一行

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

空一行

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

下面是示例

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

  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. void fun(){
  6.     
  7. }
  8.  
  9. int main() {
  10.  
  11.     return 0;//new C++ standard can ignore this
  12. }

夹带私货

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

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

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

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

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

声明

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

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

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

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

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

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

总结

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

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

          057.字符串替换

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

三道不能AC;

第1季（001-010）

001.Hello World

  1. //Difficulty: 0/10
  2. //Importance:10/10
  3.  
  4. //The place our dream begin!
  5.  
  6. //What you need:
  7. //a good coding style(tab,enter,naming...)
  8. //clear coding logics
  9.  
  10. #include <iostream>
  11.  
  12. using namespace std;
  13.  
  14. int main()
  15. {
  16.     cout << "Hello World"<<endl;//printf("hello world\n");
  17.     return 0;
  18. }//tip:no "!" here
  19.  
  20. /*
  21. Sample input:
  22. null
  24. Sample output:
  25. Hello World
  26. */
  27.  
  28. /*
  29. Additional input:
  30. null
  32. Additional output:
  33. Hello World
  34. */

002.A+B

  1. //Difficulty: 0/10
  2. //Importance: 0/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. int main()
  9. {
  10.     int A, B;
  11.     cin >> A >> B ;
  12.     cout <<A+B<<endl;
  13.     return 0;
  14. }
  15.  
  16. /*
  17. Sample input:
  18. 3 4
  20. Sample output:
  21. 7
  22. */
  23.  
  24. /*
  25. Additional input:
  26. 5 6
  28. Additional output:
  29. 11
  30. */

003.数据类型大小及范围

note：

1.sizeof()函数的学习；

2.<climits>的基本运用。

  1. //Difficulty: 1/10
  2. //Importance: 1/10
  3.  
  4. //make use of <climits> (<limits.h>) to get min and max sizes
  5. //sizeof(),return memory size(bit)
  6.  
  7. #include <iostream>
  8. #include <climits>
  9.  
  10. using namespace std;
  11.  
  12. int main()
  13. {
  14.     int n;
  15.     cin >> n;
  16.     switch (n) {
  17.         case 1: cout << sizeof(char) << "," << CHAR_MIN << "," << CHAR_MAX; break;
  18.         case 2: cout << sizeof(unsigned char) << "," << 0<< "," << UCHAR_MAX; break;
  19.         case 3: cout << sizeof(short) << "," << SHRT_MIN << "," << SHRT_MAX; break;
  20.         case 4: cout << sizeof(unsigned short) << "," << 0<< "," << USHRT_MAX; break;
  21.         case 5: cout << sizeof(int) << "," << INT_MIN << "," << INT_MAX; break;
  22.         case 6: cout << sizeof(unsigned int) << "," << 0<< "," << UINT_MAX; break;
  23.         case 7: cout << sizeof(long) << "," << LONG_MIN << "," << LONG_MAX; break;
  24.         case 8: cout << sizeof(unsigned long) << "," << 0 << "," << ULONG_MAX; break;
  25.         case 9: cout << sizeof(long long) << "," << LLONG_MIN << "," << LLONG_MAX; break;
  26.         case 10: cout << sizeof(unsigned long long) << "," << 0 << "," << ULLONG_MAX; break;
  27.     }
  28.     return 0;
  29. }
  30.  
  31. /*
  32. Sample input:
  33. 5
  35. Sample output:
  36. 4,-2147483648,2147483647
  37. */
  38.  
  39. /*
  40. Additional input:
  41. 1
  43. Additional output:
  44. 1,-128,127
  45. */

004.平均值

note：

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

2.基础位运算；

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

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

  1. //Difficulty: 3/10
  2. //Importance:10/10
  3.  
  4. //Note that the data range corresponding to the type
  5. //may be exceeded during the calculation,
  6. //resulting in overflow
  7.  
  8. //version 1:Bitwise operations(better)
  9.  
  10. #include <iostream>
  11.  
  12. using namespace std;
  13.  
  14. int main()
  15. {
  16.     int A, B;
  17.     cin >>A >>B;
  18.     int avg = ((A - B) >> 1) + B;
  19.     cout<<avg;
  20.     return 0;
  21. }
  22.  
  23. //version 2:Split
  24.  
  25. #include <iostream>
  26.  
  27. using namespace std;
  28.  
  29. int main()
  30. {
  31.     int A, B;
  32.     cin >>A >>B;
  33.     int avg = (A - B)/2 + B;
  34.     cout<<avg;
  35.        return 0;
  36. }
  37.  
  38.  
  39. /*
  40. Sample input:
  41. 3 4
  43. Sample output:
  44. 3
  45. */
  46.  
  47. /*
  48. Additional input:
  49. 5 6
  51. Additional output:
  52. 5
  53. */

005.进制转换

note：

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

        %d        ：即为dec，十进制；

        %o        ：即为oct， 八进制；

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

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

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

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

     在<iomanip>中：

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

  • showpos ：在正数前显示+号

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

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

  • left ：输出内容靠左

  • right ：输出内容靠右

  • scientific ：科学记数法

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

  1. //Difficulty: 2/10
  2. //Importance:10/10
  3.  
  4. //make use of C's good features
  5. //printf() is very useful when you need special outputs
  6.  
  7. //version 1:printf(recommended)
  8.  
  9. #include<iostream>
  10.  
  11. using namespace std;
  12.  
  13. int main()
  14. {
  15.     int a;
  16.     cin >> a;
  17.     printf("%X,%o",a,a);
  18.     return 0;
  19. }
  20.  
  21. //version 2:cout
  22.  
  23. #include <iostream>
  24. #include <iomanip>
  25.  
  26. using namespace std;
  27.  
  28. int main()
  29. {
  30.     int a;
  31.     cin>>a;
  32.     cout<<setiosflags(ios::uppercase)<<hex<<x<<endl;
  33. }
  34.  
  35.  
  36. /*
  37. Sample input:
  38. 10
  40. Sample output:
  41. A,12
  42. */
  43.  
  44. /*
  45. Additional input:
  46. 12
  48. Additional output:
  49. C,14
  50. */

006.浮点数输出

note:

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

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

  1. //Difficulty: 1/10
  2. //Importance:10/10
  3.  
  4. //version 1: printf(recommended)
  5.  
  6. #include<iostream>
  7.  
  8. using namespace std;
  9.  
  10. int main()
  11. {
  12.     double a;
  13.     cin >> a;
  14.     printf("%.6f,%.2f,%.8f",a,a,a); 
  15.     return 0;
  16.  }
  17.  
  18.  
  19. //version 2: cout
  20.  
  21. #include<iostream>
  22. #include<iomanip>
  23.  
  24. using namespace std;
  25.  
  26. int main()
  27. {
  28.     double a;
  29.     cin >> a;
  30.     cout <<fixed<< setprecision(6) << a << "," << fixed <<setprecision(2) << a << "," << fixed <<setprecision(8) << a << endl;
  31.     //or: cout <<fixed<< setprecision(6) << a << "," << setprecision(2) << a << "," << setprecision(8) << a << endl;
  32.     return 0;
  33. }
  34.  
  35.  
  36.  
  37. /*
  38. Sample input:
  39. 12345567.891234567
  41. Sample output:
  42. 12345567.891235,12345567.89,12345567.89123457
  43. */
  44.  
  45. /*
  46. Additional input:
  47. 3.141592654
  49. Additional output:
  50. 3.141593,3.14,3.14159265
  51. */

007.动态宽度输出

note：

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

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

  1. //Difficulty: 1/10
  2. //Importance:10/10
  3.  
  4. #include <iostream>
  5. #include <iomanip>
  6.  
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11.     int m, n;
  12.     cin >> m >> n;
  13.     cout << setw(n) << setfill('0') << m << endl;
  14.     return 0;
  15. }
  16.  
  17. /*
  18. Sample input:
  19. 123 5
  21. Sample output:
  22. 00123
  23. */
  24.  
  25. /*
  26. Additional input:
  27. 123 7
  29. Additional output:
  30. 0000123
  31. */

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

note：

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5. #include<cmath>
  6. #include<iomanip>
  7.  
  8. #define pi 3.141592654
  9.  
  10. using namespace std;
  11.  
  12. double hav(double x) {
  13.     double result = (1 - cos(x)) * 0.5;
  14.     return result;
  15. }
  16.  
  17. double trans(double e) {
  18.     double m;
  19.     m = (e / 180) * pi;
  20.     return m;
  21. }
  22.  
  23. int main()
  24. {
  25.     double x1, y1, x2, y2,s,m,d;
  26.     cin >> x1 >> y1;
  27.     cin >> x2 >> y2;
  28.     x1 = trans(x1), y1 = trans(y1), x2 = trans(x2), y2 = trans(y2);
  29.     s = hav(x2 - x1) + cos(x1) * cos(x2) * hav(y2 - y1);
  30.     m = acos(1 - 2*s);
  31.     d = m * 6371;
  32.     cout <<fixed<<setprecision(4)<< d <<"km"<< endl;
  33. }
  34.  
  35. /*
  36. Sample input:
  37. 34.260958 108.942369
  38. 55.755825 37.617298
  40. Sample output:
  41. 5793.2236km
  42. */
  43.  
  44. /*
  45. Additional input:
  46. 24.260958 105.942369
  47. 45.755825 31.617298
  49. Additional output:
  50. 6917.5743km
  51. */

009.风寒指数

note：

<cmath>库基础：

1.pow()函数：

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

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

2.三个取整函数：

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

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5. #include<cmath>
  6.  
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11.     double  v, t;
  12.     double chilldegree;
  13.     cin >> v >> t;
  14.     double a = pow(v, 0.16);
  15.     chilldegree = 13.12 + 0.6215 * t - 11.37 * a+ 0.3965* t * a;
  16.     chilldegree = round(chilldegree);
  17.     cout << chilldegree;
  18. }
  19.  
  20. /*
  21. Sample input:
  22. 120 35
  24. Sample output:
  25. 40
  26. */
  27.  
  28. /*
  29. Additional input:
  30. 66 39
  32. Additional output:
  33. 45
  34. */

010.颜色模型转换

note：

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

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

  1. //Difficulty: 3/10
  2. //Importance: 3/10
  3.  
  4. //given types of float,double have precision problem
  5. //(a - b < 1e-9) is used to judge whether it is 0
  6.  
  7. #include<iostream>
  8. #include<iomanip>
  9.  
  10. using namespace std;
  11.  
  12. int main() {
  13.     int R, G, B;
  14.     cin >> R >> G >> B;
  15.     double r, g, b, h, s, v;
  16.     double MAX, MIN, d;
  17.  
  18.     r = R / 255.0;
  19.     g = G / 255.0;
  20.     b = B / 255.0;
  21.  
  22.     MAX = max(r,max(g,b) );
  23.     MIN = min(r,min(g,b));
  24.     d = MAX - MIN;
  25.     v = MAX;
  26.  
  27.     if (MAX - 0 < 1e-9) {
  28.         s = 0;
  29.     }
  30.     else {
  31.         s = d / MAX;
  32.     }
  33.     if (d - 0 < 1e-9) {
  34.         h = 0;
  35.     }
  36.     else {
  37.         s = d / MAX;
  38.         if (MAX - r < 1e-9) {
  39.             h = 60 * ((g - b) / d);
  40.         }
  41.         else if (MAX - g < 1e-9) {
  42.             h = 60 * (2 + (b - r) / d);
  43.         }
  44.         else if (MAX - b < 1e-9) {
  45.             h = 60 * (4 + (r - g) / d);
  46.         }
  47.         if (h - 0 < 1e-9) {
  48.             h = h + 360;
  49.         }
  50.  
  51.     }
  52.     cout << fixed << setprecision(4) << h << ","
  53.     << fixed << setprecision(4) << s * 100 << "%,"
  54.     << fixed << setprecision(4) << v * 100 << "%";
  55. }
  56.  
  57. /*
  58. Sample input:
  59. 0 215 0
  61. Sample output:
  62. 120.0000,100.0000%,84.3137%
  63. */
  64.  
  65. /*
  66. Additional input:
  67. 0 0 0
  69. Additional output:
  70. 0.0000,0.0000%,0.0000%
  71. */
  72.  
  73. /*
  74. Additional input:
  75. 255 255 255
  77. Additional output:
  78. 0.0000,0.0000%,100.0000%
  79. */
  80.  
  81. /*
  82. Additional input:
  83. 123 54 45
  85. Additional output:
  86. 6.9231,63.4146%,48.2353%
  87. */

第2季（011-020）

011.乘数模

note：

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

2.涉及一些数论知识：

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

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

  1. //Difficulty: 2/10
  2. //Importance:10/10
  3.  
  4. //learn some formulas for mod
  5. //to prevent exceeding and TE
  6.  
  7. #include <iostream>
  8.  
  9. using namespace std;
  10.  
  11. int main()
  12. {
  13.     unsigned long long a, b, m, r;
  14.     cin >> a >> b >> m;
  15.     r = ((a % m) * (b % m)) % m;
  16.     cout << r;
  17. }
  18.  
  19. /*
  20. Sample input:
  21. 123 456 100000
  23. Sample output:
  24. 56088
  25.  */
  26.  
  27. /*
  28. Additional input:
  29. 1244 12567 5758
  31. Additional output:
  32. 378
  33. */

012.方阵

note:

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

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

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

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

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

  1. //Difficulty: 2/10
  2. //Importance: 4/10
  3.  
  4. //discover some wonderful functions in cmath!
  5.  
  6. #include <iostream>
  7. #include <cmath>
  8.  
  9. using namespace std;
  10.  
  11. void generatematrix(int n) {
  12.     for (int i = 1; i <= n; i++) {
  13.         for (int j = 1; j <= n; j++) {
  14.             int v = abs(i - j);//or : int v = (i-j)>0 ? i-j : j-i ;
  15.             cout << v << "  ";
  16.         }
  17.         cout << endl;
  18.     }
  19. }
  20.  
  21. int main()
  22. {
  23.     int m;
  24.     cin >> m;
  25.     generatematrix(m);
  26. }
  27.  
  28. /*
  29. Sample input:
  30. 5
  32. Sample output:
  33. 0  1  2  3  4
  34. 1  0  1  2  3
  35. 2  1  0  1  2
  36. 3  2  1  0  1
  37. 4  3  2  1  0
  38. */
  39.  
  40. /*
  41. Additional input:
  42. 2
  44. Additional output:
  45. 0  1
  46. 1  0
  47. */

013.组合数

note：

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

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

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

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

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. //simple enum
  5.  
  6. #include <iostream>
  7.  
  8. using namespace std;
  9.  
  10. int main() {
  11.     int a,b,c,d,n,sum=0;
  12.     cin>>n;
  13.     for (a=0;a<=9;++a){
  14.         for(b=0;b<=9;++b){
  15.             for(c=0;c<=9;++c){
  16.                 for(d=0;d<=9;++d){
  17.                     if (n==a+b+c+d) sum++;
  18.                     else sum=sum+0;
  19.                 }
  20.             }
  21.         }
  22.     }
  23.     cout<<sum;
  24. }
  25.  
  26. /*
  27. Sample input:
  28. 15
  30. Sample output:
  31. 592
  32. */
  33.  
  34. /*
  35. Additional input:
  36. 37
  38. Additional output:
  39. 0
  40. */

014.比率

note：

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

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

  1. //Difficulty: 3/10
  2. //Importance:10/10
  3.  
  4. //memorize gcd!
  5.  
  6. #include <iostream>
  7. #include <cmath>
  8.  
  9. using namespace std;
  10.  
  11. int gcd(int a,int b){
  12.     if(b==0){return a;}
  13.     return gcd(b,a%b);
  14. }
  15.  
  16. int main(){
  17.     double fz;
  18.     int fm=1,m;
  19.     cin>>fz;
  20.     for(fz;fz!=floor(fz);fz=fz*10,fm=fm*10);
  21.     m=gcd((int)(fz),fm);
  22.     fz=fz/m;
  23.     fm=fm/m;
  24.     cout<<fz<<"/"<<fm;
  25. }
  26.  
  27. /*
  28. Sample input:
  29. 4.2
  31. Sample output:
  32. 21/5
  33. */
  34.  
  35. /*
  36. Additional input:
  37. 3.33333
  39. Additional output:
  40. 333333/100000
  41. */

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

note：

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

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

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

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

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

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

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

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

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

  1. //Difficulty: 3/10
  2. //Importance: 3/10
  3.  
  4. //I don't think tuple necessary
  5. //you can use point to replace
  6. //more acceptable way is using Global variables
  7. //plus,getchar() is very useful
  8.  
  9. //version 1:use array to pass values(recommended)
  10.  
  11. #include <iostream>
  12.  
  13. using namespace std;
  14.  
  15. int gcd(int x,int y){
  16.     if(y==0)return x;
  17.     else return gcd(y,x%y);
  18. }
  19.  
  20. void add(int fz1,int fm1,int fz2,int fm2,int arr[4][2]){
  21.     int nfz,nfm,d;
  22.     nfz=fz1*fm2+fz2*fm1;
  23.     nfm=fm1*fm2;
  24.     d=gcd(nfz,nfm);
  25.     nfz=nfz/d;
  26.     nfm=nfm/d;
  27.     arr[0][0]=nfz;
  28.     arr[0][1]=nfm;
  29. }
  30.  
  31. void sub(int fz1,int fm1,int fz2,int fm2,int arr[4][2]){
  32.     int nfz,nfm,d;
  33.     nfz=fz1*fm2-fz2*fm1;
  34.     nfm=fm1*fm2;
  35.     d=gcd(nfz,nfm);
  36.     nfz=nfz/d;
  37.     nfm=nfm/d;
  38.     arr[1][0]=nfz;
  39.     arr[1][1]=nfm;
  40. }
  41.  
  42. void multi(int fz1,int fm1,int fz2,int fm2,int arr[4][2]){
  43.     int nfz,nfm,d;
  44.     nfz=fz1*fz2;
  45.     nfm=fm1*fm2;
  46.     d=gcd(nfz,nfm);
  47.     nfz=nfz/d;
  48.     nfm=nfm/d;
  49.     arr[2][0]=nfz;
  50.     arr[2][1]=nfm;
  51. }
  52.  
  53. void divi(int fz1,int fm1,int fz2,int fm2,int arr[4][2]){
  54.     int nfz,nfm,d;
  55.     nfz=fz1*fm2;
  56.     nfm=fm1*fz2;
  57.     d=gcd(nfz,nfm);
  58.     nfz=nfz/d;
  59.     nfm=nfm/d;
  60.     arr[3][0]=nfz;
  61.     arr[3][1]=nfm;
  62. }
  63.  
  64. int main() {
  65.     int fz1,fm1,fz2,fm2;
  66.     cin>>fz1;
  67.     getchar();
  68.     cin>>fm1;
  69.     cin>>fz2;
  70.     getchar();
  71.     cin>>fm2;
  72.  
  73.     int arr[4][2];
  74.  
  75.     add(fz1,fm1,fz2,fm2,arr);
  76.     sub(fz1,fm1,fz2,fm2,arr);
  77.     multi(fz1,fm1,fz2,fm2,arr);
  78.     divi(fz1,fm1,fz2,fm2,arr);
  79.  
  80.     char symbol[4]={'+','-','*','/'};
  81.  
  82.     for(int i=0;i<4;++i){
  83.         cout<<'('<<fz1<<'/'<<fm1<<')'<<symbol[i]<<'('<<fz2<<'/'<<fm2<<')'
  84.             <<'='<<arr[i][0]<<'/'<<arr[i][1]<<endl;
  85.     }
  86.  
  87.     return 0;
  88. }
  89.  
  90. //version 2:use tuple
  91.  
  92. #include <iostream>
  93. #include <tuple>
  94.  
  95. using namespace std;
  96.  
  97. int gcd(int x,int y){
  98.     if(y==0)return x;
  99.     else return gcd(y,x%y);
  100. }
  101.  
  102. tuple<int,int> add(int fz1,int fm1,int fz2,int fm2){
  103.     int nfz,nfm,d;
  104.     nfz=fz1*fm2+fz2*fm1;
  105.     nfm=fm1*fm2;
  106.     d=gcd(nfz,nfm);
  107.     nfz=nfz/d;
  108.     nfm=nfm/d;
  109.     return make_tuple(nfz,nfm);
  110. }
  111.  
  112. tuple<int,int> sub(int fz1,int fm1,int fz2,int fm2){
  113.     int nfz,nfm,d;
  114.     nfz=fz1*fm2-fz2*fm1;
  115.     nfm=fm1*fm2;
  116.     d=gcd(nfz,nfm);
  117.     nfz=nfz/d;
  118.     nfm=nfm/d;
  119.     return make_tuple(nfz,nfm);
  120. }
  121.  
  122. tuple<int,int> multi(int fz1,int fm1,int fz2,int fm2){
  123.     int nfz,nfm,d;
  124.     nfz=fz1*fz2;
  125.     nfm=fm1*fm2;
  126.     d=gcd(nfz,nfm);
  127.     nfz=nfz/d;
  128.     nfm=nfm/d;
  129.     return make_tuple(nfz,nfm);
  130. }
  131.  
  132. tuple<int,int> divi(int fz1,int fm1,int fz2,int fm2){
  133.     int nfz,nfm,d;
  134.     nfz=fz1*fm2;
  135.     nfm=fm1*fz2;
  136.     d=gcd(nfz,nfm);
  137.     nfz=nfz/d;
  138.     nfm=nfm/d;
  139.     return make_tuple(nfz,nfm);
  140. }
  141.  
  142. int main() {
  143.     int fz1,fm1,fz2,fm2;
  144.     cin>>fz1;
  145.     getchar();
  146.     cin>>fm1;
  147.     cin>>fz2;
  148.     getchar();
  149.     cin>>fm2;
  150.     tuple<int,int> result0=add(fz1,fm1,fz2,fm2);
  151.     cout<<'('<<fz1<<'/'<<fm1<<')'<<'+'<<'('<<fz2<<'/'<<fm2<<')'
  152.     <<'='<<get<0>(result0)<<'/'<<get<1>(result0)<<endl;
  153.     tuple<int,int> result1=sub(fz1,fm1,fz2,fm2);
  154.     cout<<'('<<fz1<<'/'<<fm1<<')'<<'-'<<'('<<fz2<<'/'<<fm2<<')'
  155.     <<'='<<get<0>(result1)<<'/'<<get<1>(result1)<<endl;
  156.     tuple<int,int> result2=multi(fz1,fm1,fz2,fm2);
  157.     cout<<'('<<fz1<<'/'<<fm1<<')'<<'*'<<'('<<fz2<<'/'<<fm2<<')'
  158.     <<'='<<get<0>(result2)<<'/'<<get<1>(result2)<<endl;
  159.     tuple<int,int> result3=divi(fz1,fm1,fz2,fm2);
  160.     cout<<'('<<fz1<<'/'<<fm1<<')'<<'/'<<'('<<fz2<<'/'<<fm2<<')'
  161.     <<'='<<get<0>(result3)<<'/'<<get<1>(result3)<<endl;
  162. }
  163.  
  164.  
  165. /*
  166. Sample input:
  167. 2/3
  168. 3/7
  170. Sample output:
  171. (2/3)+(3/7)=23/21
  172. (2/3)-(3/7)=5/21
  173. (2/3)*(3/7)=2/7
  174. (2/3)/(3/7)=14/9
  175. */
  176.  
  177. /*
  178. Additional input:
  179. 1/2
  180. 1/2
  182. Additional output:
  183. (1/2)+(1/2)=1/1
  184. (1/2)-(1/2)=0/1
  185. (1/2)*(1/2)=1/4
  186. (1/2)/(1/2)=1/1
  187. */

016.幂数模

note：

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

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

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

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

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

  1. //Difficulty: 3/10
  2. //Importance: 10/10
  3.  
  4. //learn fast mod algorithm!
  5. //you can use Bitwise operations
  6. //but fast mod is better
  7.  
  8. #include<iostream>
  9.  
  10. typedef unsigned long long ll;
  11.  
  12. using namespace std;
  13.  
  14. int main(){
  15.     ll a,b,m,ans=1;
  16.     cin>>a>>b>>m;
  17.     while(b){
  18.         if(b&1){
  19.             ans=(ans*a)%m;
  20.         }
  21.         a=(a*a)%m;
  22.         b>>=1;
  23.     }
  24.     cout<<ans;
  25. }
  26.  
  27. /*
  28. Sample input:
  29. 2 10 9
  31. Sample output:
  32. 7
  33. */
  34.  
  35. /*
  36. Additional input:
  37. 2 63 1314
  39. Additional output:
  40. 512
  41. */

017.对称数

note：

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

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

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

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

  1. //Difficulty: 5/10
  2. //Importance: 5/10
  3.  
  4. //there must be longer,but stupider ways
  5. //why not take C++'s unique advantages?
  6. //such as map/unordered_map,iterator(which is easier to use)
  7.  
  8. #include<iostream>
  9. #include<string>
  10. #include<unordered_map>
  11.  
  12. using namespace std;
  13.  
  14. int main()
  15. {
  16.     string ori,inver;
  17.     cin>>ori;
  18.     unordered_map<char,char> table{{'0','0'},{'1','1'},{'6','9'},{'9','6'},{'8','8'}};
  19.     for(auto it=ori.rbegin();it!=ori.rend();++it){
  20.         inver.push_back(table[*it]);}// or: inver+=table[*it];
  21.     if(inver==ori)cout<<"Yes";
  22.     else cout<<"No";
  23. }
  24.  
  25. /*
  26. Sample input:
  27. 916
  29. Sample output:
  30. Yes
  31. */
  32.  
  33. /*
  34. Additional input:
  35. 1000081800001
  37. Additional output:
  38. Yes
  39. */

018.操作数

note：

1.理清楚逻辑就行；

  1. //Difficulty: 3/10
  2. //Importance: 3/10
  3.  
  4. //version 1: no func
  5.  
  6. #include<iostream>
  7.  
  8. using namespace std;
  9.  
  10. int main()
  11. {
  12.     int n,n1,d,sum,k;
  13.     cin>>n;
  14.     sum=0;
  15.     n1=n;
  16.     for(k=0;n1>0;++k){
  17.         while(n>0){
  18.             d=n%10;
  19.             sum+=d;
  20.             n=n/10;
  21.         }
  22.         n1-=sum;
  23.         n=n1;
  24.         sum=0;
  25.     }
  26.     cout<<k;
  27. }
  28.  
  29. //version 2: func
  30.  
  31. #include<iostream>
  32.  
  33. int sumPerDig(int n){
  34.     int sum = 0;
  35.     while(n){
  36.         sum += n%10;
  37.         n /= 10;
  38.     }
  39.     return sum;
  40.  
  41. }
  42.  
  43. int main(){
  44.     int n,cnt=0;
  45.     cin>>n;
  46.  
  47.     while(n){
  48.         n -= sumPerDig(n);
  49.         ++cnt;
  50.     }
  51.  
  52.     cout<<cnt;
  53.  
  54.     return 0;
  55. }
  56.  
  57.  
  58. /*
  59. Sample input:
  60. 21
  62. Sample output:
  63. 3
  64. */
  65.  
  66. /*
  67. Additional input:
  68. 164
  70. Additional output:
  71. 17
  72. */

019.倍数和 

note：

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

  1. //Difficulty: 3/10
  2. //Importance: 3/10
  3.  
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. int main()
  9. {
  10.     int T;
  11.     cin>>T;
  12.     int num[T];
  13.     for(int i=0;i<T;++i){
  14.         int n;
  15.         cin>>n;
  16.         int sum=0;
  17.         for(int j=1;j<n;j++){
  18.             if (j%3==0||j%5==0){
  19.                 sum+=j;
  20.             }
  21.         }
  22.         num[i]=sum;
  23.     }
  24.     for(int k=0;k<T;++k){
  25.         cout<<num[k]<<endl;
  26.     }
  27. }
  28.  
  29. /*
  30. Sample input:
  31. 2
  32. 10
  33. 100
  35. Sample output:
  36. 23
  37. 2318
  38. */
  39.  
  40. /*
  41. Additional input:
  42. 2
  43. 541
  44. 5115
  46. Additional output:
  47. 68310
  48. 6102195
  49. */

020.级数和

note：

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

2.关于wid()函数

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. int wid(int n){
  9.     int i=0;
  10.     if(n==0)return 1;
  11.     else{
  12.         while(n){
  13.             n=n/10;
  14.             i++;
  15.         }
  16.         return i;
  17.     }
  18. }
  19.  
  20. double decimal(double n){
  21.     int w;
  22.     w=wid(n);
  23.     for(int i=0;i<w;++i){
  24.         n=n/10.0;
  25.     }
  26.     return n;
  27. }
  28.  
  29. int main()
  30. {
  31.     int n;
  32.     cin>>n;
  33.     int z[n];
  34.     for(int i=0;i<n;++i){
  35.         z[i]=i+1;
  36.     }
  37.     int x[n];
  38.     for(int j=0;j<n;++j){
  39.         x[j]=j+2;
  40.     }
  41.  
  42.     double sum=0.0,s;
  43.     for(int k=0;k<n;++k){
  44.         s=(double)z[k]+decimal((double)x[k]);
  45.         sum+=s;
  46.     }
  47.     cout<<z[0]+decimal(x[0]);
  48.     for(int k=0;k<n-1;++k){
  49.         cout<<'+'<<z[k+1]+decimal((double)x[k+1]);
  50.     }
  51.     cout<<'='<<sum;
  52. }
  53.  
  54. /*
  55. Sample input:
  56. 10
  58. Sample output:
  59. 1.2+2.3+3.4+4.5+5.6+6.7+7.8+8.9+9.1+10.11=59.61
  60. */
  61.  
  62. /*
  63. Additional input:
  64. 5
  66. Additional output:
  67. 1.2+2.3+3.4+4.5+5.6=17
  68. */

第3季（021-030）

021.竖式乘法

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. //You can use setfill('?') before setw(n) to control
  5. //the character used for filling setw (default is space).
  6.  
  7. #include <iostream>
  8. #include <iomanip>
  9.  
  10. using namespace std;
  11.  
  12. int wid(int n){
  13.     int i=0;
  14.     if(n==0)return 1;
  15.     else{
  16.         while(n){
  17.             n=n/10;
  18.             i++;
  19.         }
  20.         return i;
  21.     }
  22. }
  23.  
  24. int main() {
  25.     int a,b,b0,i=0,ans,n,n0;
  26.     cin>>a>>b;
  27.     int z[wid(b)];
  28.     b0=b;
  29.     while(b0>0){
  30.         int c=b0%10;
  31.         z[i]=c*a;
  32.         b0=b0/10;
  33.         ++i;
  34.     }
  35.     ans=a*b;
  36.     n=wid(ans);
  37.     n0=n;
  38.     cout<<setw(n+1)<<a<<endl<<'x'<<setw(n)<<b<<endl;
  39.     for(int j=0;j<n+1;++j){
  40.         cout<<'-';
  41.     }cout<<endl;
  42.     for(int j=0;j<wid(b)-1;++j){
  43.         cout<<setw(n0+1)<<z[j]<<endl;
  44.         n0=n0-1;
  45.     }
  46.     cout<<'+'<<z[wid(b)-1]<<endl;
  47.     for(int j=0;j<n+1;++j){
  48.         cout<<'-';
  49.     }
  50.     cout<<endl<<setw(n+1)<<ans;
  51. }
  52.  
  53. /*
  54. Sample input:
  55. 12345 120
  57. Sample output:
  58.    12345
  59. x    120
  60. --------
  61.        0
  62.   24690
  63. +12345
  64. --------
  65.  1481400
  66. */
  67.  
  68. /*
  69. Additional input:
  70. 12479 9347
  72. Additional output:
  73.      12479
  74. x     9347
  75. ----------
  76.      87353
  77.     49916
  78.    37437
  79. +112311
  80. ----------
  81.  116641213
  82. */

022.查找数列

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5. #include<tuple>
  6.  
  7. using namespace std;
  8.  
  9. tuple<int,int> sum(int n){
  10.     int i=1,k;
  11.     while(((i*(i+1))/2)<n){
  12.         ++i;
  13.     }
  14.     i=i-1;
  15.     k=(i*(i+1))/2;
  16.     return make_tuple(i+1,k);
  17. }
  18.  
  19. int main(){
  20.     int n,k;
  21.     cin>>n;
  22.     tuple<int,int> result=sum(n);
  23.     int a[get<0>(result)];
  24.     for(int j=0;j<get<0>(result);++j){
  25.         a[j]=j+1;
  26.     }
  27.     k=get<1>(result);
  28.     cout<<a[n-k-1];
  29. }
  30.  
  31. /*
  32. Sample input:
  33. 14
  35. Sample output:
  36. 4
  37. */
  38.  
  39. /*
  40. Additional input:
  41. 45
  43. Additional output:
  44. 9
  45. */

023.毕达哥拉斯三元组

  1. //Difficulty: 1/10
  2. //Importance: 1/10
  3.  
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. int main(){
  9.     int n,a,b,c;
  10.     cin>>n;
  11.     for(a=0;a<n/4;a++){
  12.         for(b=n/4+1;b>n/4&&b<n/2;b++){
  13.             c=n-a-b;
  14.             if(a*a+b*b==c*c&&c>b){
  15.                 cout<<a*b*c;
  16.             }
  17.         }
  18.     }
  19. }
  20.  
  21. /*
  22. Sample input:
  23. 1000
  25. Sample output:
  26. 31875000
  27. */
  28.  
  29. /*
  30. Additional input:
  31. 42360
  33. Additional output:
  34. 1101603584441138216
  35. */

024.余数和

  1. //Difficulty: 1/10
  2. //Importance: 1/10
  3.  
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. int main(){
  9.     int n,k,s,sum=0;
  10.     cin>>n>>k;
  11.     for(int i=0;i<n;++i){
  12.         s=k%(i+1);
  13.         sum+=s;
  14.     }
  15.     cout<<sum;
  16. }
  17.  
  18. /*
  19. Sample input:
  20. 10 5
  22. Sample output:
  23. 29
  24. */
  25.  
  26. /*
  27. Additional input:
  28. 45 2
  30. Additional output:
  31. 86
  32. */

025.最大数字

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. int wid(int n){
  9.     int i=0;
  10.     if(n==0)return 1;
  11.     else{
  12.         while(n){
  13.             n=n/10;
  14.             i++;
  15.         }
  16.         return i;
  17.     }
  18. }
  19.  
  20. int main(){
  21.     int n,m,m0,f,l,w;
  22.     cin>>n;
  23.     m=n;
  24.     m0=m;
  25.     for(;m0>=0;--m0){
  26.         int sum=0;
  27.         m=m0;
  28.         w=wid(m);
  29.         for(int i=0;i<w-1;++i){
  30.             l=m%10;
  31.             m=m/10;
  32.             f=m%10;
  33.             if (f<=l) sum++;
  34.         }
  35.         if (sum==w-1){
  36.             cout<<m0;
  37.             break;
  38.         }
  39.     }
  40. }
  41.  
  42. /*
  43. Sample input:
  44. 200
  46. Sample output:
  47. 199
  48. */
  49.  
  50. /*
  51. Additional input:
  52. 246545
  54. Additional output:
  55. 245999
  56. */

026.倒水

note：

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

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

  1. //Difficulty: 5/10
  2. //Importance:10/10
  3.  
  4. //a classic BFS
  5.  
  6. #include <iostream>
  7. #include <queue>
  8. #include <set>
  9. #include <array>
  10.  
  11. using namespace std;
  12.  
  13. int main(){
  14.     int m,n,d;
  15.     cin>>m>>n>>d;
  16.     queue<array<int,2>> q;
  17.     set<array<int,2>>visited;
  18.     q.push({0,0});
  19.     visited.insert({0,0});
  20.     int minop=0;
  21.     while(!q.empty()){
  22.         int size=q.size();
  23.         for(int i=0;i<size;++i){
  24.             array<int,2> curr=q.front();
  25.             q.pop();
  26.             int x = curr[0];
  27.             int y = curr[1];
  28.             if (x == d || y == d) {
  29.                 cout <<minop<<endl;
  30.                 return 0;
  31.             }
  32.             array<int, 2> next;
  33.  
  34.             //fill m
  35.             next = {m, y};
  36.             if (visited.find(next) == visited.end()) {
  37.                 q.push(next);
  38.                 visited.insert(next);
  39.             }
  40.  
  41.             //fill n
  42.             next = {x, n};
  43.             if (visited.find(next) == visited.end()) {
  44.                 q.push(next);
  45.                 visited.insert(next);
  46.             }
  47.  
  48.             //empty m
  49.             next={0,y};
  50.             if(visited.find(next)==visited.end()){
  51.                 q.push(next);
  52.                 visited.insert(next);
  53.             }
  54.  
  55.             //empty n
  56.             next={x,0};
  57.             if(visited.find(next)==visited.end()){
  58.                 q.push(next);
  59.                 visited.insert(next);
  60.             }
  61.  
  62.             //m to n
  63.             int pourAmount1 = std::min(x, n - y);
  64.             next = {x - pourAmount1, y + pourAmount1};
  65.             if (visited.find(next) == visited.end()) {
  66.                 q.push(next);
  67.                 visited.insert(next);
  68.             }
  69.  
  70.             //n to m
  71.             int pourAmount2 = std::min(y, m-x);
  72.             next = {x + pourAmount2, y - pourAmount2};
  73.             if (visited.find(next) == visited.end()) {
  74.                 q.push(next);
  75.                 visited.insert(next);
  76.             }
  77.  
  78.         }minop++;
  79.     }
  80. }
  81.  
  82. /*
  83. Sample input:
  84. 3 5 4
  86. Sample output:
  87. 6
  88. */
  89.  
  90. /*
  91. Additional input:
  92. 5 9 7
  94. Additional output:
  95. 12
  96. */
  97.  
  98. /*
  99. Additional input:
  100. 28 17 13
  102. Additional output:
  103. 26
  104. */

027.好数字

  1. //Difficulty: 3/10
  2. //Importance: 3/10
  3.  
  4. //fastmod algorithm
  5.  
  6. #include<iostream>
  7.  
  8. typedef long long ll;
  9.  
  10. using namespace std;
  11.  
  12.  
  13. ll fastmod(ll base,ll power){
  14.     ll m=1000000007,res=1;
  15.     while(power){
  16.         if(power&1){
  17.             res=(res*base)%m;
  18.         }
  19.         base=(base*base)%m;
  20.         power>>=1;
  21.     }
  22.     return res;
  23. }
  24.  
  25. int main(){
  26.     ll n,evenCount,oddCount,ans,m=1000000007;
  27.     cin>>n;
  28.     evenCount=fastmod(5,(n+1)/2);
  29.     //each even point corresponds to 5 possibilities(5 even numbers:0,2,4,6,8)
  30.     //occurtimes=(n+1)/2
  31.     oddCount=fastmod(4,n/2);
  32.     //each odd point corresponds to 4 possibilities(4 prime numbers:2,3,5,7)
  33.     //occurtimes=n/2
  34.     ans=(evenCount*oddCount)%m;
  35.     cout<<ans;
  36. }
  37.  
  38. /*
  39. Sample input:
  40. 1
  42. Sample output:
  43. 5
  44. */
  45.  
  46. /*
  47. Additional input:
  48. 4
  50. Additional output:
  51. 400
  52. */

028.俄罗斯农夫算法

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. int main(){
  9.     int a,b,sum=0;
  10.     cin>>a>>b;
  11.     while(a>0) {
  12.         cout << a << ' ' << b<<endl;
  13.         if (a&1) {
  14.             sum += b;
  15.         }
  16.         a /= 2;
  17.         b *= 2;
  18.     }
  19.     cout<<sum;
  20. }
  21.  
  22. /*
  23. Sample input:
  24. 11 3
  26. Sample output:
  27. 11 3
  28. 5 6
  29. 2 12
  30. 1 24
  31. 33
  32. */
  33.  
  34. /*
  35. Additional input:
  36. 54 67
  38. Additional output:
  39. 54 67
  40. 27 134
  41. 13 268
  42. 6 536
  43. 3 1072
  44. 1 2144
  45. 3618
  46. */

029.阶乘倍数

note：

1.很重要；

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

  1. //Difficulty: 5/10
  2. //Importance:10/10
  3.  
  4. //TE warning!
  5. //use binary search and transformation
  6. //never simply use violent factorial(too slow)
  7.  
  8. #include<iostream>
  9. #include<vector>
  10.  
  11. using namespace std;
  12.  
  13. bool check(long long mid, const vector<long long>& primes, const vector<long long>& powers) {
  14.     for (int i = 0; i < primes.size(); i++) {
  15.         long long cnt = 0, p = primes[i];
  16.         while (mid >= p) {
  17.             cnt += mid / p;
  18.             p *= primes[i];
  19.         }
  20.         if (cnt < powers[i]) {
  21.             return false;
  22.         }
  23.     }
  24.     return true;
  25. }
  26.  
  27. int main() {
  28.     long long k;
  29.     cin >> k;
  30.     vector<long long> primes, powers;
  31.     for (long long i = 2; i * i <= k; i++) {
  32.         if (k % i == 0) {
  33.             long long cnt = 0;
  34.             while (k % i == 0) {
  35.                 k /= i;
  36.                 cnt++;
  37.             }
  38.             primes.push_back(i);
  39.             powers.push_back(cnt);
  40.         }
  41.     }
  42.     if (k > 1) {
  43.         primes.push_back(k);
  44.         powers.push_back(1);
  45.     }
  46.     long long left = 1, right = 1e18, ans = -1;
  47.     while (left <= right) {
  48.         long long mid = (left + right) / 2;
  49.         if (check(mid, primes, powers)) {
  50.             ans = mid;
  51.             right = mid - 1;
  52.         }
  53.         else {
  54.             left = mid + 1;
  55.         }
  56.     }
  57.     cout << ans << endl;
  58. }
  59.  
  60. /*
  61. Sample input:
  62. 30
  64. Sample output:
  65. 5
  66. */
  67.  
  68. /*
  69. Additional input:
  70. 5195
  72. Additional output:
  73. 1039
  74. */
  75.  
  76. /*
  77. Additional input:
  78. 1455
  80. Additional output:
  81. 97
  82. */

030.方案数

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     int n, sum = 0;
  10.     cin >> n;
  11.     int m;
  12.     double a;
  13.     for (m = 1; m * m< 2 * n; ++m) {
  14.         a = (double)n / (double)m - (double)m * 0.5 + 0.5;
  15.         if (a - (int)a == 0) {
  16.             sum++;
  17.         }
  18.     }
  19.     cout << sum;
  20. }
  21.  
  22. /*
  23. Sample input:
  24. 9
  26. Sample output:
  27. 3
  28. */
  29.  
  30. /*
  31. Additional input:
  32. 757
  34. Additional output:
  35. 2
  36. */

第4季（031-040）

031.素数

note：

1.很重要；

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <cstring>
  6.  
  7. using namespace std;
  8.  
  9. int primecount(int n){
  10.     bool isprime[n+1];
  11.     int prime[n+1];
  12.     int cnt=0;
  13.     memset(isprime,true,sizeof(isprime));
  14.     isprime[1]=false;
  15.     for(int i=2;i<=n;++i){
  16.         if(isprime[i]) prime[++cnt]=i;
  17.         for(int j=1;j<=cnt && i*prime[j]<=n;++j){
  18.             isprime[i*prime[j]]=false;
  19.             if(i%prime[j]==0) break;
  20.         }
  21.     }
  22.     return cnt;
  23. }
  24.  
  25. int main() {
  26.     int a,b;
  27.     cin>>a>>b;
  28.     int cnt1=primecount(a-1);
  29.     int cnt2=primecount(b);
  30.     cout<<cnt2-cnt1;
  31. }
  32.  
  33. /*
  34. Sample input:
  35. 10 100
  36.  
  37. Sample output:
  38. 21
  39. */
  40.  
  41. /*
  42. Additional input:
  43. 19 41455
  44.  
  45. Additional output:
  46. 4329
  47. */

032.基思数

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <vector>
  6. #include<algorithm>
  7.  
  8. using namespace std;
  9.  
  10. inline bool IsKeith(int N){
  11.     int tmp=N;
  12.     vector<int>sequence;
  13.     while(tmp){
  14.         sequence.push_back(tmp%10);
  15.         tmp/=10;
  16.     }
  17.     reverse(sequence.begin(),sequence.end());
  18.     int num=sequence.size()-1;
  19.     int sum = 0;
  20.     while(sum<N){
  21.         sum=0;
  22.         for(int i=num;i>=0;--i){
  23.             sum+=sequence[i];
  24.         }
  25.         sequence.erase(sequence.begin());
  26.         sequence.push_back(sum);
  27.         if(sum==N) return true;
  28.     }
  29.     return false;
  30. }
  31.  
  32. int main(){
  33.     int N;
  34.     cin>>N;
  35.     if(IsKeith(N)) cout<<"Yes"<<endl;
  36.     else cout<<"No"<<endl;
  37. }
  38.  
  39. /*
  40. Sample input:
  41. 197
  43. Sample output:
  44. Yes
  45. */
  46.  
  47. /*
  48. Additional input:
  49. 891
  51. Additional output:
  52. No
  53. */

033.幂函数【C++】

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5. #include<iomanip>
  6.  
  7. using namespace std;
  8.  
  9. double pow(double base,int exp=2){
  10.     double n=base;
  11.     for(;exp>1;--exp){
  12.         base*=n;
  13.     }
  14.     return base;
  15. }
  16.  
  17. int main(){
  18.     double base;
  19.     int exp;
  20.     cin>>base>>exp;
  21.     cout<<fixed<<setprecision(6)<<pow(base)<<endl
  22.     <<fixed<<setprecision(6)<<pow(base,exp);
  23. }
  24.  
  25. /*
  26. Sample input:
  27. 1.23 5
  29. Sample output:
  30. 1.512900
  31. 2.815306
  32. */
  33.  
  34. /*
  35. Additional input:
  36. 1.01 365
  38. Additional output:
  39. 1.020100
  40. 37.783434
  41. */

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

note：

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5. #include<cmath>
  6. #include<tuple>
  7. #include<cstring>
  8. #include<iomanip>
  9. #define pi 3.1415926
  10. /*
  11.     pay attention!!! here noj define pi as 3.1415926
  12.     instead of 3.141592654(which is more precise),
  13.     you MUST define it exactly 3.1415926!!!
  14. */
  15.  
  16. using namespace std;
  17.  
  18. /*  noj is likely to pay no attention to return type "double",
  19.     so don't add ".0" after the int data in your calculation either,
  20.     even actually this is important(obviously this is his fault,
  21.     clion would even give you warnings if you don't do so,
  22.     this make me thought: is noj using a rubbish IDE?)
  23. */
  24.  
  25. double v(double r){
  26.     return 4*pi*r*r*r/3;
  27. }
  28.  
  29. double v(double r,double h){
  30.     return pi*r*r*h/3;
  31. }
  32.  
  33. double v(long a){
  34.     return a*a*a/1;
  35. }
  36.  
  37. double v(double r,long h){
  38.     return pi*r*r*h/1;
  39. }
  40.  
  41. double v(long l,long w,long h){
  42.     return l*w*h;
  43. }
  44. /*
  45.     if you are careful enough,you may fing that the 
  46.     following two examples are in reverse order in 
  47.     the stem and in the chart, this is also noj's mistake.
  48. */
  49. tuple <double,double> v(double r,double R,double h){
  50.     double m=sqrt(R*R-r*r);
  51.     double v1,v2;
  52.     double h1=R+m;
  53.     v1=(pi/3.0)*(3.0*R-h1)*h1*h1;
  54.     double h2=R-m;
  55.     v2=(pi/3.0)*(3.0*R-h2)*h2*h2;
  56.     return make_tuple(v1,v2);
  57. }
  58.  
  59. tuple <double,double> v(double r,double R,double h,double l){
  60.     double m=sqrt(R*R-r*r);
  61.     double v0,v1,v2;
  62.     v0=pi*r*r*l;
  63.     double h1=R+m;
  64.     v1=v0+(pi/3.0)*(3.0*R-h1)*h1*h1*2;
  65.     double h2=R-m;
  66.     v2=v0+(pi/3.0)*(3.0*R-h2)*h2*h2*2;
  67.     return make_tuple(v1,v2);
  68. }
  69.  
  70. double v(long r,double R,double h){
  71.     return pi*h*(r*r+R*R+R*r)/3;
  72. }
  73.  
  74. double v(double a,double b,long c){
  75.     return 4*pi*a*b*c/3;
  76. }
  77.  
  78. double v(long a,long h){
  79.     return a*a*h/3;
  80. }
  81.  
  82. double v(long d1,long d2,double l){
  83.     return pi*(d1*d1-d2*d2)*l/4;
  84. }
  85.  
  86. int main(){
  87.     bool z[12];
  88.     memset(z, false, sizeof(z));
  89.     double s[12],six[2],seven[2];
  90.     int t;
  91.     cin>>t;
  92.     for(int i=0;i<t;++i) {
  93.         int n;
  94.         cin>>n;
  95.         z[n]=true;
  96.         if(n==1){
  97.             double r;
  98.             cin>>r;
  99.             s[n]=v(r);
  100.         }
  101.         else if(n==2){
  102.             double r,h;
  103.             cin>>r>>h;
  104.             s[n]=v(r,h);
  105.         }
  106.         else if(n==3){
  107.             long a;
  108.             cin>>a;
  109.             s[n]=v(a);
  110.         }
  111.         else if(n==4){
  112.             double r;
  113.             long h;
  114.             cin>>r>>h;
  115.             s[n]=v(r,h);
  116.         }
  117.         else if(n==5){
  118.             long l,w,h;
  119.             cin>>l>>w>>h;
  120.             s[n]=v(l,w,h);
  121.         }
  122.         else if(n==6){
  123.             double r,R,h=0,l;
  124.             cin>>r>>R>>l;
  125.             tuple <double,double>result=v(r,R,h,l);
  126.             six[0]=get<0>(result);
  127.             six[1]=get<1>(result);
  128.         }
  129.         else if(n==7){
  130.             double r,R,h=0;
  131.             cin>>r>>R;
  132.             tuple <double,double>result=v(r,R,h);
  133.             seven[0]=get<0>(result);
  134.             seven[1]=get<1>(result);
  135.         }
  136.         else if(n==8){
  137.             long r;
  138.             double R,h;
  139.             cin>>r>>R>>h;
  140.             s[n]=v(r,R,h);
  141.         }
  142.         else if(n==9){
  143.             double a,b;
  144.             long c;
  145.             cin>>a>>b>>c;
  146.             s[n]=v(a,b,c);
  147.         }
  148.         else if(n==10){
  149.             long a,h;
  150.             cin>>a>>h;
  151.             s[n]=v(a,h);
  152.         }
  153.         else if(n==11){
  154.             long d1,d2;
  155.             double l;
  156.             cin>>d1>>d2>>l;
  157.             s[n]=v(d1,d2,l);
  158.         }
  159.     }
  160.     /*
  161.         in fact,you need all you outcomes outcome together,
  162.         but not beyond my imagination,noj STILL had no description of it...
  163.     */
  164.     for(int j=1;j<=5;++j){
  165.         if(z[j]) cout<<fixed<<setprecision(6)<<s[j]<<endl;
  166.     }
  167.     if(z[6]) cout<<six[0]<<' '<<six[1]<<endl;
  168.     if(z[7]) cout<<seven[0]<<' '<<seven[1]<<endl;
  169.     for(int j=8;j<=11;++j){
  170.         if(z[j]) cout<<s[j]<<endl;
  171.     }
  172. /*
  173.     noj had no description of demand on precision,
  174.     but noj had it in fact,I'm tired from bottom heart...
  175. */
  176. }
  177.  
  178. /*
  179. Sample input:
  180. 11
  181. 1 3
  182. 2 3 5
  183. 3 6
  184. 4 5 12
  185. 5 1 2 3
  186. 6 5 7 12
  187. 7 5 7
  188. 8 3 4 5
  189. 9 6 7 8
  190. 10 5 10
  191. 11 12 8 6
  193. Sample output:
  194. 113.097334
  195. 47.123889
  196. 216.000000
  197. 942.477780
  198. 6.000000
  199. 3641.261807 1117.203784
  200. 1349.392014 87.363002
  201. 193.731544
  202. 1407.433485
  203. 83.000000
  204. 376.991112
  205. */
  206.  
  207. /*
  208. Additional input:
  209. 11
  210. 1 8
  211. 2 7 4
  212. 3 9
  213. 4 7 11
  214. 5 1 5 6
  215. 6 5 6 13
  216. 7 5 9
  217. 8 3 5 5
  218. 9 6 9 8
  219. 10 5 13
  220. 11 12 5 4
  222. Additional output:
  223. 113.097334
  224. 47.123889
  225. 216.000000
  226. 942.477780
  227. 6.000000
  228. 3641.261807 1117.203784
  229. 1349.392014 87.363002
  230. 193.731544
  231. 1407.433485
  232. 83.000000
  233. 38390.261572
  234. */

035.可变参数平均

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <cstdarg>
  6. #include <iomanip>
  7.  
  8. using namespace std;
  9.  
  10. double avg(int cnt,...){
  11.     va_list nums;
  12.     double sum=0;
  13.     va_start(nums,cnt);
  14.     for(int i=0;i<cnt;++i){
  15.         sum+=va_arg(nums,double);
  16.     }
  17.     va_end(nums);
  18.     double result=sum/cnt;
  19.     return result;
  20. }
  21.  
  22. int main(){
  23.     double a,b,c,d,e;
  24.     cin>>a>>b>>c>>d>>e;
  25.     cout<<fixed<<setprecision(4)<<avg(2,a,b)-avg(3,c,d,e);
  26. }
  27.  
  28. /*
  29. Sample input:
  30. 1 2 3 4 5 6
  32. Sample output:
  33. -2.5000
  34. */
  35.  
  36. /*
  37. Additional input:
  38. 3 645 14 662 7
  40. Additional output:
  41. 96.3333
  42. */

036.可变参数累加

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <cstdarg>
  6.  
  7. using namespace std;
  8.  
  9. int pl(int first,...){
  10.     va_list nums;
  11.     va_start(nums,first);
  12.     int cnt=1;
  13.     while(va_arg(nums,int)){
  14.         cnt++;
  15.     }
  16.     va_end(nums);
  17.  
  18.     int sum=first;
  19.     va_start(nums,first);
  20.     for(int i=1;i<cnt;++i){
  21.         sum+=va_arg(nums,int);
  22.     }
  23.     va_end(nums);
  24.     return sum;
  25. }
  26.  
  27. int main(){
  28.     int a,b,c,d,e,f;
  29.     cin>>a>>b>>c>>d>>e>>f;
  30.     cout<<pl(a,b,0)-pl(c,d,e,f,0);
  31. }
  32.  
  33. /*
  34. Sample input:
  35. 1 2 3 4 5 6
  37. Sample output:
  38. -15
  39. */
  40.  
  41. /*
  42. Additional input:
  43. 123 5624 2645 167 3427 12354
  45. Additional output:
  46. -12846
  47. */

037.运动会

note：

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. int phiEuler(int n){
  9.     int phi[n+1],prime[n+1];
  10.     bool isSieved[n+1];
  11.     int sum = 0,cnt = 1, comp;
  12.     prime[0] = 1;
  13.     phi[1] = 1;
  14.     for (int i = 2; i < n; ++i){
  15.         if (!isSieved[i]){
  16.             prime[cnt++] = i;
  17.             phi[i] = i-1;
  18.         }
  19.         for (int j = 1; i*prime[j] <= n; ++j){
  20.             comp = i*prime[j];
  21.             isSieved[comp] = true;
  22.             if (i%prime[j] == 0){
  23.                 phi[comp] = prime[j]*phi[i];
  24.                 break;
  25.             } else{
  26.                 phi[comp] = (prime[j]-1)*phi[i];
  27.             }
  28.         }
  29.     }
  30.     for (int i = 1; i <= n-1; ++i) {
  31.         sum += phi[i];
  32.     }
  33.     return sum;
  34. }
  35.  
  36. int main() {
  37.     int n, num;
  38.     cin>>n;
  39.     num = n == 1 ? 0 : (2 * phiEuler(n) + 1);
  40.     cout<<num;
  41. }
  42.  
  43. /*
  44. Sample input:
  45. 4
  47. Sample output:
  48. 9
  49. */
  50.  
  51. /*
  52. Additional input:
  53. 99
  55. Additional output:
  56. 71315
  57. */

038.光线追踪

note：

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

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. unsigned int gcd(unsigned int a, unsigned int b){
  9.     if (b == 0) return a;
  10.     return gcd(b,a%b);
  11. }
  12.  
  13. int main(){
  14.     unsigned int n,x,l;
  15.     cin>>n>>x;
  16.     l = 3*(n-gcd(n,x));
  17.     cout<<l;
  18. }
  19.  
  20. /*
  21. Sample input:
  22. 5 2
  24. Sample output:
  25. 12
  26. */
  27.  
  28. /*
  29. Additional input:
  30. 5 3
  32. Additional output:
  33. 12
  34. */
  35.  
  36. /*
  37. Additional input:
  38. 199 31
  40. Additional output:
  41. 594
  42. */

039.佩尔数

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. int PA(int n){
  9.     if(n==0) return 0;
  10.     else if(n==1) return 1;
  11.     return 2*PA(n-1)+PA(n-2);
  12. }
  13.  
  14. int PB(int n){
  15.     int p0=0,p1=1,pn,i;
  16.     for (i=0;i<=n;++i){
  17.         if (i==0) pn=p0;
  18.         else if (i==1) pn=p1;
  19.         else{
  20.             pn=2*p1+p0;
  21.             p0=p1;
  22.             p1=pn;
  23.         }
  24.     }
  25.     return pn;
  26. }
  27.  
  28. int main(){
  29.     int n;
  30.     cin>>n;
  31.     if(n&1) cout<<PA(n);
  32.     else cout<<PB(n);
  33. }
  34.  
  35. /*
  36. Sample input:
  37. 10
  39. Sample output:
  40. 2378
  41. */
  42.  
  43. /*
  44. Additional input:
  45. 42
  47. Additional output:
  48. 339564650
  49. */

040.哈沙德数

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. inline int hn(int n){
  9.     int t=n,s=0;
  10.     while (t){
  11.         s+=t%10;
  12.         t/=10;
  13.     }
  14.     if ((s == 0) || (n%s != 0)) return 0;
  15.     if (s == 1) return 1;
  16.     return n/s;
  17. }
  18.  
  19.  
  20. int main(){
  21.     int cnt = 0, n;
  22.     cin>>n;
  23.     if (n == 1) cnt = 1;
  24.     while ((n != 0) && (n != 1)) {
  25.         n = hn(n);
  26.         if (n) ++cnt;
  27.     }
  28.     cout<<cnt;
  29. }
  30.  
  31. /*
  32. Sample input:
  33. 6804
  35. Sample output:
  36. 4
  37. */
  38.  
  39. /*
  40. Additional input:
  41. 1048
  43. Additional output:
  44. 0
  45. */

第5季（041-050）

041.完美矩阵

note： 

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

2.前缀和基础；

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. //这道题用正常方法暴力判断逻辑上成立，但是肯定超时；
  5. //下面的程序做了一点优化，实测34ms(再改改细节说不定能到30ms)；
  6. //修正题目：子矩阵必须是方阵（noj又错了，气死）；
  7. //规定1：一个矩阵的记号为[(x1,y1),(x2,y2)],即左上角和右下角的两个值；
  8. //规定2：记号s[(x1,y1),(x2,y2)]为矩阵[(x1,y1),(x2,y2)]内所有元素的和；
  9. //翻译题目：首先对要输入的矩阵进行处理，将所有0换成-1，简化运算；
  10. //简化之后：条件（2）转化成  s[(x1,y1),(x2,y2)]-s[(x1+1,y1+1),(x2-1,y2-1)]=2(y2-y1+x2-x1) 可类比矩形周长理解；
  11. //        上面一条仅针对 行数>=3且列数>=3
  12. //简化之后：条件（3）转化成  s[(x1,y1),(x2,y2)]=-1，0，1；
  13. //注意程序里面有多个函数需要传多个相同参数，因此最好确保顺序统一；
  14.  
  15. #include <iostream>
  16.  
  17. using namespace std;
  18.  
  19. static int arr[301][301];       //arr为转换之后的矩阵；
  20. static int preSum[301][301];    //preSum为前缀和运算后得到的矩阵；
  21. //此处两个数组要用static修饰并在main外部定义，作为全局静态参量，便于调用；
  22.  
  23. void prefixSum(int n,int m) {
  24.     for (int i = 1; i <= n; ++i) {
  25.         for (int j = 1; j <= m; ++j) {
  26.             preSum[i][j] = arr[i][j] + preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1];
  27.         }
  28.     }
  29. }//prefixSum为前缀和算法，用于快速计算某个二维数列子矩阵的s[(1，1),(x2,y2)]，结果存储在preSum中；
  30.  
  31. int getSum(int x1, int y1, int x2, int y2) {
  32.     return preSum[x2][y2]-preSum[x1-1][y2]-preSum[x2][y1-1]
  33.            +preSum[x1-1][y1-1];
  34. }//getSum利用prefixSum和容斥原理得到任意的s[(x1，y1),(x2,y2)];
  35.  
  36. bool isPerfectMatrix(int x1,int y1,int x2,int y2){
  37.     int sum1=getSum(x1,y1,x2,y2);               //sum1用来存整个子矩阵之和，sum2用来存子矩阵内层之和；
  38.     if((x2-x1)==1||(y2-y1)==1){                 //即2x2的情况，必须单独考虑，
  39.         if(sum1==4) return true;                //因为这种情况下getSum里的参数实际上会相等，
  40.         else return false;                      //导致getSum的运算失去意义；
  41.     }
  42.     else{
  43.         int sum2=getSum(x1+1,y1+1,x2-1,y2-1);
  44.         if (sum2==-1||sum2==0||sum2==1){        //先判断简单的条件(3)，优化一下；
  45.             int c=2*(y2-y1+x2-x1);
  46.             if(sum1-sum2==c) return true;       //判断条件(2)；
  47.             else return false;
  48.         }
  49.         else return false;
  50.     }
  51. }
  52.  
  53. int PerfectMatrixCount(int n,int m){
  54.     int cnt=0;
  55.     for(int i=1;i<=n;++i){
  56.         for(int j=1;j<=m;++j){
  57.             for(int k=1;i+k<=n&&j+k<=m;++k){    //记得开头说的子矩阵必须是方阵；
  58.                 if (arr[i][k + j] == -1 || arr[k + i][j] == -1) break;
  59.                 //此处为优化部分，发现扩展遍历时遇到元素为0，那么该方向的扩展均不可能为完美矩阵，
  60.                 //因为扩展的最外圈总会包含这个0，至于为什么是==-1，因为矩阵转换过了；
  61.                 if (isPerfectMatrix(i,j,i+k,j+k)) {
  62.                     ++cnt;
  63.                 }
  64.             }
  65.         }
  66.     }
  67.     return cnt;
  68. }
  69.  
  70. int main(){
  71.     int n,m;
  72.     cin>>n>>m;
  73.     for(int i=1;i<=n;++i){
  74.         for(int j=1;j<=m;++j){
  75.             int tmp;
  76.             cin>>tmp;
  77.             if (tmp==1) arr[i][j]=1;
  78.             else arr[i][j]=-1;      //此处完成0-1矩阵到(-1)-1矩阵的转换；
  79.         }
  80.     }
  81.     prefixSum(n,m);
  82.     if(n<2||m<2) cout<<0;           //其实多余，但是为了完整，还是放在这边；
  83.     else cout<<PerfectMatrixCount(n,m);
  84. }
  85.  
  86. /*
  87. Sample input:
  88. 4 4
  89. 1 1 1 1
  90. 1 0 1 1
  91. 1 1 0 1
  92. 1 1 1 1
  94. Sample output:
  95. 3
  96. */
  97.  
  98. /*
  99. Additional input:
  100. 5 5
  101. 1 0 1 0 1
  102. 1 1 0 1 1
  103. 1 1 1 1 1
  104. 0 1 1 0 0
  105. 1 0 1 1 1
  107. Additional output:
  108. 3
  109. */

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

note：

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

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

  1. //Difficulty:??/10
  2. //Importance: 0/10
  3.  
  4. //1st none AC you meet
  5.  
  6. #include <iostream>
  7. #include <cmath>
  8.  
  9. using namespace std;
  10.  
  11. double calculateSpeed(double temperature, double pressure, int elevation, int runway, int weight, int flaps, int wet) {
  12.     // 检查输入是否在有效范围内
  13.     if (flaps != 1 && flaps != 5 && flaps != 15) {
  14.         return -1;
  15.     }
  16.  
  17.     if (weight < 41413 || weight > 65000 || runway <= 6900) {
  18.         return -1;
  19.     }
  20.  
  21.     // 计算温度档和气压档
  22.     int tempRange = floor(temperature / 10);
  23.     int pressureRange = ceil(pressure);
  24.  
  25.     // 检查操纵参考表是否存在
  26.     if (tempRange < 0 || tempRange > 7 || pressureRange < 0 || pressureRange > 9) {
  27.         return -1;
  28.     }
  29.  
  30.     // 根据温度档和气压档查找操纵参考值
  31.     char referenceTable[8][10] = {
  32.             {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K'},
  33.             {'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V'},
  34.             {'W', 'X', 'Y', 'Z', 'A', 'B', 'C', 'D', 'E', 'F'},
  35.             {'G', 'H', 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R'},
  36.             {'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'A', 'B'},
  37.             {'C', 'D', 'E', 'F', 'G', 'H', 'J', 'K', 'L', 'M'},
  38.             {'N', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X'},
  39.             {'Y', 'Z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'}
  40.     };
  41.  
  42.     char reference = referenceTable[tempRange][pressureRange];
  43.  
  44.     // 检查操纵参考表是否存在V1、Vr和V2
  45.     if (reference != 'A' && reference != 'B' && reference != 'C' && reference != 'D' && reference != 'E') {
  46.         return -1;
  47.     }
  48.  
  49.     // 根据襟翼位置、起飞重量和操纵参考值查找V1、Vr和V2
  50.     int speedTable[3][5] = {
  51.             {117, 126, 134, 142, 151},
  52.             {122, 131, 139, 147, 156},
  53.             {127, 136, 145, 153, 162}
  54.     };
  55.  
  56.     int speedIndex = (flaps - 1) / 7;
  57.     int* speedRow = speedTable[speedIndex];
  58.  
  59.     int v1 = speedRow[weight / 13000];
  60.     int vr = speedRow[weight / 13000] + 11;
  61.     int v2 = speedRow[weight / 13000] + 18;
  62.  
  63.     // 如果是湿跑道，根据跑道长度和襟翼位置查找折扣值
  64.     if (wet == 1) {
  65.         int discountTable[3][3] = {
  66.                 {0, 0, 0},
  67.                 {0, 0, 0},
  68.                 {0, 0, 0}
  69.         };
  70.  
  71.         int discountIndex = (flaps - 1) / 7;
  72.         int* discountRow = discountTable[discountIndex];
  73.  
  74.         int discount = discountRow[runway / 1000];
  75.  
  76.         v1 -= discount;
  77.     }
  78.  
  79.     printf("V1=%dkts Vr=%dkts V2=%dkts\n", v1, vr, v2);
  80.  
  81.     return 0;
  82. }
  83.  
  84. int main() {
  85.     double temperature, pressure;
  86.     int elevation, runway, weight, flaps, wet;
  87.     cin>>temperature>>pressure>>elevation>>runway>>weight>>flaps>>wet;
  88.     int result = calculateSpeed(temperature, pressure, elevation, runway, weight, flaps, wet);
  89.     if (result == -1) {
  90.         cout<<"Flight not possible!\n";
  91.     }
  92.     return 0;
  93. }
  94.  
  95. /*
  96. Sample input:
  97. 23,8 28.67 1200 7250 52600 5 1
  99. Sample output:
  100. V1=128kts Vr=139kts V2=146kts
  101. */
  102.  
  103. /*
  104. Additional input:
  105. NULL
  107. Additional output:
  108. NULL
  109. */

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. #define MAXSIZE 10
  7.  
  8. using namespace std;
  9.  
  10. void swap(double arr[MAXSIZE][MAXSIZE], int r1, int r2, int n) {
  11.     for (int i = 0; i < n; i++) {
  12.         double temp = arr[r1][i];
  13.         arr[r1][i] = arr[r2][i];
  14.         arr[r2][i] = temp;
  15.     }
  16. }
  17.  
  18. double calDet(double arr[MAXSIZE][MAXSIZE], int n) {
  19.     int i, j, k;
  20.     double det = 1.0;
  21.     for (i = 0; i < n; i++) {
  22.         if (arr[i][i] == 0.0) {
  23.             for (j = i + 1; j < n; j++) {
  24.                 if (arr[j][i] != 0.0) {
  25.                     swap(arr, i, j, n);
  26.                     det *= -1.0;
  27.                     break;
  28.                 }
  29.             }
  30.         }
  31.         if (arr[i][i] == 0.0) {
  32.             return 0.0;
  33.         }
  34.         double v = arr[i][i];
  35.         det *= v;
  36.         for (j = i; j < n; j++) {
  37.             arr[i][j] /= v;
  38.         }
  39.         for (j = i + 1; j < n; j++) {
  40.             double e = arr[j][i];
  41.             for (k = i; k < n; k++) {
  42.                 arr[j][k] -= e * arr[i][k];
  43.             }
  44.         }
  45.     }
  46.     return det;
  47. }
  48.  
  49. int main() {
  50.     int n;
  51.     cin>>n;
  52.     double arr[MAXSIZE][MAXSIZE];
  53.     for (int i = 0; i < n; i++) {
  54.         for (int j = 0; j < n; j++) {
  55.             cin>>arr[i][j];
  56.         }
  57.     }
  58.     double det = calDet(arr, n);
  59.     cout<<det;
  60.  
  61.     return 0;
  62. }
  63.  
  64. /*
  65. Sample input:
  66. 3
  67. 2 6 3
  68. 1 0 2
  69. 5 8 4
  71. Sample output:
  72. 28
  73. */
  74.  
  75. /*
  76. Additional input:
  77. 3
  78. 8 91 1
  79. 4 15 15
  80. 61 237 16
  82. Additional output:
  83. 50954
  84. */

044.稀疏矩阵

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. int main () {
  9.     int raw, col, n, num = 0;
  10.     cin>>raw>>col;
  11.  
  12.     for (int i = 0; i < raw; ++i) {
  13.         for (int j = 0; j < col; ++j) {
  14.             cin>>n;
  15.             if (n) ++num;
  16.         }
  17.     }
  18.  
  19.     double ratio = (double)num / (raw * col);
  20.     if (num == raw || num == col || (ratio - 0.05) <= 1e-9)
  21.         cout<<"Yes"<<endl;
  22.     else cout<<"No"<<endl;
  23.     return 0;
  24. }
  25.  
  26. /*
  27. Sample input:
  28. 4 4
  29. 5 0 0 0
  30. 0 8 0 0
  31. 0 0 3 0
  32. 0 6 0 0
  34. Sample output:
  35. Yes
  36. */
  37.  
  38. /*
  39. Additional input:
  40. 4 4
  41. 5 5 0 0
  42. 0 1 0 0
  43. 0 0 3 0
  44. 0 6 0 2
  46. Additional output:
  47. No
  48. */

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. void pass(int a, int b, int c, int d, int e) {
  8.     bool flag = false;
  9.     if (a <= e && (b + c) <= d) flag = true;
  10.     if (b <= e && (a + c) <= d) flag = true;
  11.     if (c <= e && (a + b) <= d) flag = true;
  12.     if (flag) cout<<"YES"<<endl;
  13.     else cout<<"NO"<<endl;
  14. }
  15.  
  16. int main() {
  17.     int n, a, b, c, d, e;
  18.     cin>>n;
  19.     while (n--){
  20.         cin>>a>>b>>c>>d>>e;
  21.         pass(a, b, c, d, e);
  22.     }
  23.     return 0;
  24. }
  25.  
  26. /*
  27. Sample input:
  28. 3
  29. 1 1 1 15 5
  30. 8 7 6 15 5
  31. 8 5 7 15 6
  33. Sample output:
  34. YES
  35. NO
  36. YES
  37. */
  38.  
  39. /*
  40. Additional input:
  41. 3
  42. 1 4 5 5 16
  43. 15 51 16 15 15
  44. 15 61 16 16 16
  46. Additional output:
  47. YES
  48. NO
  49. NO
  50. */

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

note：

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. int main() {
  8.     int l3s2[4] = {0, 5, 3, 1};
  9.     int n, x1, x2, x3, x4, x5, x6, s2, s1;
  10.     while (1) {
  11.         cin>>x1>>x2>>x3>>x4>>x5>>x6;
  12.         if ((x1 + x2 + x3 + x4 + x5 + x6) == 0) break;
  13.         n = (x3 + 3) / 4 + x4 + x5 + x6;
  14.         s2 = 5 * x4 + l3s2[x3 % 4];
  15.         if (x2 > s2) n += (x2 - s2 + 8) / 9;
  16.         s1 = 36 * n - 36 * x6 - 25 * x5 - 16 * x4 - 9 * x3 - 4 * x2;
  17.         if (x1 > s1) n += (x1 - s1 + 35) / 36;
  18.         cout<<n<<endl;
  19.     }
  20.     return 0;
  21. }
  22.  
  23. /*
  24. Sample input:
  25. 1 1 1 1 1 1
  26. 2 2 2 2 2 2
  27. 1 2 3 4 5 6
  28. 0 0 0 0 0 0
  30. Sample output:
  31. 4
  32. 7
  33. 16
  34. */
  35.  
  36. /*
  37. Additional input:
  38. 1 5 6 2 1 6
  39. 1 6 7 1 2 7
  40. 1 2 7 19 8 6
  41. 0 0 0 0 0 0
  43. Additional output:
  44. 11
  45. 12
  46. 35
  47. */

047.回文数之和

note:

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. int dec0[10] , kSys[32] ;
  8.  
  9. bool isPalindrome(int arr[], int cnt){
  10.     int head = 0, tail = cnt - 1;
  11.     while (head < tail) {
  12.         if (arr[head] != arr[tail]) return false;
  13.         ++head, --tail;
  14.     }
  15.     return true;
  16. }
  17.  
  18. bool isBiPalindrome(int n, int k){
  19.     int tmp = n, cnt = 0;
  20.     while (tmp) {
  21.         dec0[cnt++] = tmp % 10;
  22.         tmp /= 10;
  23.     }
  24.     if (!isPalindrome(dec0, cnt)) return false;
  25.  
  26.     tmp = n, cnt = 0;
  27.     while (tmp) {
  28.         kSys[cnt++] = tmp % k;
  29.         tmp /= k;
  30.     }
  31.     if (!isPalindrome(kSys, cnt)) return false;
  32.     return true;
  33. }
  34.  
  35. int main() {
  36.     int n, k, sum = 0;
  37.     cin>>n>>k;
  38.     for (int i = 1; i <= n; ++i) {
  39.         if (isBiPalindrome(i, k)) sum += i;
  40.     }
  41.     cout<<sum;
  42.     return 0;
  43. }
  44.  
  45. /*
  46. Sample input:
  47. 100 2
  49. Sample output:
  50. 157
  51. */
  52.  
  53. /*
  54. Additional input:
  55. 1000 3
  57. Additional output:
  58. 2638
  59. */

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <cmath>
  6. #include <cstdlib>
  7.  
  8. using namespace std;
  9.  
  10. double func1(double x) {
  11.     return pow(x, 4) * exp(-x);
  12. }
  13.  
  14. double func2(double x) {
  15.     return x * x + 1;
  16. }
  17.  
  18. double func3(double x) {
  19.     return cos(x);
  20. }
  21.  
  22. double func4(double x) {
  23.     return sqrt(x) * (x - 2);
  24. }
  25.  
  26. double func5(double x) {
  27.     return 2 * sin(x) - 5 * cos(x);
  28. }
  29.  
  30. double func(int m, double x) {
  31.     switch (m) {
  32.         case 1: return func1(x);
  33.         case 2: return func2(x);
  34.         case 3: return func3(x);
  35.         case 4: return func4(x);
  36.         case 5: return func5(x);
  37.         default: return 0;
  38.     }
  39. }
  40.  
  41. double mtk(int m, double a, double b, int n) {
  42.     srand(RAND_MAX);
  43.     double w = b - a, sum = 0;
  44.     for (int i = 1; i < n; ++i) {
  45.         double x = ((double)rand() / RAND_MAX) * w + a;
  46.         sum += func(m, x);
  47.     }
  48.     sum *= w / n;
  49.     return sum;
  50. }
  51.  
  52. int main() {
  53.     int m, n;
  54.     double a, b;
  55.     cin>>m>>a>>b>>n;
  56.     printf("%.6lf", mtk(m, a, b, n));
  57.     return 0;
  58. }
  59.  
  60. /*
  61. Sample input:
  62. 1 1 5 2000
  64. Sample output:
  65. 13.317870
  66. */
  67.  
  68. /*
  69. Additional input:
  70. 3 8 7 1292
  72. Additional output:
  73. -0.331019
  74. */

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

note：

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. double nAvg(double arr[], int n) {
  9.     double sum = 0;
  10.     for (int i = 0; i < n; ++i) {
  11.         sum += arr[i];
  12.     }
  13.     return sum / n;
  14. }
  15.  
  16. int main() {
  17.     int n;
  18.     cin>>n;
  19.     double x[n], y[n];
  20.     for (int i = 0; i < n; ++i) {
  21.         cin>>x[i]>>y[i];
  22.     }
  23.  
  24.     double xBar = nAvg(x, n), yBar = nAvg(y, n);
  25.     double sumUp = 0, sumDown = 0;
  26.     for (int i = 0; i < n; ++i) {
  27.         sumUp += (x[i] - xBar) * (y[i] - yBar);
  28.     }
  29.     for (int i = 0; i < n; ++i) {
  30.         sumDown += (x[i] - xBar) * (x[i] - xBar);
  31.     }
  32.     double b = sumUp / sumDown;
  33.     double a = yBar - b * xBar;
  34.  
  35.     printf("Y=%.4lf+%.4lf*X",a,b);
  36.     return 0;
  37. }
  38.  
  39. /*
  40. Sample input:
  41. 7
  42. 150 6450
  43. 200 7450
  44. 250 8445
  45. 300 9450
  46. 350 11450
  47. 400 15450
  48. 600 18450
  50. Sample output:
  51. Y=1770.2394+28.7793*X
  52. */
  53.  
  54. /*
  55. Additional input:
  56. 5
  57. 1 1
  58. 2 2
  59. 3 3
  60. 4 4
  61. 5 5
  63. Additional output:
  64. Y=0.0000+1.0000*X
  65. */

050.素数筛选法

note：

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include<iostream>
  5.  
  6. using namespace std;
  7.  
  8. #define NUM (int)1e7+1
  9.  
  10. static bool isSieved[NUM];
  11. static int prime[NUM];
  12.  
  13. int main() {
  14.     int n, k = 0;
  15.     cin>>n;
  16.     isSieved[1] = true;
  17.     for (int i = 2; i <= n; ++i) {
  18.         if (!isSieved[i]) prime[++k] = i;
  19.         for (int j = 1; prime[j] * i <= n; ++j) {
  20.             isSieved[prime[j] * i] = true;
  21.             if (i % prime[j] == 0) break;
  22.         }
  23.     }
  24.     cout<<k;
  25. }
  26.  
  27. /*
  28. Sample input:
  29. 100
  31. Sample output:
  32. 25
  33. */
  34.  
  35. /*
  36. Additional input:
  37. 1590
  39. Additional output:
  40. 250
  41. */

第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();      ......

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. vector<string> split(string str, string pattern)
  10. {
  11.     string::size_type pos;
  12.     vector<string> result;
  13.     str += pattern;
  14.     int size = str.size();
  15.     for (int i = 0; i < size; i++)
  16.     {
  17.         pos = str.find(pattern, i);
  18.         if (pos < size)
  19.         {
  20.             string s = str.substr(i, pos - i);
  21.             result.push_back(s);
  22.             i = pos + pattern.size() - 1;
  23.         }
  24.     }
  25.     return result;
  26. }
  27.  
  28. int main(){
  29.     string str;
  30.     getline(cin,str);
  31.     string pattern;
  32.     getline(cin,pattern);
  33.     vector<string> result=split(str,pattern);
  34.     for(int i=0; i<result.size(); i++)
  35.     {
  36.         cout<<result[i]<<endl;
  37.     }
  38.     return 0;
  39. }
  40.  
  41. /*
  42. Sample input:
  43. www.nwpu.edu.cn
  44. .
  46. Sample output:
  47. www
  48. nwpu
  49. edu
  50. cn
  51. */
  52.  
  53. /*
  54. Additional input:
  55. https://www.bh3.com/
  56. .
  58. Additional output:
  59. https://www
  60. bh3
  61. com/
  62. */

052.Kids A+B

note:

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <map>
  6. #include <vector>
  7.  
  8. using namespace std;
  9.  
  10. vector<string> split(string str, string pattern)
  11. {
  12.     string::size_type pos;
  13.     vector<string> result;
  14.     str += pattern;
  15.     int size = str.size();
  16.     for (int i = 0; i < size; i++)
  17.     {
  18.         pos = str.find(pattern, i);
  19.         if (pos < size)
  20.         {
  21.             string s = str.substr(i, pos - i);
  22.             result.push_back(s);
  23.             i = pos + pattern.size() - 1;
  24.         }
  25.     }
  26.     return result;
  27. }
  28.  
  29.  
  30. int stringToInt(vector<string> str){
  31.  
  32.     map<string, int> stringToIntMap;
  33.     //个位映射
  34.     stringToIntMap["zero"] = 0;
  35.     stringToIntMap["one"] = 1;
  36.     stringToIntMap["two"] = 2;
  37.     stringToIntMap["three"] = 3;
  38.     stringToIntMap["four"] = 4;
  39.     stringToIntMap["five"] = 5;
  40.     stringToIntMap["six"] = 6;
  41.     stringToIntMap["seven"] = 7;
  42.     stringToIntMap["eight"] = 8;
  43.     stringToIntMap["nine"] = 9;
  44.  
  45.     //十位映射
  46.     stringToIntMap["twenty"] = 20;
  47.     stringToIntMap["thirty"] = 30;
  48.     stringToIntMap["forty"] = 40;
  49.     stringToIntMap["fifty"] = 50;
  50.     stringToIntMap["sixty"] = 60;
  51.     stringToIntMap["seventy"] = 70;
  52.     stringToIntMap["eighty"] = 80;
  53.     stringToIntMap["ninety"] = 90;
  54.  
  55.     //特殊映射（其实包含十位映射）
  56.     stringToIntMap["ten"] = 10;
  57.     stringToIntMap["eleven"] = 11;
  58.     stringToIntMap["twelve"] = 12;
  59.     stringToIntMap["thirteen"] = 13;
  60.     stringToIntMap["fourteen"] = 14;
  61.     stringToIntMap["fifteen"] = 15;
  62.     stringToIntMap["sixteen"] = 16;
  63.     stringToIntMap["seventeen"] = 17;
  64.     stringToIntMap["eighteen"] = 18;
  65.     stringToIntMap["nineteen"] = 19;
  66.  
  67.     //使用映射
  68.     int result=0;
  69.     if(str.size()==1){
  70.         result=stringToIntMap[str[0]];
  71.     }
  72.     if(str.size()==2){
  73.         result=stringToIntMap[str[0]]+stringToIntMap[str[1]];
  74.     }
  75.     return result;
  76. }
  77.  
  78. int intNumWidth(int x){
  79.     string str = to_string(x);
  80.     return str.size();
  81. }
  82.  
  83. string intToString(int num){
  84.     // 肯定有好的方法，但是下面的map可以直接让ai生成，也不费时间
  85.     map<int,string> intToStringMap;
  86.     intToStringMap[0] = "zero";
  87.     intToStringMap[1] = "one";
  88.     intToStringMap[2] = "two";
  89.     intToStringMap[3] = "three";
  90.     intToStringMap[4] = "four";
  91.     intToStringMap[5] = "five";
  92.     intToStringMap[6] = "six";
  93.     intToStringMap[7] = "seven";
  94.     intToStringMap[8] = "eight";
  95.     intToStringMap[9] = "nine";
  96.     intToStringMap[10] = "ten";
  97.     intToStringMap[11] = "eleven";
  98.     intToStringMap[12] = "twelve";
  99.     intToStringMap[13] = "thirteen";
  100.     intToStringMap[14] = "fourteen";
  101.     intToStringMap[15] = "fifteen";
  102.     intToStringMap[16] = "sixteen";
  103.     intToStringMap[17] = "seventeen";
  104.     intToStringMap[18] = "eighteen";
  105.     intToStringMap[19] = "nineteen";
  106.     intToStringMap[20] = "twenty";
  107.     intToStringMap[21] = "twenty-one";
  108.     intToStringMap[22] = "twenty-two";
  109.     intToStringMap[23] = "twenty-three";
  110.     intToStringMap[24] = "twenty-four";
  111.     intToStringMap[25] = "twenty-five";
  112.     intToStringMap[26] = "twenty-six";
  113.     intToStringMap[27] = "twenty-seven";
  114.     intToStringMap[28] = "twenty-eight";
  115.     intToStringMap[29] = "twenty-nine";
  116.     intToStringMap[30] = "thirty";
  117.     intToStringMap[31] = "thirty-one";
  118.     intToStringMap[32] = "thirty-two";
  119.     intToStringMap[33] = "thirty-three";
  120.     intToStringMap[34] = "thirty-four";
  121.     intToStringMap[35] = "thirty-five";
  122.     intToStringMap[36] = "thirty-six";
  123.     intToStringMap[37] = "thirty-seven";
  124.     intToStringMap[38] = "thirty-eight";
  125.     intToStringMap[39] = "thirty-nine";
  126.     intToStringMap[40] = "forty";
  127.     intToStringMap[41] = "forty-one";
  128.     intToStringMap[42] = "forty-two";
  129.     intToStringMap[43] = "forty-three";
  130.     intToStringMap[44] = "forty-four";
  131.     intToStringMap[45] = "forty-five";
  132.     intToStringMap[46] = "forty-six";
  133.     intToStringMap[47] = "forty-seven";
  134.     intToStringMap[48] = "forty-eight";
  135.     intToStringMap[49] = "forty-nine";
  136.     intToStringMap[50] = "fifty";
  137.     intToStringMap[51] = "fifty-one";
  138.     intToStringMap[52] = "fifty-two";
  139.     intToStringMap[53] = "fifty-three";
  140.     intToStringMap[54] = "fifty-four";
  141.     intToStringMap[55] = "fifty-five";
  142.     intToStringMap[56] = "fifty-six";
  143.     intToStringMap[57] = "fifty-seven";
  144.     intToStringMap[58] = "fifty-eight";
  145.     intToStringMap[59] = "fifty-nine";
  146.     intToStringMap[60] = "sixty";
  147.     intToStringMap[61] = "sixty-one";
  148.     intToStringMap[62] = "sixty-two";
  149.     intToStringMap[63] = "sixty-three";
  150.     intToStringMap[64] = "sixty-four";
  151.     intToStringMap[65] = "sixty-five";
  152.     intToStringMap[66] = "sixty-six";
  153.     intToStringMap[67] = "sixty-seven";
  154.     intToStringMap[68] = "sixty-eight";
  155.     intToStringMap[69] = "sixty-nine";
  156.     intToStringMap[70] = "seventy";
  157.     intToStringMap[71] = "seventy-one";
  158.     intToStringMap[72] = "seventy-two";
  159.     intToStringMap[73] = "seventy-three";
  160.     intToStringMap[74] = "seventy-four";
  161.     intToStringMap[75] = "seventy-five";
  162.     intToStringMap[76] = "seventy-six";
  163.     intToStringMap[77] = "seventy-seven";
  164.     intToStringMap[78] = "seventy-eight";
  165.     intToStringMap[79] = "seventy-nine";
  166.     intToStringMap[80] = "eighty";
  167.     intToStringMap[81] = "eighty-one";
  168.     intToStringMap[82] = "eighty-two";
  169.     intToStringMap[83] = "eighty-three";
  170.     intToStringMap[84] = "eighty-four";
  171.     intToStringMap[85] = "eighty-five";
  172.     intToStringMap[86] = "eighty-six";
  173.     intToStringMap[87] = "eighty-seven";
  174.     intToStringMap[88] = "eighty-eight";
  175.     intToStringMap[89] = "eighty-nine";
  176.     intToStringMap[90] = "ninety";
  177.     intToStringMap[91] = "ninety-one";
  178.     intToStringMap[92] = "ninety-two";
  179.     intToStringMap[93] = "ninety-three";
  180.     intToStringMap[94] = "ninety-four";
  181.     intToStringMap[95] = "ninety-five";
  182.     intToStringMap[96] = "ninety-six";
  183.     intToStringMap[97] = "ninety-seven";
  184.     intToStringMap[98] = "ninety-eight";
  185.     intToStringMap[99] = "ninety-nine";
  186.  
  187.     return intToStringMap[num];
  188. }
  189.  
  190. int main() {
  191.     string num1,num2;
  192.     cin>>num1>>num2;
  193.     vector<string> str1=split(num1,"-");
  194.     vector<string> str2=split(num2,"-");
  195.     int ans=0;
  196.     ans=stringToInt(str1)+stringToInt(str2);
  197.     cout<<intToString(ans);
  198.     return 0;
  199. }
  200.  
  201. /*
  202. Sample input:
  203. twenty-seven fifty-four
  205. Sample output:
  206. eighty-one
  207. */
  208.  
  209. /*
  210. Additional input:
  211. zero zero
  213. Additional output:
  214. zero
  215. */

053.前后缀移除

note：

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. string removePre(string input, const string& std) {
  9.     int pos = 0;
  10.     for (auto it = input.begin(); it != input.end(); ++it) {
  11.         if (std.find(*it) != string::npos) ++pos;
  12.         else break;
  13.     }
  14.     if (pos) input.erase(0, pos);
  15.     return input;
  16. }
  17.  
  18. string removeSuf(string input, const string& std) {
  19.     int pos = 0;
  20.     for (auto it = input.rbegin(); it != input.rend(); ++it) {
  21.         if (std.find(*it) != string::npos) ++pos;
  22.         else break;
  23.     }
  24.     if (pos) input.erase(input.size()-pos, pos);
  25.     return input;
  26. }
  27.  
  28. int main() {
  29.     string input,std;
  30.     getline(cin,input);
  31.     getline(cin,std);
  32.     cout<<removePre(input,std)<<endl<<removeSuf(input,std)<<endl<<removeSuf(removePre(input,std),std);
  33.     return 0;
  34. }
  35.  
  36. /*
  37. Sample input:
  38. www.example.com
  39. cmowz.
  41. Sample output:
  42. example.com
  43. www.example
  44. example
  45. */
  46.  
  47. /*
  48. Additional input:
  49. https://www.bh3.com/
  50. pthsocm/:w.
  52. Additional output:
  53. bh3.com/
  54. https://www.bh3
  55. bh3
  56. */

054.删除前后缀

note：

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. string removePre(string input, const string& std) {
  9.     int base=0;
  10.     for (auto it = input.begin(); it != input.end(); ) {
  11.         if (input.substr(distance(input.begin(), it),std.size())== std){
  12.             ++base;
  13.             it+=std.size();
  14.         }
  15.         else break;
  16.     }
  17.     int pos=std.size()*base;
  18.     if (base) input.erase(0, pos);
  19.     return input;
  20. }
  21.  
  22. string removeSuf(string input, const string& std) {
  23.     int base=0;
  24.     for (auto it = input.rbegin(); it != input.rend(); ) {
  25.         if (input.substr(distance(input.rbegin(), it),std.size()) == std){
  26.             ++base;
  27.             it+=std.size();
  28.         }
  29.         else break;
  30.     }
  31.     int pos=std.size()*base;
  32.     if (base) input.erase(input.size()-pos, pos);
  33.     return input;
  34. }
  35.  
  36. int main() {
  37.     string input,std;
  38.     getline(cin,input);
  39.     getline(cin,std);
  40.     cout<<removePre(input,std)<<endl<<removeSuf(input,std);
  41.     return 0;
  42. }
  43.  
  44. /*
  45. Sample input:
  46. antiantianwartiantianti
  47. anti
  49. Sample output:
  50. anwartiantianti
  51. antiantianwarti
  52. */
  53.  
  54. /*
  55. Additional input:
  56. yuanshenyuanshenyuanshengyuanshenshenshen
  57. yuan
  59. Additional output:
  60. shenyuanshenyuanshengyuanshenshenshen
  61. yuanshenyuanshenyuanshengyuanshenshen
  62. */

055.AtoI转换

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <climits>
  6.  
  7. using namespace std;
  8.  
  9. int ATOI(string str) {
  10.     auto it = str.begin();
  11.     int sgn = 1;
  12.     long long tmp = 0;
  13.     if (*it == '+') ++it;
  14.     else if (*it == '-') sgn = -1, ++it;
  15.  
  16.     while (it != str.end()) {
  17.         if (*it == ' ') ;
  18.         else if ('0' <= *it && *it <= '9') {
  19.             tmp = (*it - '0') + tmp * 10;
  20.             if ((tmp * sgn) >= INT_MAX) return INT_MAX;
  21.             else if ((tmp * sgn) <= INT_MIN) return INT_MIN;
  22.         }
  23.         else break;
  24.         ++it;
  25.     }
  26.     return tmp * sgn;
  27. }
  28.  
  29. int main() {
  30.     string str;
  31.     cin>>str;
  32.     cout<<ATOI(str);
  33.     return 0;
  34. }
  35.  
  36. /*
  37. Sample input:
  38. -123x+123
  40. Sample output:
  41. -123
  42. */
  43.  
  44. /*
  45. Additional input:
  46. 00519
  48. Additional output:
  49. 519
  50. */

056.大小写交换

note:

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

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

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

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

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <string>
  6.  
  7. using namespace std;
  8.  
  9. string trans(string str){
  10.     for(int i=0;i<str.size();++i){
  11.         if(str[i]>64&&str[i]<91){
  12.             str[i]+=32;
  13.         }
  14.         else if(str[i]>96&&str[i]<123){
  15.             str[i]-=32;
  16.         }
  17.     }
  18.     return str;
  19. }
  20.  
  21. int main() {
  22.     string str;
  23.     getline(cin,str);
  24.     cout<<trans(str);
  25. }
  26.  
  27. /*
  28. Sample input:
  29. Hello world
  31. Sample output:
  32. hELLO WORLD
  33. */
  34.  
  35. /*
  36. Additional input:
  37. eLYSIA tRUe
  39. Additional output:
  40. Elysia TruE
  41. */

057.字符串替换

note：

1.第二道无人AC的题；

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

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

  1. //Difficulty: 3/10
  2. //Importance: 3/10
  3.  
  4. //2nd none AC you meet
  5.  
  6. #include <iostream>
  7. #include <string>
  8.  
  9. using namespace std;
  10.  
  11. void subreplace(string &str,string olds,string news){
  12.     size_t pos=0;
  13.     while((pos=str.find(olds))!=string::npos){
  14.         str.replace(pos,olds.length(),news);
  15.     }
  16. }
  17.  
  18. int main() {
  19.     string str,olds,news;
  20.     getline(cin,str);
  21.     getline(cin,olds);
  22.     getline(cin,news);
  23.     subreplace(str,olds,news);
  24.     cout<<str;
  25. }
  26.  
  27. /*
  28. Sample input:
  29. xxforxx xx for xx
  30. xx
  31. nwpu
  33. Sample output:
  34. nwpufornwpu nwpu for nwpu
  35. */
  36.  
  37. /*
  38. Additional input:
  39. xx for xx is xx
  40. xx
  41. Genshin Impact
  43. Additional output:
  44. Genshin Impact for Genshin Impact is Genshin Impact
  45. */

058.字符串切片

note：

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <string>
  6.  
  7. using namespace std;
  8.  
  9. int len;
  10.  
  11. string string_slice(string str, int start,int stop,int step){
  12.     string res;
  13.     if (stop < 0) stop += len;
  14.     if (start < 0) start += len;
  15.     if(start>stop&&step<0){
  16.         for (int i = start; i >stop; i+=step) {
  17.             res += str[i];
  18.         }
  19.         return res;
  20.     }
  21.     if(start<=stop&&step>0){
  22.         for (int i = start; i<stop; i+=step) {
  23.             res += str[i];
  24.         }
  25.         return res;
  26.     }
  27. }
  28.  
  29.  
  30. int main() {
  31.     string str;
  32.     getline(cin,str);
  33.     len=str.size();
  34.     int T;
  35.     cin>>T;
  36.     for(int i=0;i<T;++i){
  37.         int n,a,b,c;
  38.         cin>>n;
  39.         switch (n) {
  40.             case 1:
  41.                 cin>>a;
  42.                 cout<<string_slice(str,a,len,1)<<endl;break;
  43.             case 2:
  44.                 cin>>a>>b;
  45.                 cout<<string_slice(str,a,b,1)<<endl;break;
  46.             case 3:
  47.                 cin>>a>>b>>c;
  48.                 cout<<string_slice(str,a,b,c)<<endl;break;
  49.         }
  50.     }
  51. }
  52.  
  53. /*
  54. Sample input:
  55. ABCDEFGHI
  56. 8
  57. 2 2 7
  58. 2 -7 -2
  59. 2 2 -5
  60. 3 2 7 2
  61. 3 6 1 -2
  62. 2 0 3
  63. 1 6
  64. 3 -1 -10 -1
  66. Sample output:
  67. CDEFG
  68. CDEFG
  69. CD
  70. CEG
  71. GEC
  72. ABC
  73. GHI
  74. IHGFEDCBA
  75. */
  76.  
  77. /*
  78. Additional input:
  79. NULL
  81. Additional output:
  82. NULL
  83. */

059.元宇宙A+B

note：

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

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <cstring>
  6.  
  7. using namespace std;
  8.  
  9. const static char decToMeta[37] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  10. static char c[100] = "", a[100] = "", b[100] = "";
  11. static int C[100] = {0}, A[100] = {0}, B[100] = {0};
  12.  
  13. int metaToDec(char m) {
  14.     if ('0' <= m && m <= '9') return m - '0';
  15.     return m - 'A' + 10;
  16. }
  17.  
  18. void add(void) {
  19.     int lenA = strlen(a), lenB = strlen(b);
  20.     for (int i = 0; i < lenA; ++i) A[i] = metaToDec(a[lenA - i - 1]);
  21.     for (int i = 0; i < lenB; ++i) B[i] = metaToDec(b[lenB - i - 1]);
  22.  
  23.     int carry = 0;
  24.     int lenC = lenA > lenB ? lenA : lenB;
  25.     for (int i = 0; i < lenC; ++i) {
  26.         C[i] = A[i] + B[i] + carry;
  27.         carry = C[i] / 36;
  28.         C[i] %= 36;
  29.     }
  30.     if (carry != 0) {
  31.         C[lenC] = carry;
  32.         ++lenC;
  33.     }
  34.  
  35.     for (int i = lenC - 1; i >= 0; --i) c[i] = decToMeta[C[lenC - i - 1]];
  36.     c[lenC] = '\0';
  37. }
  38.  
  39. int main() {
  40.     cin>>a>>b;
  41.     add();
  42.     cout<<c;
  43.     return 0;
  44. }
  45.  
  46. /*
  47. Sample input:
  48. ZZ 321
  50. Sample output:
  51. 420
  52. */
  53.  
  54. /*
  55. Additional input:
  56. ac 42
  58. Additional output:
  59. 1BA
  60. */

060.字符串后缀

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. bool findSuf(string input, const string& std) {
  9.     int pos = 0;
  10.     if(input.substr(input.size()-std.size(),std.size()) == std) return true;
  11.     return false;
  12. }
  13.  
  14. int main(){
  15.     string input,std;
  16.     getline(cin,input);
  17.     getline(cin,std);
  18.     if (findSuf(input,std)) cout<<"Yes";
  19.     else cout<<"No";
  20. }
  21.  
  22. /*
  23. Sample input:
  24. hello world!
  25. world!
  27. Sample output:
  28. Yes
  29. */
  30.  
  31. /*
  32. Additional input:
  33. Genshin Impact!
  34.  Impact!
  36. Additional output:
  37. Yes
  38. */

第7季（061-070）

061.有效表达式

note：

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     long long n;
  10.     cin>>n;
  11.     long long cnt = 1;
  12.     for (long long i = n + 2; i <= 2 * n; ++i) cnt *= i;
  13.     for (long long i = 1; i <= n; ++i) cnt /= i;
  14.     cout<<cnt;
  15.     return 0;
  16. }
  17.  
  18. /*
  19. Sample input:
  20. 6
  22. Sample output:
  23. 132
  24. */
  25.  
  26. /*
  27. Additional input:
  28. 14
  30. Additional output:
  31. 2674440
  32. */

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

note：

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. void displayDNA1(){
  9.     cout<<"   AT   \n";
  10.     cout<<"  T--A  \n";
  11.     cout<<" A----T \n";
  12.     cout<<"T------A\n";
  13.     cout<<"T------A\n";
  14.     cout<<" G----C \n";
  15.     cout<<"  T--A  \n";
  16.     cout<<"   GC   \n";
  17. }
  18.  
  19. void displayDNA2(){
  20.     cout<<"   CG   \n";
  21.     cout<<"  C--G  \n";
  22.     cout<<" A----T \n";
  23.     cout<<"A------T\n";
  24.     cout<<"T------A\n";
  25.     cout<<" A----T \n";
  26.     cout<<"  A--T  \n";
  27.     cout<<"   GC   \n";
  28. }
  29.  
  30. void displayDNA3(){
  31.     cout<<"   AT   \n";
  32.     cout<<"  C--G  \n";
  33.     cout<<" T----A \n";
  34.     cout<<"C------G\n";
  35.     cout<<"C------G\n";
  36.     cout<<" T----A \n";
  37.     cout<<"  G--C  \n";
  38.     cout<<"   AT   \n";
  39. }
  40.  
  41. int main() {
  42.     int n;
  43.     cin>>n;
  44.     for (int i = 1; i <= n/2; ++i) {
  45.         if (i % 3 == 1) displayDNA1();
  46.         else if (i % 3 == 2) displayDNA2();
  47.         else displayDNA3();
  48.     }
  49.     return 0;
  50. }
  51.  
  52. /*
  53. Sample input:
  54. 8
  56. Sample output:
  57.    AT
  58.   T--A
  59.  A----T
  60. T------A
  61. T------A
  62.  G----C
  63.   T--A
  64.    GC
  65.    CG
  66.   C--G
  67.  A----T
  68. A------T
  69. T------A
  70.  A----T
  71.   A--T
  72.    GC
  73.    AT
  74.   C--G
  75.  T----A
  76. C------G
  77. C------G
  78.  T----A
  79.   G--C
  80.    AT
  81.    AT
  82.   T--A
  83.  A----T
  84. T------A
  85. T------A
  86.  G----C
  87.   T--A
  88.    GC
  89. */
  90.  
  91. /*
  92. Additional input:
  93. 2
  95. Additional output:
  96.    AT
  97.   T--A
  98.  A----T
  99. T------A
  100. T------A
  101.  G----C
  102.   T--A
  103.    GC
  104. */

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

note：

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <string>
  6.  
  7. using namespace std;
  8.  
  9. string out[100];
  10. int k=0;
  11.  
  12. int check(string str){
  13.     int i,result;
  14.  
  15.     for(result=str[1],i=2;str[i]!='*';i++)
  16.     {
  17.         result^=str[i];
  18.     }
  19.     return result;
  20. }
  21.  
  22. int convert(string str){
  23.     int res=0;
  24.     res=stoi(str,0,16);
  25.     return res;
  26. }
  27.  
  28.  
  29. void convert_BeingTime(string utcTime){
  30.     int  hour=stoi(utcTime.substr(0,2));
  31.     int  B_hour=(hour+8)%24;
  32.     if(B_hour/10==0)
  33.         out[k++]="0"+to_string(B_hour)+":"+utcTime.substr(2,2)+":"+utcTime.substr(4,2);
  34.     else
  35.         out[k++]=to_string(B_hour)+":"+utcTime.substr(2,2)+":"+utcTime.substr(4,2);
  36.  
  37. }
  38.  
  39. int main(){
  40.     string str;
  41.     while(cin>>str){
  42.         if(str=="END") break;
  43.         if(str.compare(0,6,"$GPRMC")==0){
  44.             size_t asteriskPos = str.find('*');
  45.             if(asteriskPos!=string::npos){
  46.                 int checksum=check(str);
  47.  
  48.                 int senchecksum=convert(str.substr(asteriskPos + 1, 2));
  49.                 if(checksum!=senchecksum) {
  50.                     out[k++]="error";
  51.  
  52.                 }
  53.                 else{
  54.                     string utcTime = str.substr(7, 6);
  55.  
  56.                     convert_BeingTime(utcTime);
  57.                 }
  58.             }
  59.         }
  60.  
  61.     }
  62.     for(int i=0;i<k;i++){
  63.         cout<<out[i]<<endl;
  64.     }
  65. }
  66.  
  67. /*
  68. Sample input:
  69. $GPRMC,024813.640,A,3158.4608,N,11848.3737,E,10.05 ,324.27,150706,,,A*50
  70. $GPGSV,3,1,11,10,63,137,17,07,61,098,15,05,59,290,20,08,54,157,30*70
  71. $GPRMC,194548.127,A,5230.657,N,01325.713,E,3968.7,122.8,200220,000.0,W*44
  72. $GPGGA,092750.000,5321.6802,N,00630.3372,W,1,8,1.03,61.7,M,55.2,M,,*76
  73. $GPRMC,111724.681,A,5231.801,N,01329.267,E,1289.3,000.0,291123,000.0,W*48
  74. $GNVTG,112.99,T,109.99,M,0.15,N,0.08,K,A*3B
  75. END
  77. Sample output:
  78. 10:48:13
  79. error
  80. 19:17:24
  81. */
  82.  
  83. /*
  84. Additional input:
  85. NULL
  87. Additional output:
  88. NULL
  89. */

064.循环排序

note：

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

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

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

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. void swap(int *a, int *b) {
  9.     int tmp = *a;
  10.     *a = *b, *b = tmp;
  11. }
  12.  
  13. void CycleSort(int arr[], int n) {
  14.     for (int i = 0; i < n - 1; ++i) {
  15.         int item = arr[i], pos = i;
  16.         for (int j = i + 1; j < n; ++j) if (arr[j] < item) ++pos;
  17.  
  18.         if (pos == i) continue;
  19.  
  20.         swap(&arr[pos], &item);
  21.         while(pos != i) {
  22.             pos = i;
  23.             for (int j = i + 1; j < n; ++j) if (arr[j] < item) ++pos;
  24.             while (item == arr[pos]) ++pos;
  25.             swap(&arr[pos], &item);
  26.         }
  27.     }
  28. }
  29.  
  30. int main() {
  31.     int n;
  32.     cin>>n;
  33.     int arr[n];
  34.     for (int i = 0; i < n; ++i) cin>>arr[i];
  35.     CycleSort(arr, n);
  36.     for (int i = 0; i < n; ++i) cout<<arr[i]<<' ';
  37.     return 0;
  38. }
  39.  
  40. /*
  41. Sample input:
  42. 8
  43. 1 8 3 9 10 10 2 4
  45. Sample output:
  46. 1 2 3 4 8 9 10 10
  47. */
  48.  
  49. /*
  50. Additional input:
  51. 10
  52. 1 1 1 1 2 6 2 6 2 7
  54. Additional output:
  55. 1 1 1 1 2 2 2 6 6 7
  56. */

065.长安

note：

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. //version 1:simple combination
  5. //but noj doesn't fully support cmath(seemly), so it's WA
  6. //of course you can write functions to fully replace cmath to ensure AC
  7.  
  8. #include <iostream>
  9. #include <cmath>
  10.  
  11. using namespace std;
  12.  
  13. int combination(int n, int k) {
  14.     if (k > n) {
  15.         return 0;
  16.     }
  17.     return tgamma(n + 1) / (tgamma(k + 1) * tgamma(n - k + 1));
  18. }
  19.  
  20. int ways(int bx,int by,int px, int py){
  21.     bx-=1;by-=1;px-=1;py-=1;
  22.     if(bx>=px&&by>=py){
  23.         int nx=bx-px,ny=by-py;
  24.         return combination(bx+by,bx<by?bx:by)-combination(px+py,px<py?px:py)* combination(nx+ny,nx<ny?nx:ny);
  25.     }
  26.     else return combination(bx+by,bx<by?bx:by);
  27. }
  28.  
  29. int main() {
  30.     int bx,by,px,py,cnt=0;
  31.     while (1) {
  32.         cin.sync();
  33.         cin>>bx>>by>>px>>py;
  34.         if (bx <= 0 || by <= 0 || px <= 0 || py <= 0) break;
  35.         cnt=ways(bx,by,px,py);
  36.         cout<<cnt<<endl;
  37.     }
  38. }
  39.  
  40.  
  41. //version 2:DFS
  42.  
  43. #include <iostream>
  44.  
  45. using namespace std;
  46.  
  47. int bx, by, px, py, cnt;
  48.  
  49. void dfs(int x, int y) {
  50.     if ((x == px && y == py) || x > bx || y > by) return;
  51.     if (x == bx && y == by) {
  52.         ++cnt;
  53.         return;
  54.     }
  55.     dfs(x + 1, y);
  56.     dfs(x, y + 1);
  57. }
  58.  
  59. int main() {
  60.     while (1) {
  61.         fflush(stdin);
  62.         cin>>bx>>by>>px>>py;
  63.         if (bx <= 0 || by <= 0 || px <= 0 || py <= 0) break;
  64.         cnt = 0;
  65.         dfs(1, 1);
  66.         cout<<cnt<<endl;
  67.     }
  68.     return 0;
  69. }
  70.  
  71. /*
  72. Sample input:
  73. 8 6 5 3
  74. 8 6 8 6
  75. 8 6 9 6
  76. 0 0 0 0
  78. Sample output:
  79. 492
  80. 0
  81. 792
  82. */
  83.  
  84. /*
  85. Additional input:
  86. 8 5 6 1
  87. 1 6 1 6
  88. 1 6 3 7
  89. 0 0 0 0
  91. Additional output:
  92. 315
  93. 0
  94. 1
  95. */

066.时钟A-B

note：

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

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <ctime>
  6. #include <iomanip>
  7.  
  8. using namespace std;
  9. int main(){
  10.     tm begin = {0}, end = {0};
  11.     cin >> end.tm_year >> end.tm_mon >> end.tm_mday;
  12.     cin >> begin.tm_year >> begin.tm_mon >> begin.tm_mday;
  13.  
  14.     begin.tm_year -= 1900;
  15.     begin.tm_mon -= 1;
  16.     end.tm_year -= 1900;
  17.     end.tm_mon -= 1;
  18.  
  19.     time_t tmBegin =  mktime(&begin);
  20.     time_t tmEnd = mktime(&end);
  21.  
  22.     double difference = difftime(tmEnd, tmBegin);
  23.     cout << fixed<<setprecision(6)<<difference << endl;
  24.     return 0;
  25. }
  26.  
  27.  
  28. /*
  29. Sample input:
  30. 2021 1 2
  31. 2021 1 1
  33. Sample output:
  34. 86400.000000
  35. */
  36.  
  37. /*
  38. Additional input:
  39. 2024 1 1
  40. 2024 1 2
  42. Additional output:
  43. -86400.000000
  44. */

067.Arduino显示

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. static const int digit[10] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
  9.  
  10. int getUnit(int num) {
  11.     int cnt = 0;
  12.     do {
  13.         cnt += digit[num % 10];
  14.         num /= 10;
  15.     } while (num);
  16.     return cnt;
  17. }
  18.  
  19. int main() {
  20.     int n;
  21.     cin>>n;
  22.     n -= 4;
  23.     if (n <= 0) cout<<0;
  24.     else {
  25.         int cnt = 0;
  26.         for (int i = 0; i <= 1111; ++i) {
  27.             for (int j = 0; j <= 1111; ++j) {
  28.                 if (getUnit(i) + getUnit(j) + getUnit(i + j) == n) ++cnt;
  29.             }
  30.         }
  31.         cout<<cnt;
  32.     }
  33.     return 0;
  34. }
  35.  
  36. /*
  37. Sample input:
  38. 14
  40. Sample output:
  41. 2
  42. */
  43.  
  44. /*
  45. Additional input:
  46. 23
  48. Additional output:
  49. 88
  50. */

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. static int freq[26] = {0};
  9.  
  10. int main() {
  11.     char plain[8000] = "";
  12.     int x;
  13.     cin>>plain>>x;
  14.     for (int i = 0; plain[i]; ++i) ++freq[plain[i] - 'a'];
  15.     char cipher[8000] = "";
  16.     for (int i = 0; plain[i]; ++i) {
  17.         if (freq[plain[i] - 'a'] & 1)
  18.             cipher[i] = (char) (((plain[i] - 'a' - x) % 26 + 26) % 26 + 'a');
  19.         else
  20.             cipher[i] = (char) ((plain[i] - 'a' + x) % 26 + 'a');
  21.     }
  22.     cout<<cipher;
  23.     return 0;
  24. }
  25.  
  26. /*
  27. Sample input:
  28. abcda
  29. 3
  31. Sample output:
  32. dyzad
  33. */
  34.  
  35. /*
  36. Additional input:
  37. fdmrghm
  38. 1
  40. Additional output:
  41. ecnqfgn
  42. */

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

note：

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. struct PIDData {
  9.     double Kp, Ki, Kd;
  10.     double preError, integral;
  11. } ;
  12.  
  13. double PIDCalculate(PIDData *pid, double setPoint, double measuredValue) {
  14.     double error = setPoint - measuredValue;
  15.     pid->integral += error;
  16.     double differential = error - pid->preError;
  17.     double output = pid->Kp * error + pid->Ki * pid->integral + pid->Kd * differential;
  18.     pid->preError = error;
  19.     return output;
  20. }
  21.  
  22. int main() {
  23.     double setPoint, measuredValue;
  24.     int time;
  25.     PIDData pid = {0};
  26.     cin>>pid.Kp>>pid.Ki>>pid.Kd;
  27.     cin>>setPoint>>measuredValue>>time;
  28.     for (int i = 1; i <= time; ++i) {
  29.         double output = PIDCalculate(&pid, setPoint, measuredValue);
  30.         measuredValue += output;
  31.         printf("%d %.6lf\n", i, measuredValue);
  32.     }
  33.     return 0;
  34. }
  35.  
  36. /*
  37. Sample input:
  38. 0.1 0.01 0.05
  39. 100 0
  40. 100
  42. Sample output:
  43. 1 16.000000
  44. 2 25.440000
  45. 3 35.009600
  46. 4 44.265664
  47. 5 53.169142
  48. 6 61.668210
  49. 7 69.720909
  50. 8 77.293448
  51. 9 84.359807
  52. 10 90.901240
  53. 11 96.905764
  54. 12 102.367624
  55. 13 107.286754
  56. 14 111.668241
  57. 15 115.521778
  58. 16 118.861142
  59. 17 121.703666
  60. 18 124.069744
  61. 19 125.982338
  62. 20 127.466524
  63. 21 128.549046
  64. 22 129.257909
  65. 23 129.621989
  66. 24 129.670681
  67. 25 129.433566
  68. 26 128.940117
  69. 27 128.219429
  70. 28 127.299977
  71. 29 126.209409
  72. 30 124.974359
  73. 31 123.620295
  74. 32 122.171385
  75. 33 120.650395
  76. 34 119.078603
  77. 35 117.475745
  78. 36 115.859968
  79. 37 114.247816
  80. 38 112.654219
  81. 39 111.092512
  82. 40 109.574456
  83. 41 108.110278
  84. 42 106.708722
  85. 43 105.377103
  86. 44 104.121378
  87. 45 102.946217
  88. 46 101.855081
  89. 47 100.850307
  90. 48 99.933190
  91. 49 99.104069
  92. 50 98.362420
  93. 51 97.706938
  94. 52 97.135627
  95. 53 96.645882
  96. 54 96.234574
  97. 55 95.898129
  98. 56 95.632605
  99. 57 95.433761
  100. 58 95.297129
  101. 59 95.218079
  102. 60 95.191874
  103. 61 95.213729
  104. 62 95.278857
  105. 63 95.382521
  106. 64 95.520066
  107. 65 95.686962
  108. 66 95.878832
  109. 67 96.091477
  110. 68 96.320904
  111. 69 96.563341
  112. 70 96.815249
  113. 71 97.073341
  114. 72 97.334582
  115. 73 97.596194
  116. 74 97.855665
  117. 75 98.110740
  118. 76 98.359419
  119. 77 98.599956
  120. 78 98.830847
  121. 79 99.050823
  122. 80 99.258838
  123. 81 99.454062
  124. 82 99.635862
  125. 83 99.803795
  126. 84 99.957590
  127. 85 100.097136
  128. 86 100.222469
  129. 87 100.333754
  130. 88 100.431276
  131. 89 100.515421
  132. 90 100.586667
  133. 91 100.645566
  134. 92 100.692736
  135. 93 100.728849
  136. 94 100.754615
  137. 95 100.770775
  138. 96 100.778092
  139. 97 100.777339
  140. 98 100.769291
  141. 99 100.754719
  142. 100 100.734384
  143. */
  144.  
  145. /*
  146. Additional input:
  147. NULL
  149. Additional output:
  150. NULL
  151. */

070.三元搜索

note：

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. int terSearch(int arr[], int n, int k) {
  9.     int left = 0, right = n - 1, mid1 = (n - 1) / 3, mid2 = n - mid1;
  10.     while(mid1 != mid2) {
  11.         if (k > arr[right] || k < arr[left]) return -1;
  12.         if (k == arr[mid1]) return mid1;
  13.         if (k == arr[mid2]) return mid2;
  14.         if (mid1 == mid2) break;
  15.         if (k < arr[mid1]) right = mid1 - 1;
  16.         else if (k > arr[mid2]) left = mid2 + 1;
  17.         else left = mid1 + 1, right = mid2 - 1;
  18.         mid1 = left + (right - left) / 3, mid2 = right - (right - left) / 3;
  19.     }
  20.     return -1;
  21. }
  22.  
  23. int main() {
  24.     int n, k;
  25.     cin>>n;
  26.     int arr[n];
  27.     for (int i = 0; i < n; ++i) cin>>arr[i];
  28.     cin>>k;
  29.     printf("%d in [%d]", k, terSearch(arr, n, k));
  30.     return 0;
  31. }
  32.  
  33. /*
  34. Sample input:
  35. 10
  36. 1 2 3 4 5 6 7 8 9 10
  37. 5
  39. Sample output:
  40. 5 in [4]
  41. */
  42.  
  43. /*
  44. Additional input:
  45. 10
  46. 11 16 18 19 21 34 53 55 69 70
  47. 55
  49. Additional output:
  50. 55 in [7]
  51. */

第8季（071-080）

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

note：

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <vector>
  6. #include <iomanip>
  7.  
  8. using namespace std;
  9.  
  10. int main() {
  11.     vector<int> arr;
  12.     int tmp;
  13.     int cnt=0;
  14.     int count[100]={0};
  15.     cin>>tmp;
  16.     while(tmp>=0) {
  17.         arr.push_back(tmp);
  18.         if (tmp == 0) {
  19.             cnt++;
  20.         }else{
  21.             count[cnt]++;
  22.         }
  23.         cin >> tmp;
  24.     }
  25.  
  26.     vector<int> print;
  27.  
  28.     for(int i=0;i<arr.size();++i){
  29.         if(arr[i]>0){
  30.             print.push_back(arr[i]);
  31.         }
  32.     }
  33.  
  34.  
  35.     int sum[100]={0};
  36.     for(int k=0;k<cnt;++k){
  37.         for(int l=0;l<=k;++l)
  38.         {
  39.             sum[k]+=count[l];
  40.         }
  41.     }
  42.  
  43.  
  44.     for(int k=0;k<cnt;++k){
  45.         for(int i=0;i<sum[k];++i){
  46.             cout<<print[i]<<' ';
  47.         }
  48.         double ans;
  49.         if(sum[k]%2==0){
  50.             ans=(print[sum[k]/2]+print[sum[k]/2-1])/2.0;
  51.         }
  52.         else ans=print[sum[k]/2];
  53.         cout<<fixed<<setprecision(6)<<ans<<endl;
  54.     }
  55. }
  56.  
  57. /*
  58. Sample input:
  59. 1 2 3 4 5 0
  60. 7 8 9 0
  61. -1
  63. Sample output:
  64. 1 2 3 4 5 3.000000
  65. 1 2 3 4 5 7 8 9 4.500000
  66. */
  67.  
  68. /*
  69. Additional input:
  70. 145 15 163 13609 135 0
  71. 15 3614 16345 13051 16349 14 0
  72. -1
  74. Additional output:
  75. 145 15 163 13609 135 163.000000
  76. 145 15 163 13609 135 15 3614 16345 13051 16349 14 15.000000
  77. */

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

note：

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

  1. //Difficulty:??/10
  2. //Importance: 0/10
  3.  
  4. #include <iostream>
  5. #include <cmath>
  6.  
  7. #define N 11
  8. #define c 299792.458
  9.  
  10. using namespace std;
  11.  
  12. double X[N],A[N],B[N],C[N],T[N];
  13.  
  14. void scanf1(double A[N],int n){
  15.     for(int i=0;i<n;i++) {
  16.         cin >> A[i];
  17.     }
  18. }
  19.  
  20. void print1(double A[N],int n) { //输出一个矢量
  21.     int i,tmp;
  22.     double a;
  23.     for (i=0; i<n-1; i++){
  24.         tmp=(int)(A[i]*10000);
  25.         a=(double)tmp/10000.0;
  26.         printf("%.4lf,",a);
  27.     }
  28.     tmp=(int)(A[n-1]*10000);
  29.     a=(double)tmp/10000.0;
  30.     printf("%.4lf",a);
  31.  
  32. }
  33.  
  34. void print2(double A[N][N],int n) { //输出一个矩阵
  35.     int i, j;
  36.     for (i=0; i<n; i++) {
  37.         for (j=0; j<n; j++)
  38.             printf("%.7lf ", A[i][j]);
  39.         printf("\n");
  40.     }
  41. }
  42.  
  43. // 计算代数余子式函数，结果=dest
  44. int GetCoFactor(double dest[N][N], double src[N][N], int row, int col, int n)
  45. {
  46.     int i, j;
  47.     int colCount=0,rowCount=0;
  48.     for(i=0; i<n; i++ ) {
  49.         if( i!=row ) {
  50.             colCount = 0;
  51.             for(j=0; j<n; j++ )
  52.                 if( j != col ) { //当j不是元素时
  53.                     dest[rowCount][colCount] = src[i][j];
  54.                     colCount++;
  55.                 }
  56.             rowCount++;
  57.         }
  58.     }
  59.     return 1;
  60. }
  61.  
  62. // 递归计算行列式，结果=返回值
  63. double CalcDeterminant(double mat[N][N], int n)
  64. {
  65.     int i,j;
  66.     double det = 0; //行列式值
  67.     double minor[N][N]; // allocate 余子式矩阵
  68.  
  69.     // n 必须 >= 0，当矩阵是单个元素时停止递归
  70.     if( n == 1 ) return mat[0][0];
  71.     for(i = 0; i < n; i++ ) {
  72.         GetCoFactor(minor, mat, 0, i , n);
  73.         det += ( i%2==1 ? -1.0 : 1.0 ) * mat[0][i] * CalcDeterminant(minor,n-1);
  74.     }
  75.     return det;
  76. }
  77. // 伴随矩阵法矩阵求逆 , 结果存放到 inv 数组
  78. void MatrixInversion(double J[N][N], int n)
  79. {
  80.     int i,j;
  81.     double det, temp [N][N], minor[N][N];
  82.     double inv[N][N];
  83.  
  84.     det = 1.0/CalcDeterminant(J,n); //计算行列式
  85.     for(j=0; j<n; j++)
  86.         for(i=0; i<n; i++) {
  87.             // 得到矩阵A(j,i)的代数余子式
  88.             GetCoFactor(minor,J,j,i,n);
  89.             inv[i][j] = det*CalcDeterminant(minor,n-1);
  90.             if( (i+j)%2 == 1)
  91.                 inv[i][j] = -inv[i][j];
  92.         }
  93.     //结果存回J矩阵
  94.     for(j=0; j<n; j++)
  95.         for(i=0; i<n; i++)
  96.             J[i][j] = inv[i][j];
  97. }
  98.  
  99. // 由Xn计算函数Fn，结果存放到 F
  100. void CalcF(double F[N],double X[N],int n) {
  101.     double f;
  102.     int i;
  103.     for (i=0; i<n; i++) {
  104.         switch (i+1) {
  105.             case 1:
  106.                 f=X[0]*X[0]+X[1]*X[1]-2*X[0]-X[2]+1; //x^2+y^2-2x-z+1
  107.                 break;
  108.             case 2:
  109.                 f=X[0]*X[1]*X[1]-X[0]-3*X[1]+X[1]*X[2]+2; //xy^2-x-3y+yz+2
  110.                 break;
  111.             case 3:
  112.                 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
  113.                 break;
  114.         }
  115.         F[i]=f;
  116.     }
  117. }
  118.  
  119. void CalcF_re(double F[N],double X[N],int n) {
  120.     double f;
  121.     int i;
  122.     for (i=0; i<n; i++) {
  123.         switch (i+1) {
  124.             case 1:
  125.                 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]));
  126.                 break;
  127.             case 2:
  128.                 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]));
  129.                 break;
  130.             case 3:
  131.                 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]));
  132.                 break;
  133.             case 4:
  134.                 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]));
  135.         }
  136.         F[i]=f;
  137.     }
  138. }
  139.  
  140. // 由Xn计算偏导数Jacobian矩阵F'n，结果存放到 J
  141. void CalcJ(double J[N][N],double X[N],int n) {
  142.     double f;
  143.     int i,j;
  144.     for (i=0; i<n; i++)
  145.         switch (i+1) {
  146.             case 1:
  147.                 for (j=0; j<n; j++) {
  148.                     switch (j+1) {
  149.                         case 1: f=2*X[0]-2;break; // J1.1=2x-2
  150.                         case 2: f=2*X[1];break; // J1.2=2y
  151.                         case 3: f=-1;break;  // J1.3=-1
  152.                     }
  153.                     J[i][j]=f;
  154.                 }
  155.                 break;
  156.             case 2:
  157.                 for (j=0; j<n; j++) {
  158.                     switch (j+1) {
  159.                         case 1: f=X[1]*X[1]-1;break; // J2.1=y^2-1
  160.                         case 2: f=2*X[0]*X[1]-3+X[2];break; // J2.2=2xy-3+z
  161.                         case 3: f=X[1];break; // J2.3=y
  162.                     }
  163.                     J[i][j]=f;
  164.                 }
  165.                 break;
  166.             case 3:
  167.                 for (j=0; j<n; j++) {
  168.                     switch (j+1) {
  169.                         case 1: f=X[2]*X[2]+X[1];break; // J3.1=z^2+y
  170.                         case 2: f=X[2]*X[2]+X[0];break; // J3.2=z^2+x
  171.                         case 3: f=2*X[0]*X[2]-3+2*X[1]*X[2];break; // J3.3=2xz-3+2yz
  172.                     }
  173.                     J[i][j]=f;
  174.                 }
  175.                 break;
  176.         }
  177. }
  178.  
  179. // 由Xn计算偏导数Jacobian矩阵F'n，结果存放到 J
  180. void CalcJ_re(double J[N][N],double X[N],int n) {
  181.     double f;
  182.     int i,j;
  183.     for (i=0; i<n; i++)
  184.         switch (i+1) {
  185.             case 1:
  186.                 for (j=0; j<n; j++) {
  187.                     switch (j+1) {
  188.                         case 1: f=2*(X[0]-A[0]);break; // J1.1=2(x-A1)
  189.                         case 2: f=2*(X[1]-B[0]);break; // J1.2=2(y-B1)
  190.                         case 3: f=2*(X[2]-C[0]);break;  // J1.3=2(z-C1)
  191.                         case 4: f=2*c*c*(T[0]-X[3]);break;//J1.4=2*c^2(t1-d)
  192.                     }
  193.                     J[i][j]=f;
  194.                 }
  195.                 break;
  196.             case 2:
  197.                 for (j=0; j<n; j++) {
  198.                     switch (j+1) {
  199.                         case 1: f=2*(X[0]-A[1]);break; // J1.1=2(x-A1)
  200.                         case 2: f=2*(X[1]-B[1]);break; // J1.2=2(y-B1)
  201.                         case 3: f=2*(X[2]-C[1]);break;  // J1.3=2(z-C1)
  202.                         case 4: f=2*c*c*(T[1]-X[3]);break;//J1.4=2*c^2(t1-d)
  203.                     }
  204.                     J[i][j]=f;
  205.                 }
  206.                 break;
  207.             case 3:
  208.                 for (j=0; j<n; j++) {
  209.                     switch (j+1) {
  210.                         case 1: f=2*(X[0]-A[2]);break; // J1.1=2(x-A1)
  211.                         case 2: f=2*(X[1]-B[2]);break; // J1.2=2(y-B1)
  212.                         case 3: f=2*(X[2]-C[2]);break;  // J1.3=2(z-C1)
  213.                         case 4: f=2*c*c*(T[2]-X[3]);break;//J1.4=2*c^2(t1-d)
  214.                     }
  215.                     J[i][j]=f;
  216.                 }
  217.                 break;
  218.             case 4:
  219.                 for (j=0; j<n; j++) {
  220.                     switch (j+1) {
  221.                         case 1: f=2*(X[0]-A[3]);break; // J1.1=2(x-A1)
  222.                         case 2: f=2*(X[1]-B[3]);break; // J1.2=2(y-B1)
  223.                         case 3: f=2*(X[2]-C[3]);break;  // J1.3=2(z-C1)
  224.                         case 4: f=2*c*c*(T[3]-X[3]);break;//J1.4=2*c^2(t1-d)
  225.                     }
  226.                     J[i][j]=f;
  227.                 }
  228.                 break;
  229.         }
  230. }
  231.  
  232. // 计算 J^-1* F，结果存放到 R
  233. void CalcJF(double R[N], double J[N][N], double F[N], int n) {
  234.     int i,j,k;
  235.     for (i=0; i<n; i++) {
  236.         R[i]=0.0;
  237.         for (j=0; j<n; j++)
  238.             R[i] = R[i] + J[i][j]*F[j];
  239.     }
  240. }
  241.  
  242. // 计算 X=X0-R，结果存放到 X
  243. void CalcX(double X[N],double X0[N],double R[N],int n) {
  244.     int i;
  245.     for (i=0; i<n; i++)
  246.         X[i]=X0[i]-R[i];
  247. }
  248.  
  249. // 计算 A=B，结果存放到 A
  250. void AequB(double A[N],double B[N],int n) {
  251.     int i;
  252.     for (i=0; i<n; i++)
  253.         A[i]=B[i];
  254. }
  255.  
  256. // 计算 F-
  257. double Ferror(double F[N], int n) {
  258.     double m=0;
  259.     int i;
  260.     for (i=0; i<n; i++) {
  261.         double t=fabs(F[i]);
  262.         if (m<t) m = t;
  263.     }
  264.     return m;
  265. }
  266.  
  267. // Newton–Raphson method 牛顿迭代法求非线性方程组的根，存放到X0
  268. void mvNewtons(double X0[N], int n, double e) {
  269.     // Guess为初始猜测值 e为迭代精度要求
  270.     int k;
  271.     double J[N][N],Y[N][N];
  272.     double X[N],R[N],F[N];
  273.     //X0一开始为初始猜测值
  274.     for (k=1; k<=20; k++) { //限定20次迭代
  275.         /*
  276. 		printf("-------------- n=%d\n",k);
  277. 		printf("X\n");
  278. 		print1(X0,n); //输出X0
  279.         */
  280.         CalcF_re(F,X0,n); //计算F矩阵
  281.         /*
  282. 		printf("F\n"); //观察 F
  283. 		print1(F,n); //输出F
  284.         */
  285.         CalcJ_re(J,X0,n); //计算Jacobian矩阵F'n(x0)
  286.         /*
  287. 		printf("J\n");
  288. 		print2(J,n); //观察 J
  289.         */
  290.         MatrixInversion(J, n); // 求J的逆矩阵 J^-1
  291.         CalcJF(R,J,F,n); // R=J^-1 * F
  292.         CalcX(X,X0,R,n); // X=X0-R
  293.         AequB(X0,X,n); // X0=X 下次迭代
  294.         if (Ferror(F,n)<e) break; //达到精度要求，终止迭代
  295.     }
  296. }
  297.  
  298. int main() {
  299.     int n=4;
  300.     cin>>A[0]>>B[0]>>C[0];
  301.     cin>>A[1]>>B[1]>>C[1];
  302.     cin>>A[2]>>B[2]>>C[2];
  303.     cin>>A[3]>>B[3]>>C[3];
  304.     scanf1(T,n);
  305.     scanf1(X,n);
  306.     mvNewtons(X,n,1e-6); //根存放在X
  307.     print1(X,3);
  308.     return 0;
  309. }
  310.  
  311.  
  312. /*
  313. Sample input:
  314. 15600 7540 20140
  315. 18760 2750 18610
  316. 17610 14630 13480
  317. 19170 610 18390
  318. 0.07074 0.07220 0.07690 0.07242
  319. 0 0 6370 0
  321. Sample output:
  322. -41.7727,-16.7891,6370.0595
  323. */
  324.  
  325. /*
  326. Additional input:
  327. NULL
  329. Additional output:
  330. NULL
  331. */

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. int maxi(int a, int b) {
  9.     return a > b ? a : b;
  10. }
  11.  
  12. int mini(int a, int b) {
  13.     return a < b ? a : b;
  14. }
  15.  
  16. int cross(int x1, int y1, int x2, int y2) {
  17.     return x1 * y2 - y1 * x2;
  18. }
  19.  
  20. bool insert(int line1[4], int line2[4]) {
  21.     if (maxi(line2[0], line2[2]) < mini(line1[0], line1[2]) ||
  22.         maxi(line1[0],line1[2]) < mini(line2[0], line2[2]) ||
  23.         maxi(line2[1], line2[3]) < mini(line1[1], line1[3]) ||
  24.         maxi(line1[1], line2[3]) < mini(line2[1],line2[3])) return false;
  25.     if (cross(line1[2] - line1[0], line1[3] - line1[1], line2[0] - line1[0], line2[1] - line1[1]) *
  26.         cross(line1[2] - line1[0], line1[3] - line1[1], line2[2] - line1[0], line2[3] - line1[1]) > 0 ||
  27.         cross(line2[2] - line2[0], line2[3] - line2[1], line1[0] - line2[0], line1[1] - line2[1]) *
  28.         cross(line2[2] - line2[0], line2[3] - line2[1], line1[2] - line2[0], line1[3] - line2[1]) > 0) return false;
  29.     return true;
  30. }
  31.  
  32. int main() {
  33.     int n;
  34.     cin>>n;
  35.     int line[n][4];
  36.     for (int i = 0; i < n; ++i)
  37.         for (int j = 0; j < 4; ++j) cin>>line[i][j];
  38.  
  39.     int cnt = 0;
  40.     for (int i = 0; i < n; ++i) {
  41.         for (int j = i + 1; j < n; ++j) {
  42.             if (insert(line[i], line[j])) {
  43.                 cout<<"X: #"<<i + 1<<" #"<<j + 1<<endl;
  44.                 ++cnt;
  45.             }
  46.         }
  47.     }
  48.     cout<<"n="<<cnt;
  49.     return 0;
  50. }
  51.  
  52. /*
  53. Sample input:
  54. 5
  55. 1 5 4 5
  56. 2 5 10 1
  57. 3 2 10 3
  58. 6 4 9 4
  59. 7 1 8 1
  61. Sample output:
  62. X: #1 #2
  63. X: #2 #3
  64. n=2
  65. */
  66.  
  67. /*
  68. Additional input:
  69. 5
  70. 1 5 4 9
  71. 2 5 10 3
  72. 3 2 10 6
  73. 6 4 9 45
  74. 7 1 8 0
  76. Additional output:
  77. X: #2 #3
  78. X: #2 #4
  79. n=2
  80. */

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

note：

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

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

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

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

  1. //Difficulty:??/10
  2. //Importance: 0/10
  3.  
  4. //3th none AC you meet
  5.  
  6. #include <cmath>
  7. #include <iostream>
  8. #include <iomanip>
  9.  
  10. #define M_PI 3.14159265358979323846
  11.  
  12. using namespace std;
  13.  
  14. double degToRad(double deg) {
  15.     return deg * M_PI / 180.0;
  16. }
  17.  
  18. double calcSolarDeclination(int dayOfYear) {
  19.     return 0.4093 *  sin((2.0 * M_PI / 365.0) * dayOfYear - 1.405);
  20. }
  21.  
  22. double calcTime(int year, int month, int day, double longitude, double latitude, bool sunrise, int timezone) {
  23.     int dayOfYear = (month - 1) * 30 + day;
  24.     double declination = calcSolarDeclination(dayOfYear);
  25.     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;
  26.     return time - 4.0 * longitude / 60.0 + timezone;
  27. }
  28.  
  29. int main() {
  30.     int year, month, day, timezone;
  31.     double longitude, latitude;
  32.     cin >> year >> month >> day ;
  33.     cin >> longitude >> latitude ;
  34.     cin >> timezone;
  35.  
  36.     double sunrise = calcTime(year, month, day, longitude, latitude, true, timezone);
  37.     double sunset = calcTime(year, month, day, longitude, latitude, false, timezone);
  38.     double noon = calcTime(year, month, day, longitude, latitude, false, timezone) - (sunset - sunrise) / 2;
  39.  
  40.     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;
  41.     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;
  42.     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;
  43.     return 0;
  44. }
  45.  
  46. /*
  47. Sample input:
  48. 2022 8 15
  49. 108.760064 34.035672
  51. Sample output:
  53. */
  54.  
  55. /*
  56. Additional input:
  57. NULL
  59. Additional output:
  60. NULL
  61. */

075.成绩单

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

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. typedef struct tag {
  9.     long long id;
  10.     char name[31];
  11.     int score;
  12. } ST;
  13.  
  14. void load(ST* arr[], int n) {
  15.     for (int i = 0; i < n; ++i) {
  16.         arr[i] = (ST*) malloc(sizeof(ST));
  17.         cin>>arr[i]->id>>arr[i]->name>>arr[i]->score;
  18.     }
  19. }
  20.  
  21. void sort(ST* arr[], int n) {
  22.     ST* tmp = NULL;
  23.     for (int i = 0; i < n; ++i) {
  24.         bool isSwapped = false;
  25.         for (int j = 0; j < n - 1 - i; ++j)
  26.             if ((arr[j]->score < arr[j + 1]->score) ||
  27.                 (arr[j]->score == arr[j + 1]->score && arr[j]->id > arr[j + 1]->id))
  28.                 tmp = arr[j], arr[j] = arr[j + 1], arr[j + 1] = tmp, isSwapped = true;
  29.         if (!isSwapped) break;
  30.     }
  31. }
  32.  
  33. void traverse(ST* arr[], int n) {
  34.     for (int i = 0; i < n; ++i)
  35.         cout<<arr[i]->id<<' '<<arr[i]->name<<' '<<arr[i]->score<<endl;
  36. }
  37.  
  38. int main() {
  39.     int n;
  40.     cin>>n;
  41.     ST* grade[n];
  42.     load(grade, n);
  43.     sort(grade, n);
  44.     traverse(grade, n);
  45.     return 0;
  46. }
  47.  
  48.  
  49. /*
  50. Sample input:
  51. 6
  52. 2001900001 Jerry 88
  53. 2001900005 Tom 92
  54. 2001900006 Milla 85
  55. 2001900002 Alice 80
  56. 2001900003 Mickey 85
  57. 2001900004 Aladdin 83
  59. Sample output:
  60. 2001900005 Tom 92
  61. 2001900001 Jerry 88
  62. 2001900003 Mickey 85
  63. 2001900006 Milla 85
  64. 2001900004 Aladdin 83
  65. 2001900002 Alice 80
  66. */
  67.  
  68. /*
  69. Additional input:
  70. NULL
  72. Additional output:
  73. NULL
  74. */

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

note：

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

2.这题目整的多牵强；

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <string>
  6. #include <iomanip>
  7. #include <cmath>
  8.  
  9. using namespace std;
  10.  
  11. struct Atom
  12. {
  13.     string name;
  14.     double mass;
  15.     double APF;
  16.     double r;
  17. };
  18.  
  19. Atom elemList[] =
  20.         {
  21.                 { "Po",   208.998, 0.52360, 1.68 },
  22.                 { "Li",     6.941, 0.68017, 1.52 },
  23.                 { "Na", 22.989770, 0.68017, 1.86 },
  24.                 { "Cr",   51.9961, 0.68017, 1.28 },
  25.                 { "Mn", 54.938049, 0.68017, 1.27 },
  26.                 { "Fe",    55.845, 0.68017, 1.26 },
  27.                 { "Mo",     95.94, 0.68017, 1.39 },
  28.                 { "Ta",  180.9749, 0.68017, 1.46 },
  29.                 { "Al", 26.981538, 0.74048, 1.43 },
  30.                 { "Ca",    40.078, 0.74048, 1.97 },
  31.                 { "Ni",   58.6934, 0.74048, 1.24 },
  32.                 { "Cu",    63.546, 0.74048, 1.28 },
  33.                 { "Ge",     72.64, 0.74048, 1.22 },
  34.                 { "Ag",  107.8682, 0.74048, 1.44 },
  35.                 { "Pt",   195.078, 0.74048, 1.39 },
  36.                 { "Au", 196.96655, 0.74048, 1.44 },
  37.                 { "Pb",     207.2, 0.74048, 1.75 }
  38.         };
  39.  
  40. template <int N> double pow(double a) { return a * pow<N - 1>(a); }
  41.  
  42. template <> double pow<0>(double a) { return 1; }
  43.  
  44. int main()
  45. {
  46.  
  47.     int n;
  48.     cin >> n;
  49.     for (int i = 0; i < n; ++i)
  50.     {
  51.         string in;
  52.         cin >> in;
  53.         for(const auto& e : elemList)
  54.         {
  55.             if(e.name == in)
  56.             {
  57.                 double V = 4.0 * M_PI * pow<3>(e.r) / 3.0;
  58.                 cout << fixed << setprecision(2) << 10.0 * e.mass * e.APF / 6.022 / V << endl;
  59.                 break;
  60.             }
  61.         }
  62.     }
  63.     return 0;
  64. }
  65.  
  66. /*
  67. Sample input:
  68. 3
  69. Po
  70. Mo
  71. Cu
  73. Sample output:
  74. 9.15
  75. 9.63
  76. 8.89
  77. */
  78.  
  79. /*
  80. Additional input:
  81. NULL
  83. Additional output:
  84. NULL
  85. */

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

  1. //Difficulty: 2/10
  2. //Importance: 2/10
  3.  
  4. #include <iostream>
  5. #include <map>
  6.  
  7. using namespace std;
  8.  
  9. string s;
  10.  
  11. int getnum(int x)
  12. {
  13.     int res = 0;
  14.     while (true)
  15.     {
  16.         char ch = s[x];
  17.         if(ch >='0'&& ch<='9' && s[x])
  18.         {
  19.             res = res * 10 + ch - '0';
  20.             ++ x;
  21.         }
  22.         else return res;
  23.     }
  24.     return res;
  25. }
  26.  
  27. int main()
  28. {
  29.     getline(cin, s);
  30.     map<string, int> ump;
  31.     for (int i = 0; s[i]; i ++)
  32.     {
  33.         char ch = s[i];
  34.         if(!(ch>='A' && ch<='Z'))continue;
  35.         char ch1 = s[i+1];
  36.         if (ch1>='a' && ch1<='z')
  37.         {
  38.             string ele = "";
  39.             ele.append(1, ch);
  40.             ele.append(1, ch1);
  41.             int num = getnum(i+2);
  42.             if(num)
  43.             {
  44.                 if(!ump.count(ele)) ump[ele] = num;
  45.                 else ump[ele] += num;
  46.             }
  47.             else
  48.             {
  49.                 if(!ump.count(ele)) ump[ele] = 1;
  50.                 else ump[ele] += 1;
  51.             }
  52.         }
  53.         else
  54.         {
  55.             int num = getnum(i+1);
  56.             string ele = "";
  57.             ele.append(1, ch);
  58.             if(num)
  59.             {
  60.                 if(!ump.count(ele)) ump[ele] = num;
  61.                 else ump[ele] += num;
  62.             }
  63.             else
  64.             {
  65.                 if(!ump.count(ele)) ump[ele] = 1;
  66.                 else ump[ele] += 1;
  67.             }
  68.         }
  69.     }
  70.  
  71.     for (auto& p : ump)
  72.     {
  73.         cout << p.first << " " << p.second << endl;
  74.     }
  75.  
  76. }
  77.  
  78.  
  79. /*
  80. Sample input:
  81. Fe2H3OH
  83. Sample output:
  84. Fe 2
  85. H 4
  86. */
  87.  
  88. /*
  89. Additional input:
  90. H2O
  92. Additional output:
  93. H 2
  94. O 1
  95. */

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

note：

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/72094
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。