蓝桥杯算法备考

news/2024/11/8 12:12:22/

对象排序

class PII implements Comparable<PII>{int x;int y;public PII(int x,int y){this.x=x;this.y=y;}// 如果用到对象排序的话public int compareTo(PII o){return Integer.compare(x,o.x);//从小到大排序// return Integer compare(o.x,x); 从大到小排序}
}public class Main{static PII[] p=new PII[100010];public static void main(String[] args)throws IOException{BufferedReader in=new BufferedReader(new InputStreamReader(System.in));int n=Integer.parseInt(in.readLine());for(int i=0;i<n;i++){String[] strs=in.readLine().split(" ");int x=Integer.parseInt(strs[0]);int y=Integer.parseInt(strs[1]);p[i]=new PII(x,y);}Arrays.sort(p);}
}

归并排序

代码模板

void merge_sort(int q[],int l,int r){if(l>=r)return;int mid=l+r>>1;merge_sort(q,l,mid);merge_sort(q,mid+1,r);int k=0,i=l,j=mid+1;while(i<=mid && j<=r)if(q[i]<=q[j])tmp[k++]=q[i++]else tmp[k++]=q[j++];while(i<=mid) tmp[k++]=q[i++];while(j<=r) tmp[k++]=q[j++];for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
}

应用场景

  • 求逆序对的数量
    // 当j>i且q[i]>a[j]时
res+=mid-i+1;

整数二分

代码模板

bool check(int x){} //检查x是否满足某种性质int bsearch_1(int l,int r){while(l<r){int mid=l+r>>1;if(check(mid))r=mid;else l=mid+1;}return l;
}int bsearch_2(int l,int r){while(l<r){int mid=l+r+1>>1;if(check(mid))l=mid;else r=mid-1;}return l;
}

应用场景

  • 对有序数列中快速查找某个满足条件的数

浮点数二分

代码模板

bool check(double x){} //检查x是否满足某种性质double bsearch_3(double l,double r){const double eps=1e-6;while(r-l>eps){double mid=(l+r)/2;if(check(mid))r=mid;else l=mid;}return l;
}

应用场景

  • 从数据范围中找到某个浮点数，比如数的开三次方，开四次方

高精度

java版本高精度计算

