acm基础50题之数论

poj 1061 青蛙的约会

这题用的是解线性同余方程的方法，之前没接触到过，搜索资料后看到一个人的博客里面讲的很好就拷贝过来了。内容如下：

对于方程：ax≡b(mod m)，a，b，m都是整数，求解x 的值，这个就是线性同余方程。符号说明：

mod表示：取模运算

ax≡b(mod m)表示：(ax - b) mod m = 0，即同余

gcd(a,b)表示：a和b的最大公约数

求解ax≡b(mod n)的原理：对于方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整数。而ax≡b(mod n)的解可以由x，y来堆砌。具体做法如下：

第一个问题：求解gcd(a,b)

定理一：gcd(a,b) = gcd(b,a mod b)

欧几里德算法

int Euclid(int a,int b)

{

if(b == 0)

return a;

else

return Euclid(b,mod(a,b));

}

附：取模运算

int mod(int a,int b)

{

if(a >= 0)

return a % b;

else

return a % b + b;

}

第二个问题：求解ax + by = gcd(a,b)

定理二：ax + by = gcd(a,b)= gcd(b,a mod b) = b * x' + (a mod b) * y'

= b * x' + (a - a / b * b) * y'

= a * y' + b * (x' - a / b * y')

= a * x + b * y

则：x = y'

y = x' - a / b * y'

以上内容转自https://www.doczj.com/doc/9c10713363.html,/redcastle/blog/item/934b232dbc40d336349bf7e4.html

由这个可以得出扩展的欧几里德算法：

int exGcd(int a, int b, int &x, int &y) {

if(b == 0)

{

x = 1;

y = 0;

return a;

}

int r = exGcd(b, a % b, x, y);

int t = x;

x = y;

y = t - a / b * y;

return r;

}

代码：

#include

#include

#include

#include

using namespace std;

__int64 mm,nn,xx,yy,l;

__int64 c,d,x,y;

__int64 modd(__int64 a, __int64 b)

{

if(a>=0)

return a%b;

else

return a%b+b;

}

__int64 exGcd(__int64 a, __int64 b) {

if(b==0)

{

x=1;

y=0;

return a;

}

__int64 r=exGcd(b, a%b);

__int64 t=x;

x=y;

y=t-a/b*y;

return r;

}

int main()

{

scanf("%I64d %I64d %I64d %I64d %I64d",&xx,&yy,&mm,&nn,&l);

if(mm>nn) //分情况

{

d=exGcd(mm-nn,l);

c=yy-xx;

}

else

{

d=exGcd(nn-mm,l);

c=xx-yy;

}

if(c%d != 0)

{

printf("Impossible\n");

return 0;

}

l=l/d;

x=modd(x*c/d,l); ///取模函数要注意

printf("%I64d\n",x);

system("pause");

return 0;

}

POJ 1142 SmithNumber

题意：寻找最接近而且大于给定的数字的SmithNumber

什么是SmithNumber？

用sum(int)表示一个int的各位的和，那一个数i如果是SmithNumber,则sum（i） =

sigma( sum(Pj )),Pj表示i的第j个质因数。例如4937775= 3*5*5*65837，4+9+3+7+7+7+5 = 42，3+5+5+（6+5+8+3+7） = 42，所以4937775是SmithNumber。

思路：要寻找大于给定数字且最接近给定数字的SmithNumber，只要将给定数字不断的加1，判断它是否是SmithNumber就行了，如果是SmithNumber就立即输出。

但是如何判断是否是SmithNumber呢？首先就是要对数字进行质因数分解。质因数分解要保证因子都是质数。这里先介绍一个如何判断一个数int是否是质数呢，如果对于这个数，i = 2.....sqrt(int)都不是它的约数，那int就是一个质数。所以我们可以将i初始化为2，然后不断递增i，看i是否是int的一个约数，如果是的话那i就是int的一个质因数（因为这个数是从2开始第一个可以整除int的数，它不可能是一个可以分解的合数，否则，它的约数在它之前就整除int），然后将int除以该质因数，重置i为2，重新对int判断它是否是质数。这样最后剩下的int一定是一个质数，从而对int进行了质因数分解

然后就很简单的将数字各质因数的各位加起来，看和是否等于该数字的各位和，如果相等那它可能就是SmithNumber，为什么说只是可能呢，因为这个数可能是质数，但是质数不是SmithNumber。

#include

#include

int Sum( int number )

{

int sum = 0;

while( number != 0 )

{

sum += number % 10;

number /= 10;

}

return sum;

}

bool SmithNumber( int number )

{

int i = 2;

int temp = number;

int sumOfNumber = Sum( number );

int sum = 0;

while( i <= (int)sqrt( (double)number ) )

{

if ( number % i ==0 )

{

sum += Sum( i );

number /= i;

i = 2;

}

else

{

++i;

}

//以上的代码做了无谓的计算，可用下面的代码，更新于20090904 //while( number % i == 0 )

//{

// sum += sum(i);

// number /= i;

//}

// ++i;

}

sum += Sum( number );

if ( sum == sumOfNumber && number != temp )

{

return true;

}

else

{

return false;

}

}

int main()

{

while( true )

{

int num;

scanf("%d",&num );

if ( num == 0 )

{

break;

}

while( true )

{

if ( SmithNumber(++num))

{

printf("%d\n", num);

break;

}

}

}

return 0;

}

ACM——POJ 2262（Goldbach's Conjecture）

题目地址：https://www.doczj.com/doc/9c10713363.html,/JudgeOnline/problem?id=2262

题目思路：对于任何一个偶数 n，从 x = 1 和 y = n - 1 开始，看 x、y 是否是质数，不是则 x += 2, y += 2

这题需要开很大的内存，我 RE n 次，居然是因为数组开太小了，我这题耗时不是很理想，但我的耗内存

在我看到的中是最小的，所以看来 OJ 上的题只要能开内存的就尽量开。估计我这题用栈耗时了。

#include

#include

#include

#include

#include

#include

using namespace std;

// 判断是否为质数的函数

int IsPrime ( int x )

