网上找的一些算法数论江苏2002task

1、JSOI2002江苏省代表队组队选拔赛本次竞赛共分两试，本试卷为第二试第二试试题竞赛时间：2002 年 5 月 4 日 8:1511:45试题说明分数分布第一试共三道题，满分为 160 分。文件命名选手提交的可执行程序应以”.exe”为后缀，名字附于每题标题后，并最终拷贝到指定硬盘的相应目录下。源文件的名字应与编译后的可执行程序同名。选手程序应从 .IN 中读入输入数据，不需要进行判错处理。执行结果存放到 .OUT 中。输入输出文件均不需指定目录。程序运行要求评测时采用黑盒测试，对每个测试点有一定的时间限制和分数。选手程序必须在此时限内运行结束并输出正确的结果才能得到这个点的分数。程序运行时仅

2、对指定的文件读写，不应在屏幕上显示任何信息或者等待键盘输入。试题名称分值可执行文件输入文件输出文件限时圆锥 体积计算46JSOI06.EXEJSOI06.INJSOI06.OUT5s凸多边形分割54JSOI07.EXEJSOI07.INJSOI07.OUT5s基本粒子60JSOI08.EXEJSOI08.INJSOI08.OUT5s输出结果应按题面要求，不应有多余的字符。题六圆锥体积计算JSOI06.IN.OUT.PAS/.CPP/.EXE问题描述设有一个高为 H，底半径为 R 的正圆锥，其体积的计算方法如下： 将此圆锥按高分成 n 个等份，如下图中的（b）。对分成的每个部分都可以近似地看成一

3、个圆柱体，如图（c）中的ABCD。HACBDRH图(a)图（b）图（c）圆柱体的体积计算公式为底面积乘高。对图（c）阴影部分而言，此时有 2 种计算方法：（1）用 AC 为底计算，计算出来的体积要比实际体积小，称之为小体积；（2）用 BD 为底计算，计算出来的体积要比实际体积大，称之为大体积。然后，将每种分割方案中的所有小体积相加，作为圆锥的小近似值，记为 V1；再将每种分割方案中的所有大体积相加，作为圆锥的大近似值，记为 V2。可以看出，当 n 增加时，其差 V2 - V1 就必然减少。现规定，当 V2-V10.0001 时,就将(V1+V2)/2 作为圆锥的体积。问题：给出 H 与 R，假

4、设使用的是一台理想计算机，无舍入误差，求得一个最小的 n，使V2-V10.0001。 （取 3） 输 入 输入文件名：JSOI0.IN其中：第一行有一个整数，表示有组输入数据；每组均为一行，有二个实数，表示该组圆锥的高与底半径（用一个空格分开）。输出输出文件名：JSOI06.OUT .共有行，每行输出一个整数，表示求得的最小的n。题七凸多边形分割jsoi07/. in /. Out /.pas/.cpp/.exe 问题描述 设有一个凸多边形，其顶点个数为 n（3 n 2）。知道可以用 n-3 条不相交的对角线将凸多边形分为 n-2 个三角形。如下图是 n=5 的五种分法：要求给出一种分法，使对

5、角线长度之和为最小。输入输入文件名：JSOI07.IN . 其中：第一行有一个整数，表示有组输入数据；每组的第一行有一个整数 n，表示该组测试数据的凸多边形数；接下来的n 行，每行均有二个整数，表示顶点坐标（用一个空格分开）。输出输出文件名：JSOI07.OUT .共有行，每行输出一个实数，为最小对角线长度之和，结果保留二位小数。样例输入 文 件：1441012234 4输 出 文 件：200题八基本粒子的超作用jsoi08/. in /. Out /.pas/.cpp/.exe 问题描述 T 博士在一种叫做 Ft 的基本粒子。他发现把 n 个 Ft 粒子在一起的时候，会发生一种可以观测到的特

