- 浏览: 65951 次
- 性别:
- 来自: 北京
最新评论
文章列表
入门其实有两种方法:1 自己看竞赛书,看别人的程序等等。2 上题库(如:pku和zju)做题。第一种可以较为系统的学到东西,但是时间久了就会无聊,而且长久实践不足,编程能力永远得不到真正的提高。第二种虽然看着自己A ...
- 2010-11-24 23:23
- 浏览 411
- 评论(0)
此题求牛从起点到终点路径中最大权值最小的那条路径,将Floyd算法稍作修改即可,注意此题输入输出处理不当可能引起超时,一般scanf及printf更节省时间。
#include <iostream>
#include <cstdio>
#define MAX_VEX 305
#define MAX_WEI 1000005
using namespace std;
int A[MAX_VEX][MAX_VEX];
//用cin,cout会超时
int main(){
int N,M,T,i,j,k,h;
int s,e,w;
//cin> ...
- 2010-11-24 22:48
- 浏览 423
- 评论(0)
多源最短路径Floyd算法邻接矩阵形式C++实现,输入点数、边数和起点、终点、权值,输出最短路径及权值
#include <iostream>
#define MAX_VEX 305
#define MAX_WEI 1000005
using namespace std;
int A[MAX_VEX][MAX_VEX],Path[MAX_VEX][MAX_VEX];
//输出最短路径
void prn_pass(int j , int k){
if (Path[j][k]!=-1)
{
prn_pass(j,Path[j][k]);
cout< ...
- 2010-11-24 22:00
- 浏览 622
- 评论(0)
此题对kruskal算法做了变形,不是求最小生成树,而是求最大边权值与最小边权值之差最小的生成树,同样可以用kruskal算法的实现方法,采用并查集。如果求最小生成树要将边加入到堆中,并且不需要遍历所有的生成树情况
//此题对kruskal算法做了变形,不是求最小生成树
//而是求最大边权值与最小边权值之差最小的生成树
//同样可以用kruskal算法的实现方法,采用并查集
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#define inf 10000000//边权 ...
- 2010-11-23 21:02
- 浏览 540
- 评论(0)
这题开始用常规思路总是超时,后来参考鸵鸟兄写的算法总算AC,注意内联函数及_int64类型的运用。
Int64 值类型表示值介于 -9,223,372,036,854,775,808 到 +9,223,372,036,854,775,807 之间的整数。
Int64 为比较此类型的实例、将实例的值转换为它的字符串表示形式以及将数字的字符串表示形式转换为此类型的实例提供了相应的方法。
编译用VS2008才不出错,老版本VC++ 6.0报错
#include <iostream>
#include <sstream>
using namespace std;
...
- 2010-11-23 18:52
- 浏览 503
- 评论(0)
这题调试了很久,开始自己试图按照自己的理解实现prim算法,但是总是出错。后来参考了网上的算法模板,总算把此题解决。算法模板可以用,但不可以滥用,最好是理解使用的细节,代码库不在多,好用是关键!
基本算法是:修好的路的边权值赋为0,再用prim求最小生成树输出权值。
#include <iostream>
#define MAXN 200
#define inf 10000
typedef int elem_t;
using namespace std;
elem_t prim(int n,elem_t mat[MAXN][MAXN],int* pre){
...
- 2010-11-22 20:45
- 浏览 521
- 评论(0)
这题挺简单,但是题目稍微有点长,基本没什么算法。
#include <iostream>
#include <string>
using namespace std;
string transfer(string s){
int num[10] = {0};
char res[80];
int i;
int j = 0;
for (i = 0 ; i < s.length() ; i++)
num[s[i] - '0']++;
for ( i = 0 ; i < 10; i++){
if (num[i] > ...
- 2010-11-22 20:07
- 浏览 516
- 评论(0)
今天看了联通沃商店的上海发布会,开复老师直言手机平台移动互联网的未来市场前景是当前PC平台市场的14倍,并做了一些数据分析,感觉智能手机软件开发今后的确是一个很热的方向。但还是想先把算法及编程功底打牢,再学习日新月异的技术也很容易了,不管怎么变,算法及编程永远是核心。
今天搭建了android开发平台,并做一些初步了解,摘录资料如下:
The steps below provide an overview of how to get started with the Android
SDK. For detailed instructions, start with the Ins ...
- 2010-11-22 13:05
- 浏览 382
- 评论(0)
四道题目都挺简单的,但是中间断断续续的因为睡觉、吃饭、体能测试、剪头发耽误了不少时间,基本不涉及什么算法,主要是字符串处理,大整数相加等,测试数据要考虑周全,先将题目辑录下来,27日比赛结束后再贴AC代码。
27日已经更新AC代码。
Problem A: 分数加减法
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 1552
Accepted: 500
Description
编写一个C程序,实现两个分数的加减法
Input
输入包含多行数据
每行数据是一个字 ...
- 2010-11-20 22:44
- 浏览 401
- 评论(0)
#include <iostream>
using namespace std;
//要求第一个人就必须报数,因此第一个人总是最先被删除的。
//因此可以把该问题看成是n-1个人的问题。题目就转变为,
//在n-1个人的规模下,满足0号是最后胜利者的最小的M。
int main(){
int i,n,m,k;
while(cin>>n,n){
for(m = 1;;m++)
{
k = 0;
for (i = 2; i < n;i++)
k = (k+m)%i;//k是每次的最后胜利者,向前逆推被删者
...
- 2010-11-20 00:04
- 浏览 609
- 评论(0)
滑雪问题,用动态规划,计算出每个点作为起始点时的最长,
注意计算的中间结果用矩阵保存,最后再所有路径中找出最长
那条就是答案,要理解动态规划与递归的区别与联系
#include <iostream>
using namespace std;
int data[102][102],longetr[102][102];
int m,n;
int cal(int i,int j){
int max = 0;
if (longetr[i][j] > 0)
//如果该点已经计算过直接返回路径长度,保存已有的计算结果这是动态规划优越之处
return ...
- 2010-11-18 21:49
- 浏览 580
- 评论(0)
#include <iostream>
#include <algorithm>
#include <string>
#define N 30
#define f(i,a,b) for(i=a;i<b;i++)//简化代码
using namespace std;
//图论中的染色问题,使得相邻两个节点颜色不同最少需要几种颜色
//搜索就是暴力的枚举,记住
bool maps[N][N];
int n,i,j,k,q;
char ch[N];
void solve(){
//如果出现四个区域,每个区域都和其他三个邻接,试探C42 ...
- 2010-11-18 19:43
- 浏览 371
- 评论(0)
理解算法的好方法可以单步调试查看关键变量的变化过程,如head和next,同时画出搜索树分析
#include <iostream>
#include <queue>
#define SIZE 100005
using namespace std;
//搜索是一种暴力的穷举
//分1 - 1 * 2三个方向广搜
queue<int> x;
bool vistied[SIZE];//记录点是否搜过
int step[SIZE];//记录当前搜索的步数
int bfs(int n,int k){
int head,next;
x.pus ...
- 2010-11-17 23:40
- 浏览 586
- 评论(0)
路线可能有多条,线路要求输出的是按字典序搜索出现的第一个路线;也就是要从(1,1)开始;
思路:从(1,1)点开始,直接深搜八个方向,注意方向的优先顺序;直接搜索就可以;
编程要细心,如将==写成=导致调试一个多小时,此类错误以后务必杜绝!
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int map[30][30],c,r,num;//最大的行数、列数和已遍历点数
string ans;
//教训由于一个==写成=号而调试近一个小 ...
- 2010-11-16 21:36
- 浏览 436
- 评论(0)
// 如何将空格符当做字符串一部分输入,应该用gets(string *)
// gets(s)函数与scanf("%s:",&s) 及scanf("%s",s) 相似,
// 但不完全相同,使用scanf("%s",&s);函数输入字符串时存在
// 一个问题,就是如果输入了空格会认为字符串结束,空格后的
// 字符将作为下一个输入项处理,但gets()函数将接收输入的整
// 个字符串直到遇到回车为止。
#include <iostream>
using namespace std;
in ...
- 2010-11-16 18:29
- 浏览 407
- 评论(0)