import java.io.*;
import java.math.*;public class Main{public static void main(String[] args)throws IOException{BufferedReader in=new BufferedReader(new InputStreamReader(System.in));String str=in.readLine();BigInteger a=new BigInteger(str);str=in.readLine();BigInteger b=new BigInteger(str);// 高精度加法System.out.println(a.add(b));// 高精度减法System.out.println(a.subtract(b));// 高精度乘法System.out.println(a.multiply(b));// 高精度除法System.out.println(a.divide(b));// 其他常用方法// gcd最大公约数// max,min,mod,pow,abs,sqrt}
}

应用场景

看题目要求随机应变

一维前缀和

s[i]=s[i-1]+a[i]
s[r]-s[l-1]=a[l]+...+a[r]

一维差分

B[l]+=c;B[r+1]-=c;
// 然后对B数组求和

二维前缀和

s[i,j] = 第i行第j列格子左上部分所有元素的和
以(x1,y1)为左上角，（x2,y2）为右下角的子矩阵的和为：
s[x2,y2] - s[x2-1,y2] - s[x2,y1-1] + s[x1-1,y1-1]

二维差分

给以（x1,y1）为左上角，（x2,y2）为右下角的子矩阵中的所有元素加上c:
s[x1,y1] += c, s[x2+1,y1] -= c,s[x1,y2+1] -= c, s[x2+1,y2+1] += c
然后对s数组求和就行

应用场景

适用于在某个矩阵区间加上某个值后，求每个位置的值

位运算

求n的第K位数字： n>>k&1
返回n的最后一位1：lowbit(n) = n & -n
import java.io.*;public class Main{public static void main(String[] args)throws IOException{BufferedReader in=new BufferedReader(new InputStreamReader(System.in));int n=Integer.parseInt(in.readLine());System.out.println(lowbit(n));}static int lowbit(int x) {return x & -x;}
}

区间合并

import java.io.*;
import java.util.*;class PII implements Comparable<PII>{int l;int r;public PII(int l,int r) {this.l=l;this.r=r;}public int compareTo(PII o) {if(l>o.l)return 1;else if(l==o.l&&r>o.r)return 1;else return -1;}
}public class Main{static int N=100010;static PII[] p=new PII[N];static int n;public static void main(String[] args)throws IOException{BufferedReader in=new BufferedReader(new InputStreamReader(System.in));n=Integer.parseInt(in.readLine());String[] strs;for(int i=0;i<n;i++) {strs=in.readLine().split(" ");int l=Integer.parseInt(strs[0]);int r=Integer.parseInt(strs[1]);p[i]=new PII(l,r);}merge();}static void merge() {List<PII> res=new ArrayList<>();Arrays.sort(p,1,n);int st = (int)-2e9;int ed = (int)-2e9;for(int i=0;i<n;i++) {if(ed<p[i].l) {if(st!=-2e9)res.add(new PII(st,ed));st=p[i].l;ed=p[i].r;}else ed=Math.max(ed,p[i].r);}if(st!=-2e9)res.add(new PII(st,ed));System.out.println(res.size());}
}

单链表

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head,e[N],ne[N],idx;//初始化
void init(){head=-1;idx=0;
}//在链表头插入一个数a
void insert(){e[idx]=a,ne[idx]=head,head=idx++;
}//将头结点删除，需要保证头结点存在
void remove(){head=ne[head];
}

栈

// tt表示栈顶
int stk[N],tt=0;//向栈顶插入一个数
stk[++tt]=x;// 从栈顶弹出一个数
tt--;//栈顶的值
stk[tt];//判断栈是否为空,如果tt>0，则表示不为空
if(tt>0){}

队列

// hh表示对头，tt表示队尾
int q[N],hh=0,tt=-1;//向队尾插入一个数
q[++tt]=x;//从队头弹出一个数
hh++;//判断队列是否为空，如果hh<=tt,则表示不为空
if(hh<=tt){}

单调栈

// 常见模型：找出每个数左边离它最近的比它大/小的数
int tt=0;
for(int i=1;i<=n;i++){while(tt && check(stk[tt],i))tt--;// while(tt && a[stk[tt]]>=a[i])tt--;stk[++tt]=i;
}

单调队列

// 常见模型：找出滑动窗口的最大值/最小值
int hh=0,tt=-1;
for(int i=0;i<n;i++){while(hh<=tt&&check_out(q[hh]))hh++;// 判断队头是否滑出窗口while(hh<=tt&&check(q[tt],i))tt--;q[++tt]=i;
}

import java.io.*;public class Main{static int N=1000010;static int[] a=new int[N];static int[] q=new int[N];public static void main(String[] args)throws IOException{BufferedReader in=new BufferedReader(new InputStreamReader(System.in));String[] strs=in.readLine().split(" ");int n=Integer.parseInt(strs[0]);int k=Integer.parseInt(strs[1]);strs=in.readLine().split(" ");for(int i=0;i<n;i++){a[i]=Integer.parseInt(strs[i]);}// 求滑动窗口最小值int hh=0,tt=-1;for(int i=0;i<n;i++){while(hh<=tt&&q[hh]<i-k+1)hh++;while(hh<=tt&&a[q[tt]]>=a[i])tt--;q[++tt]=i;if(i>=k-1)System.out.print(a[q[hh]]+" ");}System.out.println();// 求滑动窗口最大值hh=0;tt=-1;for(int i=0;i<n;i++){while(hh<=tt&&q[hh]<i-k+1)hh++;while(hh<=tt&&a[q[tt]]<=a[i])tt--;q[++tt]=i;if(i>=k-1)System.out.print(a[q[hh]]+" ");}}
}

KMP

// s[]是长文本,p[]是模式串，n是s的长度，m是p的长度// 求模式串的Next数组：
for(int i=2,j=0;i<=m;i++){while(j && p[i]!=p[j+1]) j=ne[j];if(p[i]==p[j+1])j++;ne[i]=j;
}// 匹配
for(int i=1,j=0;i<=n;i++){while(j && s[i] != p[j+1]) j=ne[j];if(s[i] == p[j+1])j++;if(j==m){j=ne[j];}
}

应用场景

  • 字符串匹配

Tire树

// 插入一个字符串
import java.io.*;public class Main{static int N=100010;static int[][] son=new int[N][26];static int[] cnt=new int[N];// 0号点既是根结点，又是空节点// son[][]存储树中每个节点的子节点// cnt[]存储以每个节点结尾的单词数量static int idx;public static void main(String[] args)throws IOException{BufferedReader in=new BufferedReader(new InputStreamReader(System.in));int n=Integer.parseInt(in.readLine());String[] strs;for(int i=0;i<n;i++) {strs=in.readLine().split(" ");char op=strs[0].charAt(0);String str=strs[1];if(op=='I') {insert(str);}else {System.out.println(query(str));}}}// 插入一个字符串static void insert(String str) {int p=0;for(int i=0;i<str.length();i++) {int u=str.charAt(i)-'a';if(son[p][u]==0)son[p][u]=++idx;p=son[p][u];}cnt[p]++;}// 查询字符串出现的次数static int query(String str) {int p=0;for(int i=0;i<str.length();i++) {int u=str.charAt(i)-'a';if(son[p][u]==0)return 0;p=son[p][u];}return cnt[p];}
}

应用场景

  • 查询字符串出现过多少次

并查集

(1)朴素并查集

int p[N]; // 存储每个点的祖宗节点// 返回x的祖宗节点
int find(int x){if(p[x]!=x)p[x]=find(p[x]);return p[x];
}// 初始化，假定节点编号时1~n
for(int i=1;i<=n;i++) p[i]=i;// 合并a和b所在的两个集合
p[find(a)]=find(b);

(2)维护size的并查集

int p[N],size[N];
// p[]存储每个点的祖宗节点，size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量// 返回x的祖宗节点
int find(int x){if(p[x]!=x)p[x]=find(p[x]);return p[x];
}// 初始化，假定节点编号是1~n
for(int i=1;i<=n;i++){p[i]=i;size[i]=1;
}// 合并a和b所在的两个集合
size[find(b)] += size[find(a)];
p[find(a)] =find(b);

(3) 维护到祖宗节点距离的并查集

int p[N],d[N];
// p[]存储每个点的祖宗节点，d[x]存储x到p[x]的距离// 返回x的祖宗节点
int find(int x){if(p[x]!=x){int u=find(p[x]);d[x]+=d[p[x]];p[x]=u;}return p[x];
}// 初始化，假定节点编号是1~n
for(int i=1;i<=n;i++){p[i]=i;d[i]=0;
}// 合并a和b所在的集合
p[find(a)]=find(b);
d[find(a)]=distance; //根据具体问题，初始化find(a)的偏移量

堆

java用优先队列来模拟堆

import java.io.*;
import java.util.*;public class Main{public static void main(String[] args)throws IOException{BufferedReader in=new BufferedReader(new InputStreamReader(System.in));Queue<Integer> q=new PriorityQueue<>();}
}

哈希

java HashSet

import java.io.*;
import java.util.*;class PII{int x;int y;public PII(int x,int y) {this.x=x;this.y=y;}
}public class Main{public static void main(String[] args)throws IOException{BufferedReader in=new BufferedReader(new InputStreamReader(System.in));HashSet<PII> hs=new HashSet<PII>();int n=Integer.parseInt(in.readLine());String[] strs;for(int i=0;i<n;i++) {strs=in.readLine().split(" ");int x=Integer.parseInt(strs[0]);int y=Integer.parseInt(strs[1]);hs.add(new PII(x,y));}for(PII p:hs) {System.out.println(p.x+" "+p.y);}}
}

邻接表

import java.io.*;
import java.util.*;public class Main{static int N=100010;static int[] head=new int[N];static int[] e=new int[N];static int[] ne=new int[N];static int[] w=new int[N];static int idx;static int m;public static void main(String[] args)throws IOException{BufferedReader in=new BufferedReader(new InputStreamReader(System.in));m=Integer.parseInt(in.readLine());String[] strs;Arrays.fill(head, -1);for(int i=0;i<m;i++) {strs=in.readLine().split(" ");int a=Integer.parseInt(strs[0]);int b=Integer.parseInt(strs[1]);int c=Integer.parseInt(strs[2]);add(a,b,c);}}static void add(int a,int b,int c) {e[idx]=b;w[idx]=c;ne[idx]=head[a];head[a]=idx++;}
}

树与图的遍历

深度优先遍历

int dfs(int u){st[u]=true;for(int i=h[u];i!=-1;i=ne[i]){int j=ne[i];if(!st[j])dfs(j);}
}

宽度优先遍历

queue<int> q;
st[1]=true; //表示1号点已经被遍历过
q.push(1);while(q.size()){int t=q.front();q.pop();for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(!st[j]){st[j]=true; //表示点j已经被遍历过q.push(j);}}
}

拓扑排序

bool topsort(){int hh=0,tt=-1;//d[i]存储点i的入度for(int i=1;i<=n;i++){if(d[i]==0){q[++tt]=i;}}while(hh<=tt){int t=q[hh++];for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(--d[j]==0)q[++tt]=j;}}return tt==n-1;
}

朴素dijkstra

int g[N][N]; //存储每条边
int dist[N]; //存储1号点到每个点的最短距离
bool st[N]; //存储每个点的最短路时候已经确定// 求1号点到n号点的最短路，如果不存在就返回-1
int dijkstra(){memset(dist,0x3f,sizeof dist);dist[1]=0;for(int i=0;i<n-1;i++){int t=-1; // 在还未确认最短路的点中，寻找距离最小的点for(int j=1;j<=n;j++){if(!st[j]&&(t==-1||dist[t]>dist[j])t=j;}// 用t更新其他点的距离for(int j=1;j<=n;j++){dist[j]=min(dist[j],dist[t]+g[t][j]);}st[t]=true;}if(dist[n]==0x3f3f3f3f) return -1;return dist[n];
}

堆优化版dijkstra

typedef pair<int,int> PII;int n; // 点的数量
int h[N],w[N],e[N],ne[N],idx;  // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra(){memset(dist,0x3f,sizeof dist);dist[1]=0;priority_queue<PII,vector<PII>,greater<PII>> heap;heap.push({0,1}) //first存储距离，second存储节点编号while(heap.size()){auto t=heap.top();heap.pop();int ver = t.second,distance=t.first;if(st[ver]) continue;st[ver]=true;for(int i=h[ver];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>distance+w[i]){dist[j]=distance+w[i];heap.push({dist[j],j});}}}if(dist[n]==0x3f3f3f3f) return -1;return dist[n];
}

spfa求最短路

int n; // 总点数
int h[N],w[N],e[N],ne[N],idx; // 邻接表存储所有边
int dist[N],cnt[N]; // 存储每个点到1号点的最短距离
bool st[N]; //存储每个点是否在队列中// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa(){memset(dist,0x3f,sizeof dist);dist[1]=0;queue<int> q;q.push(1);st[1]=true;while(q.size()){auto t=q.front();q.pop();st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];if(!st[j]){ // 如果队列中已存在j,则不需要将j重复插入q.push(j);st[j]=true;}}}}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}

spfa判断负环

int n; // 总点数
int h[N],w[N],e[N],ne[N],idx; // 邻接表存储所有边
int dist[N],cnt[N];  // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中// 如果存在负环，则返回true,否则返回false;
bool spfa(){// 不需要初始化dist数组// 原理：如果某条最短路径上有n个点(除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。queue<int> q;for(int i=1;i<=n;i++){q.push(i);st[i]=true;}while(q.size()){auto t=q.front();q.pop();st[t]=false;for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(dist[j]>dist[t]+w[i]){dist[j]=dist[t]+w[i];cnt[j]=cnt[t]+1;if(cnt[j]>=n) return ture; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环if(!st[j]){q.push(j);st[j]=true;}}}}return false;
}

floyd

多源最短路

初始化：for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==j) d[i][j]=0;else d[i][j]=INF;}}// 算法结束后，d[a][b]表示a到b的最短距离
void floyd(){for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}
}

