The Sun Also Rises

Algorithm, Mathematica, 计算机科学, C++, photography, GNU/Linux的讨论空间

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  73 随笔 :: 6 文章 :: 169 评论 :: 0 Trackbacks
2894        Arrange the Problem Set     
 
2895       Cache       Recommended
首先我们用1000大的cache,这样次数最少。
然后我们试着用更小的cache来达到同样的效果。
注意到对两个地址i和j,如果他们的request区间有overlap,那么所满足i % n == j % n的n就不能用作cache大小。
然后我们就把所有不合法的cache size标记,寻找最小的~
注意n == 0的时候输出0,-_-bbbbbbbb
CODE


2896       Common Factor       Recommended
在一个素数域上考虑这个问题,那么他们的Common Factor可以通过GCD求出来。
然后测试一些大素数,如果都通过了就可以认为他们存在Common Factor了。

2897       Desmond's Ambition    Recommended
首先求出所有的桥,如果将那些block视为一个点那么图就成为一棵树。
接下来分为4部分求:(建议自己想想,这个不太容易描述)
1. 每块内部的距离,暴力。
2. 每个桥被使用的次数,其实就是桥左边的顶点数*桥右边的顶点数,在DFS的时候顺便计算即可,参考Bridges
3. 每块内部的点对的最短路被经过的次数,对(u, v)点对来说,就是f(u)*f(v)*dist(u,v)
f(u)定义为,列举出所有一个顶点在u上的桥,在桥的令一端的顶点个数和。
4. 每块内部点通过某个点和外界联系的距离和。f(u) * sum_dist(u),sum_dist(u)是u到同一块内的其他所有点的最短距离和。
CODE

    
2898       Greedy Grave Robber  
24个宝藏,搜12个,把他们的机关触发情况存入hash or map,然后搜右边12个,查表。
很经典的想法了。
   
2899       Hangzhou Tour     
状态f[st][i][j], st表示已访问的顶点,i表示目前位置,j表示自行车位置,dp。
注意f[st][i][j]只可能转移到>=st的状态。有序性存在。
对相同的st的那些状态使用dijstra or SPFA.

2900       Icecream      
dp, f[i][j][k] = 使用前i个icecream, 组成长度为j, 最后一个元素值为k的方案数。
复杂度2000 * 2000 * 100...10s够了。

2901       MV Maker    Recommended
f[p][a][b] = 长度为2^p + 1, 第一个是a, 最后一个是b的最大value.
然后拼接~,复杂度O(n^3*logL)
CODE

     
2902       Ten drops     
模拟,注意这句
Of cause, a left click in grid without blob should be ignored because it's meaningless.


posted on 2008-01-27 12:22 FreePeter 阅读(1636) 评论(18)  编辑 收藏 引用 所属分类: ACM/ICPC

评论

# re: ZOJ Monthly, January 2008解题报告 2008-03-16 20:30 访客
那个啥,2900开2000*2000*100的数组貌似超内存了  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告[未登录] 2008-03-16 20:38 FreePeter
@访客
滚存咯。  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 09:44 yujulong
2000*2000*100怎么过不了。。  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 10:06 FreePeter
@yujulong
?是过不了还是过的了?  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 10:58 yujulong
@FreePeter
TLe...显然过不了。。
还不用滚动。。  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 11:03 FreePeter
@yujulong
这。。。一定是常数写大了。。。你看我就是这么过的。。。@_@  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 11:05 yujulong
以下我的代码。。
感觉常数应该不大。。
#include<iostream>
using namespace std;
int const Inf=1e9;
int dp[2001][101];
int a[ 1001 ];
int main()
{
int n,k,p,m,ans;
int tp1,tp2;
int z;
while( scanf("%d%d%d%d",&n,&k,&p,&m) != EOF )
{
z=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if( a[i] > z )z =a[i];
}
if( p < 0 ){printf("%d\n",n);continue;}
memset(dp,0,sizeof(dp) );
dp[1][ a[1] ]=1;
for(int i=2;i<=n;i++)
{
for(int j=i-1;j>=1;j--)
{
tp1 = a[i]-p;
if( tp1 < 0 )tp1=0;
tp2 = a[i]+p;
if( tp2 > z )tp2=z;
for(;tp1<=tp2;tp1++)
{
dp[j+1][a[i]] += dp[ j ][tp1];
if( dp[j+1][a[i]] > Inf )dp[j+1][a[i]]%=m;
}
}
dp[1][a[i]]++;
}
ans=0;
if( k == 0 )k++;
for(int i=k;i<=n;i++)
for(int j=0;j<=z;j++)
{
ans += dp[i][j];
if( ans > Inf )ans%=m;
}
printf("%d\n",ans%m);


}
}  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 11:17 yujulong
怎么说。。
常数应该小于1吧。。  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 11:21 yujulong
发现错误了。。  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 11:25 yujulong
楼主给点反映。。
TLE。。
  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 11:52 FreePeter
@yujulong
这。。。您不要这么激动么。。。话说我都retired好久了。。。@_@,这些功力早就退化了。。。-______-b
  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 11:57 yujulong
不好意思是有点激动。。
主要已经优化很多了。。
你可不可以把你以前AC的在交一遍试试,如果AC我在想想。。
不能的话我联系ZJU的人。。  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 12:03 FreePeter
@yujulong
你给我发个邮件吧 wenlei [dot] xie [at] gmail [dot] com
我自己地方已经没有code了,我去问问我队友还有没有。。。  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 12:10 yujulong
好了。。
你是不是传说中的peter大牛?
  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 12:14 FreePeter
@yujulong
呃。。。是有人这么叫我。。。不过为什么是传说中的。。。我汗。。。@_@  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 13:58 yujulong
怎么样?  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-02 21:51 yujulong
我的代码你觉得貌似能过吗?  回复  更多评论
  

# re: ZOJ Monthly, January 2008解题报告 2009-04-03 10:56 yujulong
过了。。。  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Creative Commons License
This site is licensed under a Creative Commons Attribution-Share Alike 2.5 China Mainland License. 本站采用创作共用版权协议, 要求署名、相同方式共享. 转载本站内容必须也遵循“署名-相同方式共享”的创作共用协议. This site is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.