算法竞赛基础---BFS与DFS include<iostream>include<cstdio>include<cstring>include<queue>using namespace std;/*红黑砖问题（老鼠走迷宫问题） 经典BFS RED AND BLACKThere is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.Write a program to count the number of black tiles which he can reach by repeating the moves described above.InputThe input consists of multiple data sets. A data set starts with a line containing two positive integers W and H;W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.'.' - a black tile'#' - a red tile'@' - a man on a black tile(appears exactly once in a data set)OutputFor each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).*/int dir4={{-1,0},{0,-1},{1,0},{0,1}};//左上右下 const int MAXN=30;int Wx,Hy;//Wx表示的迷宫的行，Hy表示迷宫的列 char mpMAXN;struct node{int x; int y;};queue<node> q ;define check(x,y)(x>=0&&x<Wx&&y>=0&&y<Hy)//判断是否出界int ans=0;//记录结果void BFS(int x,int y){ans=1; node now,next; now.x=x; now.y=y; q.push(now);//起点入栈 while(!q.empty()){ now=q.front(); q.pop(); for(int i=0;i<4;i++){ next.x=now.x+dir[i][0]; next.y=now.y+dir[i][1];//向四个方位前进 if(check(next.x,next.y)&&mp[next.x][next.y]=='.'){ mp[next.x][next.y]='#'; ans++; q.push(next);//将符合条件的点入栈 } } } } void DFS(int x,int y){mp[x][y]='#'; ans++; for(int i=0;i<4;i++){ int newx=x+dir[i][0]; int newy=y+dir[i][1]; if(check(newx,newy)&&mp[newx][newy]=='.'){ DFS(newx,newy); } }}int main(){int dx=0,dy=0,x,y; memset(mp,0,sizeof(mp)); while(cin>>Wx>>Hy){//Wx为列，Hy为行 if(Wx==0&&Hy==0)break; for(y=0;y<Hy;y++){ for(x=0;x<Wx;x++){ cin>>mp[x][y]; if(mp[x][y]=='@'){//得到起点 dx=x; dy=y; } } }ans=0; // BFS(dx,dy); DFS(dx,dy); cout<<ans<<endl;}return 0;}

数论基础3 ---素数 1 试除法判断素数bool isPrim(int n){if(n<=1)return false; for(int i=2;i*i<=n;i++){ if(n%i==0) return false; } return true;}2 埃式筛法求素数的个数；const int MaxN =1e7;int a[MaxN+1];//存储素数bool vis[MaxN+1];//标志筛选过的数int E_search(int n){int k=0; for(int i=0;i<=n;i++)vis[i]=false; for(int i=2;i*i<=n;i++) { if(!vis[i]){ a[k++]=i; for(int j=i*i;j<=n;j=j+i) vis[j]=true;//i的倍数全部筛除 } } return k; //素数个数 }

数论基础知识2---欧几里得 2.1.1利用辗转相除法求最大公约数GCDint gcd(int a,int b){return b==0?a:gcd(b,a%b);}2.1.2最小公倍数LCMint lcm(int a,int b){return a/gcd(a,b)*b;}2.2.1 扩展欧几里得算法求ax+by=gcd(a,b)的解(x0,y0)void extend_gcd(int a,int b,int &x,int &y){if(b==0){ x=1,y=0; return ; } extend_gcd(a,a%b,x,y); int tmp=x; x=y; y=tmp-(a/b)*y; } 2.2.2求任意方程ax+by=n的一个整数解1）判断该方程是否有解，有解的条件为gcd(a,b)可以整除n;2) 用扩展欧几里得算法得到ax+by=gcd(a,b)的一个解(x0,y0);3) 在ax+by=gcd(a,b)同时乘n/gcd(a,b)a*n/gcd(a,b)x+b*n/gcd(a,b)y=n;4) 对照ax+by=n 得到它的一个解x'0=x0*n/gcd(a,b); y'0=y0*n/gcd(a,b);蓝桥杯例题包子凑数小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。小明想知道一共有多少种数目是包子大叔凑不出来的。输入第一行包含一个整数N。(1 <= N <= 100)以下N行每行包含一个整数Ai。(1 <= Ai <= 100)输出一个整数代表答案。如果凑不出的数目有无限多个，输出INF。实例输入：245输出：6输入：246输出：INF思路:a1x1+a2x2+a3x3+a4x4...=n 当ai不互质时，即gcd(a1,a2,...)不等于1时，方程存在无解的情况，即可能出现凑不出的数为无线多个若a1能够凑出，a1的倍数也可以凑出a2 能够凑出，a2,a1+a2的倍数也可以凑出...即当f[j]存在，f[j+a[i]]也存在。核心代码 if(i==1)g=a[i]; else g=gcd(g,a[i]);//求得蒸笼间的最大公约数 for(int j=0;j<10000;++j){ if(f[j])f[j+a[i]]=true;//将所有能够凑出的数置为真。 } 全部代码include<iostream>include<stdio.h>using namespace std;int n,g;int a[101];bool f[10000];int gcd(int a,int b){//GCDif(b==0)return a; return gcd(b,a%b);}int main(){ scanf("%d",&n);//蒸笼个数 f[0]=true; for(int i=1;i<=n;i++){ scanf("%d",&a[i]);//每个蒸笼所能装下的包子数 if(i==1)g=a[i]; else g=gcd(g,a[i]); for(int j=0;j<10000;++j){ if(f[j])f[j+a[i]]=true; } } if(g!=1){ printf("INF\n"); return 0; } int ans=0; for(int i=0;i<10000;i++){ if(!f[i]){ ans++; // cout<<i<<endl;可将所有凑不出的数目打印出来 } } cout<<ans<<endl;}