朴素版prim算法

适用于点数较小的求生成树

int n; // n表示点数
int g[N][N]; // 邻接矩阵，存储所有边
int dist[N]; //存储其他点到当前最小生成树的距离
bool st[N]; //存储每个点是否已经在生成树中//如果图不连通，则返回INF(值是0x3f3f3f3f),否则返回最小生成树的树边权重之和
int prim(){memset(dist,0x3f,sizeof dist);int res=0;for(int i=0;i<n;i++){int t=-1;for(int j=1;j<=n;j++){if(!st[j]&&(t==-1 || dist[t]>dist[j])t=j;}if(i && dist[t] == INF) return INF;if(i) res += dist[t];st[t] = true;for(int j=1;j<=n;j++)dist[j]=min(dist[j],g[t][j]);}
}

Kruskal算法

适用于点数较大的求最小生成树

int n,m; // n是点数，m是边数
int p[N]; // 并查集的父节点数组class Edge Comparable<Edge>{  // 存储边int a;int b;int w;public Edge(int a,int b,int w){this.a=a;this.b=b;this.w=w;}public int compareTo(Edge o){return Integer.compare(w,o.w);}
}Edge[] edges=new Edge[M];int find(int x) //并查集核心操作
{if(p[x]!=x) p[x]=find(p[x]);return p[x];
}int kruskal(){Arrays.sort(edges,edges+m);for(int i=1;i<=n;i++) p[i]=i; //初始化并查集int res=0,cnt=0;for(int i=0;i<m;i++){int a=edgs[i].a,b=edges[i].b,w=edges[i].w;a=find(a);b=find(b);if(a!=b){p[a]=b;res+w;cnt++;}}if(cnt<n-1)return INF;return res;
}

