首页 / 算法 / 《算法竞赛入门经典（第2版）》第三章习题题解

《算法竞赛入门经典（第2版）》第三章习题题解

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了《算法竞赛入门经典（第2版）》第三章习题题解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含11123字，纯文字阅读大概需要16分钟。

内容图文

《算法竞赛入门经典》习题源码 Github开源：https://github.com/RyanHe123/Classic-Introduction-to-Algorithmic-Competition
本文中的习题题解为本人完成，如果存在错误或可以改进的地方，欢迎在评论区提出，谢谢！

习题3-1 得分（ACM/ICPC Seoul 2005，UVa1585）

给出一个由O和X组成的串（长度为1~80），统计得分。每个O的得分为目前连续出现的O的个数，X的得分为0。例如：OOXXOXXOOO的得分为1+2+0+0+1+0+0+1+2+3。

#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	int i = 0;
	getchar();
	for (; i < n; i++)
	{
		char ch; int sum = 0;
		int state = 0;
		while ((ch = getchar()) !='\n')
		{
			if (ch == 'O')
			{
				state++;
				sum += state;
			}
			else
			{
				state = 0;
			}
		}
		printf("%d\n", sum);
	}
}

习题3-2 分子量（ACM/ICPC Seoul 2007，UVa1586）

给出一种物质的分子式（不带括号），求分子量。本题中的分子式只包含4种原子，分别为 C，H，O，N，原子量分别为12.01，1.008，16.00，14.01（单位：g/mol）。例如：C6H5OH的分子量为94.108g/mol。

#include<stdio.h>
#include<ctype.h>
#include<string.h>
char s[90];
int main()
{
	int n;
	scanf("%d",&n);
	int i=0;
	for(;i<n;i++)
	{
		double atom;
		int count=1;
		scanf("%s",s);
		int j;
		double sum=0;
		for(j=0;j<strlen(s);j++)
		{
			switch(s[j])
			{
				case 'C':atom=12.01;break;
				case 'H':atom=1.008;break;
				case 'O':atom=16.00;break;
				case 'N':atom=14.01;break;
			}
			if(isdigit(s[j+1])!=0)
				count=s[++j];
			while(isdigit(s[j+1])!=0)
				count=count*10+s[++j];
			sum+=count*atom;
		}
		printf("%.3f\n",sum);
	}
}

习题3-3 数数字（ACM/ICPC Danang 2007，UVa1225）

把前n（n≤10000）个整数顺次写在一起：123456789101112…数一数0~9各出现多少次（输出10个整数，分别是0，1，…，9出现的次数）。

#include<stdio.h>
#include<math.h> 
int main()
{
	int t;
	scanf("%d", &t);
	int i;
	for (i = 0; i < t; i++)
	{
		int a[10] = { 0 };
		int n;
		scanf("%d", &n);
		int j;
		for (j = 1; j <= n; j++)
		{
			int num = j;
			while (num != 0)
			{
				a[num % 10]++;
				num /= 10;
			}
		}
		for (j = 0; j < 9; j++)
			printf("%d ", a[j]);
		printf("%d\n", a[9]);
	}
}

习题3-4 周期串（UVa 455）

如果一个字符串可以由某个长度为k的字符串重复多次得到，则称该串以k为周期。例如，abcabcabcabc以3为周期（注意，它也以6和12为周期）。
输入一个长度不超过80的字符串，输出其最小周期。

#include<stdio.h>
#include<string.h>
int main()
{
	int n;
	scanf("%d",&n);
	int i;
	for(i=0;i<n;i++)
	{
		char s[100];
		scanf("%s",s);
		int t;
		for(t=1;t<=strlen(s);t++)
		{
			//一开始忽略了结尾不是完整周期结束的情况 
			if(strlen(s)%t!=0)
				continue;
			int j=0,state=1;
			for(;j<strlen(s);j++)
			{
				if(s[j]!=s[j%t])
				{
					state=0;
					break;
				}
			}
			if(state==1)
				{
					if(i!=0)printf("\n");
				printf("%d\n",t);break;
				}
		}
	}
}

习题3-5 谜题（ACM/ICPC World Finals 1993，UVa227）

