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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

最后一天的题  

2010-07-25 21:08:28|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
NOI 难度练习二
       @北京人大附中,2010 年 7 月 25 日
第一题 冒泡排序
【题目描述】
冒泡是大家最喜欢的排序方法。我们从数组最前面开始,比较每一对相邻的节点,如果需要
则交换。反复进行恰好 T 次这样的过程之后,数组从小到大就有序了。
下面是一个例子:
第一回合:
( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ),
( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ),
( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ),
( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ),
第二回合:
( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ),
( 1 4 2 5 8 ) -> ( 1 2 4 5 8 ),
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 ),
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 ),
这样,排序一共进行了两个回合。
现在有一个已经使用冒泡排序使其严格递增的数组,                已知数组长度 n 和排序进行的回合数 k,
问原数组的排列方式有多少种可能。                考虑到结果会很大,输出答案模质数 9875321 的值即可 。
【输入格式】
每个输入中包含多个问题。第一行是一个整数,表示问题个数。
接下来的若干行每行上两个整数,n 和 k。数据保证 0<=k<n。
【输出格式】
每一行一个整数表示答案模 9875321 的值。
【样例输入】
3
3 0
3 1
3 2
【样例输出】
1
3
2
【数据规模】
对于 50%的数据,问题个数不超过 100,000。每个问题中,有 k<n<=1,000,000。
对于另外 50%的数据,问题个数不超过 100,但每个问题中,k<n<=1,000,000,000。
【题目来源】
PKU Campus 2010,有添改。
第二题 网络调整
【题目描述】
最近清华大学的网络环境不太好,同学们看世界杯都是一顿一顿的,有很多同学向网络中心
反映情况。网络中心考虑到即将迎接百年校庆,决定痛下血本,改善网络。网络是由很多路
由器组成的,         两两之间用有向的电缆连接起来。      任何时刻,   网络中如果存在有向环就会瘫痪 。
改善网络的第一步是调整一些线路的方向。由于同学们要求在改善过程中不能断网,所以调
整方向就成了一件困难的事情。学校的工作人员只有这么几个,只够同时调整一条线路,不
能多线程开工。这样一来,先反向哪一条,后反向哪一条才能不断网呢?
虽然在调整过程中可以任意顺序对各条边反复调整方向,但是同学们已经等不及了,所以必
须要求总的调整次数尽可能小。
【输入格式】
第一行两个整数 n,m 表示路由数和电缆数。
接下来的 m 行,每行包括三个整数,表示电缆原本是从哪里连到哪里,以及在你最终达到
的调整结果中是否需要反向。
输入数据保证解的存在性。
【输出格式】
第一行输出你需要调整的次数。
第二行是若干整数依次表示调整的边在输入数据中的序号。
【样例输入】
4 5
1 2 0
2 3 1
2 4 1
1 4 1
4 3 0
【样例输出】
3
3 2 4
【数据规模】
对于 100%的数据,2 <= n <= 1,000,1 <= m <= 10,000
【评分细则】
在每个测试点上,如果你给出了一个可行方案,得到的分数是[10M/Y],其中 M 是需要改变
的边数,Y 是你改变的边数。
【题目来源】
ZJU, Electricity
第三题 矩形统计
【题目描述】
平面上给定 n 个整点,求以其中四个点为顶点可以构成的边与坐标轴平行的矩形的个数。
【输入格式】
第一行为一个整数 n;从第二行开始每行包含两个整数表示一个整点。点不会重合。
【输出格式】
一个整数表示答案。
【样例输入】
6
-1 0
-1 1
0 0
0 1
1 0
1 1
【样例输出】
3
【数据规模】
对于 20%的数据 n<=1000;
对于 50%的数据 n<=10000;
对于 100%的数据 n<=100000;
【题目来源】
SPOJ, RECTANGL


第1题:公式:k!*(k+1)^(n-k)-(k-1)!*k^(n-k+1)
第2题:按原图的拓扑逆序作为第一关键字,目标图的拓扑序作为第2关键字,排序输出。
第3题:经典的cache法优化,“长”的行用枚举第一行+hash+统计,“高”的行用枚举同行的点对+排序
  评论这张
 
阅读(452)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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