染色法判别二分图

int n; // n表示点数
int h[N],e[M],ne[M],idx; // 邻接表存储图
int color[N]; //表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色// 参数： u表示当前节点，c表示当前点的颜色
bool dfs(int u,int c){color[u]=c;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(color[j] == -1){if(!dfs(j,!c)) return false;}else if(color[j] == c) return false;}return true;
}bool check(){memset(color,-1,sizeof color);bool flag=true;for(int i=1;i<=n;i++){if(color[i]==-1){if(!dfs(i,0)){flag=false;break;}}}return flag;
}

匈牙利算法

int n1,n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N],e[M],ne[M],idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过bool find(int x){for(int i=h[x];i!=-1;i=ne[i]){int j=e[i];if(!st[j]){st[j]=true;if(match[j]==0 || find(match[j])){match[j]=x;return true;}}}return false;
}// 求最大匹配数,依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res=0;
for(int i=1;i<=n1;i++){memset(st,false,sizeof st);if(find(i))res++;
}

试除法判定质数

bool is_prime(int x){if(x<2)return false;for(int i=2;i<=x/i;i++){if(x%i==0)return false;}return true;
}

试除法分解质因数

void divide(int x){for(int i=2;i<=x/i;i++){if(x%i==0){int s=0;while(x%i==0) x/=i,s++;System.out.println(i+" "+s);}}if(x>1)System.out.println(x+" "+1);
}