有一个5*5的网络，恰好有一个格子是空的，其他格子各有一个字母，一共四种指令，A,B,L,R，分别表示把空格的上下左右的相邻字幕移到空格中。输入初始网络和指令序列(以0结束)，输出指令执行完毕后的网络，如果有非法指令，应输出，“This puzzle has no final configuration.”

//这道题的输出格式有很多坑，PE了无数次 
#include<stdio.h>
int main()
{
	 //输入矩阵
	int kase=1,state;
	int i,j;
	for(;;)
	{
	state=1;
	int x,y;
	char p[5][6],ch;
	for(i=0;i<5;i++)
	{
		fgets(p[i],7,stdin);
		if(p[0][0]=='Z'&&p[0][1]=='\n')
			return 0;
 	}
 	//搜索空格位置 
	for(i=0;i<5;i++)
	{
		for(j=0;j<5;j++)
		{
			if(p[i][j]==' ')
			{x=i;y=j;}
		}
	} 	
 	while((ch=getchar())!='0')
 	{
 		switch(ch)
 		{
 			case'A':if(x==0)state=0;
			 else{p[x][y]=p[x-1][y];p[x-1][y]=' ';x--;}break;	//边界判断和移动
 			case'B':if(x==4)state=0;
			 else{p[x][y]=p[x+1][y];p[x+1][y]=' ';x++;}break;
 			case'L':if(y==0)state=0;
			 else{p[x][y]=p[x][y-1];p[x][y-1]=' ';y--;}break;
 			case'R':if(y==4)state=0;
			 else{p[x][y]=p[x][y+1];p[x][y+1]=' ';y++;}break;
		}
	}
	//输出 
	if(kase!=1)
	printf("\n");
	printf("Puzzle #%d:\n",kase++);
	if(state==0)
	printf("This puzzle has no final configuration.\n");
	else
	{
	for(i=0;i<5;i++)
	{
		for(j=0;j<5;j++)
		{
			printf("%c",p[i][j]);
			if(j!=4)printf(" "); 
		}
		printf("\n");
	} 	
	}
	 getchar();
	}
}

习题3-6 纵横字谜的答案（ACM/ICPC World Finals 1994，UVa232）

输入一个r行c列的网格，，黑格用‘*’表示，每个白格都填有一个字母。如果一个白格的左边相邻位置或者上边相邻位置没有白格（可能是黑格，也可能出了网格边界），则称这个白格是一个起始格。首先把所有的起始格从上到下，从左到右的顺序编号为1，2，3…

#include<stdio.h>
int main()
{
	int a,b;
	int kase=1;
	while(scanf("%d",&a)&&a!=0)
	{
		scanf("%d",&b);
		if(kase!=1)
		printf("\n"); 
		char p[a][b+1];int n[a][b];
		int i,j;
		getchar();//用这行吞掉输入a和b时产生的\n 
		for(i=0;i<a;i++)
			for(j=0;j<b;j++)n[i][j]=0;//给n数组初始化0 
		//读取行列式
		for(i=0;i<a;i++)
			fgets(p[i],b+2,stdin);
		//标记起始格
		int count=1;
		for(i=0;i<b;i++)
		if(p[0][i]!='*')n[0][i]=count++;		//标记第一行 
		for(i=1;i<a;i++)
		{
			if(p[i][0]!='*')n[i][0]=count++;
			for(j=1;j<b;j++)
			if((p[i][j-1]=='*'||p[i-1][j]=='*')&&p[i][j]!='*') n[i][j]=count++;
		}
		/*for(i=0;i<a;i++)
		for(j=0;j<b;j++)
		{
			printf("%d ",n[i][j]);d
			if(j==b-1)printf("\n");
		}*/
		//寻找符合条件单词 
		printf("puzzle #%d:\nAcross\n",kase++);
		//横向 
		for(i=0;i<a;i++)
		for(j=0;j<b;j++)
		{
			if(j==0&&p[i][0]!='*')
			{
				printf("%3d.",n[i][0]);
				while(p[i][j]!='*'&&j<b)
				putchar(p[i][j++]);
				printf("\n");
			}
			while(p[i][j]=='*'&&j<b){
				j++;
			}
			if(j>=b)break;
			printf("%3d.",n[i][j]);
			while(p[i][j]!='*'&&j<b)
				putchar(p[i][j++]);
				printf("\n");
		 } 
		//纵向 还是要按照横向顺序搜索，比横向复杂 
		printf("Down\n");
		int temp; 
		for(i=0;i<a;i++)
		for(j=0;j<b;j++)
		{
			if(i==0&&p[0][j]!='*')
			{
				printf("%3d.",n[0][j]);
				temp=i;
				while(p[temp][j]!='*'&&temp<a)
				putchar(p[temp++][j]);
				printf("\n");
			}
			if(i>0&&p[i][j]!='*'&&p[i-1][j]=='*')
			{
				printf("%3d.",n[i][j]);
				temp=i;
				while(p[temp][j]!='*'&&temp<a)
				putchar(p[temp++][j]);
				printf("\n");
			}

		 } 
		 
	} 
	
 }

