注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

Nordic Collegiate Programming Contest NCPC 2007  

2014-08-07 10:58:06|  分类: cf_gym |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://codeforces.com/gym/100240
比赛出了A,C,H,L,G,I,题目都挺简单,这里就简单总结下。

A题:
题意:给出一组字符串,判断是否有字符串是其他字符串的前缀。
题解:数据有点大,字符全是数字,比较裸的字典树,字符串结束的结点上设个标记。

C题:
题意:给出x轴上的几个坐标,问经过所有点的最短距离。
题解:找出最大和最小的坐标,结果为差值乘2.

H题:
题意:给出n件商品,买三件最便宜的那件可以免费,问最多能优惠多少钱。
题解:所有商品价格降序排列,依次选出三个商品,加上价格最小的即可。

L题:
题意:给出n个候选人以及所属的party,然后给出m张选票,问最后哪个party获票数最多。
题解:这题只需简单模拟下即可。

G题:
题意:套娃,只有宽和高都小于的情况下才能被套进,给出n个娃娃的宽和高,问套成娃娃的最小个数。
题解:类似求LIS,dp下即可,具体见代码。

/*
* dp[i]表示前i位以node[i]为结尾的最大递减子序列的高度
* 排序顺序:w大的优先,如果相同h小的优先,不能h大的优先,否则出错(考虑相同宽度下的娃娃),比如:

* 3
* 50 60 40 50 40 40
*/
struct Node{
int w,h;
}node[N];
int n,dp[N];
bool cmp(Node a,Node b)
{
if(a.w > b.w || (a.w == b.w && a.h < b.h)) return true;
return false;
}

int LIS()
{
int j,res=0;
for(int i=0;i<n;i++)
{
for(j=0;j<res;j++)
if(dp[i] < dp[j]) //如果后面的娃娃可以被套进,则更新当前娃娃的最大高度
break;
if(j == res)
res++;
dp[j]=dp[i];
}
return res;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif
int T;
sf(T);
while(T--)
{
sf(n);
fr(n) sf2(node[i].w,node[i].h);
sort(node,node+n,cmp);
fr(n) dp[i]=node[i].h;
pf(LIS());
}
return 0;
}


I题:
题意:给出x轴上n个地点的坐标,最多只能存储c个坐标,其余坐标按给出的公式计算,求最小的平均误差。
题解:dp,具体见代码。

/*
* w[i][j]表示区间[i,j]的误差和
* dp[i][j]表示第i个位置放第j个的误差和
* dp[i][j]=dp[k][j-1]+w[k][i], 0<=k<i
*/
int n,c,f[210];
double dp[210][210];
double w[210][210];

void fun()
{
MEM(w);
for(int i=0;i<n;i++)
{
for(int j=i+2;j<n;j++)
{
for(int k=i+1;k<j;k++)
{
double cnt=f[i]+(f[j]-f[i])*(k-i)*1.0/(j-i);
w[i][j]+=fabs(cnt-f[k]);
}
}
}
for(int i=0;i<n;i++)
for(int j=0;j<c;j++)
dp[i][j]=INF;
dp[0][0]=0;
for(int i=1;i<n;i++)
{
for(int j=1;j<c && j<=i;j++)
{
for(int k=0;k<i;k++)
dp[i][j]=min(dp[i][j],dp[k][j-1]+w[k][i]);
}
}
printf("%.4lf\n",dp[n-1][c-1]/n);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt", "r", stdin);
// freopen("testout.txt", "w", stdout);
#endif
int T;
sf(T);
while(T--)
{
sf2(n,c);
fr(n) sf(f[i]);
fun();
}
return 0;
}


  评论这张
 
阅读(37)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017