朴素筛法求素数

int primes[N],cnt; // primes[]存储所有素数
bool st[N];  // st[x]存储x是否被筛掉void get_primes(int n){for(int i=2;i<=n;i++){if(st[i])continue;primes[cnt++]=i;for(int j=i+i;j<=n;j+=i){st[j]=true;}}
}

线性筛法求素数

int primes[N],cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉void get_primes(int n){for(int i=2;i<=n;i++){if(!st[i])primes[cnt++]=i;for(int j=0;primes[j]<=n/i;j++){st[primes[j]*i]=true;if(i%primes[j]==0)break;}}
}

试除法求所有约数

vector<int> get_divisors(int x){vector<int> res;for(int i=1;i<=x/i;i++){if(x%i==0){res.push_back(i);if(i!=x/i)res.push_back(x/i);}}sort(res.begin(),res.end());return res;
}

约数个数和约数之和

如果 N = p 1 c 1 ∗ p 2 c 2 ∗ . . . ∗ p k c k 约数个数： ( c 1 + 1 ) ∗ ( c 2 + 1 ) ∗ . . . ∗ ( c k + 1 ) 约数之和： ( p 1 0 + p 1 1 + . . . + p 1 c 1 ) ∗ . . . ∗ ( p k 0 + p k 1 + . . . + p k c k ) 如果N=p_1^{c_1}*p_2^{c_2}*...*p_k^{c_k} \\ 约数个数：(c_1+1)*(c_2+1)*...*(c_k+1) \\ 约数之和：(p_1^0+p_1^1+...+p_1^{c_1})*...*(p_k^0+p_k^1+...+p_k^{c_k}) 如果N=p1c1​​∗p2c2​​∗...∗pkck​​约数个数：(c1​+1)∗(c2​+1)∗...∗(ck​+1)约数之和：(p10​+p11​+...+p1c1​​)∗...∗(pk0​+pk1​+...+pkck​​)

