日历
网志分类
· 所有网志
· ACM ICPC
· 随笔胡言
· 有关数学
· 算法学习
· 诗&歌&文
· 伪愤青
· 菜鸟做工程
· 更新通告
· 未分类
站内搜索
友情链接
· 管理我的Blog
· ==============
· SJTU dwyak - 文渊阁
· NJU phoenix - No motto
· NJU Phoenix - Illumination
· PKU frkstyc
· HIT wywcgs - wc的小屋
· NIT 小蓓 - 虎皮蛋糕
· HDU - 流浪的枫之羽
· ZJUT - zeism
· Fluke's Blog
· UESTC - Tom Riddle
· UESTC - zhucheng
· OIer winsty
· ZZU Cheapwine
· 小用的空间
· owen的文档集中营
· Fish过生活
· ECUST - CodeStar
· Wiskey's blog
· richardxx - Try Again
· Vivian's House
· Sicheng's Blog
· ==============
· BunnyQ EndTech
· wtommy的无悔青春
· zxj 桂花飘香的时候
· Washington 天空的城堡
· echo 寻找心灵的宁静
· pizza 天天快乐
· 牛牛小屋
· fanskyer's PureWater
· sdragons' space
· NightElf's space
· NeverStop's space
· cnhawk
· ==============
· 看雪论坛
· 老罗 天空之城的点滴回忆
· Monkeycz像人一样死去
· Cyclotron's Blog
· tsing's blog
· Hedgehog's Parchment
· The Life Of Sam & Yangyy
· 莫言无意 没有过往的将来
· Eric 涅磐·人生·路
· dazh 左手年华
· Bakey 灵魂深处
· keo 还好没有忘记
· 开心生活一角
· 听风竹轩
· ξNew York,New Yorkζ
· flykite's blog
· fickle的角落世界
· Taiyuan123's blog
· RoBa's Tech Blog
Online Judge
+ TOJ
+ ZOJ
+ POJ
+ UVA
+ URAL
+ SGU

订阅 RSS

0122732

歪酷博客

失去色彩的花丛

曾经沧海难为水, 除却巫山不是云. 取次花丛懒回顾, 不缘修道只缘君.


« 上一篇: Ural 1114 Boxes 下一篇: 一些牢骚 »
robby @ 2006-09-20 12:01

http://acm.timus.ru/problem.aspx?space=1&num=1124

一道简单题,但是很有意思,简单写一下。

题目大意是,有M种卡片,每种有N个,初始时放在M个盒子里,每个盒子里有N张,但是可能有某些卡片放错了位置,因此需要进行一些移动,最后使得每张卡片都放到它应该在的盒子(第1种卡片都放入盒子1,第2种卡片都放入盒子2……)。一次移动是指把一张卡片从当前手边的盒子里拿出放到另一个盒子,或者不拿卡片,只是把手从当前的盒子处移到另一个盒子处。

容易联想到欧拉路,如果盒子i里面有一张卡片j,就把i,j之间连一条边,表示至少要有一次从i到j的移动。容易发现这样建图后每个点的出度必然等于入度(因为初始时盒子里就有N张卡片,后面拿出多少张也就要拿入多少张),也就是说对于每个连通分量,欧拉回路必定存在,最少的移动次数实际上就是边的总数。在不同的连通分量之间必然要有一次空着手的移动。因此最后的答案就是 边数+连通分量数-1(第一次开始时手可以在任何位置)。




最新评论

2006-09-20 12:10 网址: http://pigsty.ycool.com/

HOHO~有意思也~


评论 / 个人网页 / 扔小纸条
* 昵称

已经注册过? 请登录

新用户请先注册 以便能显示头像及追踪评论回复

Email
网址
* 评论
表情
 


 

分类小组论坛
杂谈 , 娱乐、八卦 , 文学、艺术 , 体育 , 旅游、同城 , 象牙塔 , 情感 , 时尚、生活 , 星座 , 科技

请注意遵守中华人民共和国法律法规, 如威胁到本站生存, 将依法向有关部门报告, 同时本站的相关记录可能成为对您不利的证据.

相关法律法规
全国人大常委会关于维护互联网安全的决定
中华人民共和国计算机信息系统安全保护条例
中华人民共和国计算机信息网络国际联网管理暂行规定
计算机信息网络国际联网安全保护管理办法
计算机信息系统国际联网保密管理规定