OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【APIO2010】巡逻

【题目描述】

在一个地区中有n个村庄,编号为1,2,...,n。有n–1条道路连接着这些村庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其他任一个村庄。每条道路的长度均为1个单位。

为保证该地区的安全,巡警车每天要到所有的道路上巡逻。警察局设在编号为1的村庄里,每天巡警车总是从警察局出发,最终又回到警察局。下图表示一个有8个村庄的地区,其中村庄用圆表示(其中村庄1用黑色的圆表示),道路是连接这些圆的线段。为了遍历所有的道路,巡警车需要走的距离为14个单位,每条道路都需要经过两次。


为了减少总的巡逻距离,该地区准备在这些村庄之间建立K条新的道路,每条新道路可以连接...

【JSOI2010】连通数

【题目描述】

度量一个有向图情况的一个指标是连通数,指图中可达顶点对的个数。

请编写一个程序,输入一个图,求它的连通数。

【输入】

输入数据第一行是图顶点的数量,一个正整数N。 接下来N行,每行N个字符。第i行第j列的1表示顶点i到j有边,0则表示无边。

【输出】

输出一行一个整数,表示该图的连通数。

【输入样例】

3

010

001

100

【输出样例】

9

【数据范围】

对于100%的数据,N不超过2000。

【题解】

又见BZOJ省选水题……

【代码】

http://paste.ubuntu.com/8438400/

【HAOI2008】移动玩具

【题目描述】

在一个4*4的方框内摆放了若干个相同的玩具,某人想将这些玩具重新摆放成为他心中理想的状态,规定移动时只能将玩具向上下左右四个方向移动,并且移动的位置不能有玩具,请你用最少的移动次数将初始的玩具状态移动到某人心中的目标状态。

【输入】

前4行表示玩具的初始状态,每行4个数字1或0,1表示方格中放置了玩具,0表示没有放置玩具。接着是一个空行。接下来4行表示玩具的目标状态,每行4个数字1或0,意义同上。

【输出】

一个整数,所需要的最少移动次数。

【输入样例】

1111

0000

1110

0010


1010

0101

1010

0101

【输出样例】...

【HAOI2012】最长滑坡

【题目描述】

顺治喜欢滑雪,这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待太监们来载你。顺治想知道载一个区域中最长的滑坡。

区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:


顺治可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上,这是最长的一条。

【输入】

输入的第一行表示区域的行数R和列数C。下面是R行,每行有C个整数,代表高度h。

【输出】

输出最长区域的长度。...

【ZJOI2012】旅游

【题目描述】

到了难得的暑假,为了庆祝Eric在数学考试不及格,Kevin决定带Eric出去旅游~~

经过一番抉择,两人决定将T国作为他们的目的地。T国的国土可以用一个凸N边形来表示,N个顶点表示N个入境/出境口。T国包含N-2个城市,每个城市都是顶点均为N边形顶点的三角形(换而言之,城市组成了关于T国的一个三角剖分)。两人的旅游路线可以看做是连接N个顶点中不相邻两点的线段。

为了能够买到最好的纪念品,Eric希望旅游路线上经过的城市尽量多。作为Kevin的好友,你能帮帮Kevin吗?


【输入】

每个输入文件中仅包含一个测试数据。

第一行包含两个由空格隔开的正整数N,N的含义如...

© OI技术宅 | Powered by LOFTER