欧几里得算法

int gcd(int a,int b){return b?gcd(b,a%b):a;
}

求欧拉函数

求某个数的欧拉函数
如果 N = p 1 a 1 p 2 a 2 . . . p m a m ϕ ( N ) = N × p 1 − 1 p 1 × p 2 − 1 p 2 × . . . × p m − 1 p m 如果N=p_1^{a_1}p_2^{a_2}...p_m^{a_m} \\ \phi(N)=N \times \frac{p_1-1}{p_1} \times \frac{p_2-1}{p_2} \times ... \times \frac{p_m-1}{p_m} 如果N=p1a1​​p2a2​​...pmam​​ϕ(N)=N×p1​p1​−1​×p2​p2​−1​×...×pm​pm​−1​

int phi(int x){int res=x;for(int i=2;i<=x/i;i++){if(x%i==0){res=res/i*(i-1);while(x%i==0)x/=i;}}if(x>1)res=res/x*(x-1);return res;
}

筛法求欧拉函数

求1-n的每个数的欧拉函数

int primes[N],cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉void get_eulers(int n){euler[1]=1;for(int i=2;i<=n;i++){if(!st[i]){primes[cnt++]=i;euler[i]=i-1;}for(int j=0;primes[j]<=n/i;j++){int t=primes[j]*i;st[t]=true;if(i%primes[j]==0){euler[t]=euler[i] * primes[j];break;}euler[t]=euler[i]*(primes[j]-1);}}
}

快速幂

求 m k m o d p m^kmodp mkmodp，时间复杂度为O(logk)

int qmi(int m,int k,int p){int res=1%p,t=m;while(k){if(k&1)res=res*t%p;t=t*t%p;k>>=1;}return res;
}

扩展欧几里得算法

// 求x,y,使得ax+by=gcd(a,b)
int exgcd(int a,int b,int &x,int &y){if(!b){x=1;y=0;return a;}int d=exgcd(b,a%b,y,x);y-=(a/b)*x;return d;
}

高斯消元