习题3-7 DNA序列（ACM/ICPC Seoul 2006，UVa1368）

输入m个长度均为n的DNA序列，求一个DNA序列，到所有序列的总Hamming距离尽量小。两个等长字符串的Hamming距离等于字符不同的位置个数，例如，ACGT和GCGA的Hamming距离为2（左数第1, 4个字符不同）。
输入整数m和n（4≤m≤50, 4≤n≤1000），以及m个长度为n的DNA序列（只包含字母A，C，G，T），输出到m个序列的Hamming距离和最小的DNA序列和对应的距离。如有多解，要求为字典序最小的解。例如，对于下面5个DNA序列，最优解为TAAGATAC。
TATGATAC
TAAGCTAC
AAAGATCC
TGAGATAC
TAAGATGT

#include<stdio.h>
int main()
{
	int n;
	scanf("%d", &n);
	int t;
	for (t = 0; t < n; t++)
	{
		int m, n;
		scanf("%d %d", &m, &n);
		char s[50][1100];
		int i,j;
		for (j = 0; j < m; j++)
			scanf("%s", s[j]);
		//读取字符串，二维数组 
		
		int sum = 0;
		for (j = 0; j < n; j++)
		{
			int a[4] = { 0 };
			for (i = 0; i < m; i++)
			{
				
				//逐位读取出现次数 
				switch (s[i][j])
				{
				case'A':a[0]++; break;
				case'C':a[1]++; break;
				case'G':a[2]++; break;
				case'T':a[3]++; break;
				}
			}
			int max = 0, index = 0;
			int z;
			//找到出现次数最多的字母 
			for (z = 0; z < 4; z++){
				if(a[z]==max)
				{
					if(z<index)
					index=z;
				}
				if (a[z] > max)
				{
					index=z;
					max = a[z];  // 如果出现次数相同输出字典序小的解 
				}
			}
			sum += m - max;	
			switch (index)
			{
			case 0:putchar('A'); break;
			case 1:putchar('C'); break;
			case 2:putchar('G'); break;
			case 3:putchar('T'); break;
			}
		}
		printf("\n%d\n", sum);
	}

}

习题3-8 循环小数（ACM/ICPC World Finals 1990，UVa202）

输入整数a和b a大于等于0小于等于3000,b大于等于1小于等于3000,输出a/b的循环小数表示以及循环节长度。如果循环周期大于50,只显示50位，之后的全部用…表示

#include<stdio.h>
#include<string.h>
struct combine
{
	int x, y;
};// 记录除数和余数 
combine c[2000] = { 0 }; int yu[3000] = { 0 };//记录余数 ，数组一定要开在main外面，不然会出问题 
int main()
{
	int a, b;
	while (EOF != scanf("%d", &a))
	{
		scanf("%d", &b);
		int n = a;
		int d = a / b;
		c[0].y = a % b;
		yu[a%b]++;
		a = a % b * 10;
		int i;
		for (i = 1;; i++)//当有相同余数时，停止循环 
		{
			c[i].x = a / b; c[i].y = a % b;
			if (yu[a%b] == 1)
				break;
			else
				yu[a%b]++;
			a = a % b * 10;
		}
		int j, l;
		for (j = 0;; j++)//寻找前一次出现相同余数的位置 
		{
			if (c[j].y == a % b)
			{
				l = i - j;
				break;
			}
		}
			printf("%d/%d = %d.", n, b, d);
			int t;
			for (t = 1; t <= j; t++)
				printf("%d", c[t].x);
			printf("(");
			for (; t <= i; t++)
			{
				if (t == 51)
				{
					printf("..."); break;
				}
				printf("%d", c[t].x);
			}
			printf(")\n   %d = number of digits in repeating cycle\n\n",l);//此题的输出格式给的很模糊，需要在每个output之间加一个blank line 
		memset(c, 0, sizeof(c));
		memset(yu, 0, sizeof(yu));
	}
}