6、殊效应，被称之为 Ft 效应。奇怪的是，每次选取 n 个粒子进行试验得到 Ft 效应的结果都不尽相同。有人认为，这说明 Ft 粒子并不是基本粒子，而是在精细结构上分化为几种不同的粒子。然而，T 博士却不同意这种观点。他猜想，在两个 Ft 粒子之间存在着一种超作用。但并不是每两个粒子之间都有这种作用，有的粒子根本不和其他粒子发生作用，而有的则和多个粒子分别发生作用。如果用点来表示粒子，用边来表示超作用，那么 n 个粒子之间的超作用关系就是一个无自环无重边的无向图。T 博士认为正是图的结构决定了 Ft 效应的结果。T 博士打算这样验证他的想法。他先把试验结果分类，发现 n 个粒子产生 Ft 效应的

7、结果最多只有 X 种。如果表示 n 个粒子超作用关系的无向图的数量也恰好是 X，T 博士的猜想将得到很好的支持。你的任务就是统计表示 n 个 Ft 粒子超作用关系的无向图的数量。请注意：T 博士认为 Ft 粒子之间是没有差别的。所以两个结构相同的无向图（同构）是同一个无向图。 输 入 输入文件名：JSOI08.IN。 第一行包含一个正整数 N，表示有 N 组数据。接下来的 N 行，每行一个整数（20）。 输 出 输出文件名：JSOI08.OUT。共 N 行。每行包含一个正整数，即粒子的所有可能的超作用关系的数量。【输入输出样例】：输入文件输出文件134Jsoi8.outJsoi7.out16.

8、7235.8816.2556.8823.04Jsoi6.out314177854001879649659336011642177152Jsoi6. in51 210 107 421 20108 44Jsoi5.out71391522Jsoi4.out 71820181Jsoi2.out 202102. 5302102. 53331-12707011. 510010104. 5Jsoi3.out 341804551700JSOI1 . OUT12Caban321imix03pk91imix15 9cimi2801JSOI1.IN 51 pop 230 pop 014 no 710 mac 10

9、10 zac 1995JSOI2002表江苏省代表队组队选拔赛测试第一试选手签名辅导教师签名题输入文件名输 出分 值得 分玛雅日历Jsoi01.in44444点的划分Jsoi02.in44444运输问题Jsoi03.in66666最多珠子链Jsoi04.in66666单词连接Jsoi05.in88888评委签名分得JSOI2002 江苏省组队选拔赛参考第一试题输入文件名输 出分值得分玛雅日历Jsoi01.in12Caban3241imix043ok941imix1549cimi28014点的划分Jsoi02.in220102.5( 205)(0 1 3.5)4320102.543331-124

10、770011.5(410100104.54运输问题Jsoi03.in346180645561700606最多珠子链Jsoi04.in76单词连Jsoi05.in6813898188接218JSOI2002表江苏省代表队组队选拔赛测试第二试选手签名辅导教师签名评委签名得分题输入文件名输 出分 值得 分圆锥体积计算Jsoi06.in8881012凸多边形分割Jsoi07.in1010101212基本粒子Jsoi08.in612121416JSOI2002 江苏省组队选拔赛参考第二试题输入文件名输 出分 值得 分圆锥体积计算Jsoi06.in12566583141600183518593826389

11、440110656870860912凸多边形分割Jsoi07.in167210358810162510568812230412基本粒子Jsoi08.in2611123412123461464549012279579984185616463849074274944016完美 Hamilton 道路【 问题描述 】：一个图 G 上的 Hamilton 道路指的是经过图的每个顶点一次且仅一次的道路。对一个无向完全图来说，Hamilton 道路显然是存在的。然而，另一个不那么明显的结论是：在任意一个有向完全图上总是存在着 Hamilton 道路。之为完美 Hamilton 道路。请你找出一个给定的有向完全图上的完美 Hamilton 道路（任意一条即可）。【输入】：输入文件的一行为一个正整数，表示有向图的顶点数V。2V10000接下来的 V-1 行为有向图的边的信息。第 i 行（2iV）一共有 i-1 个整数（取值为