HDOJ

test(谄笑) 2013-09-21
上一篇     下一篇 共81篇  

2012 Multi-University Training Contest 1 Solution Report 2012年07月19日 17:17:17

1001  Clairewd's message

这道题问的就是将1个串如何变为stringA+stringB的形式,使得stringA是stringB经过映射得到相同的串。映射那步其实没有什么价值,假设str为原串s经过映射后得到的串,我们可以以str为模式串,以s为原串做一次扩展KMP,得到extend数组,extend[i]表示原串以第i开始与模式串的前缀的最长匹配。经过O(n)的枚举,我们可以得到,若extend[i]+i=len且i>=extend[i]时,表示stringB即为该点之前的串,stringA即为该点之前的str串,最后输出即可。

1002  Divide Chocolate

题意:

给定一个2*n的矩形,求把这个矩形分割为k部分的方法,且对称的切割方法视为不同,输出时模上100000007。

(1<=n<=1000,1<=k<=2*n)

 

解法:

看到这个题目,很容易想到DP。

状态表示 f[i][0][j]:前i行已经出现了j部分且第i行的两个格子属于同一部分的方法数

         f[i][1][j]:前i行已经出现了j部分且第i行的两个格子属于不同部分的方法数

初始条件 f[1][0][1]=f[1][1][2]=1

状态转移 f[i+1][0][j]=(f[i+1][0][j]+f[i][0][j]+f[i][1][j]*2)%mod;

         f[i+1][0][j+1]=(f[i+1][0][j+1]+f[i][0][j]+f[i][1][j])%mod;

         f[i+1][1][j]=(f[i+1][1][j]+f[i][1][j])%mod;

         f[i+1][1][j+1]=(f[i+1][1][j+1]+f[i][0][j]*2+f[i][1][j]*2)%mod;

         f[i+1][1][j+2]=(f[i+1][1][j+2]+f[i][0][j]+f[i][1][j])%mod;

 

共12种不同的状态转移(见下图)

 

1003  Holedox Eating

每次吃蛋糕的时候,都要找离当前位置最近的蛋糕。可以利用线段树求区间[0, now]
已经存在的蛋糕的最大位置,,[now,L]已经存在的蛋糕的最小位置。按照输入顺序模拟就可以了。

1004  Hourai Jeweled


一次dfs就能搞定的问题,其实没什么复杂的算法,主要难点在于统计时的一些小技巧,个人难度评价是偏难的中档题。
从任意一点开始深搜,每颗子树搜索完毕之后向上返回pair<可以延伸到该点且最后一条边与由父节点到该点的边颜色不同的gorgeous边的条数 , 所有这种边分数的总和>
每次深搜完一个子节点之后,增加的过这一点的gorgeous边的总分数为:
    之前深搜的所有子节点向上返回的边数之和 * 当前子节点返回的分数 +
    之前深搜的所有子节点向上返回的分数之和 * 当前子节点返回的边数 +
    之前深搜的所有子节点向上返回的边数之和 * 当前子节点返回的边数 * 当前点的权

用O(n)的时间把所有的累计起来就好了什么的