{

int i;

if( x < 2 )

return 0;

for( i = 2; i <= (int) ( sqrt( (double)x + 0.5 ) ); i++ )

if( x % i == 0)

return 0;

return 1;

}

int main()

{

// 输入数，输入数 / 2 向上延伸，输入数 / 2 向下延伸，输入数 / 2

int m_Input, m_Num_Max, m_Num_Min, m_InputToTwo;

// 总体输出

char m_Output[ 1000000 ];

memset( m_Output, 0, 1000000 );

// 标识 m_Output 的 Pos

int m_Output_Pos = 0;

// 是否找到标识

bool b_Find;

// 栈

stack m_Stack;

// 临时数

int m_Value_Top;

// 循环输入

while ( scanf( "%d", &m_Input ) && ( m_Input != 0 ) )

{

b_Find = true;

// m_Input 肯定是一个偶数

m_InputToTwo = m_Input / 2;

// 置值

m_Num_Max = m_Input - 1;

m_Num_Min = 1;

// 寻找，直至都为素数或者找不到为止

while ( ( !IsPrime( m_Num_Max ) ) || ( !IsPrime( m_Num_Min ) ) )

{

// 否则，前进 & 后退 2 格

m_Num_Max -= 2;

m_Num_Min += 2;

// 如果发生如下情况，则输出 "Goldbach's conjecture is wrong."

if ( ( m_Num_Max < m_InputToTwo ) || ( m_Num_Min > m_InputToTwo ) ) {

char* m_TempChar = "Goldbach's conjecture is wrong.\n";

strcat( m_Output, m_TempChar );

b_Find = false;

m_Output_Pos += strlen( m_TempChar );

break;

}

}

// 如果找到了

if ( b_Find )

{

// 将 m_Input 转换为字符串存入 m_Output

while ( m_Input != 0 )

{

m_Value_Top = m_Input % 10;

m_Stack.push( m_Value_Top );

m_Input /= 10;

}

while ( !m_Stack.empty() )

{

m_Value_Top = m_Stack.top();

m_Output[ m_Output_Pos++ ] = m_Value_Top + 48; m_Stack.pop();

}

// 加入 =

m_Output[ m_Output_Pos++ ] = ' ';

m_Output[ m_Output_Pos++ ] = '=';

m_Output[ m_Output_Pos++ ] = ' ';

// 将 m_Num_Min 转换为字符串存入 m_Output

while ( m_Num_Min != 0 )

{

m_Value_Top = m_Num_Min % 10;

m_Stack.push( m_Value_Top );

m_Num_Min /= 10;

}

while ( !m_Stack.empty() )

{

m_Value_Top = m_Stack.top();

m_Output[ m_Output_Pos++ ] = m_Value_Top + 48; m_Stack.pop();

}

// 加入 +

m_Output[ m_Output_Pos++ ] = ' ';

m_Output[ m_Output_Pos++ ] = '+';

m_Output[ m_Output_Pos++ ] = ' ';

// 将 m_Num_Max 转换为字符串存入 m_Output

while ( m_Num_Max != 0 )

{

m_Value_Top = m_Num_Max % 10;

m_Stack.push( m_Value_Top );

m_Num_Max /= 10;

}

while ( !m_Stack.empty() )

{

m_Value_Top = m_Stack.top();

m_Output[ m_Output_Pos++ ] = m_Value_Top + 48;

m_Stack.pop();

}

// 加入 \n

m_Output[ m_Output_Pos++ ] = '\n';

}

}

// 输出

printf( "%s", m_Output );

system( "pause" );

return 0;

}

POJ 2407 Relatives

这题从题意可以看出就是求比从1~n - 1从有几个数和n没有公共因子，通常的算法很简单就能够想到，我开始也是按通常的做法写了一个，觉得

可能会TLE, 果不其然，后来上网查了一下，知道了欧拉函数，这个就是求比n小的数中与n互质（也就是没有公共因子）的算法，看来还是那些经典的算法效率比较高，比纯用暴力试探高多了...

欧拉函数描述如下：

利用欧拉函数和它本身不同质因数的关系，用筛法计算出某个范围内所有数的欧拉函数值。

欧拉函数和它本身不同质因数的关系：欧拉函数ψ（Ｎ）＝Ｎ｛∏ｐ｜Ｎ｝（１－１/ｐ）。（Ｐ是数Ｎ的质因数）

如：

ψ（１０）＝１０×（１－１/２）×（１－１/５）＝４；

ψ（３０）＝３０×（１－１/２）×（１－１/３）×（１－１/５）＝８；

ψ（４９）＝４９×（１－１/７）＝４２。

注意的是P是N的质因子，这里求质因子还是不能够用常规的判断这个数是不是质数，这样的话可能还会TLE, 网上学到他们用的一个while() 循环，感觉还挺巧的，学习了...

#include

#include

int enlerFun(int n)

{

int count = n;

int i = 2;

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

if(n % i == 0)

{

count -= count / i;

while(n % i == 0)

n /= i;

}

return count;

}

int main()

{

int inputVal = 0;

int count = 0;

while(scanf("%d", &inputVal) && inputVal != 0)

{

count = enlerFun(inputVal);

printf("%d\n", count);

}

return 0;

}

POJ 1811 Prime Test

Miller Robin素性测试 + Pollard rho寻找素因子

Miller Robin 和 Pollard rho的理论想非常强，细节这里就不说了，可以参考

算法导论第31章

#include

#include

#include

#define MAX_L 64 //最长位数

#define TIMES 8 //miller robin素性测试的测试次数

#define MAX_VAL (pow(2.0, 60)) //定义最大值

#define CVAL 200

using namespace std;

//最小的素因子

__int64 minFactor;

//(1)计算a * b mod n, 思路: 利用b的二进制表示进行拆分计算

//(2)例如: b = 1011101那么a * b mod n = (a * 1000000 mod n + a * 10000 mod n + a * 1000 mod n + a * 100 mod n + a * 1 mod n) mod n

//(3)思路就是上面描述的那样, 那么可以用从低位往高位遍历b, 并用a来记录当前位为1的值，每次遇到b当前位为