习题3-9 子序列（UVa10340）

输入两个字符串s和t，判断是否可以从t中删除0个或多个字符（其它字符顺序不变），得到字符串s.
例如：abcde可以得到bce，但无法得到dc.

#include<stdio.h>
#include<string.h>
//字符串一定要开大一些，刚开始开的比较小，就RE了 
char s[1000000],t[1000000];
int main()
{
	//读取字符串
	while((s[0]=getchar())!=EOF)
	{
		int i=1;
		while((s[i]=getchar())!=' ')
			i++;
		s[i]='\0';
		i=0;
		while((t[i]=getchar())!='\n')
			i++;
		int index=0; 
		for(i=0;i<strlen(t);i++)
	{
		if(s[index]==t[i])
			index++;
		
	}
		if(index==strlen(s))
		printf("Yes\n");
		else
		printf("No\n");
		//初始化数组，防止上一次实验对下一次有影响 
		memset(s,0,sizeof(s));
		memset(t,0,sizeof(t));
	 } 
}

习题3-10 盒子（ACM/ICPC NEERC 2004，UVa1587）

多实例测试。给出6个矩形的长和宽，判断这6个面是不是可以围成一个长方体，若可以围成，则输出“POSSIBLE”（不包含引号），否则输出“IMPOSSIBLE”（不包含引号），每个输出占一行。

struct rectangle
{
	int x, y;
};
void internal_swap(struct rectangle &r1)
{
	if (r1.x > r1.y)
	{
		int temp;
		temp = r1.x;
		r1.x = r1.y;
		r1.y = temp;
	}
}
void external_swap(rectangle &r1, rectangle &r2)
{
	if (r1.x > r2.x)
	{
		rectangle temp;
		temp = r1;
		r1 = r2;
		r2 = temp;
	}
	if (r1.x == r2.x&&r1.y > r2.y)
	{
		rectangle temp;
		temp = r1;
		r1 = r2;
		r2 = temp;
	}
}
#include<stdio.h>
int main()
{
	rectangle rec[6];
	while (scanf("%d %d", &rec[0].x,&rec[0].y)!=EOF)
	{
		internal_swap(rec[0]);
		int i;
		for (i = 1; i < 6; i++)
		{
			scanf("%d %d", &rec[i].x,&rec[i].y);
			internal_swap(rec[i]);
		}
		int j;
		for (i = 0; i < 5; i++)
		{
			for (j = 0; j < 5 - i; j++)
			{
				external_swap(rec[j], rec[j + 1]);
			}
		}
		int state = 1;
		for (i = 0; i < 6; i += 2)
		{
			if (rec[i].x != rec[i + 1].x || rec[i].y != rec[i + 1].y)
				state = 0;
		}
		if (rec[0].x != rec[2].x || rec[0].y != rec[4].x || rec[2].y != rec[4].y)
			state = 0;
		if (state == 1)
			printf("POSSIBLE\n");
		else
			printf("IMPOSSIBLE\n");
	}
}

习题3-11 换低档装置（ACM/ICPC NEERC 2006，UVa1588）

//a在前和b在前都尝试进行插入，对两个方向的最小长度进行比较，输出最小的长度
#include<stdio.h>
#include<string.h> 
int main()
{
	char a[200], b[200];
	while (EOF != scanf("%s", a))
	{
		scanf("%s", b);
		int la = strlen(a), lb = strlen(b), s1, s2, s;
		int i, j; int state_2 = 0;
		//a在前 
		for (i = 0; i < la; i++)
		{
			int state = 1;
			for (j = 0; j < lb; j++)
			{
				if (a[i + j] + b[j] - '0' - '0' > 3)
				{
					state = 0;
					break;
				}
			}
			if (state == 1) {
				//输出上和下中最长的那一个
				state_2 = 1;
				s1 =( (i + lb)>la? (i + lb):la); break;
			}
			if (state_2 == 0)
				s1 = la + lb;
		}
		state_2 = 0;
		//b在前 
		for (i = 0; i < lb); i++)
		{
			int state = 1;
			for (j = 0; j < la; j++)
			{
				if (b[i + j] + a[j] - '0' - '0' > 3)
				{
					state = 0;
					break;
				}
			}
			if (state == 1)
			{
				state_2 = 1;
				s2 = ((i + la) > lb ? (i + la) : lb);
				break;
			}
			if (state_2 == 0)
			{
				s2 = la + lb;
			}
		}
		if (s1 > s2)s = s2;
		else s = s1;
		printf("%d\n", s);
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
	}
	return 0;
}

