主题：[活动]第78次编程比赛题目
liuwenhan [专家分：20] 发布于 2008-11-30 12:27:00
1 . 1. 百度时间
Baidu的服务器上使用的不是北京时间，而是Baidu时间。Baidu时间的时分秒与北京时间相同，但是日期与北京时间不同，是用一个正整数表示从2000年1月1日开始经过了几天。
现在就请大家设计一个程序将北京时间转换为百度时间。在本题中，闰年的年份是400的倍数，或者是4的倍数但不是100的倍数。比如2000和8888均为闰年，但6100不是。
输入格式
输入数据的每一行为一个待转化的北京时间（不含空格和TAB），正确的格式包括两种：
一种为：YYYY-MM-DD，（YYYY表示四位数年份，MM为两位月份，DD为两位日期）；
另一种为：MM/DD/YYYY，（YYYY表示四位数年份，MM为两位月份，DD为两位日期）；
输出格式
每个数据输出一行。如果可以成功转换，输出一个正整数，否则输出Error。
输入样例 例
2000-01-01
AStar2007
05/26/2007
输出样例 例
0
Error
2702
1 . 2
已知一个字串由GBK汉字和ansi编码的数字字母混合组成，编写C语言函数实现从中去掉所有
ansi编码的的数字和字母（包括大小写).要求在原字串上返回结果。
int filter_ansi(char* gbk_string);
注：汉字的GBK编码范围是0x8140 - 0xFEFE
1 . 3 . 实习生小胖的百度网页过滤器
百度网页采集器(Baiduspider)每天从互联网收录数亿网页，互联网的网页质量参差不齐。百度的工程师们每天都在改进方法来判断一个网页质量的好坏，使质量差的网页出现在检索结果中较后的位置。现在实习生小胖想到一个很简单的方法来判断一个网页内容的好坏，方法如下：
1. 利用数据挖掘技术在互联网语料库中挖掘出一批有特点的词汇，分为好词和坏词两种，好词标上正的权重，坏词标上负的权重；
2. 通过好词和坏词词典对每个网页计算网页总权重：从第一个字开始匹配，找到一个好词则加上相应的权重，找到一个坏词则减去相应的权重，下一次匹配将从找到的词末尾的下一个位置开始。
3. 坏词采用正向最短匹配：从当前匹配位置开始的若干连续汉字，如果形成多个坏词，则只计算最短的那个坏词的权重，下一次匹配将从这个最短坏词末尾的下一个位置开始。
4. 好词采取正向最长匹配：从当前匹配位置开始的若干连续汉字，如果形成多个“有效”好词，则只计算最长“有效”好词的权重，下一次匹配从这个最长“有效”好词末尾的下一个位置开始。
5. “无效”好词的定义：好词的一部分本身是一个坏词；或者好词的一部分与后续相邻的若干字组成一个坏词。
现在小胖已经做好了第1步的工作，有一个好词和坏词的列表（词典），但是由于没有对中文文本处理的程序经验，他想请未来的百度之星们帮他完成这个程序。
输入格式
输入第一行为一个字符串（网页正文）。从第二行开始为词典，格式为“词 空格 词的权重”。权重为一个带符号32位整数。如果权重为正，则为好词，反之则为坏词；不存在重复的词，不存在权重为0的词。
作为“网页”的字符串中同时包含中文和ASCII字符，每个汉字占2个字节。并非“网页”中的所有字都在词典中。
输出格式
输出仅一行，为网页总权重（答案保证不超过带符号32位整数的范围）。
样例输入 例
小胖之喷火龙骑士!!
小胖 6
喷火 -1
喷火龙 -1
火龙 -1
龙 4
龙骑 3
龙骑士 2
骑士 -2
士 3
样例输出 例
7
样例解释
从“网页”中找到的好词为“小胖”和“龙”，坏词为“喷火”和“骑士”。特别要说明一下“龙”被识别为好词的原因——“喷火”和“喷火龙”均为坏词，按正向最短匹配得到“喷火”，接着往下匹配到好词“龙”、“龙骑”和“龙骑士”，但是由于“骑士”是坏词，所以“龙骑”、“龙骑士”无效而“龙”是最长的有效好词。注意题目描述中的匹配规则，好词的“有效”和“无效”只考虑该好词的一部分与后续字是否能够组成坏词，而不考虑和前面的字是否能够组成坏词——样例中的 “龙”虽然可以与前面的字组成坏词“喷火龙”和“火龙”，但由于这两个词都是未能匹配成功的坏词，因此对好词“龙”的词性没有影响，可以累积“龙”的权重。
注意事项
输入数据的中文采用GBK编码。
GBK：是又一个汉字编码标准，全称《汉字内码扩展规范》。采用双字节表示，总体编码范围为 8140-FEFE，首字节在 81-FE 之间，尾字节在 40-FE 之间，排除xx7F。总计 23940 个码位，共收入 21886 个汉字和图形符号，其中汉字（包括部首和构件）21003 个，图形符号 883 个。
1.4. Wii游戏开始啦！
为了在紧张的上班时间让员工们轻松些，百度休息室里放置着按摩椅、CD、高尔夫套装和Wii游戏机等休闲用品。其中最受欢迎的当然是游戏机。
Wii游戏机有两个手柄，每个手柄使用两节电池（这两个电池可以是不同的品牌），其中至少一块电池没电时该手柄没电。
工程师们在玩游戏时，总是用最简单的方式更换电池：有手柄没电时把所有没电的电池拿走，一一换上新电池即可（有电的电池总是继续使用）。当有手柄没电但没有新电池可用时才停止玩Wii。
告诉你每个品牌电池的使用时间以及该品牌电池的个数，请计算工程师们玩游戏时间的最小值和最大值。
输入格式
输入第一行为一个正整数n，表示电池的种数。接下来n行，每行两个整数L和F，表示使用时间为L的电池有F个（电池不必成对出现，即F可以是奇数）。
输出格式
输出仅一行，包含两个整数，分别表示工程师们的最短游戏时间和最长游戏时间（短的时间在前）。两个整数之间以空格隔开。
输入样例 例
3
3 2
5 2
8 2
输出样例 例
5 8
样例解释
有三对电池，使用时间分别为3小时、5小时和8小时。
方案1：一开始给手柄1使用一对3小时的电池，给手柄2使用一对5小时的电池，则3小时后手柄1没电，换上一对8小时的。再过2小时后，手柄2没电。此时已经没有电池可用了。总时间为5小时。
方案2：一开始给手柄1使用一对8小时的电池，给手柄2使用一对5小时的电池，则5小时后手柄2没电，换上一对3小时的。再过3小时后，手柄1和手柄2同时没电。此时已经没有电池可用了。总时间为8小时。
2.问题
某栋写字楼6层，有1部电梯，编写一个电梯仿真程序
A. 考虑如下条件
1. 每层楼都有上行和下行两个按键
2.电梯一开始停在1层
3.电梯可以容纳8个人
4.乘坐电梯的客人的请求频率，时间间隔和到达楼层是随机的
5.电梯的上下一层需要1秒
6.电梯空间有限，同时只能容纳一定数量的客人，如果已经达到人数额度，电梯将不理会任何请求
7.不考虑客人请求当前楼层和不请求楼层的情况
8.电梯的响应延迟为0（比如，电梯往3楼上行，3楼的客人在电梯到达3楼之前按上行键，程序有权调度电梯在3楼开门）
9.电梯的开关门时间和客人上下电梯时间为0，匀速运行
10.电梯调度算法不能预读尚未发生的请求（比如在10秒的时候电梯无法预知11秒时某层客人的请求)
11.客人请求发生在整数秒
B. 目标
1.在运送所有客人到达目标楼层的前提下电梯的总行程尽可能小
2. 设计一个接口，实现调度算法的可替换性（比如，通过重新实现该接口可以使系统使用其它算法）
C. 输入和输出
输入:
input.txt
客人的请求序列，格式为到达时间，所在楼层，请求楼层，假设该输入是按照时间递增的
比如：
input.txt
1 2 3
2 3 1
在1秒的时候有客人请求从2层到3层，2秒的时候有客人请求从3层到1层
输出: 设计一种简单实用的输出可以清晰地反映电梯的运转情况
[color=808000]前四题任选 一题,最后一题选做,有兴趣的朋友可以做一下.上面的题目都是出自论坛里的,还很少人回答!
这是很好的锻炼机会,希望大家踊跃参加，提交自己写的代码。请相信自己 ,期待很好的代码出现！
希望以前参加过的继续参加!
比赛结束时间: 2008 .12 .9 13:00:00
比赛已经结束了，好激动啊
明天上午公布结果，谢谢大家了，只要参加就是好样的
[/color]
最后更新于：2008-12-09 13:09:00
回复列表 （共19个回复）
沙发
liuwenhan [专家分：20] 发布于 2008-11-30 12:28:00
test
板凳
JKwangw [专家分：10] 发布于 2008-12-01 22:26:00
我选了第四题
c代码如下（新手呵呵）交流下！~
[code=c]
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int L; //电池使用时间
int F; //电池个数
int tag; //标志
}PlayWii;
int Max(PlayWii *a,int n);
int Min(PlayWii *a,int n);
void main()
{
int n,i,j;
PlayWii *a,t;
scanf("%d",&n);//输入电池种类数
a=(PlayWii *)malloc(n*sizeof(PlayWii));
for(i=0;i<n;i++)scanf("%d%d",&a[i].L,&a[i].F);//依次输入每种电池使用时间及个数
for(i=0;i<n-1;i++) //得到按使用时间由大到小的序列
for(j=i+1;j<n;j++)
if(a[j].L>a[i].L){t=a[i];a[i]=a[j];a[j]=t;}
printf("%d,",Max(a,n));
printf("%d",Min(a,n));
}
int Max(PlayWii *a,int n)
{
PlayWii *b;
b=(PlayWii *)malloc(n*sizeof(PlayWii));
int k,i,t=0,count=0,time=0;
for(i=0;i<n;i++)
{
a[i].tag=a[i].F%2;
k=a[i].F/2;
time+=k*a[i].L;
if(a[i].tag==1){b[++t]=a[i];count++;}
}
for(i=2;i<=count;i*=2)
time+=b[i].L;
return(time);
}
int Min(PlayWii *a,int n)
{
PlayWii *b,t;
int i,j,time=0;
b=(PlayWii *)malloc(n*sizeof(PlayWii));
for(i=0;i<n;i++)a[i].tag=0;
for(i=0;i<n;i++)b[i]=a[i];
for(i=0;i<n-1;i++) //得到按使用时间由小到大的序列
for(j=i+1;j<n;j++)
if(b[j].L<b[i].L)
{t=b[i];b[i]=b[j];b[j]=t;}
i=0;j=0;
while(i+j<=n-2)
{
if(a[i].F<b[j].F)
{time+=b[i].L*a[i].F;b[j].F-=a[i].F;a[i].tag=1;i++;}
else if(a[i].F>b[j].F)
{time+=b[j].F*b[j].L;a[i].F-=b[j].F;b[j].tag=1;j++;}
else {time+=a[i].F*a[i].L;a[i].tag=1;b[j].tag=1;i++;j++;}
}
if(a[i].tag==0)time+=a[i].F/2*a[i].L;
else if(b[i].tag==0)time+=b[i].F/2*b[i].L;
return(time);
}
[/code]
这个方法不是最优的，有更好的来交流啊！
3 楼
廖增祥 [专家分：3930] 发布于 2008-12-02 11:02:00
[code=c]
//////////////////////////////////////////////////////////////////////////
// 题目编号: 1.1
// 程序设计: 廖增祥
// Language: C ++
// 编译环境: Visual C++ 6.0
#include <stdio.h>
#include <string.h>
int nBaiduLoryDate;
int IsLeapYear(int nYear)
{
if (nYear % 400 == 0)
return 1;
if (nYear % 4 == 0 && nYear % 100 != 0)
return 1;
return 0;
}
int GetFullYearDays(int nYear)
{
if (IsLeapYear(nYear))
return 366;
return 365;
}
int GetMonthDays(int nYear, int nMonth)
{
switch (nMonth)
{
case 1:
case 3:
case 5:
case 7:
case 8:
case 10:
case 12:
return 31;
case 4:
case 6:
case 9:
case 11:
return 30;
}
if (IsLeapYear(nYear))
return 29;
return 28;
}
int GetDate(char *szDate, char cType, int &nYear, int &nMonth, int &nDay)
{
if (cType == '-')
{
nYear = szDate[0] - '0';
nYear = nYear * 10 + szDate[1] - '0';
nYear = nYear * 10 + szDate[2] - '0';
nYear = nYear * 10 + szDate[3] - '0';
nMonth = szDate[5] - '0';
nMonth = nMonth * 10 + szDate[6] - '0';
nDay = szDate[8] - '0';
nDay = nDay * 10 + szDate[9] - '0';
if (nMonth < 1 || nMonth > 12)
return 0;
if (nDay > GetMonthDays(nYear, nMonth))
return 0;
return 1;
}
if (cType == '/')
{
nMonth = szDate[0] - '0';
nMonth = nMonth * 10 + szDate[1] - '0';
nDay = szDate[3] - '0';
nDay = nDay * 10 + szDate[4] - '0';
nYear = szDate[6] - '0';
nYear = nYear * 10 + szDate[7] - '0';
nYear = nYear * 10 + szDate[8] - '0';
nYear = nYear * 10 + szDate[9] - '0';
if (nMonth < 1 || nMonth > 12)
return 0;
if (nDay > GetMonthDays(nYear, nMonth))
return 0;
return 1;
}
return 0;
}
[/code]
4 楼
廖增祥 [专家分：3930] 发布于 2008-12-02 11:03:00
[code=c]
// 接上
int IsDateValid(char *szDate)
{
int nLen = strlen(szDate);
if (nLen != 10)
return 0;
int nYear, nMonth, nDay;
if (szDate[0] >= '0' && szDate[0] <= '9' &&
szDate[1] >= '0' && szDate[1] <= '9' &&
szDate[2] >= '0' && szDate[2] <= '9' &&
szDate[3] >= '0' && szDate[3] <= '9' &&
szDate[4] == '-' &&
szDate[5] >= '0' && szDate[5] <= '9' &&
szDate[6] >= '0' && szDate[6] <= '9' &&
szDate[7] == '-' &&
szDate[8] >= '0' && szDate[8] <= '9' &&
szDate[9] >= '0' && szDate[9] <= '9')
{
if (!GetDate(szDate, '-', nYear, nMonth, nDay))
return 0;
return 1;
}
if (szDate[0] >= '0' && szDate[0] <= '9' &&
szDate[1] >= '0' && szDate[1] <= '9' &&
szDate[2] == '/' &&
szDate[3] >= '0' && szDate[3] <= '9' &&
szDate[4] >= '0' && szDate[4] <= '9' &&
szDate[5] == '/' &&
szDate[6] >= '0' && szDate[6] <= '9' &&
szDate[7] >= '0' && szDate[7] <= '9' &&
szDate[8] >= '0' && szDate[8] <= '9' &&
szDate[9] >= '0' && szDate[9] <= '9')
{
if (!GetDate(szDate, '/', nYear, nMonth, nDay))
return 0;
return 1;
}
return 0;
}
int GetLoryYear(int nYear, int nMonth, int nDay)
{
int i;
int nTotal = 0;
for (i = 1; i < nYear; i ++)
{
nTotal += GetFullYearDays(i);
}
for (i = 1; i < nMonth; i ++)
{
nTotal += GetMonthDays(nYear, i);
}
nTotal += nDay;
return nTotal;
}
int GetBaiduYear(int nYear, int nMonth, int nDay)
{
int nLoryDate = GetLoryYear(nYear, nMonth, nDay);
return nLoryDate - nBaiduLoryDate;
}
int main()
{
char szDate[100];
int nYear, nMonth, nDay;
char cType;
nBaiduLoryDate = GetLoryYear(2000, 1, 1);
while (gets(szDate))
{
if (IsDateValid(szDate))
{
if (szDate[2] == '/')
cType = '/';
else
cType = '-';
GetDate(szDate, cType, nYear, nMonth, nDay);
printf("%d\n", GetBaiduYear(nYear, nMonth, nDay));
}
else
{
printf("Error\n");
}
}
return 0;
}
5 楼
廖增祥 [专家分：3930] 发布于 2008-12-02 11:16:00
LZ，偶的代码太长了
LS 两个回复加到一起啊
6 楼
q96456 [专家分：10] 发布于 2008-12-04 23:52:00
#include <iostream.h>
class day
{
int d_year;
int d_month;
int d_data;
public:
day(){};
day(int year,int month,int data)
{
d_year=year;
d_month=month;
d_data=data;
}
void print()
{
cout<<d_year<<"年";
cout<<d_month<<"月";
cout<<d_data<<"日";
};
friend day operator+(day& ,int);
~day(){};
};
day operator +(day& a,int data)
{
int i;
int tian=0;
int num=0 ;//一年的天数
int monthp_day[13]={0.31,28,31,30,31,30,31,31,30,31,30,31};
int monthr_day[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
//int num;//一年的天数
if(a.d_month<2)
{
for(i=1;i<=a.d_month;i++)
{
tian+=monthp_day[i];
}
tian+=(monthp_day[a.d_month]+a.d_data);
tian=num-tian;
}
else
{
if((a.d_year%4==0&&a.d_year%100!=0)||a.d_year%400==0)
{
for(i=0;i<=a.d_month-1;i++)
{
tian+=monthr_day[i];
}
tian+=(monthr_day[a.d_month]+a.d_data);
}
else
{
for(i=a.d_month+1;i<=12;i++)
{
tian+=monthp_day[i];
}
tian+=(monthp_day[a.d_month]+a.d_data);
}
}
while(data!=-1)
{
//data++;
while(data > 0)
{
if(a.d_year%100==0 && a.d_year%400 != 0)
num=365;
else if(num%4==0)num= 366;
else num=365;
data-=num;
a.d_year++;
}
a.d_year--; // +2000后，得到年数
data+=num; //多减了一年的信息，加回去
a.d_month=1;
while(data>0)
{
if(num == 365)
data-=monthp_day[a.d_month];
else
data-=monthr_day[a.d_month];
a.d_month++;
} //找到月号
a.d_month--;
if(num == 365)
data+=monthp_day[a.d_month];
else data+=monthr_day[a.d_month];//多减了一个月，加回去
a.d_data=data;
cin>>data;
}
#include "head.h"
#include <conio.h>
void main()
{
day a(2000,1,1);
//day b;
int m;
cin>>m;
a+m;
a.print();
getch();
}
这个是我做实习是的一道题的代码 和这个基本是一样的 我没改进发了 请大家指教
7 楼
chaosuper85 [专家分：380] 发布于 2008-12-06 00:13:00
/*
**第一题 北京时间转换为百度时间
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int
dayofyear(int i) //compute the days from 2000 to the year
{
int sum=0,k;
for (k=2000;k<i;k++)
{
if ((k%400==0)||((k%4==0)&&(k%100!=0))) //366 days
sum+=366;
else
sum+=365;
}
return sum;
}
int
dayofmonth(int i) //compute the days form 1 to the month
{
int sum=0,k;
for (k=1;k<i;k++)
{
if (k==1||k==3||k==5||k==7||k==8||k==10||k==12)
sum+=31;
else if (k==2&&((k%400==0)||((k%4==0)&&(k%100!=0))))
sum+=29;
else if (k==2&&!((k%400==0)||((k%4==0)&&(k%100!=0))))
sum+=28;
else
sum+=30;
}
return sum;
}
int
dayofday(int i) //compute the days from 1 to the day
{
return (i-1);
}
void
error(void) //print the error information
{
printf("Error\n");
}
int
check1(char *ch) //check whether the input is changable
{
char *cha=ch;
if (*(cha+4)=='-'&&*(cha+7)=='-') return 1;
else return 0;
}
int
change1result(char *ch) //change the time format YYYY-MM-DD into baidu time
{
char *cha=ch;
char stry[5],strm[3],strd[3];
int y,m,d,sumy=0,summ=0,sumd=0,i;
for (i=0;i<4;i++)
stry[i]=*(cha+i);
for (i=0;i<2;i++)
strm[i]=*(cha+i+5);
for (i=0;i<2;i++)
strd[i]=*(cha+i+8);
y=atoi(stry);
m=atoi(strm);
d=atoi(strd);
sumy=dayofyear(y);
summ=dayofmonth(m);
sumd=dayofday(d);
return (sumy+summ+sumd);
}
int
check2(char *ch) //check whether the input is changable
{
char *cha=ch;
if (*(cha+2)=='/'&&*(cha+5)=='/') return 1;
else return 0;
}
int
change2result(char *ch) //change the time format MM/DD/YYYY into baidu time
{
char *cha=ch;
char stry[5],strm[3],strd[3];
int y,m,d,sumy=0,summ=0,sumd=0,i;
for (i=0;i<2;i++)
strm[i]=*(cha+i);
for (i=0;i<2;i++)
strd[i]=*(cha+i+3);
for (i=0;i<4;i++)
stry[i]=*(cha+i+6);
m=atoi(strm);
d=atoi(strd);
y=atoi(stry);
sumy=dayofyear(y);
summ=dayofmonth(m);
sumd=dayofday(d);
return (sumd+summ+sumy);
}
int
main(void)
{
while (1)
{
char *str;
puts("please input the time to be changed...");
scanf("%s",str);
if (strcmp(str,"exit")) //input exit to quit
{
if (check1(str))
printf("the changed result of baidu time is:\n%d\n",change1result(str));
else if (check2(str))
printf("the changed result of baidu time is:\n%d\n",change2result(str));
else
error();
}
else break;
}
return 0;
}
8 楼
shbgreenery [专家分：10] 发布于 2008-12-06 13:56:00
1.4
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
int main()
{
int kind;
int i;
int count=0;
int ji=0;
scanf("%d",&kind);
int *c=(int*)malloc(sizeof(int)*kind);
int *d=(int*)malloc(sizeof(int)*kind);
for(i=0;i<kind;i++)
{
scanf("%d %d",&c[i],&d[i]);
count+=d[i];
}
int *a=(int*)malloc(sizeof(int)*(count));
int *b=(int*)malloc(sizeof(int)*(count));
for(i=0;i<kind;i++)
{
for(int j=0;j<d[i];j++)
{
a[ji]=c[i];
b[ji]=c[i];
ji++;
}
}
int n=count;
int min=0,max=0;
sort(a,a+n);
if(n<4)
min=0;
else
{
for(i=0;i<n-3;i++)
{
min+=a[i];
a[i+1]-=a[i];
a[i+2]-=a[i];
a[i+3]-=a[i];
}
}
cout<<min<<" ";
sort(b,b+n);
if(n<4)
max=0;
else{
while(b[n-4]!=0)
{
max+=b[n-4];
b[n-4]=0;
b[n-3]-=b[n-2];
b[n-2]-=b[n-4];
b[n-1]-=b[n-4];
sort(b,b+n);
}
}
cout<<max;
}
9 楼
lifengjiang [专家分：480] 发布于 2008-12-08 16:45:00
[em2]
10 楼
alexanderip [专家分：30] 发布于 2008-12-09 00:52:00
//Programmer Ip Hiu Pan
#include <stdio.h>
#define DATE_FORMAT_LENGTH 11
#define MSG_ERROR -1
#define MSG_NORMAL 1
#define TRUE 1
#define FALSE 0
#define NORMAL_YEAR_DAY 365
#define LEAP_YEAR_DAY 366
int checkLeapYear(int year){ //检查闰年
if((year % 400) == 0)
return TRUE;
else if( (year % 4 ==0) && (year % 100 != 0))
return TRUE;
else
return FALSE;
}
int giveNum(char year[],char month[],char day[]){
char temp[5]; //暂存年月日的字符串
int index;
int yearNum, monthNum, dayNum ; //年月日的数字
int countLeapYear; //贮存闰年数
int numOfDay; // 由二千年至该天的日数
int numOfLongMonth ; //贮存长月份
//检测日期是否输入合理数字
if(year[0] < '2'){ //年份头一数字不会低于二
return MSG_ERROR ;
}else
for(index =0; index < 4; index++){
if(year[index]< '0' || year[index]>'9'){ //检查是否为数字年份
return MSG_ERROR ;
}else
temp[index] = year[index];
}
我来回复
您所在位置：