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条新的道路,每条新道路可以连接...

【CTSC2007】风铃

【题目描述】

你准备给弟弟Ike买一件礼物,但是,Ike挑选礼物的方式很特别:他只喜欢那些能按照他的特有方式排成有序的东西。

你准备给Ike买一个风铃。风铃是一种多层的装饰品,一般挂在天花板上。每个风铃都包含一些由竖直的线连起来的水平杆。每根杆的两端都有线连接,下面或者挂着另一根水平杆,或者挂着一个玩具。下面是一个风铃的例子:


为使你的弟弟满意,你需要选一个满足下面两个条件的风铃:

(1)所有的玩具都在同一层(也就是说,每个玩具到天花板之间的杆的个数是一样的)或至多相差一层。

(2)对于两个相差一层的玩具,左边的玩具比右边的玩具要更靠下一点。

风铃可以按照下面的规则重新排列:任...

【JSOI2010】连通数

【题目描述】

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

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

【输入】

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

【输出】

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

【输入样例】

3

010

001

100

【输出样例】

9

【数据范围】

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

【题解】

又见BZOJ省选水题……

【代码】

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

【ZJOI2012】旅游

【题目描述】

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

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

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


【输入】

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

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

【NOI2011】道路修建

【题目描述】

在 W 星球上有 n 个国家。为了各自国家的经济发展,他们决定在各个国家 之间建设双向道路使得国家之间连通。但是每个国家的国王都很吝啬,他们只愿 意修建恰好 n – 1 条双向道路。 每条道路的修建都要付出一定的费用,这个费用等于道路长度乘以道路两端 的国家个数之差的绝对值。例如,在下图中,虚线所示道路两端分别有 2 个、4 个国家,如果该道路长度为 1,则费用为 1×|2 – 4|=2。图中圆圈里的数字表示国家的编号。

由于国家的数量十分庞大,道路的建造方案有很多种,同时每种方案的修建 费用难以用人工计...

© OI技术宅 | Powered by LOFTER