博文
第36次编程比赛(冠军的代码)(2006-08-11 13:51:00)
摘要：//昨天在9楼交过一次。那个算法空间占用太大O(n*n)，在n=1000时临时数据需要超过500M内存。//所以又想了这个算法：将1/2,1/3,....1/n这n－1个元素构造小顶堆。每次从堆顶拿出一个元素，放到farey[]中。//从堆顶删去这个元素，加入分母相同分子更大的元素（如果存在），整理堆。重复，直到堆为空。//时间复杂度与我的上一个程序相同，但空间是线性的。#include<iostream.h>#include<string.h>//求最大公约数int gcd(int a,int b) { if (a%b==0) return b; return gcd(b,a%b);}//数字转字符串void num2str(int x,char* str) { int p=0; long t=1; while (t*10<=x) t*=10; while (t>0) { str[p++]=char(x/t+48); x%=t; t/=10; } str[p]=0;}//字符串连接函数//开始用的是strcat，时......
第36次编程比赛第1题题目(2006-08-05 15:47:00)
摘要：法雷序列：对任意给定的一个自然数n，将分母小于等于n的不可约的真分数按升序排列，并且在第一个分数之前加上数0/1，在最后一个分数之后加上1/1，这个序列称为n级法雷序列，以Fn表示。例如，F8为：0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1。请编程输出任意的Fn序列。函数原型：// n － 序列级数// farey[] - 存放Fn序列，以','分隔void FareySequence(int n, char farey[]);例：输入：5数组中存放结果为：0/1,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1/1......
第35次编程比赛(冠军的代码)(2006-07-28 10:02:00)
摘要：作者：boxertony
// vc6下编译通过// 为使用qsort进行数据比较int cmp(const void*x, const void *y){ return (*(int*)x - *(int*)y);}int MaxVisitors(int X[], int Y[], int n){ qsort((void*)X, n, sizeof(int), cmp); qsort((void*)Y, n, sizeof(int), cmp); int i, j; int start_pos = 0; // 进校循环起始位置 int max = 0; // 最大车辆数 for(i=0; i<n; ++i) { for(j = start_pos; j<n......
第35次编程比赛第一题(2006-07-21 14:09:00)
摘要：近年来，随着私家车的普及，车辆停放这一社会问题日益突出。华东地区某高校由于地处市中心附近，交通便捷，结果若大校区成了社会车辆的免费露天停车场，给学校的治安、管理等各方面带来严重问题。 鉴于这一状况给学校的恶劣影响，学校领导决定出台一系列的规定来对进出校门的车辆进行管理，而在这之前，他们迫切需要有人提供一天内究竟最多有多少车辆停放于校内的报告，以便使出台的规定能适应当前的局面。 我光荣地接受了这项任务，并得到了一份某天的车辆进出时刻记录表。请问我该如何又快又好的解决该问题？定义函数：int MaxVisitors(int X[], int Y[], int n)参数说明：X[i]：车辆进校时刻 Y[i]：车辆出校时刻 n：X，Y长度，1<=n<=10000 返回值： 学校内的最多的车辆数目。 X[i],Y[i]满足 1=<X[i]<Y[i], 且X[i]和Y[i]一一对应。 例如： 下标i 进校时刻 出校时刻 0 &nb......
第34次编程比赛第2题(2006-07-09 10:19:00)
摘要：问题描述:某人有一个奇怪的嗜好，就是看见一个单词就有找它所有的变位词的冲动。一个单词的变位词就是该单词所有字母的一个排列（单词中字母可能重复）。输入输出格式：输入数据第一行为一个整数n，1<=n<=10^5，之后n行每行只包含一个单词，不含词组。这些单词构成了字典。每个单词长度不大于9个字母。接着一行为一个整数m，1<=m<=100，表示将看见的单词数。之后 m 行每行包含一个单词。（题目中出现的每个单词都只由小写字母和 '-' 组成，可能字符 27 个）对应随后看到的每个单词，输出落在字典里的它的变位词的个数。输入样例3teaateeat3ateabceat输出样例303通过标准输入/输出进行输入/输出。关于题目有任何问题到如下处提：http://www.programfan.com/club/showbbs.asp?id=179992......
第34次编程比赛题目（第1题）(2006-07-09 10:16:00)
摘要：题目描述：某实验室的管理员管理着一跟长为1米的电线。做实验的人可以从他那里借走或是还回电线。该管理员采用了以下的管理办法：1、将开始时的电线放在柜子里。2、当有人要还回电线时，把还来的电线放到柜子里。3、当有人要借走电线时，在柜子里找到长度大于等于借者所要求长度的所有电线，从中选出长度最短的一根，然后剪下借者需要的长度，将剪下的部分借出。如果有剩下的部分，将它放到柜子里。如果借电线时柜子里没有可以满足要求的电线，则无法借出。请根据以上规则编写四个函数，对管理过程进行模拟：void Start(void); /* 保证只在实验开始时调用一次 */void In(int length); /* 实验开始后、实验结束前可能调用多次 */int Out(int length); /* 实验开始后、实验结束前可能调用多次 */void End(void); /* 保证只在实验结束时调用一次 */四个函数的功能介绍：Start函数：用于初始化。End函数： 用于处理释放内存等善后工作，如果不需要善后，此函数中可以没有任何代码。In函数： 用于处理还回电线，其中参数length表示了还回的长度，单位为厘米。Out函数： 用于处理借出电线，其中参数length表示了还回的长度，单位为厘米。如果成功借出，返回1，否则返回0。补充：因为有可能有人上一次实验时有剩余的电线，在这一次实验是还回。所以如果出现柜子中的电线总长度大于初始值，或者还回了一段“没被借出”的电线，也是合理的。测试时的程序可能像下面这样：（伪代码）int main(){ ......
pku(1580)一些解释(2006-06-20 19:20:00)
摘要：
C
A
R
C
A
R
T
C
A
R
T
C
A
R
T
C
A
R
T
C
A
R
T
C
A
R
T
字符串a不动，把字符串b动.第一个测试数据（CAR CART）总共就可以得到上面的情况。变量j记录循环。变量i开始其实是表示字符串b最后一个字符的位置。 if(j>strlen(a)-1) i=strlen(a)-1;把i移动到能和字符串a比较的位置。while(i>=0)防止i在b中出界。 for(i=2;i<=strlen......
pku(1580)(2006-06-20 18:04:00)
摘要：#include <iostream.h>
#include <string.h>
int main()
{
int i,j;
char a[100],b[100];
int sum,sum1;
int s2,w1,w2,w;
while(cin>>a)
{
if(strcmp(a,"-1")==0)
return 0;
cin>>b;
sum=0;
for(j=0;j<strlen(a)+strlen(b);j++)
{
sum1=0;
i=j;
if(j>strlen(a)-1)
i=strlen(a)-1;
while(i>=0)
{
if(a[i]==b[strlen(b)-j+i])
sum1++;
i--;
}
if(sum<sum1)
sum=sum1;
}
//cout<<sum<<endl;
cout<<"appx("<<a<<","<<b<<") = ";
w1=strlen(a);
w2=strlen(b);
w=w1+w2;
s2=2*sum;
if(s2==0)
cout<<"0\n";
else if(s2==w)
cout<<"1\n";
else
{
for(i=2;i<=strlen(a);i++)
{
while(w%i==0 && s2%i==0)
{
s2=s2/i;
w=w/i;
}
}
cout<<s2<<"/"<<w<<endl;
}
}
}......
zju(2005-10-07 13:42:00)
摘要：http://acm.zju.edu.cn/icpc2005/pre/show_problem.php?cid=141&pid=1004
#include <stdio.h>#include <string.h>#include <stdlib.h>struct Team{ char Nm[20]; int w; int d; int l; int Pt; int Gd;};int comp(const void *a,const void *b){ struct Team *t1=(struct Team *)a; struct Team *t2=(struct Team *)b; if(t1->Pt>t2->Pt) return 1; if(t1->Pt<t2->Pt) return -1; if(t1->Gd>t2->Gd) return 1; if(t1->Gd<t2->Gd) return -1; if(strcmp(t1->Nm,t2->Nm)<0) return 1; return -1;} int main(){ struct Team T[20000]; char T1[20],T2[20]; int v1,v2; int n,i,j; int N; int flag,pos; while(scanf("%d",&n)) { N=0; for(i=0;i<n;i++) { scanf("%s %d:%d %s",T1,&v1,&v2,T2); for(j=0,flag=0;j<N;j++) { if(strcmp(T1,T[j].Nm)==0)......
acm网址(2005-09-27 10:48:00)
摘要：0） 29届ACM 上海赛区官方网站
http://acm.sjtu.edu.cn/chinese/index.html
1) 中山大学 逸仙时空 BBS 分类精华 程序设计竞赛:
http://bbs.zsu.edu.cn/bbs0an?path=boards/ACMICPC
2) 浙江大学 ACM ICPC 网站
http://acm.zju.edu.cn
3) 北京大学 ACM ICPC 网站
http://acm.pku.edu.cn
4) 汕头大学 ACM ICPC 网站
http://acm.stu.edu.cn
5）西安交大ACM ICPC 网站
http://acm.eeyes.net/
6）国外 ACM ICPC 网
http://acm.timus.ru
http://acm.uva.es/contest
http://www.acm.shu.edu.cn/......