首页 > ACM题库 > POJ 1846 System [解题报告] Java
2013
11-10

POJ 1846 System [解题报告] Java

System

问题描述 :

The county where the National Olympiad in Informatics is held this year it is a little bit strange. In the county there are N cities, numbered from 1 to N. Each of the N cities of the county is connected to exactly two other cities, through bidirectional roads. Even stranger is the fact that, inside this roads system it is not always possible to get from every town to any other town walking these roads. Anyway, the inhabitants of the county are very proud of their system and they think there is not another like this. You want to prove them the opposite and for this you want to calculate how many different road systems, with the upper feature, exist. Two systems are considered different if there is at least one road between a pair of cities i and j inside the first system, which does not exist inside the second one.

Write a program that calculates how many different road systems exist.

输入:

From the input, you will read the integer value n(3 <= n <= 100), representing the number of cities of the county.

输出:

In the output, you will write an integer value, representing the number of different street systems, with the feature that every city is connected through direct streets to exactly two other cities.

样例输入:

4

样例输出:

3

解题代码:

/* @author:[email protected] */
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
 static String data[] = new String[]{
  "1",
  "3",
  "12",
  "70",
  "465",
  "3507",
  "30016",
  "286884",
  "3026655",
  "34944085",
  "438263364",
  "5933502822",
  "86248951243",
  "1339751921865",
  "22148051088480",
  "388246725873208",
  "7193423109763089",
  "140462355821628771",
  "2883013994348484940",
  "62053912734368432430",
  "1397632884350901759561",
  "32874958880640907159723",
  "806125893050067459184032",
  "20572437191556957007469100",
  "545567728616689177021106575",
  "15013278861111181457743472757",
  "428148189369521610565640556996",
  "12637797989534502512274145422334",
  "385664715990618439302342773319315",
  "12154695103765999167285648831901905",
  "395218591123321086599228738750338624",
  "13245844477112642393726185363073772912",
  "457177496175042566919537551339205247713",
  "16236367427844865888710355396428635151235",
  "592854109422996136701620291050167342379020",
  "22240082261103435407528362778048102363000598",
  "856537292223705486205841165409517220305340929",
  "33844259291806954099323706086639345592611150051",
  "1371117635835938843590820366432451343547586468480",
  "56918183648896931085912424779366309206101424769460",
  "2419703620503916893087839551673981463211498040511231",
  "105285374906828279178539611512869706481317886323020373",
  "4686401097632300780663016060407547613686958946044805572",
  "213283555977752412853992683874496884264492535632122369430",
  "9920013938005178260233451956142676822374820651421955079835",
  "471306654672783895374868962300006369622012173237506323575577",
  "22863303275436531699693013937810738227306931895593337564344736",
  "1131967796887484142918992222453149961081152451970145759826778024",
  "57175740496348367417783825601475005856844587510723233237718983025",
  "2945113476989948316224083698445933989938890301213766400518207672675",
  "154646890102150116417162936006161444325215903814428266104477106638924",
  "8275073345817924220411341720005389107307174743754474718938863410471422",
  "451068418059740523942729116652767143334189988183778534541840179345054713",
  "25038413625087421739729588375871342628203394967272245374966358367336811355",
  "1414894775957455220724290415297603486404643167272627632065281918222987425760",
  "81368907424798293457497149342141215085826027755681085568849846264944990590268",
  .............................................(请下载源码)
};
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new
                InputStreamReader(System.in));
		System.out.println(data[Integer.parseInt(br.readLine())-3]);
		br.close();
	}

}

  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。