素数筛与欧拉筛
朴素算法优化方法1.只判断奇数2.因子是成对出现，并且分布在 sqrt (n) 两侧的 所以只判断到n的根
[素数筛] [c++]123456789101112131415int IsPrime(int n){ int i; if(n<2||(n!=2&&n%2==0)) return 0; else //n都是奇数 { for(i=3;i*i<=n;i+=2) { if(n%i==0) return 0; } return 1; }}
显然如此优化依旧不够
埃氏筛1.0便是数组a储存已经筛选过的素数 数组b包含范围内所有数字，用来标记是否被访问过 从2开始循环 对其进行倍增操作优化方法1.易知很多倍增其实重复了 浪费了时间空间 优化方法便是只对素数进行倍增2.倍增从i开始 而不是从2开始 减少一半计算量
[素数筛] [c++]12345678910 ...
链表
head 表示头结点的下标e[i] 表示节点i的值ne[i] 表示节点i的next指针是多少 (下一个节点的下标)idx 存储当前已经用到了哪一个点
[数组模拟单链表] [c++]1234567891011121314151617181920212223242526272829303132333435#include<bits/stdc++.h>using namespace std;const int N=100010;int head,e[N],ne[N],idx;void init() //初始化{ head=-1; idx=0;}void add_to_head(int x) //将x插到头结点{ e[idx]=x;//这个结点赋值 ne[idx]=head;//新头结点的下一个结点是之前的头结点 head=idx; head变成新的头结点的下标 idx++;}void add(int k,int x)//将x插到下标为k的位置的后面 注意不是第k个点 是下标为k的点{ e[ ...
小技巧
cin，cout之所以效率低，是因为先把要输出的东西存入缓冲区，再输出，导致效率降低.在调用下列代码后，效率与scanf与printf相差无几,但是不能再用scanf了
[tips] [c++]12ios::sync_with_stdio(false);cin.tie(0);
多层循环提高效率
[tips] [c++]1register int
auto的原理就是根据后面的值，来自己推测前面的类型是什么针对迭代器 可以如下操作
[tips] [c++]12345678vector<string> ve;ve.push_back(1);ve.push_back(2);ve.push_back(3);for(auto i:ve) cout<<i<<endl;
快读 字符串输入 再转为数字 超级快
[int快读] [c++]1234567891011121314151617int read(){ int s=0,w=1; char ch=getchar(); if(ch=='-') //先判断是不是个负 ...
前缀和与差分
例 输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l, r。对于每个询问，输出原序列中从第l个数到第r个数的和。如果暴力遍历，时间复杂度为O(m*n) 可能超时则采用前缀和算法并查询a[N]记得是从1开始,a[0]=0, 因为如果是求（1，r) 需要sum[r]-sum[0]
[前缀和] [c++]1234567891011const int N = 1e5 + 10;int sum[N], a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i];for(int i = 1;i <= n; i++){ sum[i] = sum[i - 1] + a[i]; //前缀和的初始化}while(m--){ cin>>l>>r; cout<<sum[r] - sum[l - 1];}
输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩 ...
stl-map
map是c++的一个关联容器 提供一对一的映射第一个称为关键字key（有唯一性） 第二个称为关键字的值value和python里的字典很像
[map] [c++]12345678910111213141516171819202122232425262728293031323334353637如你想建立一个姓名-电话对应关系定义一个map对象map<string,string>friends;cout<<friends.find("jack"); 找到jack的对应号码cout<<friedns.find(123); 找123对应的姓名 找不到返回null用insert函数插入friends.insert(pair<string, string>("judy", "789"));遍历 不能写小于for(iter=friends.begin();iter!=friends.end();iter++){ cout<<iter->first<<&q ...
stl-其它
[stl] [c++]123456789101112131415161718192021222324252627282930313233343536373839vector<int> a({1,2,3,4,5});动态数组array.pop_back(); //删除向量的最后一个元素array.push_back(a); //尾部插入数字aarray.insert(array.begin()+i,a); //在第i+1个元素前面插入a;array.erase(array.begin()+2); //删除第3个元素array.erase(array.begin()+i,array.end()+j); //删除区间[i,j-1],区间从0开始array.clear();array.back();//返回最后一个元素array.front(); //返回第一个元素reverse(a.begin().a.end()); 翻转 必须用迭代器 数组不用 注意是都是前闭后开 end()是back()的后一位必须相同元素排一起才能去重 返回值是去重后元素的下一个位置in ...
