帮助|留言交流|
首 页 阅览室 馆友 我的图书馆
来自：babylls > 馆藏分类
配色： 字号：大中小
2015编程之美资格赛题解
2015-04-21 | 阅：  转：  |  分享 
  
2015编程之美资格赛

1/11



第一题：2月29日

描述

给定两个日期，计算这两个日期之间有多少个2月29日（包括起始日期）。

只有闰年有2月29日，满足以下一个条件的年份为闰年：

1.年份能被4整除但不能被100整除

2.年份能被400整除

输入

第一行为一个整数T，表示数据组数。

之后每组数据包含两行。每一行格式为"monthday,year"，表示一个日期。month为{"January",

"February","March","April","May","June","July","August","September","October",

"November","December"}中的一个字符串。day与year为两个数字。

数据保证给定的日期合法且第一个日期早于或等于第二个日期。

输出

对于每组数据输出一行，形如"Case#X:Y"。X为数据组数，从1开始，Y为答案。

数据范围

1≤T≤550

小数据：

2000≤year≤3000

大数据：

2000≤year≤2×10

9



样例输入

4

January12,2012

March19,2012

August12,2899

August12,2901

August12,2000

August12,2005

February29,2004

February29,2012

样例输出

Case#1:1

Case#2:0

Case#3:1

Case#4:3

2015编程之美资格赛

2/11



解析：编程之美第一题一般都是模拟题，主要考察思维清晰度与细节问题。

代码：

#include

#include

#include

usingnamespacestd;

stringmonths[]={"January","February","March","April","May","June","July","August",

"September","October","November","December"};

boolis_leapyear(longlongy){

return((y%4==0&&y%100!=0)||y%400==0);

}

intmain()