// a[N][N]是增广矩阵
int gauss(){int c,r;for(c=0,r=0;c<n;c++){int t=r;for(int i=r;i<n;i++) // 找到绝对值最大的行if(fabs(a[i][c])>fabs(a[t][c])){t=i;}if(fabs(a[t][c])<eps)continue;for(int i=c;i<=n;i++) swap(a[t][i],a[r][i]); //将绝对值最大的行换到最顶端for(int i=n;i>=c;i--) a[r][i]/=a[r][c]; // 将当前行的首位变成1for（int i=r+1;i<n;i++){  // 用当前行将下面所有的列消成0if(fabs(a[i][c])>eps){for(int j=n;j>=c;j--){a[i][j]-=a[r][j]*a[i][c];}}}r++;}if(r<n){for(int i=r;i<n;i++){if(fabs(a[i][n]>eps)return 2; // 无解}return 1; //有无穷组解}for(int i=n-1;i>=0;i--){for(int j=i+1;j<n;j++){a[i][n]-=a[i][j]*a[j][n];}}return 0;// 有唯一解
}

递推求组合数

// c[a][b]表示从a个苹果中选b个的方案数
for(int i=0;i<N;i++){for(int j=0;j<=i;j++){if(!j)c[i][j]=1;else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;}
}

来源：https://www.acwing.com/


http://www.ppmy.cn/news/276059.html

相关文章

ChatGPT扩展系列之使用pandora本地搭建ChatGPT

ChatGPT扩展系列之使用pandora本地搭建ChatGPT

ChatGPT扩展系列之使用pandora本地搭建ChatGPT 1. 为什么要本地搭建 主要解决使用上的几个痛点，我们可以看一下下面就是我们最常遇到的几个问题，这里我们重点提一下就是我们本地搭建好了之后，我们获取Access Token，这个Token的有效期长达14天，也就是这14天中，我们都不需…
阅读更多...
MySQL数据库迁移到ORACLE（持续更新）

MySQL数据库迁移到ORACLE（持续更新）

1. 使用Oracle SQL Developer 官方 SQL Developer 23.1下载 选择Windows 64-bit with JDK 11 included安装 2.下载后解压&#xff0c;选择exe执行启动&#xff0c;启动后见图 3. 创建连接 默认支持创建Oracle连接&#xff08;见下图&#xff09;&#xff0c;第三方连接需导入…
阅读更多...
如何在桌面版linux怎么安装360安全卫士？

如何在桌面版linux怎么安装360安全卫士？

安装方法参考网址&#xff1a;https://m.jb51.net/LINUXjishu/275881.html 360安全卫士现在是我们中国比较常见的安全软件&#xff0c;可对于linux系统来说&#xff0c;没有什么更好的安全软件&#xff0c;不过最近360推出linux版360安全卫士。今天在这里教大家在桌面版linux里…
阅读更多...
基于Android的手机安全卫士的开发

基于Android的手机安全卫士的开发

基于Android的手机安全卫士的开发 开发环境 处理器&#xff1a;Intel Core™ i5-5200U CPU 2.20GHz 内存&#xff1a;4GB 硬盘&#xff1a;500GB 操作系统&#xff1a;Windows 7中文版&#xff0c;64位操作系统 开发工具&#xff1a;Eclipse&#xff08;根据自己的使用工具写&…
阅读更多...
轻巧和实用并存——360安全卫士极速版试用报告

轻巧和实用并存——360安全卫士极速版试用报告

导语 近些年来&#xff0c;随着数字经济、大数据、物联网、5G等应用技术的发展与应用&#xff0c;个人电脑、智能手机、智能穿戴、智能家居等产品层出不穷&#xff0c;与我们的生活越来越密切&#xff0c;在给人们带来方便的同时&#xff0c;各种黑产盗号、木马等也在悄悄侵入一…
阅读更多...
老男孩 linux 2014 360下载,360安全卫士2014旧版

老男孩 linux 2014 360下载,360安全卫士2014旧版

iefans为用户提供的360安全卫士2014旧版能够很好的帮助用户防止木马病毒的侵害&#xff0c;相信许多用户在日常生活中上网是少不了的&#xff0c;这个时候网络安全就是非常重要了&#xff0c;毕竟许多重要的资料以及资金都可以通过网络交易&#xff0c;该软件就可以很好的帮助您…
阅读更多...
关于手机安全卫士开发详解

关于手机安全卫士开发详解

手机安全卫士 1 初始化界面的搭建 1.1 界面UI 界面的ui主要完成的是背景图片的显示&#xff0c;以及版本号的显示&#xff0c;其中版本号是需要动态获取显示的。 主要实现&#xff1a;由于布局的特点选择相对布局&#xff0c;在RelativeLayout中设置背景图片&#xff0c;…
阅读更多...
基于android平台的手机安全卫士的设计与实现 开题报告,开题报告-基于android的手机安全卫士的设计与开发.doc...

基于android平台的手机安全卫士的设计与实现 开题报告,开题报告-基于android的手机安全卫士的设计与开发.doc...

毕业设计开题报告 题 目&#xff1a; 基于Android的手机安全卫士的设计与开发 专 业 计算机科学与技术 学 生 姓 名 班 级 学 号 指 导 教 师 指 导 单 位 电气信息工程学院 专 业 负 责 人 学院工作领导小组 日 期 2016.12.15 开 题 报 告 学院 学号 毕业设计(论文)题目 基于a…
阅读更多...
最新文章

Copyright @ 2022~2023