习题3-12 浮点数（UVa11809）

这道题笔者想了很久都没想出来（是我太菜了），于是在网上找了大神的题解，贴在这里。链接：https://blog.csdn.net/crazysillynerd/article/details/43339157

//非原创，链接：https://blog.csdn.net/crazysillynerd/article/details/43339157 
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
 
using namespace std;
 
int main() {
    double M[20][40];
    long long E[20][40];
 
    // 打表
    for(int i = 0; i <= 9; ++i) for(int j = 1; j <= 30; ++j) {
        double m = 1 - pow(2, -1 - i), e = pow(2, j) - 1;
        double t = log10(m) + e * log10(2);
        E[i][j] = t, M[i][j] = pow(10, t - E[i][j]);
    }
 
    // 输入并输出结果
    string in;
    while(cin >> in && in != "0e0") {
        // 处理输入
        for(string::iterator i = in.begin(); i != in.end(); ++i) if(*i == 'e') *i = ' ';
        istringstream ss(in);
        double A; int B;
        ss >> A >> B;
        while(A < 1) A *= 10, B -= 1;
        // 在打好的表中寻找答案
        for(int i = 0; i <= 9; ++i) for(int j = 1; j <= 30; ++j) {
            if(B == E[i][j] && (fabs(A - M[i][j]) < 1e-4 || fabs(A / 10 - M[i][j]) < 1e-4)) {
                cout << i << ' ' << j << endl;
                break;
            }
        }
    }
}

内容总结

以上是互联网集市为您收集整理的《算法竞赛入门经典（第2版）》第三章习题题解全部内容，希望文章能够帮你解决《算法竞赛入门经典（第2版）》第三章习题题解所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/717690.html

来源：【匿名】

【上一篇】K-means聚类算法【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【《算法竞赛入门经典（第2版）》第三章习题题解】教程文章相关的互联网学习教程文章

《算法竞赛入门经典》动态规划复习【代码】

codevs 4979 数塔 1#define N 1002 #include<iostream>3usingnamespace std;4 #include<cstdio>5int a[N][N],b[N][N],n;6int main()7{8 scanf("%d",&n);9for(int i=1;i<=n;++i) 10for(int j=1;j<=i;++j) 11 { 12 scanf("%d",&a[i][j]); 13 b[i][j]=a[i][j]; 14 } 15for(int i=n-1;i>=1;--i) 16for(int j=1;j<=i;++j) 17 { 18if(a[i+1][j]>=a[i+1][j+1]) 19 a[i][j]+=a[i+1][j]...

数据结构和算法(Golang实现)(4)简单入门Golang-结构体和方法【代码】

结构体和方法一、值，指针和引用我们现在有一段程序：package mainimport "fmt"func main() {// a,b 是一个值a := 5b := 6fmt.Println("a的值：", a)// 指针变量 c 存储的是变量 a 的内存地址c := &afmt.Println("a的内存地址：", c)// 指针变量不允许直接赋值，需要使用 * 获取引用//c = 4// 将指针变量 c 指向的内存里面的值设置为4*c = 4fmt.Println("a的值：", a)// 指针变量 c 现在存储的是变量 b 的内存地址c = &bfmt.Printl...

A*寻路算法入门(六)【图】

大熊猫猪·侯佩原创或翻译作品.欢迎转载,转载请注明出处. 如果觉得写的不好请告诉我,如果觉得不错请多多支持点赞.谢谢! hopy ;)免责申明：本博客提供的所有翻译文章原稿均来自互联网，仅供学习交流之用，请勿进行商业用途。同时，转载时不要移除本申明。如产生任何纠纷，均与本博客所有人、发表该翻译稿之人无任何关系。谢谢合作！步骤3我们再一次选择最小F值(5)的瓦块去继续迭代:这时,只有一个可能的瓦块被添加到开放列表中,因为一...