数论基础知识1----快速幂 1.1 模运算定义取模运算为a除以m的余数,记为: a mod m = a % m;取模结果0<=a mod m<=m-1;取模操作性质:加:(a+b) mod m =( a mod m + b mod m) mod m;减:(a-b) mod m =( a mod m - b mod m) mod m;乘:(ab) mod m =( a mod m b mod m) mod m;以上方法对于除法不适用1.2 快速幂1.2.1 分治法int fastPow(int a,int n){//分治法 if(n==1)return a;int temp=fastPow(a,n/2);if(n%2==0)return temp*temp;//偶数个a;elsereturn temptempa; //奇数个a;} 1.2.2 按位乘将所需求的指数化为二进制按位进行累乘(1)n&1,取n的最后一位，判断需不需要进行累乘(2)n>>=1,将n右移一位，目的把刚处理的最后一位去除掉。 例如 a的11次方 为 a的8次方，a的2次方，a的1次方相乘对应二进制位 1011;int fastPow2(int a,int n){ //按位乘int temp=1,base=a; while(n){ if(n&1) temp*=base; base*=base; n>>=1; } return temp;} 快速幂取模 const int mod=200907; int fastPow3(int a,int n){int temp=1,base=a; while(n){ if(n&1) temp=(temp*base)%mod; base=(base*base)%mod; n>>=1; } return temp; } /*矩阵快速幂m*m 的矩阵A 求他的n次幂 */ const int MAXN=2;const int MOD=1e4;//模为10000 typedef long long LL;struct Matrx{int m[MAXN][MAXN]; Matrx(){ memset(m,0,sizeof(m)); }};Matrx Multi(Matrx a,Matrx b){//矩阵相乘 Matrx ans; for(int i=0;i<MAXN;i++) for(int j=0;j<MAXN;j++) for(int k=0;k<MAXN;k++) ans.m[i][j]=(ans.m[i][j]+a.m[i][k]+b.m[k][j])%MOD; return ans;} Matrx fastm(Matrx a, int n){Matrx res; for(int i=0;i<MAXN;i++){ //初始化为单位矩阵，相当于快速幂中的基数1; res.m[i][i]=1; } while(n){ if(n&1)res=Multi(res,a); a=Multi(a,a); n>>=1; } return res;}

XML数据的封装与解析 在Android的开发中，XML是一种非常常用的封装数据的形式，从服务器中获取数据也经常是这种形式，所有学会生成和解析XML是非常有用的。本次案例主要使用的是XML的解析技术，还有AsyncTask的一个异步下载机制。话不多说。开始吧首先是两个布局文件activity_mian和listview_layout1,activity_mian只需要存放一个listview即可 2,listview_layout设计样式最后填充到activity_mian的listview中 布局做好了接下来就是java代码实现具体的功能了首先创建一个Music实体类 接下来就是通过url，使用AsyncTask实现图片和XML文件的下载 然后将下载的XML文件解析出来，由于证书问题这里需要加一个验证通过类 一切就绪后就是剩下MainActivity的代码咯 编写完成后看看效果ps:我这里url使用的是自己的云服务器地址。也可以使用Androidapi地址:XML网络地址：https://api.androidhive.info/music/music.xml