{

intT;

cin>>T;

intT1=T;

charm1[20];charm2[20];intm11,m22,d1,d2;longlongy1,y2;

while(T--){

scanf("%s%d,%ld\n%s%d,%ld",&m1,&d1,&y1,&m2,&d2,&y2);

for(inti=0;i<12;i++)

{if(months[i]==m1)m11=(i+1);

if(months[i]==m2)m22=(i+1);}

longlongN=0;

if(y1==y2&&is_leapyear(y1)){

if(m11<=2&&((m22>2)||(m22==2&&d2==29)))

N=1;

}

if(y1
for(longlongj=y1+1;j
if(is_leapyear(j))N++;

if(is_leapyear(y1)&&m11<=2)N++;

if(is_leapyear(y2)&&(m22>2||(m22==2&&d2==29)))N++;



}

cout<<"Case#"<
}

return0;

}

思路比较清晰：判断year1+1----year2-1之间有多少个闰年，再单独判断两个端点。

问题也比较突出：英语的月份转换，可以用map；更大的问题是在判断中间有多少个闰年的时候有没有必

要逐个去判断。







2015编程之美资格赛

3/11



NO1代码：

#include

#include

#include

#include

#include

usingnamespacestd;



#definemxn200005

#defineLLlonglong

#defineMPmake_pair

#defineREP(i,a,b)for(inti=a;i<=b;++i)

#defineFOR(i,a,b)for(inti=a;i


strings[]={"January","February","March","April","May","June","July","August","September",

"October","November","December"};

mapmp;

voidinit(){

FOR(i,0,12)mp[s[i]]=i+1;

}

intcal(inty,intm,intd){

intret=y/4-y/100+y/400;

if(y%400==0||y%4==0&&y%100!=0)

if(m==1||m==2&&d<29)

--ret;

returnret;

}



intmain()

{

init();

intd,y,cas=0,t;

charss[100];

scanf("%d",&t);

while(t--){

scanf("%s%d,%d",ss,&d,&y);

intans=0;

ans-=cal(y,mp[ss],d);

if(y%400==0||y%4==0&&y%100!=0)

if(mp[ss]==2&&d==29)

++ans;

scanf("%s%d,%d",ss,&d,&y);

ans+=cal(y,mp[ss],d);

printf("Case#%d:%d\n",++cas,ans);

2015编程之美资格赛

4/11



}

return0;

}

思路：

ret=y/4-y/100+y/400y之前包含y最近的闰年是第几个闰年









intcal(inty,intm,intd){

intret=y/4-y/100+y/400;

if(y%400==0||y%4==0&&y%100!=0)

if(m==1||m==2&&d<29)

--ret;

returnret;

}

端点A（B）是闰年但是取不到就减去

ret(B)-ret(A)属于(A,B]B端点没问题，A端点需要再考虑

if(m==1||m==2&&d<29)

--ret;

末尾端点的判断条件，现在A在B-A中位起始端点

Whenm==2&&d==29,++ans













































AB

2015编程之美资格赛

5/11



第三题：基站选址

描述

需要在一个N×M的网格中建立一个通讯基站，通讯基站仅必须建立在格点上。

网格中有A个用户，每个用户的通讯代价是用户到基站欧几里得距离的平方。

网格中还有B个通讯公司，维护基站的代价是基站到最近的一个通讯公司的路程（路程定义

为曼哈顿距离）。

在网格中建立基站的总代价是用户通讯代价的总和加上维护基站的代价，最小总代价。

输入

第一行为一个整数T，表示数据组数。

每组数据第一行为四个整数：N,M,A,B。

接下来的A+B行每行两个整数x,y，代表一个坐标，前A行表示各用户的坐标，后B行表示

各通讯公司的坐标。

输出

对于每组数据输出一行"Case#X:Y"，X代表数据编号（从1开始），Y代表所求最小代价。

数据范围

1≤T≤20

1≤x≤N

1≤y≤M

1≤B≤100

小数据

1≤N,M≤100

1≤A≤100

大数据

1≤N,M≤10

7



1≤A≤1000

样例输入

2

3341

12

21

23

32

22

4442

12

24

2015编程之美资格赛

6/11



31

43

14

13

样例输出

Case#1:4

Case#2:13

解析：编程之美第三题一般都是实际应用题，主要考察建模能力与实际解决问题的能力。

没有太好的思路，最小代价为距离的平方和+最近邻（？指的是哪种距离）的曼哈顿距离

考虑到距离为平方项，占主导地位，而且可以求导得到最值在平均值附近。那么就遍历平均值邻

域的点。小数据竟然还AC了，不可思议。

注：大数据不AC的原因在于最近邻用的是欧几里得距离距离理解错误

设选取的基站位置为（x,y）,第i个用户的位置为(,),1,2...

ii

axayiA=，第i个通讯公司的位

置为(,),1,2...

ii

bxbyiB=，则代价为：

22

1111

cos()()

iAiAiBiB

iiii

iiii

taxxayybxxbyy

====

====

=?+?+?+?

∑∑∑∑



对x和y求解偏导得

1

cos

2()

iA

i

i

dt

xaxC

dx

=

=

=?+

∑



1

cos

2()

iA

i

i

dt

yayC

dy

=

=

=?+

∑



当

cos

0

dt

dx

=,

cos

0

dt

dy

=时，cost取的最小值，此时：

i

ax

xax

A

==

∑



i

ay

yay

A

==

∑



故x取ax,y取ay时，cost取最小值，此时x，y是浮点数，由于基站只能落在网格上，故

x，y取值只能在其周围的四个点。







2015编程之美资格赛

7/11



NO1代码：

#include

#include

#include

#include

#include

usingnamespacestd;



#definemxn200005

#defineLLlonglong

#defineMPmake_pair

#defineREP(i,a,b)for(inti=a;i<=b;++i)

#defineFOR(i,a,b)for(inti=a;i


intdx[]={0,0,0,1,1,1,-1,-1,-1};

intdy[]={0,1,-1,0,1,-1,0,1,-1};//遍历了平均值附近的9个点



LLABS(LLx){

returnx<0?-x:x;

}



structpoint{

LLx,y;

point(){};

point(LLx,LLy):x(x),y(y){}

pointoperator-(constpoint&b)const{

returnpoint(x-b.x,y-b.y);

}

voidinput(){

cin>>x>>y;

}

LLdis(){

returnxx+yy;

}

LLlen(){

returnABS(x)+ABS(y);

}

}A[1005],B[105];



LLcal(pointo,inta,intb){

LLret=~0uLL>>1;//常用宏longlong最大值

REP(i,1,b)ret=min(ret,(o-B[i]).len());//最近邻用的曼哈顿距离

REP(i,1,a)ret+=(o-A[i]).dis();

returnret;

2015编程之美资格赛

8/11



}



intmain()

{

intt,n,m,a,b,cas=0;

cin>>t;

while(t--){

cin>>n>>m>>a>>b;

REP(i,1,a)A[i].input();

REP(i,1,b)B[i].input();

LLans=~0uLL>>1,x=0,y=0;

REP(i,1,a)x+=A[i].x,y+=A[i].y;

x/=a,y/=a;

FOR(k,0,9){

LLtx=x+dx[k],ty=y+dy[k];

if(tx<1||tx>n||ty<1||ty>m)continue;

ans=min(ans,cal(point(tx,ty),a,b));

}

cout<<"Case#"<<++cas<<":"<
}

return0;

}

NO1的代码不好理解，再贴个NO3的代码

#include

longlongeuclidDist(longx1,longy1,longx2,longy2){

return(x1-x2)(x1-x2)+(y1-y2)(y1-y2);

}



longmanDist(longx1,longy1,longx2,longy2){

longs=0;

if((x1-x2)>0)s+=(x1-x2);

elses+=(x2-x1);

if((y1-y2)>0)s+=(y1-y2);

elses+=(y2-y1);

returns;

}



intmain()

{

intt;

scanf("%d",&t);

longn,m,a,b;

longi,j,k,x,y;

longxsum,ysum,xavr,yavr,nx,ny;

2015编程之美资格赛

9/11



longdeltax[4]={0,0,1,1};

longdeltay[4]={0,1,0,1};

longlongans[10],fans=0,temp;

longuserx[1010],usery[1010],cpnx[110],cpny[110];

for(j=0;j
scanf("%d%d%d%d",&n,&m,&a,&b);

xsum=0;ysum=0;

for(i=0;i
scanf("%d%d",&x,&y);

userx[i]=x;

xsum+=x;

usery[i]=y;

ysum+=y;

}

xavr=xsum/a;

yavr=ysum/a;

//printf("%d%d",xavr,yavr);

for(i=0;i
scanf("%d%d",&x,&y);

cpnx[i]=x;

cpny[i]=y;

}

for(i=0;i<4;i++){

ans[i]=0;

nx=xavr+deltax[i];

ny=yavr+deltay[i];



for(k=0;k
ans[i]+=euclidDist(nx,ny,userx[k],usery[k]);

}

temp=2147483647;

for(k=0;k
if(temp>manDist(nx,ny,cpnx[k],cpny[k]))//最近邻用的是曼哈顿距离

temp=manDist(nx,ny,cpnx[k],cpny[k]);

}

ans[i]+=temp;

//printf("%d%lld%lld\n",i,temp,ans[i]);

if(i==0)fans=ans[i];

elseif(fans>ans[i])fans=ans[i];

}

printf("Case#%d:%lld\n",j+1,fans);

}

return0;

}

2015编程之美资格赛

10/11



第二题回文字符序列

描述

给定字符串，求它的回文子序列个数。回文子序列反转字符顺序后仍然与原序列相同。例如

字符串aba中，回文子序列为"a","a","aa","b","aba"，共5个。内容相同位置不同的子序列

算不同的子序列。

输入

第一行一个整数T，表示数据组数。之后是T组数据，每组数据为一行字符串。

输出

对于每组数据输出一行，格式为"Case#X:Y"，X代表数据编号（从1开始），Y为答案。答

案对100007取模。

数据范围

1≤T≤30

小数据

字符串长度≤25

大数据

字符串长度≤1000

样例输入

5

aba

abcbaddabcba

12111112351121

ccccccc

fdadfa

样例输出

Case#1:5

Case#2:277

Case#3:1333

Case#4:127

Case#5:17

解析：编程之美第二题一般都是算法，一般考察DP、树、图论等。

区间DP回文字符串[i,j]=[i+1,j]+[i,j+1]-[i+1,j-1]+(s[i]==s[j])[i+1,j-1]



2015编程之美资格赛

11/11



NO1代码

#include

#include

#include

#include

#include

usingnamespacestd;



#definemxn200005

#defineLLlonglong

#defineMPmake_pair

#defineREP(i,a,b)for(inti=a;i<=b;++i)

#defineFOR(i,a,b)for(inti=a;i


#definemod100007



intdp[1005][1005];

chars[1005];



intF(intl,intr){

if(dp[l][r]!=-1)returndp[l][r];

if(l>r)returndp[l][r]=0;

if(l==r)returndp[l][r]=1;

int&ret=dp[l][r];

ret=(F(l+1,r)+F(l,r-1))%mod;

if(s[l]==s[r])++ret;

elseret-=F(l+1,r-1);

ret=(ret+mod)%mod;

returnret;

}



intmain()

{

intcas=0,t;

scanf("%d",&t);

while(t--){

memset(dp,-1,sizeof(dp));

scanf("%s",s+1);

intans=F(1,strlen(s+1));

printf("Case#%d:%d\n",++cas,ans);

}

return0;

}
献花(0)
+1
(本文系babylls首藏)