数据结构与算法入门---基本概念【图】

有哪些数据结构：　　线性表、栈、队列、（字符）串、数组、广义表、树、二叉树、图重点是：线性表、二叉树对于每种数据结构都会有其添加、更新、删除、查询等操作的实现　　数据结构与算法是不可分的数据：数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合　　数据的含义非常的广泛，除了通常的数值数据、字符、字符串是数据之外，声音、图像等一切可以输入计算机并能被处理的都属数据...

（Step1-500题）UVaOJ+算法竞赛入门经典+挑战编程+USACO

下面给出的题目共计560道，去掉重复的也有近500题，作为ACMer Training Step1，用1年到1年半年时间完成。打牢基础，厚积薄发。一、UVaOJ http://uva.onlinejudge.org 西班牙Valladolid大学的程序在线评测系统，是历史最悠久、最著名的OJ。二、《算法竞赛入门经典》刘汝佳（UVaOJ 351道题）以下部分内容摘自：http://sdkdacm.5d6d.com/thread-6-1-1.html “AOAPC I”是刘汝佳（大名鼎鼎的SRbGa）写的《算法竞赛入门经...

算法竞赛入门经典第二版第三章习题【代码】

写这个的原因是看到一位大神的习题答案总结，于是自己心血来潮也想写一个这个，目的主要是督促自己刷题吧，毕竟自己太弱了。习题3-1 得分 UVa 1585大致就是设置一个变量记录到当前为止的连续的O的数量，碰到X就变0，水题。#include<stdio.h>#include<ctype.h>#include<string.h>char s[90]; int main(void) {int length,n,sum,num;scanf("%d",&n);while(n--){sum=num=0;scanf("%s",s);length=strlen(s);for(int i=0;i<length;i++){...

A*算法详尽的入门教程【图】

A*算法详尽的入门教程一：为什么我们需要A*算法求最短路径或者最小代价的算法有很多。其本质就是图的搜索策略。图的直接搜索方法有很多种，比较典型的是广度优先搜索、深度优先搜索。所谓的广度优先搜索是每到达一个节点就优先遍历该节点的所有相邻节点。而对应的深度优先搜索是指一直延伸到从未达到过的节点。基于以上两种基本思想的最短路径算法有Dijkstra算法和Floyd算法。当搜索完毕也遍历了整张图，其时间开销是很大的，尤其...

python入门到精通（算法与人工智能算法实战）

提供安装包、开发工具、01-Python入门到项目实战篇(Python 60多G)02-大数据入门到实战篇(Hadoop 19多G)03-数据分析与数据挖掘篇(30多G)04-高等数学与程序算法篇(80多G)05-人工智能机器学习篇(40多G)06-人工智能神经网络量化交易篇(14多G)07-机器人与自然语言处理篇(30G) 如有需要联系qq：1757733513 原文：https://www.cnblogs.com/zhishifenxiang/p/9889469.html

算法入门 2014-4-25 运行号：837134【代码】【图】

素数筛今天让张神帮我看写了个素数筛，大神就是大神不多说直接上代码！ #include <iostream> #include <cstdio> #include <cstdlib> #include <string> #include <cmath> #include <cstring> #include <algorithm> usingnamespace std; bool pre_arry[1100]; void pre_cnt() {memset(pre_arry,1,sizeof(pre_arry));pre_arry[1] = 0;for(int i = 2; i <= 1000; ++i){if(pre_arry[i]){for(int j = i+i; j <= 1000; j+=i)pre_arry[...

Kaggle竞赛入门（四）：随机森林算法的Python实现【代码】

首先导入数据，将数据分为训练集和测试集：import pandas as pd# Load data melbourne_file_path = ‘../input/melbourne-housing-snapshot/melb_data.csv‘ melbourne_data = pd.read_csv(melbourne_file_path) # Filter rows with missing values melbourne_data = melbourne_data.dropna(axis=0) # Choose target and features y = melbourne_data.Price melbourne_features = [‘Rooms‘, ‘Bathroom‘, ‘Landsize‘, ‘Buil...

《算法竞赛——从入门到进阶》随笔（1）【代码】

