Xiaruize's Blog

二分 Stop learning useless algorithms, go and solve some problems, learn how to use binary search. —— Um_nik 所以，let’s learn how to use binary search。。。 让我们先看一道题： 如果让你在1~100中猜一个数，每次你猜完我会告诉你大了或小了，你会先猜多少？50 大了小了对了这时你相当于得到了一个新的范围1~49这时你相当于得到了一个新的范围51~100输出答案 其实，你刚刚已经完成了一部分二分，然后就是代码实现部分 Code: 1234567891011121314151617//查找x的位置int find(int x){ int l = 1 ,r = n + 1; while(l < r) { int mid = (l + r)/ 2; //防止溢出 if(a[mid] >= x) r = mid; //小于中间的数，在左区间 ...

Prime and GCD 素数 素数是什么？见小学数学书 如何判断一个数是否是素数？ 对于任何正整数，因子总是成对出现。所以只要要判断的数nnn在222~n\sqrt{n}n​之间没有因子，nnn就是质数 123456789bool isPrime(int a){ if (a < 2) return 0; for (int i = 2; i * i <= a; ++i) if (a % i == 0) return 0; return 1;} GCD GCD(Greatest Common Divisor) 最大公约数 其实C++有内置的GCD函数，但是因为某种原因，建议不要使用! 再一次翻一翻你的小学数学课本，老师肯定教过你辗转相除求最大公约数 好习惯，使用前先证明： 证明 设gcd⁡(x,y)=d\gcd(x,y)=dgcd(x,y)=d,则此时x=k1⋅d,y=k2⋅dx=k_1\cdot d,y=k_2\cdo ...

STL和其他的一些东西 尽管巨佬都说：“STL常数大，你手写它不香吗？” 但是，STL确实很香。。。 queue 首先，查一下词典 所以，其实就是一个先进先出的容器 123456queue<变量名> q; //存的变量可以是int,char等，也可以是struct等q.front(); //返回队首元素的值q.pop(); //弹出队首元素q.size() //返回队列的大小q.push(x) //把x压到队尾q.empty() //返回1为空，0为有元素 用处见BFS stack 还是查一下字典 可以发现，stack是一个后进先出的容器 123456stack<变量名> st; //存的变量可以是int,char等，也可以是struct等st.top(); //返回栈顶元素的值st.pop(); //弹出栈顶元素st.size() //返回栈的大小st.push(x) //把x压到栈顶st.empty() //返回1为空，0为有元素 vector vector，可以当数组用，但又比数组高级！！！当然会更慢qwq 12345678910111213 ...