才没有呢 = =
如果有当前节点分别到两个子节点的边的颜色相同的话也是不行的,
由于数据中添加了度数很大的点,理论上O(儿子数^2)的两两统计也是要被卡掉的 (希望确实的做到了
正确的做法是对所有的儿子按边的颜色排个序,然后在按这个序深搜和统计

1005  Let's Hit Our Head

这个问题等价于把N因数分解,不能有1
然后将序列交替组合的方案数算出来就可以了

比如6=2*3
我们有[6],[2,3],[3,2]
交替组合有
A6B6 B6A6
A2B6A3 A3B6A2 B2A6B3 B3A6B2
A2B2A3B3 A2B3A3B2 A3B3A2B2 A3B2A2B3
B2A2B3A3 B2A3B3A2 B3A3B2A2 B3A2B2A3
共14种

再比如8=2*2*2=2*4
我们有[8],[2,4],[4,2],[2,2,2]
交替组合有
A8B8 B8A8
A2B8A4 A4B8A2 B2A8B4 B4A8B2
A2B2A4B4 A2B4A4B2 A4B2A2B4 A4B4A2B2
B2A2B4A4 B2A4B4A2 B4A2B2A4 B4A4B2A2
A2B2A2B4A2 A2B4A2B2A2 B2A2B2A4B2 B2A4B2A2B2
A2B2A2B2A2B2 B2A2B2A2B2A2
共20种

1006  Lightning

题目模型:给定平面上N个点。如果两点距离小于等于R,且两点间线段上没有其他点的时候,两点可以建立一条边。得到这个图后,求此图的生成树个数 mod 10007,如果图不连通则输出-1.
第一部分:构图。枚举两点是否符合距离限制,如果符合则对比此两点方向向量上是否有距离更小的其他点,然后根据情况建边删边。(O(N*N*log(N)))
第二部分:如果图连通,则根据生成树定理,从建好的图中构建M矩阵,高斯消元法求出行列式的值(由于是整数高消,需要提出系数,最后求其逆元)(O(N^3))

1007  Mahjong

这道题目需要用2-sat解决,但要成功转化出模型需要一些巧妙的构造和基础图论知识的证明,最后还要注意一些细节。

首先,题目中的前三段可以直接无视(偶已经很体贴的用图隔开了不是么)。。

要解决这道题目,我们首先可以构造证明,一个状态经过最多三段操作(每段操作指若干次某种操作)之后可以到达任意状态。
我们不妨假设操作顺序为A...AB...BA...A(反之类似)。
原图中的一个格子坐标为(x0,y0),要转移到目标的坐标为(x1,y1),则显然最后一段操作之前坐标为(x1,y2).
依次类推,它的转移路径应该为:(x0,y0)--->(x0,y2)--->(x1,y2)--->(x1,y1),则唯一影响路径的是y2。
那么这种构造方式能否成功就取决于从(x0,y2)是否能转换到(x1,y2)。
换言之,就是我们第一段操作需要使每一列各点所要到达的x1互不相等。
再换言之,如果我们以每个点的原始位置集x0到其目标位置集x1构建二分图,则如果能够找到n个不相交的完美匹配就构造成功了。
显然每行有n个点,则x集每个点的度都是n;同理y集每个点的度也是n。
对于x集的任意子集S,其在y集中的相邻集记作

...
注册或登录后查看完整内容

阅读(8232)| 评论(29)

  1. 倪裕芳JoinHands 2012年07月19日 17:21:42 举报
    1010我一次费用流过的,是数据太弱了吗?
  2. 柯阳 2012年07月19日 17:36:36 举报
    http://jxsmx.cn/nRtD9P ' target='_blank' title='http://blog.renren.com/blog/240725952/861867892'>http://jxsmx.cn/nRtD9P
  3. 张煜 2012年07月19日 18:05:57 举报
    回复倪裕芳.php:呃,这题我出的,出的时候没想到好的费用流做法,因为桥只用修复一次,修复后通过的人数未知…求您AC的费用流建图方法……
  4. 张勇威 2012年07月19日 19:16:32 举报
    回复张煜:查下最后一组数据吧,u,v有大于n的了
  5. 柯阳 2012年07月19日 20:16:40 举报
    1010已确认是数据有问题,已经向资料中的那个邮箱反馈了。给大家造成的困惑和不便,深表抱歉!
  6. 王世轩 2012年07月19日 20:18:03 举报
    求问1005AB是啥意思啊。。。看着都昏啦
  7. 林大白 2012年07月19日 20:28:19 举报
    回复柯阳:TAT...那AC的是怎么过的= =
  8. 柯阳 2012年07月19日 20:29:31 举报
    回复林鹏鹏:因为建图方法和标程一样。当初验题的程序也是这么通过的。造成的困惑深表抱歉。
  9. 林大白 2012年07月19日 20:34:22 举报
    回复柯阳:1004 用并查集测试。发现有环....
  10. 王世轩 2012年07月19日 20:35:10 举报
    回复柯阳:1005题解中啊AB是什么意思啊?求解释...
  11. 李翔 2012年07月19日 20:35:57 举报
    什么时候第十题的数据能改啊!!
  12. 李静 2012年07月19日 22:32:58 举报
    请问201203《ACM程序设计》作业—— 刘春英老师这几份文档在哪儿下载?或者谁有给我发一份吧,不胜感激。1259972162@qq.com
  13. 秦星耀 2012年07月20日 10:47:34 举报
    1003数据好弱……错误的程序都过了。。
  14. 伍建威 2012年07月20日 11:29:41 举报
    1003确实是挺水的 我生成的数据 两种思想两个代码运行出来答案对不到 但是照样能AC
  15. 陈成焱 2012年07月20日 11:34:12 举报
    回复李静:你来错地方了吧
  16. 王耀 2012年07月20日 12:56:16 举报
    1005 Let's Hit Our Head! 数据有问题,有负数
  17. 谷飞洋 2012年07月20日 16:52:49 举报
    请问一下是不是可以给学校发标程?
  18. 范坚劲 2012年07月20日 18:19:50 举报
    1001O(n^2)的和O(n)的代码跑出来一样的时间,不要这样好吗?
  19. 刘施剑 2012年07月20日 18:40:03 举报
    1005数据标准答案爆long long有负的,出题人怎么查的数据???
  20. 陈思捷 2012年07月20日 18:52:11 举报
    1007我写了一天,始终过不去数据,查看数据后,发现标程有问题,跑出的至少第8组数据的答案是有问题的~哭哭哭弄了俺一天啊...
  21. 李森 2012年07月20日 22:00:13 举报
    回复倪裕芳.php:请问1010费用流做法第一类边如何构图?
  22. 陈松奎 2012年07月20日 22:47:25 举报
    请问有标程吗?谁有的话发给我一份 谢谢 email 463497880@qq.com
  23. 王琳 2012年07月21日 10:49:52 举报
    能不能不考英语啊,每道题都琢磨半天的题意 尤其是1005
  24. 易毅 2012年07月21日 11:08:30 举报
    其实我一直在想,咲的岭上开花已经够bug了啊……怎么还要去练开挂控场啊……
  25. 肖英男 2012年07月21日 12:38:44 举报
    回复易毅:谄笑
  26. 吴卓锋 2012年07月24日 02:27:27 举报
    请问 1008,“S到点i有一条容量为C[i]的边,点i到汇点有一条容量为sum{j}B[i][j]的边” 这里应该是 “S到点i有一条容量为*sum{j}B[i][j]*的边,点i到汇点有一条容量为*C[i]*的边” 吧?
  27. 张云帆 2012年07月27日 15:27:51 举报
    回复倪裕芳.php:求大神费用流构图方法
  28. 閻凱 2012年08月13日 17:21:22 举报
    目测1008题解是错的。。。S到i有一条C[i]的边,i到汇点有一条容量为sum{i}B[i][j]的边才对,或者按题解中的连源和汇,那么就在加i到j时加成j->i, c = B[i][j]才可以。。。
  29. 陈竞 2012年09月02日 15:17:37 举报
    回复閻凱:经验证,的确有错。。。应该是sum{i}B[i][j]..

玩转人人 公共主页 公众平台 客服帮助 隐私

商务合作 品牌营销 中小企业
自助广告
开放平台

公司信息 关于我们 人人公益 招聘

友情链接 经纬网 人人游戏 人人分期

人人移动客户端下载 iPhone/Android iPad客户端 其他人人产品