第一章算法竞赛概述算法竞赛（程序设计竞赛）是培养杰出程序员的捷径。在国内众多竞赛中，面向中学生的程序设计竞赛有全国青少年信息学奥林匹克竞赛（NOI），最具影响力的面向大学生的程序设计竞赛有ACM-ICPC（国际大学生程序设计竞赛），CCPC（中国大学生程序设计竞赛）培养杰出程序员的捷径：1.编写大量代码； 2.丰富的算法知识； 3. 计算思维和逻辑思维； 4. 团队合作精神。算法竞赛入门： 1. 竞赛队员主要的学习方法就是“刷...

网络流最经典的入门题各种网络算法都能AC。【代码】

Drainage Ditches 题目抽象：给你m条边u,v,c。 n个定点，源点1，汇点n.求最大流。最好的入门题，各种算法都可以拿来练习（1）：一般增广路算法 ford() 1 #include <iostream>2 #include <cstdio>3 #include <cstring>4 #include <cmath>5 #include <algorithm>6 #include <string>7 #include <vector>8 #include <set>9 #include <map>10 #include <stack>11 #include <queue>12 #include <sstream>13 #include <iomanip>1...

Kaggle竞赛入门：决策树算法的Python实现【代码】【图】

本文翻译自kaggle learn，也就是kaggle官方最快入门kaggle竞赛的教程，强调python编程实践和数学思想（而没有涉及数学细节），笔者在不影响算法和程序理解的基础上删除了一些不必要的废话，毕竟英文有的时候比较啰嗦。一.决策树算法基本原理背景：假设你的哥哥是一个投资房地产的大佬，投资地产赚了很多钱，你的哥哥准备和你合作，因为你拥有机器学习的知识可以帮助他预测房价。你去问你的哥哥他是如何预测房价的，他告诉你说他完全...

算法竞赛入门经典——读书笔记day1

1-1：整数值用%d输出，实数用%f输出。1-2：整数/整数=整数，浮点数/浮点数=浮点数。1-3：scanf中的占位符和变量的数据类型应一一对应，且每个变量前需要加&符号。1-4：在算法竞赛中，输入前不要打印提示信息。输出完毕后应立即终止程序，不要等待用户按键，因为输入输出过程都是自动的，没有人工干预。1-5：在算法竞赛中不要使用头文件conio.h，包括getch()、clrscr()等函数。1-6：在算法竞赛中，每行输出均应以回车符结束，包括最...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 《算法竞赛入门经典（第2版）》第三章习题题解

《算法竞赛入门经典（第2版）》第三章习题题解

内容导读

内容图文

习题3-1 得分（ACM/ICPC Seoul 2005，UVa1585）

习题3-2 分子量（ACM/ICPC Seoul 2007，UVa1586）

习题3-3 数数字（ACM/ICPC Danang 2007，UVa1225）

习题3-4 周期串（UVa 455）

习题3-5 谜题（ACM/ICPC World Finals 1993，UVa227）

习题3-6 纵横字谜的答案（ACM/ICPC World Finals 1994，UVa232）

习题3-7 DNA序列（ACM/ICPC Seoul 2006，UVa1368）

习题3-8 循环小数（ACM/ICPC World Finals 1990，UVa202）

习题3-9 子序列（UVa10340）

习题3-10 盒子（ACM/ICPC NEERC 2004，UVa1587）

习题3-11 换低档装置（ACM/ICPC NEERC 2006，UVa1588）

习题3-12 浮点数（UVa11809）

内容总结

内容备注

内容手机端

【《算法竞赛入门经典（第2版）》第三章习题题解】教程文章相关的互联网学习教程文章

《算法竞赛入门经典》动态规划复习【代码】

数据结构和算法(Golang实现)(4)简单入门Golang-结构体和方法【代码】

A*寻路算法入门(六)【图】

数据结构与算法入门---基本概念【图】

（Step1-500题）UVaOJ+算法竞赛入门经典+挑战编程+USACO

算法竞赛入门经典第二版第三章习题【代码】

A*算法详尽的入门教程【图】

python入门到精通（算法与人工智能算法实战）

推荐算法入门【图】

算法入门 2014-4-25 运行号：837134【代码】【图】

Kaggle竞赛入门（四）：随机森林算法的Python实现【代码】

《算法竞赛——从入门到进阶》随笔（1）【代码】

网络流最经典的入门题各种网络算法都能AC。【代码】

Kaggle竞赛入门：决策树算法的Python实现【代码】【图】

算法竞赛入门经典——读书笔记day1

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程