//1就将结果值加上a并 mod n，然后a 要乘以2

__int64 multAndMod(__int64 a, __int64 b, __int64 n)

{

a = a % n;

__int64 res = 0;

while(b)

{

//当前位为1

if(b & 1)

{

//加上当前权位值

res += a;

//相当于mod n

if(res >= n) res -= n;

}

//乘以2，提高一位

a = a<<1;

//mod n

if(a >= n) a -= n;

b = b >> 1;

return res;

}

//(1)计算a ^ b mod n, 思路: 和上面类似，也是利用b的二进制表示进行拆分计算

//(2)例如: b = 1011101那么a ^ b mod n = [(a ^ 1000000 mod n) * (a ^ 10000 mod n) * (a ^ 1000 mod n) * (a ^ 100 mod n) * (a ^ 1 mod n)] mod n

//(3)思路就是上面描述的那样, 那么可以用从低位往高位遍历b, 并用a来记录当前位为1的值，每次遇到b当前位为

//1就将结果乘上a并 mod n，然后a 要乘以a以提升一位

__int64 modAndExp(__int64 a, __int64 b, __int64 n)

{

a = a % n;

__int64 res = 1;

while(b >= 1)

{

//遇到当前位为1，则让res * 当前a并mod n

if(b & 1)

res = multAndMod(res, a, n);

//a * a以提升一位

a = multAndMod(a, a, n);

b = b >> 1;

}

return res;

}

//MillerRobin素性测试，true:素数，flase:合数

bool millerRobin(__int64 a, __int64 n)

{

__int64 u = 0, cur = n - 1;

int t = 0;

bool find1 = false;

while(cur != 0)

{

if(!find1)

{

int pb = cur % 2;

if(pb == 0) t++;

else find1 = true;

}

if(find1)

break;

cur = cur / 2;

u = cur;

cur = modAndExp(a, u, n);

__int64 now;

for(int p = 1; p <= t; p++)

{

now = modAndExp(cur, 2, n);

if(cur != 1 && now == 1 && cur != n - 1)

{

//printf("%d %d\n", cur, now);

return false;

}

cur = now;

}

if(cur != 1)

{

//printf("a:%I64d u:%I64d n:%I64d val:%I64d\n", a, u, n, start); return false;

}

//printf("a:%I64d u:%I64d n:%I64d val:%I64d\n", a, u, n, start);

return true;

}

//利用Miller Robin对n进行n次素性测试

bool testPrime(int times, __int64 n)

{

if(n == 2) return true;

if(n % 2 == 0) return false;

__int64 a; int t;

srand(time(NULL));

for(t = 1; t <= times; t++)

{

a = rand() % (n - 1) + 1;

if(!millerRobin(a, n)) return false;

}

return true;

}

;

void getSmallest(__int64 n, int c)

{

if(n == 1) return;

//判断当前因子是否为素数

if(testPrime(TIMES, n))

{

if(n < minFactor) minFactor = n;

return;

}

__int64 val = n;

//循环，知道找到一个因子

while(val == n)

val = PollardRho(n, c--);

//二分

getSmallest(val, c);

getSmallest(n / val, c);

}

int main()

{

int caseN;

__int64 n;

scanf("%d", &caseN);

while(caseN--)

{

scanf("%I64d", &n);

minFactor = MAX_VAL;

if(testPrime(TIMES, n)) printf("Prime\n"); else

{

getSmallest(n, CVAL);

printf("%I64d\n", minFactor);

}

}

return 0;

}

poj 2447 RSA

密码学:RSA公钥密码

#include

#include

#include

#include

using namespace std;

typedef unsigned __int64 u64;

#define MAX 30

#define MAXN 5

u64 len, dig, limit;

u64 factor[MAXN];

u64 mod(u64 a, u64 b, u64 n){

if(!a)return 0;

else return ( ((a&dig)*b)%n + (mod(a>>len,b,n)<

}

u64 by(u64 a, u64 b, u64 n){

u64 p;

p = 8, len = 61;

while(p

p<<=4;

len -=4;

}

dig = ((limit/p)<<1) - 1;

return mod(a,b,n);

}

u64 random(){//产生随机数

u64 a;

a = rand();

a *= rand();

a *= rand();

a *= rand();

return a;

}

u64 square_multiply(u64 x, u64 c, u64 n){//(x^c)%n快速算法

u64 z=1;

while(c){

if(c%2==1)z = by(z,x,n);

x = by(x,x,n);

c=(c>>1);

}

return z;

}

bool Miller_Rabin(u64 n){//Miller_Rabin素数测试

if(n<2)return false;

if(n==2)return true;

if(!(n&1))return false;

u64 k = 0, i, j, m, a;

m = n - 1;

while(m%2==0)m=(m>>1),k++;

for(i=0;i

a = square_multiply(random()%(n-1)+1, m, n);//平方乘 if(a==1)continue;

for(j=0;j

if(a==n-1)break;

a = by(a,a,n);

}

if(j

return false ;

}

return true;

}

u64 gcd(u64 a,u64 b){

if(a==0) return b;

else return gcd(b%a,a);

}

u64 f(u64 x, u64 n ){

return (by(x,x,n)+1)%n;

}

u64 Pollard(u64 n){

if(n<=2)return 0;

if(!(n&1))return 2;

u64 i, p, x,xx;

for(i=0;i

xx = f(x,n);

p = gcd((xx+n-x)%n , n);

while(p==1){

x = f(x,n);

xx = f(f(xx,n),n);

p = gcd((xx+n-x)%n,n)%n;

}

if(p)return p;

}

return 0;

}

u64 prime(u64 a){

if(Miller_Rabin(a))return a;

u64 t = Pollard(a);

if(t!=0)

{return prime(t);}

}

u64 Euclid(u64 a,u64 b,__int64 &x,__int64 &y)

{

if(b==0)

{

x=1,y=0;

return a;

}

u64 t,d;

if(b!=0)

d=Euclid(b,a%b,x,y);

t=x;

x=y;

if(b!=0)

y=t-a/b*y;

return d;

}

int main(){

u64 c,e,n,i,j,m,t,n0,T,ans,l;

__int64 T0,x,y,d;

limit = 1;

limit = limit<<63;

while(scanf("%I64u%I64u%I64u",&c,&e,&n)!=EOF){

m=0;n0=n;

while(n%2==0){n/=2;factor[m++]=2;}

while(n>1){

if(Miller_Rabin(n))break;

t = prime(n);

factor[m++] = t;

if(t!=0)

n/=t;

}

if(n>1)factor[m++]=n;

//for(l=0;l

Euclid(e,T,x,y);

d=x;

//printf("%I64d\n",d);

//while(d<0)d+=T0;

d=(d%T0+T0)%T0;

//d=(__int64)d;

// printf("%I64d %I64d\n",d,T0);

ans=square_multiply(c,(u64)d,n0);

printf("%I64u\n",ans);

}

}

ACM经典算法及配套练习题

POJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,p oj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序(poj1094) (5)二分图的最大匹配(匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串(poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253) (6)堆 (7)trie树(静态建树、动态建树) (poj2513) 四.简单搜索 (1)深度优先搜索(poj2488,poj3083,poj3009,poj1321,poj2251) (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 五.动态规划 (1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书page149): 1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159) 3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 六.数学 (1)组合数学:

(2020年编辑)ACM必做50题的解题-数论

poj 1061 青蛙的约会 这题用的是解线性同余方程的方法，之前没接触到过，搜索资料后看到一个人的博客里面讲的很好就拷贝过来了。内容如下： 对于方程：ax≡b(mod m)，a，b，m都是整数，求解x 的值，这个就是线性同余方程。符号说明： mod表示：取模运算 ax≡b(mod m)表示：(ax - b) mod m = 0，即同余 gcd(a,b)表示：a和b的最大公约数 求解ax≡b(mod n)的原理：对于方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整数。而ax≡b(mod n)的解可以由x，y来堆砌。具体做法如下： 第一个问题：求解gcd(a,b) 定理一：gcd(a,b) = gcd(b,a mod b) 欧几里德算法 int Euclid(int a,int b) { if(b == 0) return a; else return Euclid(b,mod(a,b)); } 附：取模运算 int mod(int a,int b) { if(a >= 0) return a % b; else return a % b + b; } 第二个问题：求解ax + by = gcd(a,b) 定理二：ax + by = gcd(a,b)= gcd(b,a mod b) = b * x' + (a mod b) * y' = b * x' + (a - a / b * b) * y' = a * y' + b * (x' - a / b * y') = a * x + b * y 则：x = y' y = x' - a / b * y' 以上内容转自https://www.doczj.com/doc/9c10713363.html,/redcastle/blog/item/934b232dbc40d336349bf7e4.html

ACM必做50题——数学

1、POJ 2249 Binomial Showdown 组合数学。 高精度，也可把分子分母的数组进行两两约分 #include using namespace std; double c(int c,int k) { double a=1; int i,j=2; for(i=c;i>c-k;i--) a=a*i/(c-i+1); return a; } int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF && (n!=0 || k!=0)) { if(k>n/2 )k=n-k; printf("%.0lf\n",c(n,k)); } return 0; } 2、poj 1023 the fun number system （经典进位制） 题意：一种由2进制衍生出来的进制方法（我们暂且称为“类2进制”）； 标明'n'的位置上原2进制该位的权重要乘上-1，才是现在进制方法该位的权重； 譬如说；pnp对于的能表示的数2来说就是110；即1*2^2+(-1)*1*2^1+1*2^0=2; 算法：这是数论中的进位制问题，我们可以仿照原来的求一个数二进制表示方法； 但首先，我们应该考虑几个问题； ①k位这种类2进制的表示范围； 显然，当给出的'p','n'序列中，我们将所有p的位置都置为1其余位是0，此时最大；当我们将所有n的位置置为1，其余为0，此时最小；不过当我们求最大限max和最小限min时会

有一个溢出问题；比如64位全是p的序列，那么max会溢出，值为-1；同理min在全是n 时也会溢出，为1；显然是max>=0,min<=1,溢出时产生异常，依次可以判断； ②是否是最大限和最小限之间的数都能表示呢？ 都可以，而且能够表示的数是2^k个，这个原始2进制是一样的；因为每个位上要么是0，要么是1，而且每个位上的权重唯一的，不能通过其他位的01组合获得；最后，我们就可以仿照原始二进制来算在类2进制下的表示；不断求N的二进制最后一位和右移；如果取余是1，则该位上一定是1，如果该位对于字母为‘n’，则高位应该再加1；这里对2取余可能会出错，因为对于负数，补码的表示，最后一位一定是和原码一样的每次的右移后(有时需先加1）补码表示正好符合要求（可找实例验证）； #include using namespace std; __int64 N,M; char s[100],res[100]={'\0'}; int main() { int T;scanf("%d",&T); int i,j; __int64 _max,_min; char ch; while(T--) { scanf("%I64d",&N); scanf("%s",s); _max=0;_min=0; for(i=0;i_max&&_max>=0)) puts("Impossible"); //注意防止64位数的溢出； else { memset(res,'\0',sizeof(res)); for(i=N-1;i>=0;i--) { int flag=0; if(M&1) //这里不能是平常的%2； { res[i]='1';

ACM数论方面十道基础题目详解

1、公约数和公倍数 https://www.doczj.com/doc/9c10713363.html,/JudgeOnline/problem.php?pid=40 这道题目是非常基础的题目，在学习了欧几里德算法之后，应该很好就能做的出来了。注意两个数的最小公倍数和最大公约数之间有关系为： a*b=gcd(a,b)*lcm(a,b); 代码如下： #include using namespace std; inline int Gcd(int m,int n) //求最大公约数 { if (m==0) return n; return Gcd(n%m,m); } int main() { int n,a,b,g; cin>>n; while(n--) { cin>>a>>b; g=Gcd(a,b); cout<

?????≡≡≡)33(mod ) 28(mod )23(mod d n e n p n 那么找到k1、k2、k3满足： k1：k1%23==0&&k1%28==0&&k1%33==1 k2：k2%33==0&&k2%28==0&&k2%23==1 k3：k3%33==0&&k3%23==0&&k3%28==1 则n=k2*p+k3*e+k1*i+k*21252； 代码如下： #include int main() { int n,a,b,c,t; while(scanf("%d%d%d%d",&a,&b,&c,&t),~a) { n=(5544*a+14421*b+1288*c)%21252-t; if(n<=0) n+=21252; printf("%d\n",n); } } 3、韩信点兵 https://www.doczj.com/doc/9c10713363.html,/JudgeOnline/problem.php?pid=34 这个题目也是很经典的中国剩余问题类的题目，思路跟上面差不多这道题目因为数据范围很小实际上暴力就可以过，但是这个题目不失为练习中国剩余的很好题目，所以建议大家用中国剩余定理做一下。 直接给出代码： 暴力求解代码： #include main() { int a,b,c,n; scanf("%d%d%d",&a,&b,&c); for(n=11;n<100;n++) if(n%3==a&&n%5==b&&n%7==c) printf("%d\n",n); } 中国剩余定理思路代码：

数论50题

数论50题 1．由1，3，4，5，7，8这六个数字所组成的六位数中，能被11整除的最大的数是多少？ 【分析】各位数字和为1+3+4+5+7+8=28 所以偶数位和奇数位上数字和均为14 为了使得该数最大，首位必须是8，第2位是7，14-8=6 那么第3位一定是5，第5位为1 该数最大为875413。 2．请用1，2，5，7，8，9这六个数字（每个数字至多用一次）来组成一个五位数，使得它能被75整除，并求出这样的五位数有几个？ 【分析】75=3×25 若被3整除，则各位数字和是3的倍数，1+2+5+7+8+9=32 所以应该去掉一个被3除余2的，因此要么去掉2要么去掉8 先任给一个去掉8的，17925即满足要求 1）若去掉8 则末2位要么是25要么是75，前3位则任意排，有3！=6种排法 因此若去掉8则有2*6=12个满足要求的数 2）若去掉2 则末2位只能是75，前3位任意排，有6种排法 所以有6个满足要求 综上所述，满足要求的五位数有18个。 3．已知道六位数20□279是13的倍数，求□中的数字是几？ 【分析】根据被13整除的判别方法，用末三位减去前面的部分得到一个两位数，十位是7，个位是（9-□），它应该是13的倍数，因为13|78,所以9-□=8 □中的数字是1 4．某自然数，它可以表示成9个连续自然数的和，又可以表示成10个连续自然数的和，还可以表示成11个连续自然数的和，那么符合以上条件的最小自然数是？（2005全国小学数学奥赛） 【分析】可以表示成连续9个自然数的和说明该数能被9整除，可以表示成连续10个自然数的和说明该数能被5整除，可表示成连续11个自然数的和说明该数能被11整除 因此该数是[9,5,11]=495，因此符合条件的最小自然数是495。 5．一次考试中，某班同学有考了优秀，考了良好，考了及格，剩下的人不及格，已知该班同学的人数不超过50，求有多少人不及格？ 【分析】乍一看这应该是一个分数应用题，但实际上用到的却是数论的知识，由于人数必须是整数，所以该班同学的人数必须同时是2，3，7的倍数，也就是42的倍数，又因为人数不超过50，所以只能是42人，因此不及格的人数为（1---）×42=1人 6．（1）从1到3998这3998个自然数中，有多少个能被4整除？ （2）从1到3998这3998个自然数中，有多少个数的各位数字之和能被4整除？ （第14届迎春杯考题） 【分析】（1）3998/4=999….6所以1-3998中有996个能被4整除的 （2）考虑数字和，如果一个一个找规律我们会发现规律是不存在的 因此我们考虑分组的方法 我们补充2个数，0000和3999，此外所有的一位两位三位数都在前面加上0补足4位 然后对这4000个数做如下分组

数论

断断续续的学习数论已经有一段时间了，学得也很杂，现在进行一些简单的回顾和总结。学过的东西不能忘啊。。。 1、本原勾股数： 概念：一个三元组(a,b,c)，其中a,b,c没有公因数而且满足：a^2+b^2=c^2 首先，这种本原勾股数的个数是无限的，而且构造的条件满足： a=s*t,b=(s^2-t^2)/2,c=(s^2+t^2)/2 其中s>t>=1是任意没有公因数的奇数！ 由以上概念就可以导出任意一个本原勾股数组。 2、素数计数（素数定理） 令π(x)为1到x中素数的个数 19世纪最高的数论成就就是以下这个玩意儿： lim(x->∞){π(x)/(x/ln(x))}=1 数论最高成就，最高成就！！！有木有！！！ 3、哥德巴赫猜想(1+1) 一个大偶数(>=4)必然可以拆分为两个素数的和，虽然目前还没有人能够从理论上进行证明，不过我根据科学家们利用计算机运算的结果，如果有一个偶数不能进行拆分，那么这个偶数至少是一个上百位的数！！ 所以在ACM的世界中（数据量往往只有2^63以下）哥德巴赫猜想是成立的！！所以拆分程序一定能够实现的 4、哥德巴赫猜想的推广 任意一个>=8的整数一定能够拆分为四个素数的和 证明： 先来说8=2+2+2+2，（四个最小素数的和）不能再找到比2小的素数了，所以当n小于8，就一定不可能拆分为四个素数的和！ 那么当n大于等于8，可以分情况讨论： （1）n&1==0(n为偶数)，那么n就一定可以拆分为两个偶数的和 那么根据哥德巴赫猜想，偶数可以拆分为两个素数的和，于是，n一定可以拆分为四个素数的和 （2）n&1==1(n为奇数)，n一定可以拆分为两个偶数+1 由于有一个素数又是偶数，2，那么奇数一定有如下拆分：2+3+素数+素数 得证。

ACM入门之新手入门

ACM入门之新手入门 1.ACM国际大学生程序设计竞赛简介 1)背景与历史 1970年在美国T exasA&M大学举办了首次区域竞赛，从而拉开了国际大学生程序设计竞赛的序幕。1977年，该项竞赛被分为两个级别：区域赛和总决赛，这便是现代ACM竞赛的开始。在亚洲、美国、欧洲、太平洋地区均设有区域赛点。1995至1996年，来自世界各地的一千多支s代表队参加了ACM区域竞赛。ACM大学生程序设计竞赛由美国计算机协会（ACM）举办，旨在向全世界的大学生提供一个展示和锻炼其解决问题和运用计算机能力的机会，现已成为全世界范围内历史最悠久、规模最大的大学生程序设计竞赛。 2)竞赛组织 竞赛在由各高等院校派出的3人一组的队伍间进行，分两个级别。参赛队应首先参加每年9月至11月在世界各地举行的“区域竞赛(Regional Contest)”。各区域竞赛得分最高的队伍自动进入第二年3月在美国举行的“总决赛(Final Contest)”，其它的高分队伍也有可能被邀请参加决赛。每个学校有一名教师主管队伍，称为“领队”(faculty advisor)，他负责选手的资格认定并指定或自己担任该队的教练(coach)。每支队伍最多由三名选手(contestant)组成，每个选手必须是正在主管学校攻读学位的学生。每支队伍最多允许有一名选手具有学士学位，已经参加两次决赛的选手不得再参加区域竞赛。 3)竞赛形式与评分办法 竞赛进行5个小时，一般有6~8道试题，由同队的三名选手使用同一台计算机协作完成。当解决了一道试题之后，将其提交给评委，由评委判断其是否正确。若提交的程序运行不正确，则该程序将被退回给参赛队，参赛队可以进行修改后再一次提交该问题。 程序运行不正确是指出现以下4种情况之一： (1)运行出错(run-time error)； (2)运行超时〔time-limit exceeded〕； (3)运行结果错误(wrong answer)； (4)运行结果输出格式错误(presentation error)。 竞赛结束后，参赛各队以解出问题的多少进行排名，若解出问题数相同，按照总用时的长短排名。总用时为每个解决了的问题所用时间之和。一个解决了的问题所用的时间是竞赛开始到提交被接受的时间加上该问题的罚时(每次提交通不过，罚时20分钟)。没有解决的问题不记时。美国英语为竞赛的工作语言。竞赛的所有书面材料(包括试题)将用美国英语写出，区域竞赛中可以使用其它语言。总决赛可以使用的程序设计语言包括PASCAL，C，C++及Java，也可以使用其它语言。具体的操作系统及语言版本各年有所不同。 4)竞赛奖励情况 总决赛前十名的队伍将得到高额奖学金：第一名奖金为12000美元，第二名奖金为 6000美元，第三名奖金为3000美元，第四名至第十名将各得到l500美元。除此之外还将承认北美冠军、欧洲冠军、南太平洋冠军及亚洲冠军。 2.ACM竞赛需要的知识 语言是最重要的基本功 无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当

ACM部分练习题目答案

ACM部分习题答案： A + B Problem Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 100972 Accepted Submission(s): 33404 Problem Description Calculate A + B. Input Each line will contain two integers A and B. Process to end of file. Output For each case, output A + B in one line. Sample Input 1 1 Sample Output 2 # include Int main() {int x,y,s; while(scanf("%d %d",&x,&y)!=EOF) {s=x+y; printf("%d\n",s);} return 0; } Sum Problem Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 85964 Accepted Submission(s): 19422 Problem Description Hey, welcome to HDOJ(Hangzhou Dianzi University Online Judge). In this problem, your task is to calculate SUM(n) = 1 + 2 + 3 + ... + n. Input The input will consist of a series of integers n, one integer per line. Output For each case, output SUM(n) in one line, followed by a blank line. You may assume the result will be in the range of 32-bit signed integer. Sample Input 1 100 Sample Output 1 5050 # include int main() {int n; long int s;

北大 poj acm题目推荐50题

-北大poj acm题目推荐50题 POJ == 北京大学ACM在线评测系统https://www.doczj.com/doc/9c10713363.html,/JudgeOnline 1. 标记难和稍难的题目大家可以看看，思考一下，不做要求，当然有能力的同学可以直接切掉。 2. 标记为A and B 的题目是比较相似的题目，建议大家两个一起做，可以对比总结，且二者算作一个题目。 3. 列表中大约有70个题目。大家选做其中的50道，且每类题目有最低数量限制。 4. 这里不少题目在BUPT ACM FTP 上面都有代码，请大家合理利用资源。 5. 50个题目要求每个题目都要写总结，养成良好的习惯。 6. 这50道题的规定是我们的建议，如果大家有自己的想法请与我们Email 联系。 7. 建议使用C++ 的同学在POJ 上用G++ 提交。 8. 形成自己编写代码的风格，至少看上去美观，思路清晰(好的代码可以很清楚反映出解题思路)。 9. 这个列表的目的在于让大家对各个方面的算法有个了解，也许要求有些苛刻，教条，请大家谅解，这些是我们这些年的经验总结，所以也请 大家尊重我们的劳动成果。 10. 提交要求：一个总文件夹名为bupt0xx (即你的比赛帐号), 这个文件夹内有各个题目类别的子目录(文件夹)，将相应的解题报告放入对应 类别的文件夹。在本学期期末，小学期开始前，将该文件夹的压缩包发至buptacm@https://www.doczj.com/doc/9c10713363.html,。 对于每个题目只要求一个POJxxxx.cpp 或POJxxxx.java (xxxx表示POJ该题题号) 的文件，注意不要加入整个project 。 11. 如果有同学很早做完了要求的题目，请尽快和我们联系，我们将指导下一步的训练。 下面是一个解题报告的范例： 例如：POJ1000.cpp

step1-数论 程序设计基础题ACM

目录 数A01 敲七 (1) 数A02 三角形面积 (2) 数A03 3n+1数链问题 (3) 数A04 统计同成绩学生人数 (4) 数A05 分解素因子 (5) 数A06 亲和数 (6) 数B01 寒冰王座 (7) 数B02 整数对 (8) 数B03 麦森数 (9) 数B04 Feli的生日礼物 (10) 注：数表示本题属于初等数论，A表示简单，B表示稍难。

数A01 敲七 【问题描述】 输出7和7的倍数，还有包含7的数字例如（17，27，37...70，71，72，73...）【数据输入】一个整数N。(N不大于30000) 【数据输出】从小到大排列的不大于N的与7有关的数字，每行一个。 【样例输入】 20 【样例输出】 7 14 17

数A02 三角形面积 【问题描述】 给出三角形的三个边长为a，b，c，根据海伦公式来计算三角形的面积： s = (a+b+c)/2； area = sqrt(s*(s-a)*(s-b)*(s-c)); 【数据输入】测试的数据有任意多组，每一组为一行。 每一行为三角形的三个边长为a，b，c； 【数据输出】输出每一个三角形的面积，两位小数。如果不是一个三角形，则输出错误提示信息：“Input error!” 【样例输入】 3 4 5 6 8 10 1 2 3 【样例输出】 6.00 24.00 Input error!

数A03 3n+1数链问题 【问题描述】 在计算机科学上，有很多类问题是无法解决的，我们称之为不可解决问题。然而，在很多情况我们并不知道哪一类问题可以解决，那一类问题不可解决。现在我们就有这样一个问题，问题如下： 1. 输入一个正整数n； 2. 把n显示出来； 3. 如果n=1则结束； 4. 如果n是奇数则n变为3n+1 ，否则n变为n/2； 5. 转入第2步。 例如对于输入的正整数22，应该有如下数列被显示出来： 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 我们推测：对于任意一个正整数，经过以上算法最终会推到1。尽管这个算法很简单，但我们仍然无法确定我们的推断是否正确。不过好在我们有计算机，我们验证了对于小于1,000,000的正整数都满足以上推断。对于给定的正整数n，我们把显示出来的数的个数定义为n的链长，例如22的链长为16。 你的任务是编写一个程序，对于任意一对正整数i和j，给出i、j之间的最长链长，当然这个最长链长是由i、j之间的其中一个正整数产生的。我们这里的i、j之间即包括i也包括j。 【数据输入】输入文件只有一行，即为正整数i和j，i和j之间以空格隔开。0 < i ≤j < 10,000。 【数据输出】文件只能有一行，即为i、j之间的最长链长。 【样例输入】 1 10 【样例输出】 20

ACM数论模板

目录 目录 (1) 一．扩展的欧几里德和不定方程的解 (2) 二．中国同余定理 (3) 三．原根 (5) 四．积性函数 (6) 五．欧拉函数性质 (7) 六．线性求1-max的欧拉函数值 (9) 七．求单个欧拉函数，求最小的x(phi（n）%x==0),使得2^x =1(mod n) (10)

一．扩展的欧几里德和不定方程的解 解不定方程ax + by = n的步骤如下: (1)计算gcd(a, b). 若gcd(a, b)不能整除n，则方程无整数解；否则，在方程的两边同除以gcd(a, b)，得到新的不定方程a'x + b'y = n'，此时gcd(a', b') = 1 (2)求出不定方程a'x + b'y = 1的一组整数解x0, y0，则n'x0，n'y0是方程a'x + b'y = n'的一组整数解。 (3)根据扩展欧几里德定理，可得方程a'x + b'y = n'的所有整数解为： x = n'x0 + b't y = n'y0 - a't (t为整数) 这也就是方程ax + by = n的所有整数解 利用扩展的欧几里德算法，计算(a, b)和满足gcd = (a, b) = ax0 + by0的x0和y0，也就是求出了满足a'x0 + b'y0 = 1的一组整数解。因此可得： x = n/gcd * x0 + b/gcd * t y = n/gcd * y0 - a/gcd * t (t是整数) int extend_Euclid(int a, int b, int &x, int &y) { if (b == 0){ x = 1; y = 0; return a; } int gcd= extend_Euclid ( b, a % b, x, y ); int temp = x; x = y; y = temp - (a / b) * y; return gcd; }

数论2—数的奇偶性

第二讲——数的奇偶性 一、基本概念和知识 一、奇数和偶数 整数可以分成奇数和偶数两大类.能被2整除的数叫做偶数，不能被2整除的数叫做奇数。 偶数通常可以用2k（k为整数）表示，奇数则可以用2k+1（k为整数）表示。 特别注意，因为0能被2整除，所以0是偶数。 二、奇数与偶数的运算性质 性质1：偶数±偶数=偶数， 奇数±奇数=偶数。 性质2：偶数±奇数=奇数。 性质3：偶数个奇数相加得偶数。 性质4：奇数个奇数相加得奇数。 性质5：偶数×奇数=偶数， 奇数×奇数=奇数。 三、奇反偶同：搞清一件事情的初始状态，进行奇数次操作，会和起始状态相反，进行偶数次操作，会回到初始状态。

二、例题 例1 1+2+3+…+99的和是奇数？还是偶数？ 例2 能不能在下面的每个方框中，分别填入加号或减号，使等式成立1□2□3□4□5□6□7□8□9=10 例3 元旦前夕，同学们相互送贺年卡.每人只要接到对方贺年卡就一定回赠贺年卡，那么送了奇数张贺年卡的人数是奇数，还是偶数？ 为什么？ 例4 桌上有9只杯子，全部口朝上，每次将其中6只同时“翻转”.请说明：无论经过多少次这样的“翻转”，都不能使9只杯子全部 口朝下。 例5 某校六年级学生参加区数学竞赛，试题共40道，评分标准是：答对一题给3分，答错一题倒扣1分.某题不答给1分，请说明该校 六年级参赛学生得分总和一定是偶数。 例5 在中国象棋盘任意取定的一个位置上放置着一颗棋子“马”，按中国象棋的走法，当棋盘上没有其他棋子时，这只“马”跳了若 干步后回到原处，问：“马”所跳的步数是奇数还是偶数？ 例6 一个俱乐部里的成员只有两种人：一种是老实人，永远说真话； 一种是骗子，永远说假话。某天俱乐部的全体成员围坐成一圈， 每个老实人两旁都是骗子，每个骗子两旁都是老实人。外来一位 记者问俱乐部的成员张三：“俱乐部里共有多少成员？”张三答：

ACM数论基础之扩展欧几里德详细证明

ACM数论基础之扩展欧几里德算法 欧几里德算法概述： 欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理： gcd函数就是用来求(a,b)的最大公约数的。 gcd函数的基本性质： gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|) 欧几里得算法的公式表述 gcd(a,b)=gcd(b,a mod b) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a, d|b，而r = a - kb，因此d|r 因此d是(b,a mod b)的公约数 假设d 是(b,a mod b)的公约数，则 d | b , d |r ，但是a = kb +r 因此d也是(a,b)的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证 欧几里德算法的C++语言描述 intGcd(int a, int b) { if(b == 0) return a; returnGcd(b, a % b); } 当然你也可以写成迭代形式： intGcd(int a, int b) { while(b != 0) { int r = b; b = a % b; a = r; } return a; }

扩展欧几里德定理 对于不完全为0 的非负整数a，b，gcd（a，b）表示a，b 的最大公约数，必然存在整数对x，y ，使得gcd（a，b）=ax+by。 c++语言实现 #include using namespace std; intx,y,q; voidextend_Eulid(inta,int b) { if(b == 0) { x = 1;y = 0;q = a; } else { extend_Eulid(b,a%b); int temp = x; x = y; y = temp - a/b*y; } } int main() { inta,b; cin>>a>>b; if(a < b) swap(a,b); extend_Eulid(a,b); printf("%d=(%d)*%d+(%d)*%d\n",q,x,a,y,b); return 0; } 求解x，y的方法的理解 设a>b。 1，显然当b=0，gcd（a，b）=a。此时x=1，y=0； 2，ab<>0 时 设ax1+by1=gcd(a,b); bx2+(a mod b)y2=gcd(b,a mod b);

数论中的基础概念

数论中的基础概念

1群、环、域概念 A1：加法的封闭性：如果a 和b 属于G ，则a+b 也属于G A2：加法结合律：对G 中的任意元素a,b,c,a+(b+c)=(a+b)+c A3：加法单位元：G 中存在一个元素0，使得对于G 中的任意元素a ，有a+0=0+a A4：加法逆元：对于G 中的任意元素a ，G 中一定存在一个元素a,使得 a+(-a)=(-a)+a=0 A5：加法交换律：对于G 中的任意元素a 和b ，有a+b=b+a M1：乘法的封闭性：如果a 和b 属于G ，则ab 也属于G M2：乘法结合律：对于G 中的任意元素a,b,c 有a(bc)=(ab)c M3：乘法分配了：对于G 中的任意元素a,b,c ，有a(b+c)=ab+ac 和(a+b)c=ac+bc M4：乘法交换律：对于G 中的任意元素a,b 有ab=ba M5：乘法单位元：对于G 中的任意元素a,在G 中存在一个元素1，使得a1=1a=a M6：无零因子：对于G 中的元素a,b ，若ab=0，则必有a=0或b=0 M7：乘法逆元：如果a 属于G ，且a 不为0,则G 中存在一个元素1-a ，使得 111==--a a aa 满足A1---A4称为群 满足A1---A5称为可交换群 满足A1---M3称为环 满足A1---M4称为可交换换 满足A1---M6称为整环 满足A1---M7称为域 2循环群：如果群中的每一个元素都是一个固定元素)(G a a ∈的幂k a （k 为整数）， 则称群G 是循环群。我们认为元素a 生成了群G ，或者说a 是群G 的 生成元。 循环群总是交换群 3模运算 )mod ()mod (n b n a =则称整数a 和b 是模n 同余的，可以表示为：)(mod n b a ≡ 若b 整除a 。则用符号：a |b 表示。其性质可表示如下： ①如果a|1,那么a=-1或1。 ②如果a|b ，且b|a ，那么a=b 或a=-b ③任何不等于零的数整除0 ④如果b|g 且b|h ，那么对任意整数m,n 都有b|（mg+nh ）

简便算法的题型 ACM 题型算法分类

ACM 题型算法分类 题目均来自 主流算法 搜索//回溯 DP（动态规划） 贪心 图论//Dijkstra、最小生成树、网络流 数论//解模线性方程 计算几何//凸壳、同等安置矩形的并的面积与周长组合数学//Polya定理 模拟

数据结构//并查集、堆 10.博弈论 1、排序 1423, 1694, 1723, 1727, 1763, 1788, 1828, 1838, 1840, 2201, 2376, 2377, 2380, 1318, 1877, 1928, 1971, 1974, 1990, 2001, 2002, 2092, 2379, 1002（需要字符处理，排序用快排即可）1007（稳定的排序）2159（题意较难懂）223 1 2371（简单排序）2388（顺序统计算法）2418（二叉排序树） 2、搜索、回溯、遍历 1022 1111d 1118 1129 1190 1562 1564 1573 1655 2184 2225 2243 2312 2362 2378 238 6 1010,1011,1018,1020,1054,1062,1256,1321,1363,1501，

1650,1659,1664,1753,2078 ,2083,2303,2310,2329 简单1128, 1166, 1176, 1231, 1256, 1270, 1321, 1543, 1606, 1664, 1731, 1742, 1745, 1847, 1915, 1950, 2038, 2157, 2182, 2183, 2381, 2386, 2426, 不易1024, 1054, 1117, 1167, 1708, 1746, 1775, 1878, 1903, 1966, 2046, 2197, 2349, 推荐1011, 1190, 1191, 1416, 1579, 1632, 1639, 1659, 1680, 1683, 1691, 1709, 1714, 1753, 1771, 1826, 1855, 1856, 1890, 1924, 1935, 1948, 1979, 1980, 2170, 2288, 2331, 2339, 2340,1979（和迷宫类似）1980（对剪枝要求较高）

ACM常用算法及其相应的练习题

ACM常用算法及其相应的练习题 2007-12-03 23:48 OJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3 094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 三.数据结构. (1)串 (poj1035,poj3080,poj1936) (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) (3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) (5)哈夫曼树(poj3253)