|
快速幂： 通常求a的b次方的取模m结果 降幂（降低循环次数） 2^1000 ->4^500 ->16^250 ->256^125 125/2不能整除 ->256*256^124 -> long long ksm(long long a,long long b,long long m){ long long ans=1; while(b){ if(b%2){ ans*=a; ans%=m; } b/=2; a=a*a; a%=m; } return ans; } 快速幂模板题：(1616) 差分数组： 频繁更改范围内的数据，减少操作次数 O(n)->O(1) int a[100]={}; int b[100]={}; 每次在x-y下标之间增加k或减少k while(n--){ cin>>x>>y>>k; //记录变化 b[x]+=k; b[y+1]-=k; } 将a数组和b数组合并就是更新后的数据 int sum=0; for(int i=0;i<100;i++){ sum+=b[i]; a[i]+=sum; } 二分法：在有序的数据范围内寻找正确答案，每次找中间，数据范围减半 O(logn) 二分查找：范围内找唯一解 int l=0,r=n; while(l<r){ int mid=(l+r)/2; if(mid>x) r=mid-1; else if(mid<x) l=mid+1; else{ 找到答案 break; } } 二分答案：在有效解范围内找最优解 bool pd(int mid){ } int l=0,r=L; while(l<r){ int mid=(l+r)/2; if(pd(mid)) 更改数据范围 else 更改数据范围 } 二分答案要注意死循环的情况 二分答案模板题（1890） 高精加 字符串存数据 倒序（对齐个位） 加法进位 结果：倒序+去除前导零 高精减 字符串存数据 倒序（对齐个位） 减法借位 结果：倒序+去除前导零 a-b->-(b-a) 判断两个字符串的数字属性谁大谁小 string a="12345",b="999"; string sign=""; //a-b if(a.size()<b.size()||a.size()==b.size()&&a<b){ swap(a,b); sign="-"; } 高精乘 字符串存数据 倒序（对齐个位） 乘法进位+累加进位 结果：倒序+去除前导零 a*b的结果长度=a.size()+b.size() 对于结果数组 c[i+j]=a[i]*b[j]+jw; 高精除（除低精） 字符串存数据 不需要倒序 除法过程中，余数需要*10拼接 答案：有商有余数 深度优先搜索：一条路走到底【递归，栈】 用于判断是否有解 int dir[][2];//方向数组，通常用x和y的+1 -1 表示 int vis[][];//记录是否已访问【回溯】 void dfs(当前位置){ 标记已走过位置 探索所有能走的方向 能走就走 } void dfs(int x,int y){ vis[x][y]=1; for(int i=0;i<4;i++){ int xx=dir[i][0]+x; int yy=dir[i][1]+y; if(xx>=0&&xx<n&&yy>=0&&yy<n){//有效范围 if(没被访问过||访问过的数据次于当前数据){ dfs(xx,yy); } } } } 深度优先模板题（1212） 广度优先搜索：同时分身走其他各个方向【队列】 用于寻找最优解 【结构体】 void bfs(起点){ 创建队列，起点入队 while(队不为空){ 获取对头，出队 通过对头记录其他路线 } } 答案类型 bfs(int x,int y){ queue<node> q; q.push((node){x,y}); while(!q.empty()){ node u=q.front();q.pop(); if(u是终点) { return 答案; } for(所有连接的方向){ //筛选最优方案，剔除次级方案 q.push(方向入队); } } } 广度优先模板题（1416） struct node{ int x,y; bool m;//魔法 int g;//金币 int c;//颜色 node(int xx,int yy,bool mm,int gg,int cc){ x=xx;y=yy;m=mm;g=gg;c=cc; } }; ming[][]={}; bfs(int x,int y){ queue<node> q; q.push(new node(x,y,1,0,mg[x][y])); while(!q.empty()){ node u=q.front();q.pop(); if(u是终点) 更新/return @; for(方向){ if(没出界){ if(能走){ if(同色&&优于原方案) 入队 else if(异色){ if(用魔法&&优于原方案) 入队 else if(不用魔法&&优于原方案) 入队 } } } } } } fill(地址开头，地址结尾+1，数据) memset(地址开头，数据，sizeof(变量)) 按字节 int a[10]; memset(a,0,sizeof(a)); 容器库：https://www.apiref.com/cpp-zh/cpp/container.html bfs，dijstra，floyd，贪心，动归 栈stack、队列queue、优先队列priority_queue stack push pop top queue push pop front priority_queue push pop top 有固定的进出逻辑 字典map，集合set，可重复字典multimap，可重复集合multiset 自动有序，数据存储顺序与存入的先后顺序无关 数组类模版array，双向队列deque，向量vector，单向链表forward_list，双向链表list 哈希 kmp trie字典树 ac自动机 (责任编辑：admin) |