ACM模板总结

1、Dijkstra算法

#include \#include \#define max 20

int mincost(int v[],int d[],int n) { int temp=1000000,i,w=2; for(i=2;i<=n;i++) if(v[i]==0&&d[i]

int main() { int c[max][max]; int d[max],v[max]={0}; int n,i,j,k,w,sum; scanf(\ for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf(\ v[1]=1;//原点是1 也可以改 for(i=1;i<=n;i++) d[i]=c[1][i]; for(i=1;i<=n;i++) w=mincost(v,d,n); v[w]=1; for(k=2;k<=n;k++) if(v[k]==0) { sum=d[w]+c[w][k]; if(sum

}

for(i=2;i<=n;i++) printf(\ memset(v,0,max*sizeof(int)); return 0; }

/*从原点出发到其他各个点的最短距离 4

0 2 1 5

2 0 3 100000 1 3 0 4

5 100000 4 0 /*

2、求最小生成树prim算法

#include \#include \#define mvnum 12 #define mvalue 1000 #define menum 20

typedef int vexlist[mvnum];

typedef int adjmaxt[mvnum][mvnum]; int visited[mvnum]={0}; struct edge { int fvex; int evex; int weight; };

typedef struct edge edgeset[mvnum];

void creatmaxt(vexlist gv,adjmaxt ga,int n,int e) { int i,j,k,w; for(i=0;i

1

if(i==j) ga[i][j]=0; else ga[i][j]=mvalue; for(k=0;k

void prim(adjmaxt ga,edgeset ct ,int a,int n) { int i,j,t,k,w,min,m; struct edge x; for(i=0;i

ct[m]=x;

j=ct[k-1].evex; for(i=k;i

void output(edgeset ge,int e) { int k; for(k=0;k

int main() { int n,e; vexlist gv; adjmaxt ga; edgeset ge; scanf(\ creatmaxt(gv,ga,n,e); prim(ga,ge,0,n); output(ge,n-1); return 0; } /*

输入图的顶点数和边数： 输入4个顶点数据

2

输入5条无向带权边 4 5 0 1 2 3 0 1 2 1 2 3 2 3 4 0 3 5 0 2 1

利用prim算法从0点出发求图的最小生成树：

0 2 1,0 1 2,2 3 4, 4 5 0 1 2 3 0 1 2 1 2 3 2 3 4 0 3 5 0 2 1

0 2 1;0 1 2;2 3 4;

Press any key to continue */

else { return

((int)(pow((float)GetPow(a,b/2),2))00); } }

int main() { int a,b; scanf(\ printf(\ return 0; }

4、全排列算法

#include

void swap(int k,int i,int a[]) { int t; t=a[k]; a[k]=a[i]; a[i]=t; }

int pailie(int a[],int i,int n) { 3

int k,t; static int v=0; if(i==n) { } else

for(k=i;k

for(t=0;t

printf(\

printf(\

3、求任意数的任意次方的最后三位数构成的整数

#include \#include \int GetPow(int a,int b) { if(b==1||b==0) { return a; } if(b%2) { return

((int)(pow((float)GetPow(a,b/2),2)*a)00); }

}

}

swap(i,k,a); pailie(a,i+1,n); swap(i,k,a);

return v;

int main() { int

a[50]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15},c=0;

c=pailie(a,0,5); printf(\//getch(); return(0); }

//如何选择得分最多The two grids are adjacency only if the Manhattan distence between them is exactly #include int arc[101][101]; int link[101][101]; int visited[101][101];

int dir[4][2]={-1,0,1,0,0,-1,0,1}; int n,m,p;

int ko(int a,int b) {

if(a>=0 && b>=0 && a

struct node // 记录访问过的点 {

int x,y; }cc[10000];

4

int dfs(int a,int b) {

int tx,ty; int i;

for(i=0;i<4;i++) {

tx=a+dir[i][0]; ty=b+dir[i][1]; if(ko(tx,ty)) {

visited[tx][ty]=1; cc[p].x=tx; cc[p++].y=ty;

if(link[tx][ty]==-1) {

link[tx][ty]=i; // 这里赋值i,表示是从加a+dir[i][0],及b+dir[i][1] 得到的,即指向和它组和的点 return 1; } else

if(dfs(tx-dir[link[tx][ty]][0],ty-dir[link[tx][ty]][1])) // 寻找与它组合的点的增广路径 {

link[tx][ty]=i; return 1; } } }

return 0; }

int main() {

int t,i,j,k; int a;

scanf(\ while(t--) {

scanf(\ for(i=0;i

for(j=0;j

scanf(\ Press any key to continue

//二分图匹配算法.给始点及终点坐标，时间及速度，求最少未匹配 #include #include link[i][j]=-1; visited[i][j]=0; } p=0;

for(i=k=0;i

for(j=0;j

if(arc[i][j]==1) {

if(dfs(i,j)) k++; }

for(a=0;a

visited[cc[a].x][cc[a].y]=0; } }

printf(\ }

return 0; }

测试数据： 2 3 3 1 0 1 1 1 0 0 1 1 4 2 2 1 1 1 1 4

using namespace std;

const int MAXN=101; int Nx,Ny,s,v; int

Mx[MAXN],My[MAXN],g[MAXN][MAXN];

int chk[MAXN],Q[MAXN],prev[MAXN]; double

x[MAXN],y[MAXN],xx[MAXN],yy[MAXN];

int hungry(void) // {

int res = 0; int qs, qe;

memset(Mx, -1, sizeof(Mx)); memset(My, -1, sizeof(My)); memset(chk, -1, sizeof(chk)); for (int i = 0; i < Nx; i++) {

if (Mx[i] == -1) {

qs = qe = 0; Q[qe++] = i; prev[i] = -1; bool flag = 0;

while (qs < qe && !flag) {

int u = Q[qs];

for (int v = 0; v < Ny && !flag; v++)

if (g[u][v] && chk[v] != i)

5

{

chk[v] = i; Q[qe++] = My[v];

if (My[v] >= 0) prev[My[v]] = u;

else {

flag = 1; int d = u, e = v;

while (d != -1)

{

int t = Mx[d];

Mx[d] = e;

My[e] = d;

d = prev[d];

e = t; } } } qs++; }

if (Mx[i] != -1) res++; } }

return res; }

int main() {

int i,j;

double d,tmp;

6

while(scanf(\v)!=EOF) {

d=s*v;

memset(g,false,sizeof(g)); for(i=0;i

scanf(\ for(j=0;j

tmp=sqrt((x[j]-xx[i])*(x[j]-xx[i])+(y[j]-yy[i])*(y[j]-yy[i]));

if(tmp<=d) g[j][i]=true; } }

printf(\ }

return 0; }

/*二分图匹配算法 2 2 5 10 1.0 1.0 2.0 2.0 100.0 100.0 20.0 20.0 1*/

//组合算法（几个苹果几个盒子求不重复组合数

#include using namespace std;

/*****放置苹果的递归函数***** *****递推式为:

f(m,n) = f(m-n,n) + f(m,n-1); m>n f(m,n) = f(m,m); m

int f( int m, int n ) { //递归出口，没有苹果或者盒子剩下1个 if ( m==0 || n == 1 ) { return 1; } //苹果树多于盒子数 if ( m >= n ) { return f(m-n, n)+f(m, n-1); } else //苹果树少于盒子数，只需要相同的盒子数就足够了 { return f(m, m); } }

int main() { cout <<\请输入苹果数目: \ int apple_count; cin >> apple_count; cout <<\请输入盒子数目: \ int box_count; cin >> box_count; cout <<\把这些苹果房间这些盒子，不重复的放置方法有: \<

//

Time Limit: 10000MS Memory Limit: 65536KB

Description

Given a set of integer number S={s_1, s_2, ..., s_k}. Find out how many integers between 1 and n (includsive) that can't be divided by any number in the set S.

Input

Input contains several cases.

The first line of each case contains a integer n (<=10^18).

The second line contains an integer k (<=20) followd by k integers indicating the set S. The last case is followed by a line containing one zero.

Output

For each case, output an integer in a line indicating the number of undividable integers.

Sample Input

6 2 2 3 0

7

P4 Division

Sample Output

2

#include using namespace std;

const int And_Bit =1000000000; //进位数 const int Num_Bit = 9; //数组一位表示整形数的位数

const int Num_Len = 2001; //整形数的位数 const int BigNum_Len = Num_Len/Num_Bit + 10; //数组的位数 const char OutStr[] = {'%','0','0'+Num_Bit,'d',0}; //标准化输出字符串

void toBigInt(const char *s,int *a){ //将输入的字符串转为整形数组的大整数 int as=0,e,ten; memset(a,0,sizeof(int)*BigNum_Len); for(int

i=(int)strlen(s)-1;i>=0;i-=Num_Bit){ e = 0; ten = 1; for(int

j=0;j=0;j++){ e += (s[i-j]-'0')*ten; ten *= 10; } a[++as]=e; } a[0]=as; }

void outBigInt(const int *a){ //输出大整数

8

int ns = a[0];

printf(\ for(int i=ns-1;i>0;i--) printf(OutStr,a[i]); //printf(\}

void leftShiftBigInt(int *a,int b){ //大整数左移移位运算 int l=a[0]; for(int i=l+1;i>1;i--) a[i] = a[i-1]; a[1] = b; if(a[l+1]!=0) a[0]++; }

int cmpBigInt(const int *a,const int *b){ //大整数比较：若a>b返回，若a=b返回，否则返回-1 int la=a[0],lb=b[0]; if(la>lb) return 1; if(la=1;i--){ if(a[i]>b[i]) return 1; if(a[i]

void addBigInt(const int *a,const int *b,int *c){ //大整数加法：c=a+b memset(c,0,sizeof(int)*BigNum_Len);//初始化全为零 int i=0,la=a[0],lb=b[0]; for(i=1;;i++){ if(i>la&&i>lb) break; c[i] += a[i] + b[i]; if(c[i]>=And_Bit){ c[i+1]++; c[i]-=And_Bit; }

} while(c[i]==0&&i>1) i--; c[0]=i; }

void subBigInt(const int *a,const int *b,int *c){ //大整数减法：c=a-b memset(c,0,sizeof(int)*BigNum_Len);//初始化全为零 int i=0,la=a[0],lb=b[0]; for(i=1;;i++){ if(i>la&&i>lb) break; c[i] += a[i]-b[i]; if(c[i]<0){ c[i+1]--; c[i]+=And_Bit; } } while(c[i]==0&&i>1) i--; c[0]=i; }

void mulBigInt(const int *a,const int *b,int *c){ //大整数乘法：c=a*b memset(c,0,sizeof(int)*BigNum_Len); int i,j,k; __int64 t; for(i=1;i<=a[0];i++) for(j=1;j<=b[0];j++){ t = (__int64)a[i]*(__int64)b[j] + c[i+j-1]; if(t >= And_Bit){ c[i+j] += t/And_Bit; t %= And_Bit; } c[i+j-1] = t; }

9

k=i+j+1;

while(c[k]==0&&k>1) k--; c[0]=k; }

void mulIntBigInt(const int *A,const int b,int *C){ //大整数与Int数乘法：C=A*b; memset(C,0,sizeof(int)*BigNum_Len); int i=0; __int64 t; for(i=1;i<=A[0];i++){ t = C[i] + (__int64)A[i]*(__int64)b; if(t>=And_Bit){ C[i+1]+=t/And_Bit; t%=And_Bit; } C[i] = t; } while(C[i]==0&&i>1) i--; C[0]=i; }

void divBigInt(const int *a,const int *b,int *c,int *d){ //大整数除法：c=a/b,d=a%b int *td = new int[BigNum_Len],*tb = new int[BigNum_Len]; memset(c,0,sizeof(int)*BigNum_Len); memset(d,0,sizeof(int)*BigNum_Len); if(b[0]==1&&b[1]==0) return ; int

t_max,t_mid,t_min,la=a[0],lb=b[0],lc=la,ld=0;//二分辅助变量 double

b_min=b[lb],b_max=b_min+1,d_max=0,d_min=0; if(lb>1){ b_min = b_min*And_Bit + b[lb-1];

b_max = b_min + 1; } for(int i=la;i>=1;i--){ leftShiftBigInt(d,a[i]); if(cmpBigInt(b,d)==1) continue; ld = d[0]; d_min = d[ld]; while(d_min=0){ t_min = t_mid+1; continue; } break; } memcpy(d,td,sizeof(int)*BigNum_Len); c[i] = t_mid; } delete []td;delete []tb; while(c[lc]==0&&lc>1) lc--; c[0]=lc; }

int main(){ char str1[Num_Len],str2[Num_Len]; int

a[BigNum_Len],b[BigNum_Len],c[BigNum

10

_Len],d[BigNum_Len]; char yes[20][Num_Len]; int shu[20][BigNum_Len]; int i,j,w,k; scanf(\ for(i=0;i

//////////////////

he gopher family, having averted the canine threat, must face a new predator.

The are n gophers and m gopher holes, each at distinct (x, y) coordinates. A hawk arrives and if a gopher does not reach a hole in s seconds it is vulnerable to being eaten. A hole can save at most one gopher. All the gophers run at the same velocity v. The gopher family needs an escape strategy that minimizes the number of vulnerable gophers. Input

The input contains several cases. The first line of each case contains four positive

integers less than 100: n, m, s, and v. The next n lines give the coordinates of the gophers; the following m lines give the coordinates of the gopher holes. All distances are in metres; all times are in seconds; all velocities are in metres per second. Output

Output consists of a single line for each case, giving the number of vulnerable gophers. Sample Input 2 2 5 10 1.0 1.0 2.0 2.0 100.0 100.0 20.0 20.0 Sample Output 1 q

{

if (Mx[i] == -1) {

qs = qe = 0; Q[qe++] = i; prev[i] = -1; bool flag = 0;

while (qs < qe && !flag) {

int u = Q[qs];

for (int v = 0; v < Ny && !flag; v++)

if (g[u][v] && chk[v] != i)

{

chk[v] = i; Q[qe++] = My[v]; if (My[v] >= 0) prev[My[v]] = u;

else {

flag = 1; int d = u, e = v; while (d != -1) {

int t = Mx[d];

Mx[d] = e; My[e] = d; d = prev[d];

e = t; } } } qs++; }

if (Mx[i] != -1) res++; } 11

#include #include using namespace std;

const int MAXN=101; int Nx,Ny,s,v;

int Mx[MAXN],My[MAXN],g[MAXN][MAXN]; int chk[MAXN],Q[MAXN],prev[MAXN]; double x[MAXN],y[MAXN],xx[MAXN],yy[MAXN];

int hungry(void) {

int res = 0; int qs, qe;

memset(Mx, -1, sizeof(Mx)); memset(My, -1, sizeof(My)); memset(chk, -1, sizeof(chk)); for (int i = 0; i < Nx; i++)

}

return res; }

int main() {

int i,j; double d,tmp;

while(scanf(\) {

d=s*v;

memset(g,false,sizeof(g)); for(i=0;i

scanf(\ for(j=0;j

tmp=sqrt((x[j]-xx[i])*(x[j]-xx[i])+(y[j]-yy[i])*(y[j]-yy[i]));

if(tmp<=d) g[j][i]=true; } }

printf(\ } return 0; }

//积木游戏

#include #include \#include %using namespace std;

ifstream fin(\

12

ofstream fout(\

int N,M;

struct demension{

unsigned a,b,c;

}demen[101];

int dp[101][101][101][3];

inline int h(int a, int k) {

//memo调用的子过程，返回积木a第k面朝上时的高度

assert(a>0&&a<=N);

switch(k) {

case 0: return demen[a].c;

case 1: return demen[a].b;

case 2: return demen[a].a; }

assert(0); }

inline bool canput(int a, int k, int aa, int kk) {

//memo调用的子过程，返回a的k面能否容纳

assert(0); }

if(i

aa的kk面

int i,j,ii,jj;

switch(k)

{

case 0:

i=demen[a].a; j=demen[a].b;

break;

case 1:

i=demen[a].a;

j=demen[a].c;

break;

case 2:

i=demen[a].b;

j=demen[a].c;

break;

default:

switch(kk) {

case 0:

ii=demen[aa].a;

jj=demen[aa].b;

break;

case 1:

ii=demen[aa].a;

jj=demen[aa].c;

break;

case 2:

ii=demen[aa].b;

jj=demen[aa].c;

break; default:

assert(0); }

13

if(ii

return (i>=ii&&j>=jj);

//这里的题意我开始理解错了，不需要j>=ii。这个错误让我花了一下午调试 }

int memo(int i, int a, int b, int k) {

/*已经用前a块积木摆成了i根柱子，顶面积木b的的面k朝上

之后还能获得的最大高度（决策是否使用a+1块积木、如何使用）*/

if(dp[i][a][b][k]!=0) return dp[i][a][b][k];

if(a==N) //边界条件

if(i==M) return 0;

else return INT_MIN;

int ans=memo(i,a+1,b,k); //不使用第a+1块积木

if(i

for(int kk=0;kk<=2;kk++)

if(ans

14

ans=memo(i+1,a+1,a+1,kk)+h(a+1,kk); //新起一堆

if(i>0)//这个条件的疏忽让我调试了一早上

for(int kk=0;kk<=2;kk++)

if(canput(b,k,a+1,kk)&&ans

ans=memo(i,a+1,a+1,kk)+h(a+1,kk); //放在前一堆上

dp[i][a][b][k]=ans;

return ans; }

int main() {

fin >> N >> M;

for(int i=1;i<=N;i++)

fin >> demen[i].a >> demen[i].b >> demen[i].c;

demen[0].a=demen[0].b=demen[0].c=1001;

fout << memo(0,0,0,0) << endl;

return 0; } 第二次测试 2

#include

#include

using namespace std;

int r,n,m,a[15],b[200010];

char s[5000],c[5000];

void to_n(int t)//根据下标转化成相应的序列 {

r=0;

while (t) {

s[r++]= a[(t-1)%m+1]+'0';

t = (t-1)/m; }

int i;r--;

for(i =0; r>=0;++i,r--) c[i]=s[r];

c[i]='\\0';

15

}

int main() {

while (scanf(\ {

for(int i = 1;i<=m;++i) scanf(\

if(!n){ printf(\

int ok =0; b[0]=0; sort(a+1,a+m+1);

int num = 200000;

if(10%n==0&&n!=10) num = m;

for(int i = 1;i<=num&&!ok;i++)

{

b[i] = b[(i-1)/m]*10+ a[(i-1)%m+1];

if(b[i]&&!(b[i]%=n)) ok=i;

}

if(!ok) printf(\

else{ to_n(ok); printf(\ }

return 0;

} 1

#include #include #include //#include #define MAX_LEN 80 char szInput[MAX_LEN+1];

unsigned char B[(MAX_LEN+1)*MAX_LEN/8]; unsigned char

Bit8[8]={0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};

#define GETB(i,j) (B[(i)*10+((j)>>3)] & Bit8[(j) & 0x7])

#define SETB(i,j) B[(i)*10+((j)>>3)] |= Bit8[(j) & 0x7] int length; int getcode() {

int i,j,notfound1,notfound2=0; if(length<2) return 1;

memset(B,0,(length+1)*10); for(i=0;i<2;++i) {

for(j=0;j

for(i=2;i<=length;++i) {

for(notfound1=1,j=0;j<=length-i;++j) {

if(GETB(i-2,j+1)/*B[i-2][j+1]*/ && szInput[j]==szInput[j+i-1]) {

SETB(i,j);//B[i][j]=1; //printf(\ notfound1=0; }

}

if(notfound1) {

if(notfound2) return i-2; notfound2=1; } else {

notfound2=0; } }

if(notfound2) return length-1; return length; }

int main(void) {

while(scanf(\ {

length=strlen(szInput); //assert(length<=MAX_LEN); printf(\ }

return 0; } 7

#include \#include \#define eps 1e-8 typedef struct Point {

double x,y; }Point; Point p[10001]; double R;

double multity(Point A,Point B) {

return A.x*B.y - A.y*B.x;

16

}

double AREA(Point *p,int n) {

double s = 0.0; p[n+1] = p[1];

for(int i = 1;i <= n;i ++) s += multity(p[i],p[i+1]); return s / 2; }

void CHANGE(Point *p,int n) {

Point temp;

for(int i = 1;i <= n / 2;i ++) {

temp = p[i]; p[i] = p[n+1-i]; p[n+1-i] = temp; } }

double multi(Point A,Point B,Point C) {

return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x); }

int ISCOVEY(Point *p,int n) { int i; p[n+1] = p[1]; p[n+2] = p[2];

for(i = 1;i <= n;i ++) {

if(multi(p[i],p[i+1],p[i+2]) < 0) return 0; } return 1; }

double AREAOFTHREE(Point A,Point B,Point C) {

double s = multity(A,B) + multity(B,C) +

17

multity(C,A); if(s < 0) s = -s; return s / 2; }

int INCOVEY(Point *p,int n) { int i; double s1,s2; s1 = AREA(p,n); if(s1 < 0) s1 = -s1; s2 = 0.0; p[n+1] = p[1];

for(i = 1;i <= n;i ++) {

s2 += AREAOFTHREE(p[i],p[i+1],p[0]); }

if(s1-s2>1e-8) return 0; if(s2-s1>1e-8) return 0; return 1; }

double dist(Point A,Point B) { double s;

s = (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y); return sqrt(s); }

double min(double m,double n) {

if(m - n > 1e-10) return n; return m; }

int boowl(Point A,Point B,Point C) {

double a,b,c,s,h; a = dist(A,B); b = dist(A,C); c = dist(B,C);

if(a < R || b < R) return 0; s = AREAOFTHREE(A,B,C); if(c > 1e-10) {

h = 2 * s / c; if(h < R) return 0; } return 1; }

int INSIDE(Point *p,int n) { int i; p[n+1] = p[1]; p[n+2] = p[2];

for(i = 1;i <= n;i ++)

if(!boowl(p[0],p[i],p[i+1])) return 0; return 1; }

int main() { int n,i; double Area;

while(scanf(\{

scanf(\ for(i = 1;i <= n;i ++) scanf(\ p[n+1] = p[1]; Area = AREA(p,n);

if(Area < 0) CHANGE(p,n); p[n+1] = p[1];

if(!ISCOVEY(p,n)) { printf(\ILL-FORMED\\n\

if(!INCOVEY(p,n)) { printf(\FIT\\n\

if(!INSIDE(p,n)) printf(\FIT\\n\

else printf(\

18

} return 0; } 滑雪

#include using namespace std;

int matrix[100][100];// 保存原始数据 int cnt[100][100]; // 记录每一个点的最大滑雪长度 int row ,col;

int DP(int i, int j) {

// 以下四块语句,只对合法的i和j,进行递归(递归的重点就是:剪去所有不合法的,只处理所有合法的!!!)

if (j+1 <= col-1) {

if (j-1 >= 0) { }

if (matrix[i][j] > matrix[i][j-1]) { }

if (max < DP(i, j-1)) { }

max = DP(i, j-1);

// 如果已经处理过,直接返回(记忆化搜索if (cnt[i][j] > 0) { }

return cnt[i][j];

效率之所以高的原因:不重复计算)

int max = 0;

}

if (matrix[i][j] > matrix[i][j+1]) { }

if (max < DP(i, j+1)) { }

max = DP(i, j+1);

}

// 如果左右上下都没有一个点的值比这个// 否则将左右上下各点最大滑雪长度记录// 这就是max为什么要初始化为0的原因. return cnt[i][j] = max + 1;

点的值大,则cnt[i][j] = max+1 = 1 在max中, 则cnt[i][j] = max+1

if (i-1 >= 0) { }

if (matrix[i][j] > matrix[i-1][j]) { }

if (max < DP(i-1, j)) { }

max = DP(i-1, j);

int main() { 19

// 遍历数组,求最大值,在这里因为将cntfor (i=0; i<=row-1; i++)

// 处理每一个点,将其最大滑雪长度保存for (i=0; i<=row-1; i++) { }

for (j=0; j<=col-1; j++) { }

DP(i, j);

在cnt数组里面

// 初始化数据

for (i=0; i<=row-1; i++) { }

for (j=0; j<=col-1; j++) { }

cin>>matrix[i][j]; cnt[i][j] == 0;

int i, j; cin>>row>>col;

// 在这里我曾经很SB地将row错写成col,调试所有的行数等于列数的数据都没有问题,可是一提交就Wa

// 将结果记录在cnt数组中(记忆化搜索的重点)

// 注意,行数可能不等于列数!!!! if (i+1 <= row-1) { }

if (matrix[i][j] > matrix[i+1][j]) { }

if (max < DP(i+1, j)) { }

max = DP(i+1, j);

错写成matrix而wa了一次,真不应该!!!

{ }

cout<

for (j=0; j<=col-1; j++) { }

if (cnt[0][0] < cnt[i][j]) { }

cnt[0][0] = cnt[i][j];

数就足够了 {

return f(m, m); } }

int main() {

cout < <\请输入苹果数目: \int apple_count; cin >> apple_count;

cout < <\请输入盒子数目: \int box_count; cin >> box_count;

cout < <\把这些苹果房间这些盒子，不重复的放置方法有: \

return 0; }

////////////////////////////////////////////////////////////////////////////////////////////////////////////// #include /*c语言*/ int main() {

int fpg(int x,int y); int q,i,m,n,sum; scanf(\for (i=0;i

scanf(\ sum=fpg(m,n); printf(\} }

int fpg(int x,int y) 20

return 0; } 放苹果

#include using namespace std;

/*****放置苹果的递归函数***** *****递推式为:

f(m,n) = f(m-n,n) + f(m,n-1); m>n f(m,n) = f(m,m); m

int f( int m, int n ) {

//递归出口，没有苹果或者盒子剩下1个 if ( m==0 || n == 1 ) {

return 1; }

//苹果树多于盒子数 if ( m >= n ) {

return f(m-n, n)+f(m, n-1); }

else //苹果树少于盒子数，只需要相同的盒子

{ int z;

if (x==1||x==0) z=1; else if (y==1) z=1;

else if (x>=y) z=fpg(x-y,y)+fpg(x,y-1); else z=fpg(x,x); return(z); }

\

//若度数为零的点大于1，则不唯一。

if(s.size()>1) only=false; //找与该点相连的点，并除去该点，查找新的入度为零的点，并入度。 while(!s.empty()) Sort it all out { #include \ #include \ using namespace std; int t=s.top();

int

// link[30][30],degree_in[30],degree[30],Top[cout<

30]; char a,b,c;

Top[record++]=t;

bool only,visit_m[30]; s.pop(); int n,m,record,count_n,circle; for(int i=1;i<=n;i++)

{ int Top_sort() {

if(link[t][i]==1)

only=true; { record=0; stack s; degree[i]--;

//寻找入度为零的点，入栈。

for(int i=1;i<=n;i++) for(int i=1;i<=n;i++)

{

{

if(visit_m[i]&&!degree_in[i]) { if(visit_m[i]&&!degree[i])

s.push(i);

{

degree[i]=-1; // cout<

}

s.push(i);

// cout<<\

21

degree[i]=-1;

}

}

} //若入度为零的点大于1，则不唯一。 if(s.size()>1)

only=false; }

// cout<

for(int j=1;j<=n;j++) { if(degree[j]>0)//-1表示有圈 }

if(record==n&&only) {

return 1;//1表示可以唯一排序 } } int main() {

// freopen(\ while(cin>>n>>m&&n!=0&&m!=0) {

int i,s;

22

circle=-1;count_n=-1;record=0;

memset(degree_in,0,sizeof(degree_in)); memset(visit_m,false,sizeof(visit_m));

memset(degree,0,sizeof(degree)); for(i=1;i<=m;i++) {

cin>>a>>c>>b; int a1=(int)(a-'A')+1; int b1=(int)(b-'A')+1; //

cout<

//当有圈或排好序时结束

if(circle==-1&&count_n==-1) visit_m[a1]=true;

visit_m[b1]=true;

if(link[a1][b1]!=1) degree_in[b1]++;

link[a1][b1]=1; for(int j=1;j<=n;j++)

degree[j]=degree_in[j]; //每输入一条边就排序

memset(link,0,sizeof(link));

}

return -1; {

return 0;//不唯一

s=Top_sort();

if(s==1) count_n=i;

else if(s==-1)

circle=i;

} } if(s==1) {

cout<<\sequence determined after \relations: \

for(int i=0;i

cout<

////////////////////////////////////////////////////////////////////////////////////

23

////////////////////////// 题目大意：

题目给定两个数字n（2<=n<=26）代表字母表里的前n个大写字母，m代表有m个关于前n个字母的偏序，问是否能确定这n个大写字母的一个全序关系。

若能确定，输出：Sorted sequence determined after xxx relations: yyy...y.

不能确定，输出：Sorted sequence cannot be determined.

出现矛盾，输出：Inconsistency found after xxx relations.

注：xxx代表一共用了几个偏序关系，yyy代表全序关系。 问题分析：

每次读入一条边后，对新图作DFS找是否有环，如果有环则不用进行拓扑排序了，这种属于不能确定的情况。

否则进行拓扑排序， 因为拓扑排序的序列可能是不唯一的，拓扑排序不唯一的情况比较好判断，就是如果每次队列中如果有多于一个点（这个点代表入度为0的点），则不唯一，如果不出现这样的点，则有唯一拓扑排序序列，最后输出即可。 Stitcs

#include

#include //due to:qsort #include int n;

int stick[100]; int total;

int ns; //一共需要还原出的木棍数ns

int ok;

int len; //当次需要达到的长度

int cmp(const void *a,const void *b) { int a1 = *(int *)a;

int a2 = *(int *)b; return a2 - a1; }

int used[100];

int adds() { int j = 0;

for (int i = 1;i <= n;i++) j += stick[i]; return j; }

void search(int,int,int);

void s(int x) { //x 正在还原第x根木棍

if (x > ns) { ok = 1;

printf(\ return; }

int i;

for (i = 1;i <= n;i++)

if (!used[i]) break; //找到第一根没有使用的木棍

used[i] = 1; //改变它的使用状态

search(x,stick[i],i); //搜索 used[i] = 0; //还原它的使用状态 }

void search(int num,int now,int next) { //num正在还原第num根木棍

if (ok) return;

if (now == len) { //一根木棍还原完

24

s(num + 1); //还原下一根 return; }

if (next + 1 > n) return; //总共只有n根短棍

for (int i = next + 1;i <= n;i++) if (!used[i])

if(stick[i] + now <= len) { //该木棍加上当前长度小于len

used[i] = 1; search(num,now + stick[i],i); //搜索

used[i] = 0; if (ok) return;

if (stick[i] == len - now) return; //有一根木棍长度正好等于当前差值 } }

int main () {

while (scanf(\ if (!n) break; //读数据 ok = 0; int i;

for (i = 1;i <= n;i++) scanf(\&stick[i]);

qsort(stick+1,n,sizeof(int),cmp); //快速排序，从大到小

total = adds(); //计算木棍总长度

for (i = stick[1];i <= total;i++) //从最大的木棍 到 总长度 ，依次枚举 if (total % i == 0 && !ok) { //如果该长度可以被总长度整除，且还没有ok

ns = total / i; 4 1 2 //求出一共需要还原出的木棍数ns //所有木棍使用状态清零 //当次需要达到的长度 s(1); } } return 0; }

求最小次生成树daima

//pku 1679 求最次小生成树的算法！ /*

题目描述：给定一个无向图，要求判断该图的最小生成树是否唯一，如果唯一的话输出最小生成树的权值，如果不唯一，输出Not Unique！

解题思路：要判断最小生成树是否唯一，可以求出次小生成树，看权值是否和最小生成树相等，如果相等的话说明最小生成树不唯一，否则说明最小生成树是唯一的，那么，只要求出次小生成树来就好办了。

本题可以用Kruskal或prim算法求出最小生成树来，然后依次枚举这些树边并去掉，再求最小生成树，所得的这些值的最小值就是次小生成树的值，当然，前提是去掉一条树边以后，剩下的边可以形成次小生成树。

Sample Input 2 3 3 1 2 1 2 3 2 3 1 3 4 4 1 2 2 2 3 2 3 4 2

25

Sample Output Not Unique!

#include #include #include using namespace std; const int MAXV=105; const int MAXE=5465; const int INF=0x7fffffff; int set[MAXV]; int rank[MAXV];

int num;//记录最小生成树边的个数 int st,ed;

typedef struct Edge { int st; int ed; int distance; }Edge;

Edge edge[MAXE]; Edge edge1[MAXE];

/*下面三个函数是求并查集的函数!*/ //第一函数是初始化 void Make_Set(int x) { set[x]=x; rank[x]=0; }

//返回包含x的集合中的一个代表元素 int Find_Set(int x) {

if(x!=set[x])

set[x]=Find_Set(set[x]); return set[x]; }

memset(used,0,sizeof(used)); 3 len = i;

//实现树与树的合并 void Union(int x,int y) {

x=Find_Set(x); y=Find_Set(y); if(rank[x]>rank[y]) set[y]=x; else {

set[x]=y;

if(rank[x]==rank[y]) rank[y]++; } }

bool cmp(Edge a,Edge b) {

return a.distance

/*关键函数-Kruskal算法的实现!*/ int Kruskal(int v,int e) { int i; int sum=0; for(i=1;i<=v;i++)

Make_Set(i);//每个点构成一个树也即一个集合

sort(edge+1,edge+e+1,cmp);//将边按照权值非降序排序

for(i=1;i<=e;i++)

if(Find_Set(edge[i].st)!=Find_Set(edge[i].ed))

{//如果是安全边就加sum中去 sum+=edge[i].distance; //并将包含这两棵树的集合合并 Union(edge[i].st,edge[i].ed); edge1[++num]=edge[i]; } return sum;

26

}

int Kruskal1(int v,int e) { int i; int sum=0; for(i=1;i<=v;i++)

Make_Set(i);//每个点构成一个树也即一个集合

sort(edge+1,edge+e+1,cmp);//将边按照权值非降序排序

for(i=1;i<=e;i++)

if(Find_Set(edge[i].st)!=Find_Set(edge[i].ed))

{//如果是安全边就加sum中去

if(edge[i].st==st&&edge[i].ed==ed) {continue;}

if(edge[i].st==ed&&edge[i].ed==st) {continue;}

sum+=edge[i].distance; //并将包含这两棵树的集合合并 Union(edge[i].st,edge[i].ed); } return sum; }

bool Judge(int V) {

int i;

for(i=1;i<=V-1;i++)

if(Find_Set(i)!=Find_Set(i+1)) return false; return true; }

int main() {

int i,V,E,T,min,sum; scanf(\ while(T--) {

scanf(\ for(i=1;i<=E;i++)

scanf(\ge[i].distance); num=0; min=INF;

sum=Kruskal(V,E);

//printf(\ for(i=1;i<=num;i++) {

st=edge1[i].st; ed=edge1[i].ed; int temp=Kruskal1(V,E);

if(min>temp&&Judge(V))//一定要加一个判断！看看是不是所有的点都联通！ min=temp; }

if(min==sum)

printf(\ else

printf(\ } return 0; }

NNetworking求最短网线 //PKU 1287

//Prim to compute MST

//suppose there is a unique edge between vertices

#include #include #define N 51 int ad[N][N]; int visit[N]; int mark[N]; int n; int prim(); int main()

27

{ }

int prim() {

int cnt,i,j,k,tmp,min,sum=0; memset(visit,0,sizeof(visit)); visit[1]=1; for(i=2;i<=n;i++) {

if(visit[i]==0&&mark[i]

min=mark[i]; tmp=i;

min=1e9;

for(i=2;i<=n;i++){ mark[i]=ad[1][i]; for(cnt=1;cnt<=n-1;cnt++) int i,j,k,r,x,y,cost;//r是边数 while(scanf(\ } return 0;

for(i=1;i<=n;i++){//初始化邻接矩 }

for(scanf(\{//初始化两个顶点间的权值 }

printf(\

scanf(\scanf(\if(cost

ad[x][y]=ad[y][x]=cost; for(j=1;j<=n;j++){ }

ad[i][j]=1e9;

阵均为无穷大

mark[i]中最小的一个

}

}

if(ad[tmp][i]

mark[i]=ad[tmp][i];

int i,j,k,r,x,y; float cost;//r是边数 scanf(\

scanf(\

}

for(i=1;i<=n;i++)

for(j=1;j<=n;j++) {

for(i=1;i<=n;i++) {

for(j=1;j<=n;j++) { }

ad[i][j]=1e9;

visit[tmp]=1; sum+=mark[tmp];

for(i=2;i<=n;i++){//再次初始化

mark[i](也就是将访问过的顶点集所关联的未取的带权边)

if(visit[i]==0&&ad[tmp][i]<1e9) }

return sum;

}

{ }

}//xu yao i=1;

while(i++<=n) {

}////////////////////////////////////////////////////////////////////////////////////////////////////////////// //PKU 1287

//Prim to compute MST

//suppose there is a unique edge between vertices

#include #include #include\#define N 51 float ad[N][N]; int visit[N]; float mark[N]; int n; struct xy {

int x; int y;

cost=(float)sqrt((adxy[i].x-adxy[j].x

)*(adxy[i].x-adxy[j].x)+(adxy[i].y-adxy[j].y)*(adxy[i].y-adxy[j].y)); }

float prim() { 28

int cnt,i,tmp; float sum=0,min;

}

}

printf(\if(cost

ad[i][j]=ad[j][i]=cost;

printf(\

return 0;

}adxy[N]; float prim(); int main() {

memset(visit,0,sizeof(visit)); visit[1]=1; for(i=2;i<=n;i++) {

if(visit[i]==0&&mark[i]

}

visit[tmp]=1; sum+=mark[tmp];

for(i=2;i<=n;i++){//再次初始化

}

min=mark[i]; tmp=i;

min=1e9;

for(i=2;i<=n;i++){ mark[i]=ad[1][i]; for(cnt=1;cnt<=n-1;cnt++)

AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/

struct MGraph/*定义图*/ {

Vertex vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; };

typedef struct {

Vertex adjvex; /*当前点*/ int lowcost; /*代价*/ }minside[MAX_VERTEX_NUM];

int LocateVex(MGraph G,Vertex u)//定位 { int i;

for(i=0;i

if(strcmp(u,G.vexs[i])==0)

return i;

mark[i]中最小的一个

mark[i](也就是将访问过的顶点集所关联的未取的带权边) }

最小代价生成树的各条kruskal #include #include #include #define MAX_NAME 5

#define MAX_VERTEX_NUM 20

typedef char Vertex[MAX_NAME];/*顶点名字串*/

typedef int

29

if(visit[i]==0&&ad[tmp][i]<1e9) }

return sum;

}

{ }

if(ad[tmp][i]

mark[i]=ad[tmp][i];

return -1; }

void CreateGraph(MGraph &G) {

int i,j,k,w; Vertex va,vb;

printf(\请输入无向网G的顶点数和边数(以空格为分隔)\\n\

scanf(\ printf(\请输入%d个顶点的值(<%d个字符):\\n\

for(i=0;i

for(i=0;i

for(j=0;j

printf(\请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \\n\ for(k=0;k

scanf(\ i=LocateVex(G,va); j=LocateVex(G,vb);

G.arcs[i][j]=G.arcs[j][i]=w; /*对称*/

int main() {

MGraph g; CreateGraph(g); kruskal(g); system(\ return 0; } }

void kruskal(MGraph G) {

int set[MAX_VERTEX_NUM],i,j; int k=0,a=0,b=0,min=G.arcs[a][b]; for(i=0;i

printf(\最小代价生成树的各条边为:\\n\ while(k

for(i=0;i

min=G.arcs[i][j]; a=i; b=j; }

min=G.arcs[a][b]=0x7fffffff; if(set[a]!=set[b]) {

printf(\ k++;

for(i=0;i

}

K-th number

For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2...5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.

#include #define MAX 100000 int len; struct TNode {

int left , right;

char depth;

TNode *LeftChild , *RightChild;

void construct ( int , int , int );

int GetRank ();

} Node [2 * MAX + 2];

int SortArray [18] [MAX + 2];

int Key , ls , rs;

30

void TNode :: construct ( int l , int r , int dep ) {

left = l; right = r; depth = dep;

if ( left == right ) {

scanf ( \[dep] [l] );

return;

}

int mid = ( l + r ) >> 1;

LeftChild = &Node [len ++];

LeftChild->construct( l , mid , dep + 1 );

RightChild = &Node [len ++];

RightChild->construct( mid + 1 , right , dep + 1 );

int i = left , j = mid + 1 , k = left;

while ( i <= mid && j <= r ) {

if ( SortArray [dep + 1] [i] < SortArray [dep + 1] [j] )

SortArray [dep] [k

31

++] = SortArray [dep + 1] [i ++];

else

SortArray [dep] [k ++] = SortArray [dep + 1] [j ++];

}

while ( i <= mid ) SortArray [dep] [k ++] = SortArray [dep + 1] [i ++];

while ( j <= right ) SortArray [dep] [k ++] = SortArray [dep + 1] [j ++]; }

int TNode :: GetRank () {

if ( ls <= left && right <= rs ) {

if ( SortArray [depth] [left] >= Key ) return 0;

if ( SortArray [depth] [right] < Key ) return right - left + 1;

if ( SortArray [depth] [right] == Key ) return right - left;

int low = left , high = right , mid;

while ( low + 1 < high ) {

mid = ( low +

high ) >> 1;

if ( SortArray [depth] [mid] < Key ) low = mid;

else high = mid;

}

return low - left + 1;

}

int ret = 0;

if ( ls <= LeftChild->right ) ret += LeftChild->GetRank();

if ( RightChild->left <= rs ) ret += RightChild->GetRank();

return ret; }

int main () {

int N , Q , i;

int low , high , mid , Index; scanf ( \ len = 1;

Node [0].construct( 0 , N - 1 , 0 );

for ( i = 0; i < Q; i ++ ) { scanf ( \, &ls , &rs , &Index );

32

ls --; rs --; low = 0; high = N; while ( low + 1 < high ){ mid = ( low + high ) >> 1;

Key = SortArray [0] [mid];

if ( Node [0].GetRank() >= Index ) high = mid;

else low = mid;

}

printf ( \[0] [low] ); } return 0; }

Sample Input 7 3

1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3 Sample Output 5 6 3

给定一个图判断有几个堆 题目大意：

本题主要是给定一个图的点数和相应的边，判断

一个图有多少堆

解题思路：

此题主要应用并查集来处理即先把每个节点的根节点初始化为自己，并将每个节点看成一棵树每读进一条边时，判断其根节点是否相等，如果不相等就两节点的根节点归一。并将树的数目减一，后有几棵树就有几堆。

注意事项：

当输入数据比较多时，用scanf()比用cin输入更省时。

#include

#include

#define MAXN 1000000

int set[MAXN],rank[MAXN];

int FindSet(int x) {

if(set[x]!=x)

set[x]=FindSet(set[x]);

return set[x]; }

void MakeSet(int x) {

set[x]=x;

33

rank[x]=0; }

void Link(int a,int b) {

if(rank[a]>rank[b])

set[b]=a;

else if(rank[a]

set[a]=b;

else {

set[a]=b;

rank[b]++; } }

void Union(int a,int b) {

Link(FindSet(a),FindSet(b)); }

int main()

{

int point1,point2;

int n,m,num,cas=0; int i;

while(scanf(\ {

cas++;

num=n;

for(i=1;i<=n;i++)

MakeSet(i);

for(i=0;i

{

scanf(\

if(FindSet(point1)!=FindSet(point2))

{

Union(point1,point2);

num--;

}

}

printf(\ }

return 0; }

100层楼和两个玻璃球的问题

【转】 100层楼和两个玻璃球的问题2010-04-27 13:46转载自 kewenpan最终编辑 常雅敏给你两个玻璃球,有一座100层的大厦,用最少的实验次数找出临界层,即从那一层抛下玻璃球,玻璃求刚好不破,再上一层就回破碎.玻璃球碎了之后,不可再用哦.

#include \#include \const int INF = 200000000; const int maxN = 110; int f[maxN][maxN][maxN]; int n, k; int

find(int l, int r, int k) {

if (l > r) {

return 0; }

if (k == 1) {

return r - l + 1; }

if (l == r) {

return 1; }

if (f[l][r][k] != -1)

34

{

return f[l][r][k]; } int mid;

int left, right, t; f[l][r][k] = INF;

for (mid = l; mid <= r; ++mid) {

left = find(l, mid - 1, k - 1); right = find(mid + 1, r, k); t = left > right ? left : right; f[l][r][k]

return ++f[l][r][k]; } int main() {

memset(f, -1, sizeof(f));

while (scanf(\{

printf(\} return 0; }

结果是14 分析：

题目的意思应该是

找出一个固定的方案A, 使得对于目标t为任意[1,100]里的数的时候, 找出t要扔的最多的次数 最小

因为t不同的时候, 方案A要扔的次数不一定一样, 我们就是要使得这个最多的次数最小 动态规划就好了

F(l,r,k)为 确定目标t是否在[l,r]中且手上有k

35

个棋子的最少扔子次数, 有状态转移方程: / (r-l+1) (k = 1)F(l,r,k)

= | 1 (l = r) | 0 (l > r) \\

1+min{max{F(l,mid-1,k-1),F(mid+1,r,k)}} (l<=mid<=r)

所求就是F(1,100,2).

2. 基本概念： 大前提： 1）临界层

使玻璃球破碎的最低的楼层。 2）最优解

100层中任意一层都可能是临界层，c(n)表示临界层为n层时该算法需要的测试次数，那么(c(1)+c(2)+...+c(100))/100为平均测试次数，平均测试次数最小的算法既为最优算法。 定理1：

若：a(n,m)表示有m个玻璃球，n层楼时的最优算法的测试平均值

则：a(n,m)<=a(n,m-1) a(n,m)<=a(n+1,m) 例：a(100,2)<=a(100,1) a(100,2)<=a(101,2) 定理2：

必然存在1<=k

a(n,m)=(a(k,m-1)*k+a(n-k,m)*(n-k))/n +1 例如：a(100,2)为2个玻璃球100层的最小平均测试次数。因为第一次测试点选择100层是无意义的（必然会碎，所以无任何测试价值），所以第一次测试点k是1-99中的一个数。测试结果只有两种，碎了或没碎。

如果碎了,则临界层为[1，k]中的一个数，由于减少了一个测试球，所以接下来的测试等价于求解用m-1=1个球测试k个层的最优算法，其最小测试平均值为a(k,1)

若没碎,则临界层为[k+1，100]中的一个数，当然测试球没有减少，后续的测试等价于求解用2个球测试(100-k)个层的最优算法，其最小测试平均值

为a(100-k,2)。

所以：必定存在k，使（因为已经测试了一次，所以a(k,1)要加1，同理a(100-k,2)+1） a(100,2)=((a(k,1)+1)*k+(a(100-k,2)+1)*(100-k))/100=(a(k,1)*k+a(100-k,2)*(100-k))/100+1 定理3：

设t(n,m)=a(n,m)*n，那么t(n,m)最小的算法即为最优算法 同理

必然存在1<=k

t(n,2)=t(k,1)+t(n-k,2)+n

====================================================

显然t(1,0)=t(1,1)=t(1,2)=0 n=2时，k只能为1

t(2,2)=t(1,1)+t(1,2)+2=2 t(2,1)=t(1,0)+t(1,1)+2=2

n=3时，k=1 or 2用穷举法算出口k=1时最小（k=2时同样最小，取一个即可），记为k[3]=1 t(3,2)=t(1,1)+t(2,2)+3=0+2+3=5 t(3,1)=t(1,0)+t(2,1)+3=5

n=4时，k=1 , 2 or 3 用穷举法算出口k=2时最小,记为k[4]=2

t(4,2)=t(2,1)+t(2,2)+4=2+2+4=8 t(4,1)=t(1,0)+t(3,1)+4=9

循环至100时，得出k=14时最小，记为k[100]=14 即

t(100,2)=t(14,1)+t(100-14,2)+100 到这里方案已经出来了 首先在14层测试

若碎，执行用1球测14层楼的方案，即从1层开始逐层测试

若不碎，执行用2球测86层的方案，测试层为14+k[86]=14+13=27

最后在电子表格中演算了一下：若一直不碎，依次所选的测试楼层为

36

14，13，12，11，10，9，8，7，5，4，3，2，1 其中数字代表每次上升的楼层数。 t(100,2)=1030

临界层为任意楼层的情况下,测试的平均次数为1030/100=10.3

3.投掷次数分布不均。按最坏情况估计，这种方法就多做了几次。为了使最坏情况的投掷数最小，我们希望无论临界段在哪里，总的投掷数都不变，也就是说将投掷数均匀分布。

接下来的解决方案就很容易想出了：既然第一步（确定临界段）的投掷数增加不可避免，我们就让第二步（确定临界层）的投掷数随着第一步的次数增加而减少。第一步的投掷数是一次一次增加的，那就让第二步的投掷数一次一次减少。假设第一次投掷的层数是f，转化成数学模型，就是要求f+(f-1)+...+2+1>=99，即f(f+1)/2>=99，解出结果等于14。

GDBHArich

namespace GDBHArith {

class Program {

#region 判断一个数是否是素数 ///

///

/// 如果是，返回true,否则，返回false

static bool IsPrimeNumber(int intNum) {

bool blFlag = true; //标识是否是素数

if (intNum == 1 || intNum == 2) //判断输入的数字是否是1或者2

blFlag = true;

//为bool类型变量赋值 else {

int sqr =

Convert.ToInt32(Math.Sqrt(intNum)); //对要判断的数字进行开方运算

for (int i = sqr; i >= 2; i--) //从开方后的数进行循环 {

//对要判断的数字和指定数字进行求余运算 { //如果余数为0，说明不是素数 } } } //返回bool型变量 }

#endregion

#region 判断一个数是否符合哥德巴赫猜想

///

///

/// 如果符合，返回true，否则，返回false

static bool ISGDBHArith(int intNum) {

//标识是否符合哥德巴赫猜想

if (intNum % 2 == 0 && intNum > 6) //对要判断的数字进行判断 {

for (int i = 1; i <= intNum

37

/ 2; i++)

{

bool bl1 =

IsPrimeNumber(i); //判断i是否为素数

bool bl2 = IsPrimeNumber(intNum - i); //判断intNum-i是否为素数

if (bl1 & bl2) //输出等式 intNum - i);

blFlag = true; //符合哥德巴赫猜想 } }

return blFlag; //返回bool型变量 }

#endregion

static void Main(string[] args) {

Console.WriteLine(\输入一个大于6的偶数:\提示输入信息 int intNum =

Convert.ToInt32(Console.ReadLine()); //记录输入的数字

bool blFlag =

ISGDBHArith(intNum); //判

if (intNum % i == 0) {

blFlag = false; Console.WriteLine(\

return blFlag; }

bool blFlag = false; 断是否符合哥德巴赫猜想

//如果为true，说明符合，并输出信息 {

Console.WriteLine(\能写成两个素数的和,所以其符合哥德巴赫猜想。\

if (blFlag)

intNum); } else {

Console.WriteLine(\猜想错误。\ }

Console.ReadLine(); } } } 棋盘分割

题目是中文的，意思就不说了。。分析部分见《算法艺术与信息学竞赛》（刘汝佳）116面。。。。大致如下：

1，先化简均方差公式，可以看出，只需要让每个分割后的矩形的总分的平方和尽量小，即可使均方差最小。

2，考虑左上角坐标为(x1,y1),右下角坐标为(x2,y2)的棋盘，设它的总和为s[x1,y1,x2,y2]切割k次以后得到k+1块矩形的总分平方和最小值为d[k,x1,y1,x2,y2]，则它可以沿着横线切，也可以沿着竖线切，然后选一块继续切（递归）。。 3，由1，2部可以得到状态转移方程： d[k,x1,y1,x2,y2]=min{

min{d[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2]^2,d[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2]^2}, min{d[k-1,x1,y1,x2,b]+s[x1,b+1,x2,y2]^2,d[k-1,x1,b+1,x2,y2]+s[x1,y1,x2,b]^2}} 其中：(x1<=a

k==0,d[k,x1,y1,x2,y2]=s[x1,y1,x2,y2]^2; 我的代码(记忆化搜索)： #include #include #include using namespace std; int sum[9][9];

int d[15][9][9][9][9];

38

int SUM(int x1,int y1,int x2,int y2) {

return

sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]; }

int min(int a,int b) { return a>b?b:a; }

int fun(int k,int x1,int y1,int x2,int y2) {

int t,a,b,c,e,MIN=10000000; if(d[k][x1][y1][x2][y2]!=-1) return d[k][x1][y1][x2][y2]; if(k==0) {

t=SUM(x1,y1,x2,y2); d[k][x1][y1][x2][y2]=t*t; return t*t; }

for(a=x1;a

c=SUM(a+1,y1,x2,y2); e=SUM(x1,y1,a,y2);

t=min(fun(k-1,x1,y1,a,y2)+c*c,fun(k-1,a+1,y1,x2,y2)+e*e);

if(MIN>t) MIN=t; }

for(b=y1;b

c=SUM(x1,b+1,x2,y2); e=SUM(x1,y1,x2,b);

t=min(fun(k-1,x1,y1,x2,b)+c*c,fun(k-1,x1,b+1,x2,y2)+e*e);

if(MIN>t) MIN=t; }

d[k][x1][y1][x2][y2]=MIN; return MIN;

}

int main() {

int n,i,j,s,value; double b; while(cin>>n) {

for(i=0;i<=8;i++){sum[0]=0;sum[0]=0;} for(i=1;i<=8;i++) for(j=1,s=0;j<=8;j++) {

cin>>value;s+=value; sum[j]=sum[i-1][j]+s; }

memset(d,-1,sizeof(d)); s=sum[8][8]*sum[8][8]; value=fun(n-1,1,1,8,8); value*=n;value-=s;

b=double(value)/double(n*n);

cout<

但昨天晚上写的时候，给MIN赋初值是写成MIN＝0x7fffffff，当n<=3的时候，没问题，贡献了五六次WA后，才发现n再大点，就会出现错误，但花了几个小时仍是没有找出错误，后来去掉递归，写成递推的形式，一步步调试，才找出错误。。原来很简单的道理，MIN已经是最大的int，它还要加上一些数，就溢出了，改成MIN＝10000000后，AC...

下面是递推版本的DP： #include #include #include using namespace std;

39

int sum[9][9];

int f[15][9][9][9][9];

int SUM(int x1,int y1,int x2,int y2) {

return

sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]; }

int min(int a,int b) { return a>b?b:a; } int fun(int k) {

int t,a,b,c,e,d,MIN,i,j,m,n; for(i=1;i<=8;i++) for(j=1;j<=8;j++) for(m=1;m<=8;m++) for(n=1;n<=8;n++) {

t=SUM(i,j,m,n); f[0][j][m][n]=t*t; } for(a=1;a<=k;a++) for(i=1;i<=8;i++) for(j=1;j<=8;j++) for(m=1;m<=8;m++) for(n=1;n<=8;n++) {

MIN=10000000; if((m-i+1)*(n-j+1)

for(d=i;d

e=SUM(i,j,d,n);

t=min(f[a-1][j][d][n]+c*c,f[a-1][d+1][j][m

][n]+e*e);

if(MIN>t) MIN=t;

}

for(b=j;b

e=SUM(i,j,m,b);

t=min(f[a-1][j][m]+c*c,f[a-1][b+1][m][n]+e*e);

if(MIN>t) MIN=t;

}

f[a][j][m][n]=MIN; } return f[k][1][1][8][8]; }

int main() {

int n,i,j,s,value; double b; while(cin>>n) {

for(i=0;i<=8;i++){sum[0]=0;sum[0]=0;} for(i=1;i<=8;i++) for(j=1,s=0;j<=8;j++) {

cin>>value;s+=value; sum[j]=sum[i-1][j]+s;

}

s=sum[8][8]*sum[8][8]; value=fun(n-1); value*=n; value-=s;

40

b=double(value)/double(n*n);

cout<

求单整点集B的最大权和 #include #include using namespace std; const int MAXN = 1000; vector v[MAXN]; int c[MAXN], d[MAXN]; int result, visited[MAXN]; void dfs(int u) {

d[u] = c[u]; visited[u] = true;

for(vector::size_type i = 0; i != v[u].size(); i++) {

if(! visited[v[u][i]]) { dfs(v[u][i]); if(d[v[u][i]] > 0) d[u] += d[v[u][i]]; } }

result = result > d[u] ? result : d[u]; }

int main() {

int n, x[MAXN], y[MAXN]; scanf(\

for(int i = 0; i < n; i++)

scanf(\&c[i]);

for(i = 0; i < n; i++)

for(int j = i + 1; j < n; j++)

if(abs(x[i] - x[j]) + abs(y[i] - y[j]) == 1) {

v[i].push_back(j); v[j].push_back(i); } result = 0;

memset(visited, false, sizeof(visited)); dfs(0);

printf(\ return(0);

}////////////////////////////////////////////////////////////////////////////////////////////////////////////// #include #include using namespace std; const int maxn=1000; vector v[maxn];

int c[maxn],d[maxn],result,visited[maxn]; void dfs(int u) { }

int main() {

int x[maxn],y[maxn],n,j; scanf(\

41

d[u]=c[u]; visited[u]=true;

for(vector::size_type

if(!visited[v[u][i]]) { }

result=result>d[u]?result:d[u];

dfs(v[u][i]); if(d[v[u][i]]>0)

d[u]+=d[v[u][i]];

for(i=1;i<=n;i++) {n+=i;} { { x[i]=i; y[i]=j; } ; }

((x[i]-x[j])==0 && (y[i]-y[j])==1) || ((y[i]-y[j])==1 && (x[i]-x[j])==-1)

////////////////////////////////////////////////////////////////////////////////////////////////////////////// #include \int main() {

int n,j,tmp=0; scanf(\int **a=new int*[n+1];

dfs(0);

printf(\return 0;

memset(visited,false,sizeof(visited))if(((x[i]-x[j])==0&&y([i]-y[j]==1))||

}

result=0;

v[i].push_back(j); v[j].push_back(i);

((y[i]-y[j]==1)&&x([i]-x[j]==-1))){

for(i=0;i

scanf(\for(i=0;i

for(j=0;j<=i;j++) for(int i=0;i

i=0;i!=v[u].size();i++)

for(int i=0;i

{ a[i][0]=1; a[i][i]=1;

}

for(i=0;i

scanf(\ int sum=a[0][0]; for(i=1;ia[i][j+1]) { sum+=a[i][j]; tmp=j;

} else { sum+=a[i][j+1]; tmp=j+1;

}

}

printf(\

return 0;

}

Fibonacci

42

#include void main() {

int fibonacci(int ,int num[]); int n,num[47]; while(1) {

scanf(\ if(n==-1) break;

printf(\ } }

int fibonacci(int n,int num[]) {

int i; num[0]=0; num[1]=1;

for(i=2;i<=n;i++) {

num[i]=num[i-1]+num[i-2]; }

return num[n]; }

字典树模版

用字符串构建树，从第一个字母开始，找出每个节点匹配字符窜的个数只和 #include #include #define kind 26//字母种类 struct Treenode//树的结点结构 {

int count;//这个附加变量在本题中记录遍历到该结点形成的字符串出现的次数，在不同题中可记录不同的内容。 Treenode *next[kind];//指向儿子结点

Treenode()//每个结点的初始化

43

{ count=1;

for(int i=0;i

void insert(Treenode *&root,char *word)//向以root为根结点的树中插入串word {

Treenode *location=root; int i=0,branch=0; if(location==NULL) {

location=new Treenode(); root=location; }

while(word[i]) {

branch=word[i]-'a'; if(location->next[branch])

location->next[branch]->count++;//如果该字符存在，串数量加1 else location->next[branch]=new

Treenode();//如果不存在，建新结点 i++;

location=location->next[branch]; } }

int search(Treenode *&root,char *word)//查找，与插入类似 {

Treenode *location=root; int i=0,branch=0,ans; if(location==NULL) return 0; while(word[i]) {

branch=word[i]-'a'; if(!location->next[branch])

return 0; i++;

location=location->next[branch]; ans=location->count; } return ans; }

int main() {

char word[101][10]; char ask[10]; Treenode *root=NULL; int n,i;

scanf(\ for(i=0;i

scanf(\insert(root,word[i]); }

while(scanf(\ {

printf(\} return 0; }

最小费用最大流问题 #include #include using namespace std; int n, m, kind; int s, t;

int order[51][51]; 7int store[51][51]; 8int cost[51][51][51]; 9int c[102][102]; 10int f[102][102]; 11int b[102][102]; 12int p[102]; 13int d[102];

14bool visit[102]; //表示spfa中点是否在队列中

15void spfa() //求Gf的最短路 16{

17 queue q;

18 memset(visit, 0, sizeof(visit)); 19 q.push(s); 20 visit[s] = true; 21 while(!q.empty()) 22 {

23 int u = q.front(); 24 visit[u] = false; 25 q.pop();

26 for(int v=0; v<=n+m+1; v++) 27 if(c[u][v] > f[u][v] && d[v] > d[u] + b[u][v]) 28 {

29 d[v] = d[u] + b[u][v]; 30 p[v] = u; 31 if(!visit[v]) 32 {

33 q.push(v); 34 visit[v] = true; 35 } 36 } 37 } 38}

39void mcmf() 40{

41 while(1) 42 {

43 memset(p, -1, sizeof(p)); 44 for(int i=1; i<=n+m+1; i++) 45 d[i] = 100000; 46 d[s] = 0; 47 spfa();

48 if(p[t] == -1) //表示已无增广路 49 break;

50 int minf = INT_MAX;

44

51 int it = t; 52 while(p[it] != -1) 53 {

54 minf = min(minf, c[p[it]][it] 85 bool flag = true;

86 for(int i=1; i<=kind; i++) 87 {

88 memset(c, 0, sizeof(c)); - f[p[it]][it]);

55 it = p[it]; 56 } 57 it = t;

58 while(p[it] != -1) 59 {

60 f[p[it]][it] += minf; 61 f[it][p[it]] = -f[p[it]][it];

62 it = p[it]; 63 } 64 } 65}

66int main() 67{

68 while(1) 69 {

70 scanf(\ 71 if(n==0 && m==0 && kind==0) 72 break;

73 for(int i=1; i<=n; i++) 74 for(int j=1; j<=kind; j++) 75 scanf(\&order[i][j]);

76 for(int i=1; i<=m; i++) 77 for(int j=1; j<=kind; j++) 78 scanf(\&store[i][j]);

79 for(int i=1; i<=kind; i++) 80 for(int j=1; j<=n; j++) 81 for(int k=1; k<=m; k++) 82 scanf(\&cost[i][k][j]);

83 s = 0; t = m+n+1; 84 int res = 0;

89 for(int j=1; j<=m; j++) 90 c[s][j] = store[j][i]; 91 for(int j=1; j<=m; j++) 92 for(int k=1; k<=n; k++) 93 c[j][k+m] = store[j][i];

94 for(int j=1; j<=n; j++) 95 c[j+m][t] = order[j][i]; 96 memset(b, 0, sizeof(b)); 97 for(int j=1; j<=m; j++) 98 for(int k=1; k<=n; k++) 99 {

100 b[j][k+m] = cost[i][j][k];

101 b[k+m][j] = -b[j][k+m]; //负费用，表示回流会减小费用 102 }

103 memset(f, 0, sizeof(f)); 104 mcmf();

105 for(int j=1; j<=n; j++) 106 if(c[j+m][t] != f[j+m][t])

107 {

108 flag = false; 109 break; 110 }

111 if(!flag) break; 112 for(int j=1; j<=m; j++) 113 for(int k=1; k<=n; k++) 114 res += f[j][m+k] * b[j][m+k]; 115 } 116 if(flag)

117 printf(\118 else

45

119 printf(\ continue; 120 }

121}

} 字符串最小表示

输入字符串，求该串最小字典数 #include

#include else #include

#include { #include

using namespace std; if (s[j + k] >

s[i + k]) j += k + 1; int min(int i,int j)

{ else if(i>j)

return j; i += k return i;

+ 1; }

int minP(string s)

{ k = 0;

int i = 0, j = 1, k = 0; if

int l = s.size(); }

while (1) }

{ return min(i, j);

if (i + k >= l || j + k >= } l) break;

if (s[i + k] == s[j + k])

int main () {

{ k++;

string s;

46

(i == j) j++;

int t, pos;

scanf(\

while (t--)

{

cin >> s;

s += s;

pos = minP(s);

printf(\

} }

求字符串的循环最小表示：

上面说的两个字符串同构的，并没有直接先求出Min(s)，而是通过指针移动，当某次匹配串长时，那个位置就是Min(s)。而这里的问题就是：不是给定两个串，而是给出一个串，求它的Min(s)，eg：Min(“babba”) = 4。那么由于这里并非要求两个串的同构，而是直接求它的最小表示，由于源串和目标串相同，所以处理起来既容易又需要有一些变化：我们仍然设置两个指针，p1, p2，其中p1指向s[0]，p2指向s[1]，仍然采用上面的滑动方式：

(1) 利用两个指针p1, p2。初始化时p1指向s[0], p2指向s[1]。

47

return 0;

(2) k = 0开始，检验s[p1+k] 与 s[p2+k] 对应的字符是否相等，如果相等则k++，一直下去，直到找到第一个不同，(若k试了一个字符串的长度也没找到不同，则那个位置就是最小表示位置，算法终止并返回)。则该过程中，s[p1+k] 与 s[p2+k]的大小关系，有三种情况：

(A). s[p1+k] > s[p2+k]，则p1滑动到p1+k+1处 --- 即s1[p1->p1+k]不会

是该循环字符串的“最小表示”的前缀。

(B). s[p1+k] < s[p2+k]，则p2滑动到p2+k+1处，原因同上。

(C). s[p1+k] = s[p2+k]，则 k++； if (k == len) 返回结果。

注:这里滑动方式有个小细节，若滑动后p1 == p2，将正在变化的那个指针再+1。直到p1、p2把整个字符串都检验完毕，返回两者中小于 len 的值。

(3) 如果 k == len， 则返回p1与p2中的最小

值

如果 p1 >= len 则返回p2

如果 p2 >= len 则返回p1

(4) 进一步的优化，例如：p1要移到p1+k+1时，如果p1+k+1 <= p2的话，可以直接把p1移到 p2之前，因为，p2到p2+k已经检验过了该前缀比以p1到p1+k之间任何一个位前缀都小；p2时的类似，移动到p1+1。

至此，求一个字符串的循环最小表示在O(n)时间实现，感谢大牛的论文。其中实现时的小细节“如果滑动后p1 == p2，将正在变化的那个指针再+1”，开始没有考虑，害得我想了几个小时都觉得无法进行正确的移动。具体例题有两个：

http://acm.zju.edu.cn 的2006和1729题。一个是10000规模一个是100000规模。运行时间前者是0S，后者是0.05S。 is it a tre

输入若干节点，判断是不是树 #include #include #include #define N 100

typedef struct {

int x, y; }node;

48

node nodes[N];

int t, parent[N], rank[N], num[N], count;

int find(int x) {

int y, z;

y = x;

while(parent[y]!= y) y = parent[y]; while(x != y) {

z = parent[x]; parent[x] = y; x = z; } return y; }

void _union(int x, int y) {

if(rank[x] > rank[y]) parent[y] = x; else {

if(rank[x] == rank[y]) rank[y]++; parent[x] = y; } }

void fun(int n) {

int i, x, y; int ok = 0; if(count != n+1) ok = 1; else {

for(i=0; i

x = find(nodes[i].x);

y = find(nodes[i].y); if(x == y) {

ok = 1; break; } else

_union(nodes[i].x, nodes[i].y); } } t++; if(ok)

printf(\t);

else printf(\}

int cmp(const void *p, const void *q) {

return *(int *)p > *(int *)q ? 1 : -1; }

int main() {

int i, j, k, s; int a, b, c; k = 0; s = 0;

while(scanf(\ {

if(a == -1 && b == -1) break; if(!a && !b) {

if(!k) { t++;

printf(\

49

tree.\\n\

continue; }

qsort(num, s, sizeof(num[0]), cmp);

count = 1; c = num[0]; for(i=1; i

if(num[i] != c) {

count ++; c = num[i]; } } fun(k); k = 0; s = 0;

memset(num, 0, sizeof(num)); memset(nodes, 0, sizeof(nodes));

memset(rank, 0, sizeof(rank)); continue; }

nodes[k].x = a; nodes[k].y = b; parent[a] = a; parent[b] = b; num[s++] = a; num[s++] = b; k++; } return 0; } Network

给出节点个数m和边数n，下面n行给出边(x,y)以及权值w，求最小生成树的最大边，并把生成树的每条边输出来

Andrew要在公司里用电缆连接n个集线器，要用总

长度最小的线连接，求出其中最长的那根电缆。 也就是告诉n个顶点，m条边，求最小生成树的最大边。并把生成树的每条边输出来，Sample里面的输出有问题，应该是三条。

给出节点个数m和边数n，下面n行给出边(x,y)以及权值w。输出第一行为最小生成树中的最大边权值，第二行为一个可行生成树方案的边数k，下面k行为可行生成树的k条边。题目是Special Judge，意思就是不具有唯一解，可能有多解，样例输出为以下结果也可算对。 1 3 1 3 2 4 2 3

一样按照Kruskal解题即可，结果虽然不唯一，但是最小生成树一定是可行解之一。将边加入生成树时记录最大权值和边信息然后输出即可。 #include #include #define MAX 15001

/* 定义边(x,y)，权为w */ typedef struct {

edge e[MAX]; edge v[MAX];

/* rank[x]表示x的秩 */ int rank[MAX];

/* father[x]表示x的父节点 */ int father[MAX];

/* 比较函数，按权值非降序排序 */ int cmp(const void *a, const void *b) {

50

int x, y; int w;

}

return (*(edge *)a).w - (*(edge *)b).w;

/* 初始化集合 */ void Make_Set(int x) { }

/* 查找x元素所在的集合,回溯时压缩路径 / int Find_Set(int x) { }

/* 合并x,y所在的集合 */ void Union(int x, int y) { }

if (x == y) return; if (rank[x] > rank[y]) { } else { }

if (rank[x] == rank[y]) { }

father[x] = y;

rank[y]++; father[y] = x; if (x != father[x]) { }

return father[x];

father[x] = Find_Set(father[x]); father[x] = x; rank[x] = 0;

}edge;

本文来源：https://www.bwwdw.com/article/uvv5.html