企业商务网站优化,网站推广阶段,链家网,网站建设的大功效1. 洛谷练习——P1579 哥德巴赫猜想#xff08;升级版#xff09;
题目描述#xff1a; 现在请你编一个程序验证哥德巴赫猜想。 先给出一个奇数n#xff0c;要求输出3个质数#xff0c;这3个质数之和等于输入的奇数。 输入格式#xff1a; 仅有一行#xff0c;包含一个…1. 洛谷练习——P1579 哥德巴赫猜想升级版
题目描述 现在请你编一个程序验证哥德巴赫猜想。 先给出一个奇数n要求输出3个质数这3个质数之和等于输入的奇数。 输入格式 仅有一行包含一个正奇数n其中9n20000 输出格式 仅有一行输出3个质数这3个质数之和等于输入的奇数。相邻两个质数之间用一个空格隔开最后一个质数后面没有空格。如果表示方法不唯一请输出第一个质数最小的方案如果第一个质数最小的方案不唯一请输出第一个质数最小的同时第二个质数最小的方案。 分析过程 如果一个奇数能分为三个数和则只有两种情况①偶数偶数奇数 ②奇数奇数奇数。如果在加上三个数必须是质数这个条件则①22n−42 2n-422n−4偶质数只有222如果n−4n-4n−4为质数则成立②质数质数质数这三个数为大于等于3的奇数 代码
#includeiostream
#includecmath
using namespace std;
bool isPrime_3(int num);
int main()
{int n;cin n;if (isPrime_3(n - 4))//如果满足第一种情况直接输出返回{cout 2 2 n - 4 endl;return 0;}elsefor (int i 3; i n; i 2){if (isPrime_3(i)) //i必须是质数{for (int j i; i n; j 2)//这里先判断n-j-i是不是奇数因为判断奇数比较快 另一种判断奇数(n-j-i)1if ((n - j - i) % 2 1 isPrime_3(j) isPrime_3(n - j - i)){cout i j n - j - i endl;return 0;}}}
}
bool isPrime_3(int num)//优化后的判断质数 第一次洛谷刷题学到的详细看【c算法刷题笔记】——洛谷1
{if (num 2 || num 3)return 1;if (num % 6 ! 1 num % 6 ! 5)return 0;int tmp sqrt(num);for (int i 5; i tmp; i 6)if (num % i 0 || num % (i 2) 0)return 0;return 1;
}总结 这是看洛谷一个牛犇的想法为什么可以这么做题目中很明显只让输出一组解所以只需要在iii和jjj都是质数的前提下判断n−j−in-j-in−j−i这个数是不是质数如果是就输出而且对于分析过程将题目简化值得学习
2. 关于取模运算的优化技巧——P1226 【模板】快速幂||取余运算
(A1A2A3⋯An)modX(A1modXA2modXA3modX⋯AnmodX)modX(A_1A_2A_3\cdotsA_n)modX(A_1modXA_2modXA_3modX\cdotsA_nmodX)modX(A1A2A3⋯An)modX(A1modXA2modXA3modX⋯AnmodX)modX (A1×A2×A3×⋯×An)modX(A1modX×A2modX×A3modX×⋯×AnmodX)modX(A_1×A_2×A_3×\cdots×A_n)modX(A_1modX×A_2modX×A_3modX×\cdots×A_nmodX)modX(A1×A2×A3×⋯×An)modX(A1modX×A2modX×A3modX×⋯×AnmodX)modX
3.洛谷练习——P1032 字串变换.
题目描述 已知有两个字串AAABBB及一组字串变换的规则至多666个规则: A1−B1A_1-B_1A1−B1 A2−B2A_2-B_2A2−B2 规则的含义为在AAA中的子串A1A_1A1可以变换成B1B_1B1A2A_2A2可以变换成B2B_2B2 输入格式 AAA BBB A1A_1A1 B1B_1B1 A2A_2A2 B2B_2B2 ............... 所有字符串长度的上限为202020。 输出格式 若在101010步包含101010步以内能将AAA变换为BBB则输出最少的变换步数否则输出NO ANSWER! 分析过程 这里明显是个宽搜题BFS如果拿到手里不知道怎么运用宽搜字符串。这题的难点①字符串宽搜如何更新。②优化用到mapstring,intmapstring,intmapstring,int 代码
#includeiostream
#includequeue
#includemap
#includestring
using namespace std;
int main()
{mapstring, intmp;string a, b;cin a b;string x[7], y[7];int n 0;while (cin x[n] y[n])n;queuestringQ;queueints;Q.push(a);//记录字符串s.push(0);//记录布数while (!Q.empty()){if (Q.front() b)//如果得到结果直接返回{cout s.front() endl;return 0;}if (s.front() 10){cout NO ANSWER! endl;return 0;}string t Q.front();if (mp.count(t)){Q.pop();s.pop();continue;}mp[t] 1;//将字符串映射到mp中的一个位置for (int i 0; i n; i){int p 0;while (t.find(x[i], p) ! -1)//查找成功返回位置否则返回-1{p t.find(x[i], p);//在t字符串中从p这个位置开始查找x[i]字符串Q.push(t.substr(0, p) y[i] t.substr(p x[i].length()));//字符串替换substr(0,p)将字符串中0-p的字符取出来s.push(s.front() 1);p;}}Q.pop();s.pop();}cout NO ANSWER! endl;return 0;
}总结 本题是我参考b站一个up主的解答。用mapmapmap这个函数作为原来的visitvisitvisit记录已经遍历过的点优化BFS而且学到了字符串的拼接更新。
4.洛谷练习——P1012 拼数
题目描述 设有nnn个正整数(n≤20)(n≤20)(n≤20)将它们联接成一排组成一个最大的多位整数。 例如n3n3n3时333个整数13,312,34313,312,34313,312,343联接成的最大整数为343312133433121334331213 又如n4n4n4时444个整数7,13,4,2467,13,4,2467,13,4,246联接成的最大整数为742461374246137424613 输入格式 第一行一个正整数nnn。 第二行nnn个正整数。 输出格式 一个正整数表示最大的整数。 分析过程 刚拿到这个题的时候感觉简单啊不就是个字符串比较最大的放最前面如果是000不输出就ok了?其实这题远远没有那么容易如果不是测试点我可能跟不想不到哪里出了问题。比如a32b321a32b321a32b321明显323213213232321321323232132132但是如果你按字符串的比较方法得到的结果确实后者所以我们不是比较字符串aaa和bbb的大小而是比较字符串ababab和bababa的大小 代码
#includeiostream
#includecstring
using namespace std;
int main()
{string arr[21];int n;cin n;for (int i 1; i n; i)cin arr[i];for (int i 1; i n - 1; i){for (int j 1; j n - i; j){if ((arr[j]arr[j1])(arr[j1]arr[j])){string p arr[j];arr[j] arr[j 1];arr[j 1] p;}}}if (arr[1] 0)//注意如果为0最终结果只需要输出一个0cout 0 endl;else{for (int i 1; i n; i)cout arr[i];}return 0;
}总结 这一题我自己先用字符串比较硬凑条件怼出来了我看了别的神犇的方法恍然大悟柳暗花明。为什么我想不到呢可能见得多了就知道了所以记录下来方便复习
5.洛谷练习——P1538 迎春舞会之数字舞蹈
此代码来自b站up主——嘉持
#includeiostream
#includestring
#includealgorithm
using namespace std;
int n, h, w;
string a;
string c[5] {- - - - - - - - ,
| | | | | | | | | | | | | | ,- - - - - - - ,
| | | | | | | | | | | | | ,- - - - - - - ,
};
char f(int x, int y)
{if (x 1)x max(x - n 1, 1);if (x 3)x max(x - n 1, 3);int m y / (n 3);y % (n3);if (y 0)y max(y - n 1, 1);return c[x][y (a[m] - 0)* 4];
}
int main()
{cin n a;h 2 * n 3;w (n 3) * (a.length());for (int i 0; i h; i){for (int j 0; j w; j)cout f(i, j);cout endl;}return 0;
}总结 这题把我心态搞崩了啥也不想写看上方老师的视频讲解吧。
2020/3/1第二次刷洛谷前几天学习数据结构算法的知识比如dfsbfs然后又刷了几十道题不过现在有刷不懂了又开始看算法hhh
