博文
导线和开关(2005-09-27 10:45:00)
摘要：#include <iostream.h>
int M; //导线条数
int *link; //link[i]为连接导线i的开关序号
//判断集合p1中的元素是否全为零,若全为零,则返回true;反之,返回false;
bool empty(int p1[])
{
int i;
bool falg=true;
for(i=0;i<M;i++)
if(p1[i]!=0)
{
falg=false;
break;
}
return falg;
}
//判断导线和开关之间的连接,其中开关左区间的起始下标为head,终止下标为tail;区间开关状态为state:0表示断开,1表示闭合.
void check(int *p1,int head,int tail,int state)
{
int *p2=new int [M];
int i,j;
char ch;
if(!empty(p1))
{
if(head==tail) //如果左区间只剩下一个开关,则将p1中所有导线与这个开关连接
{
for(i=0;i<M;i++)
......
ACM and STL(2005-09-27 10:42:00)
摘要：DNA Sorting
Time Limit:1000MS Memory Limit:10000K
Description
One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to its right and E is greater than one letter to its right. This measure is called the number of inversions in the sequence. The sequence ``AACEDGG'' has only one inversion (E and D)---it is nearly sorted---while the sequence ``ZWQM'' has 6 inversions (it is as unsorted as can be---exactly the reverse of sorted).
You are responsible for cataloguing a sequence of DNA strings (sequences containing only the four letters A, C, G, and T). However, you want to catalog them, not in alphabetical order, but rather in order of ``sortedness'', from ``most sorted'' to ``least sorted''. All the strings are of the same length.
Input
The first line contains two integers: a positive integ......
ACM竞赛之新人向导(2005-09-27 10:40:00)
摘要：我们学校的计算机学院从去年起开始组织学生参加世界上最具权威性的大学生程序设计竞赛——ACM/ICPC。从这学期开始，学院计划有组织地进行训练和讲座，以帮助大家在有限的时间内尽可能多地提高自己的能力，这对有兴趣投入数据结构与算法研究的同学来说无疑是一件好事。但是，刚刚接触信息学领域的同学往往存在很多困惑，不知道从何入手学习，在这篇文章里，我希望能将自己不多的经验与大家分享，希望对各位有所帮助。
一、语言是最重要的基本功
无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降低程序的执行效率。
接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。
而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。
C++的另一个支持来源于标准模版库（STL），库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度，这可以节省一些时间。但是，与此相对的，使用STL要在效率上做出一些牺牲，对于输入规模很大的......
ACM/ICPC整体介绍(2005-09-27 10:36:00)
摘要：一、ACM/ICPC简介
ACM国际大学生程序设计竞赛（ACM/ICPC ：ACM International Collegiate Programming Contest）是由国际计算机界历史悠久、颇具权威性的组织ACM( 美国计算机协会）学会（Association for Computer Machineary）主办，是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛，其目的旨在使大学生运用计算机来充分展示自已分析问题和解决问题的能力。该项竞赛从1970年举办至今已历25届，因历届竞赛都荟萃了世界各大洲的精英，云集了计算机界的“希望之星”，而受到国际各知名大学的重视，并受到全世界各著名计算机公司如Microsoft(微软公司) 、IBM等的高度关注，成为世界各国大学生最具影响力的国际级计算机类的赛事，ACM所颁发的获奖证书也为世界各著名计算机公司、各知名大学所认可。
该项竞赛是年度性竞赛，分区域预赛和国际决赛两个阶段进行，各预赛区第一名自动获得参加世界决赛的资格，世界决赛安排在每年的3~4月举行，而区域预赛安排在上一年的9月~12月在各大洲举行。从1998年开始，IBM公司连续5年独家赞助该项赛事的世界决赛和区域预赛。这项比赛是以大学为单位组队（每支队由教练、3名正式队员，一名后备队员组成）参赛，要求在5个小时内，解决5~8到题目。
ACM/ICPC的区域预赛是规模很大，范围很广的赛事，近几年，全世界有1000多所大学， 2000多支参赛队在六大洲的28~30个赛站中争夺世界决赛的60~66个名额，去年我校举办的区域预赛，就有来自50多所高校的100多支队伍参加，其激烈程度可想而知。
与其他编程竞赛相比，ACM/ICPC题目难度更大，更强调算法的高效性，不仅要解决一个指定的命题，而且必需要以最佳的方式解决指定的命题；它涉及知识面广，与大学计算机系本科以及研究生如程序设计、离散数学、数据结构、人工智能、算法分析与设计等相关课程直接关联，对数学要求更高，由于采用英文命题，对英语要求高，ACM/ICPC采用3人合作、共用一台电脑，所以它更强调团队协作精神；由于许多题目并无现成的算法，需要具备创新的精神，ACM/ICPC不仅强调学科的基础，更强调全面素质和能力的培养。ACM/ICPC是一种全封闭式的竞赛，能对学生能力进行实时的全面的考察，其成绩的真实......
H: Search Strategy(2005-09-25 12:20:00)
摘要：2005' ACM/ICPC Asia Preliminary Internet Chengdu Site
H: Search Strategy
Submit your solution
Description
You must have enjoyed the convenience that web search engines brought to you, but have you ever attempted to build your own search engine? Now it's the time.
The common aim of different search engines is to make search results as close as possible to people's purpose. Hence there are lots of strategies to evaluate the authority of web pages being searched. The most widely used search engine Google uses a technology named PageRank to rank results pages by calculating the importance of sites where these pages come from. For simplicity, we use a simplified strategy similar with PageRank to organize search results.
Your partners have designed an internet crawler to collect web information for you, you are only required to rank search results of keyword in the rule below:
For a specific web page A, there may be some hyperlinks linked to other websites (html......
Search Strategy (2005-09-25 12:17:00)
摘要：#include <iostream.h>
#include <fstream.h>
ifstream f("a.txt");
#define cin f
#include <string.h>
int fun(char *s,char *t)
{
int pos1,pos2,i;
pos2=0;
while(s[pos2]!='\0')
{
if(s[pos2]=='.')
{
if(s[pos2+1]=='c' && s[pos2+2]=='o' && s[pos2+3]=='m' && (s[pos2+4]=='\0' ||
s[pos2+4]=='/' || s[pos2+4]=='.'))
{
pos1=pos2-1;
while(s[pos1]!='.')
pos1--;
goto loop;
}
else if (s[pos2+1]=='n' && s[pos2+2]=='e' && s[pos2+3]=='t' && (s[pos2+4]=='\0' ||
s[pos2+4]=='/' || s[pos2+4]=='.'))
{
pos1=pos2-1;
while(s[pos1]!='.')
&......
pku(2601)(2005-09-09 20:01:00)
摘要：#include <iomanip.h>
#include <iostream.h>
int main()
{
int n;
float a,b,c,sum=0.0,c1=0.0;
cin>>n;
cin>>a>>b;
for(int i=1;i<=n;i++)
{
cin>>c;
c1+=c;
sum+=c1;
}
cout.setf(ios::fixed);
cout<<setprecision(2)<<(n*a+b-2*sum)/(n+1)<<endl;
}......
pku(2608)(2005-09-09 20:01:00)
摘要：#include <iostream.h>
#include <string.h>
int fun(char a)
{
if(a=='B' || a=='F' || a=='P' || a=='V')
return 1;
if(a=='C' || a=='G' || a=='J' || a=='K' || a=='Q'
|| a=='S' || a=='X' || a=='Z')
return 2;
if(a=='D' || a=='T')
return 3;
if(a=='L')
return 4;
if(a=='M' || a=='N')
return 5;
if(a=='R')
return 6;
return 0;
}
int main()
{
char s[20];
int i......
网络流(2005-09-05 15:56:00)
摘要：#include<iostream.h>
#include<stdio.h>
const maxn=1000;
typedef struct Nbour
{
int k;
int f,c;
Nbour *next,*g;
}Nbour,*Link;
typedef struct Wtype
{
int p,d;
Nbour *w;
}Wtype;
int N,stt,trm;
Link Nbs[maxn];
Wtype Pth[maxn];
void Insert(int u,int v,int c)
{
Link x;
x=Nbs[u];
while(x!=NULL&&x.k!=v)
x=x.next;
if(x!=NULL)
x.c=c;
else
{
x.k=v;
x.c=c;
x.f=0;
&nb......
Enigma(f)(2005-09-04 16:56:00)
摘要：#include<iostream.h>
#include<fstream.h>
//#include<math.h>
int m[21][51],w[21],v[21],flag[21];
int min(int a,int b)
{
if(a>b)
return b;
else
return a;
}
int max(int a,int b)
{
if(b>a)
return b;
else
return a;
}
void knapsack(int n,int c)
{
int i,j;
// int k=n-1;
int jMax=min(w[n]-1,c);//jMax表示第N个物品不能装入的最大容积
for(i=0;i<=jMax;i++)
{
m[n][i]=0;
&......