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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

2007-7-18做的题  

2009-07-18 14:18:00|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

NOI训练试题
生成树计数 
count.c/cpp/pas/in/out
给一张N个点,M条边的无向带权图,求图中有多少个最小生成树。
输入文件
  输入文件的第一行包含两个整数N和M,含义如上文所述。接下来的M行每
行包含三个整数p1,p2和v,表示一条连接 p1,p2的,权为v的边。
输入文件
  输出文件中仅包含一个整数,表示图中最小生成树的个数对1000003取模
的结果。
样例数据
输入数据  输出数据
3 5
1 2 6
1 2 6
2 3 6
3 1 6
3 3 8
5
数据规模和约定
  , ,每个权值出现次数不超过4。 
置换表示 
permu.c/cpp/pas/in/out
  一个置换就是一个集合X到自身的双射,X中的元素通常是1,2,
3,……,n。我们通常将一个置换写成下面的形式:
 
  表示1映射到3,2映射到2,3映射到5……另一种表示置换的方法是将它
写成轮换乘积的形式,例如:
(247)
  表示将2映射到4,4映射到7,7映射到2。若干个轮换的乘积是从右至左
运算的,例如上文中的置换可以写成: (53)(51)(54)
(1354)(1)
(1)(1354)
  可以证明,一个置换可以唯一地表示成如下的形式:
 
  其中 。对于上文中的置换,可以表示成:
 
  你的任务就是,给定一个置换,计算所有的ai。
输入文件
输入文件的第一行包含一个整数n,第二行包含n个整数,表示给定的置
换。
输出文件
  输出文件中包含一行n个整数,表示所有的ai。
样例数据
输入数据 #1  输出数据 #1
5
1 2 3 4 5
3 2 5 1 4
0 1 2 2 2
4
1 2 3 4
3 4 1 2
0 0 0 2
数据规模和约定
40%的数据中,n不超过5000。
100%的数据中,n不超过200000。
质数游戏 
game.c/cpp/pas.in/out 
Alice和Bob最近在玩一个游戏。游戏开始之前,选定一个整数n,计数器c清
零。第一回合,Alice从1到n中选择一个整数,并将它加到计数器c里面;第二
回合,Bob从1到n中选择一个整数,并将它加到计数器c里面;以此类推……如
果某回合之后,c不是质数,那么最后选择数字的人就输了。
现在假设Alice和Bob都足够聪明,你需要判断Alice是否可以获胜,如果可
以获胜的话,第一回合应该选择哪个数。 输入文件
输入文件中仅包含一个整数n,含义如上文所述。
输出文件
  如果Alice可以获胜,则输出”A”以及第一回合应该选择的数字;否则
输出”B”。
样例数据
输入数据 #1  输出数据 #1
3  A 3
4  B
10  A 7
500  A 157
数据规模和约定
  所有数据中,n不超过1000。
 

 

 

第一题:裸kruskal

默写代码竟然默错了......

 

第二题:用树状数组

比较不容易想...其实是维护一个可以旋转的环

 

第三提:特殊优化的动态规划

dp[i]:要达到i的,必须达到dp[i]

可以维护一个区间内的所有dp值

最终发现,这个区间内的dp可能值会只剩1个!

 

 

  评论这张
 
阅读(473)| 评论(1)
推荐 转载

历史上的今天

评论

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

页脚

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