素数筛快速幂
素数筛快速幂 素数筛埃氏筛法—-求解n以内的素数个数1234567891011121314151617181920int prime[MAXN]; //第i个素数的值bool is_prime[MAXN]; //is_prime[i]为true时表示i是素数//返回n以内素数的个数int solve(int n){ int p = 0; //代表素数个数 for(int i = 2; i <= n; i++) is_prime[i] = true; for(int i = 2; i <= n; i++) { if(is_prime[i]) { prime[p++] = i; //每有一个素数，p就++，然后prime存的就是素数的值，然后进行筛选 for(int j = i * i; j <= n; j += i) is_prime[j] = false; } &...
欧几里得
gcd, lcm, exgcd 欧几里得—最大公约数gcd（a, b) = gcd(b, a mod b)123456int gcd(int a, int b){ if(b == 0) return a; return gcd(b, a % )b;} 一波应用：线段上格点个数—-挑战编程—-欧几里得 algorithm库的std::_gcd函数123456789101112#include <iostream>#include <algorithm>using namespace std;int main(){ int a = 8; int b = 12; cout <<__gcd(a, b); //两个'_' return 0;}//out：4 //g++-4.8 最小公倍数(LCM)和最大公约数(GCD)lcm(a, b) = (a*b)/gcd(a,b) 扩展欧几里得基本算法：对于不完全为 0 的非负整数 a，b，gcd（...
牛客--applese的回文串
判断一个字符串在任意位置(包括最前面和最后面)插入一个字符后能不能构成一个回文串 Applese 的回文串 解析 TAG：思维，想法 可以认为插入和删除是等价的操作。想到这一点，这题就会好做很多。如果这个串本身就是回文串，答案一定是Yes。否则我们只需要考虑串中对称的位置不相等的两个字符，分别尝试把它们删掉后判断一下是不是回文的就行了。 参考自：https://ac.nowcoder.com/discuss/153012?type=101 123456789101112131415161718192021222324252627282930313233343536373839404142434445/*提交时间：2019-01-30 12:03:32 语言：C++ 代码长度：695 运行时间： 4 ms 占用内存：996K 运行状态：答案正确*/#include <iostream>#include <string>using namespace std;//判断对称位置的字符是否相等，相等返回-1，不是返回不相等的位置int check(string...
日常wa于模拟题
牛客—Applese 走迷宫 模拟题，就是给出个m×n矩阵，从(0,0)开始，输出一种方案能够不重复得走完所有的点并且回到起点，没有的话输出-1。 掉了两个坑： 特殊情况：1行2列或2行1列，没有考虑这个也可以回到原点，以为只要是m==1||n==1就不能走了 没有考虑到别的走法，以至于以为m%2==0就不能走了 有一个还需要的优化的地方就是代码逻辑。 解析 主要是两种情况，当n%2==0时，可以按照下面这种走法输出方案 当n%2!=0&&m%2==0时，可以按照下面这种走法输出方案 其他情况都没有方案，输出-1 代码逻辑方面，有一部分都是一样的输出，所以可重复利用，如红色部分。所以可精简代码。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071/*提交时间：2019-01-29 19:41:29 语言：C++ 代码长度：1360 运行时间...
平衡三进制
平衡三进制 平衡三进制—百度百科 一道简单平衡三进制题目: 牛客—处女座的砝码 参考:https://blog.csdn.net/Sherry_Yue/article/details/86658533 123456789101112131415161718//submit time:2019-01-28 22:26:07#include<iostream> using namespace std; int main() { long double n, res = 0, cnt = 0; cin >> n; while(cnt < n) { cnt = 3 * cnt + 1; res++; } cout << res << endl; return 0;} long long与 long double 按道理来说，long double 比double和long long要表示的范围要大，但是依据情况而定...
博弈论
博弈论 博弈论两道题牛客—处女座和小姐姐分析： 作者：儒生雄才1链接：https://ac.nowcoder.com/discuss/152781?type=101&order=0&pos=1&page=1来源：牛客网 显然处女座十分牛逼，因此输出“cnznb”即可 咳咳……至于正确的做法。首先因为每次在右边砍掉一个头就相当于在左边会多出来一个头，所以可以把每𝑛次操作看作一轮，每轮的操作都是从01串右边向左边对每个位置在原位依次进行操作。我们考虑这种做法，从右到左我们首先看到1就把他变成0，0的话让他随机，直到第一次出现有0变成了1的情况。如果没有出现这种情况那么这个串已经符合了要求，如果有0变成1发生，那么在这之后的1我们都继续变成1。这样一轮结束之后，这个01串所表示的二进制数的的大小一定是严格增加了的（因为虽然你可能把一些1变成了0但是有一个高位的0变成了1）而这个二进制数的大小是有限的，因此在有限步内一定可以把这串数变成全0串。 HDU6312—GAME参考： https://blog.csdn.net/qq_37025443/article...
文件测试testCast
采用文件读写办法进行样例测试以及生成各种测试用例 写OJ调试的时候如果输入数据比较多，每次调试手动输入会很麻烦，把测试数据写到文件里用文件输入会比较方便。本次主要用freopen进行文件读取 freopen参考 https://blog.csdn.net/u013480600/article/details/18372341 头文件首先必须知道调取freopen必须用到头文件cstdio 或者 stdio.h 函数声明1234FILE * freopen ( const char * filename, const char * mode, FILE * stream );//filename: 要打开的文件名//mode: 文件打开的模式，和fopen中的模式(r/w)相同//stream: 文件指针，通常使用标准流文件(stdin/stdout/stderr) 使用方法因为文件指针使用的是标准流文件，因此我们可以不定义文件指针 使用freopen()函数以只读方式r(read)打开测试样例文件in.txt 1freopen("in.txt", &qu...
n1配置
某讯日常倒闭 清空data1mkfs.ext4 /dev/data 开启WiFi1modprobe dhd && echo dhd >> /etc/modules 配置Sakura Frp配置frp内网穿透，今天卡在开机自启这里了，后来查了下linux启动顺序才知道错处 参考： centos 6和centos 7启动顺序 linux添加开机自启动脚本示例详解‘ Linux 将 Sakura Frp 设置为服务，开机自动启动 1. 获取Sakura Frp arm版并且解压 12wget https://s1.tcotp.cn/cdn/SakuraFrpClient-2.3/Sakura_frpc_linux_arm.tar.gz tar -xvf Sakura_frpc_linux_arm.tar.gz 2. 在/etc/init.d目录下放个启动无线网卡的脚本dhd并且赋予权限 1vim /etc/init.d/dhd dhd内容： 12#!/bin/shmodprobe dhd 如果开机不能启动话ln -s /etc/init.d/dhd /et...
大数模板
大数四则运算模板 参考： https://www.xuebuyuan.com/1860973.html 大数加法1234567891011121314151617181920212223242526272829303132#include <iostream>#include <string>using namespace std;const int MAXN = 1e6;int ia[MAXN];int ib[MAXN];int ans[MAXN];int main(){ string sa, sb; cin >> sa >> sb; int la = sa.size(); int lb = sb.size(); int ml = la > lb ? la : lb; for(int i = 0; i < la; i++) ia[i] = sa[la - i - 1] - '0'; for(int i = 0; i < lb...
字符串常见算法--kmp，E-kmp，manacher，ac自动机
kmp，E-kmp，manacher，ac自动机 KMPhttp://t.cn/EZlzRyg Manacher—最长回文串O(N)关于求最长回文串办法四种方法求最长回文串 但是上面几种都不是最快的，最快的是Manacher（马拉车）算法，算法复杂度是O(N) Manacherhttps://www.cnblogs.com/grandyang/p/4475985.html https://www.cnblogs.com/z360/p/6375514.html https://segmentfault.com/a/1190000008484167 https://www.bilibili.com/video/av4829276?from=search&seid=9253656566579281943 https://www.bilibili.com/video/av20495920?from=search&seid=9253656566579281943 模板题—HDU-3068(最长回文)注意，此题别的算法O(NlogN)都会超时，所以只能用马拉车的O(N)算...
