《科学》杂志称赞一o人大开眼界的叫做HPTN 052的HIV研究?011q最重要的科学突破。这一临床试验表明Q感染了HIV的h如果服用抗逆{录病毒药物（ARVsQ的话，他们病毒传播给其伴侣的可能性要降低96%?/span>
q些发现l结了一个长期存在的争论Q即ARVs是否可以在治疗病Z内病毒的同时也降低病毒的传播率而提供一U双重的裨益。研Ih员同意，现在已经清楚QARVs可治疗及预防HIV?/span>
除了认可HPTN 052?011q的q度H破之外Q《科学》杂志及其出版机构——美国科学促q会QAAASQ还认了在q去q一q中另外9开创性的U学成就Qƈ其~纂成十大科学进展名录而登载于12?3日的《科学》杂志上?/span>
北卡|来U_北卡|来U_学查珀?希尔分校d院的Myron Cohen及其一个国际性团队中的同事，是在2007q开始这HPTN 052的研I的Q他们从9个不同的国家中招募了1763对异性恋夫妇Q这些国家有Q巴ѝ印度、泰国、美国、博茨瓦U뀁肯g、马拉维、南非和z巴布韦。每一对参与该研究的夫妇中有一人感染了HIV?/span>
研究人员立刻l一半的感染了HIV的h提供ARVsQƈ{待另外一半被感染的参与者出现CD4计数低于250时再l他们提供治疗，CD4计数低于250时表明免疫功能受C重的损害。（CD4计数低于250时表明罹患了AIDS。）
接着Q在今年早些时候，即于该研I正式计划结束之?q的时候，一个独立的监督委员会决定所有的研究参与者都应该立刻接受ARVs。该委员会成员已l看到早期给予ARVȝ对HIV传播率所产生的巨大媄响；他们该试验的发现应该早公布。随后，HPTN 052的结果登载于8?1日的《新英格兰医学杂志》上?/span>
为《科学—年度突破》专题撰写该试验报道的《科学》新闻通讯员Jon Cohen_“这一QHPTN 052Q试验ƈ不意味仅仅治疗病人就能终止一U传染病。但是，当这U方法结合自2005q以来开展的大型临床研究中被证明有h值的3U其它的重要生物d的预防措施，许多研究人员怿Qh们有可能用正的成套l干预措施来解决某些特定区域中该疄行中最艰难的部分。?/span>
Z已知用ARVsȝ可降低病毒蝲量，或在某个被感染的Z减少其HIV的实际数量。许多HIV/AIDS的研Ih员因此推断，得到ȝ的h的感染性也应该较小。但是，在开展HPTN 052之前Q持怀疑态度者声U这U理论ƈ未得到证实——且病毒载量可能q不能够反映在生D器官分泌液中的病毒度?/span>
Jon Cohen解释道：“大多数人所最为期待的是降低一个h体内的病毒含量似乎应该降低其感染性。o人感到意外的是其提供保护的程度及随后的这些结果在HIV/AIDS研究人员、权益维护者及决策者中的媄响力。?/span>
q些发现为某个已l在开展中的一个运动增M动能Q该q动提倡对HIV做持l治疗以降低人群中的病毒载量Q而这U方法可能在某些国家中消除HIV/AIDS的流行。但研究人员_向前推进q一q动q易事?/span>
Jon Cohen_“要这一临床试验的证据应用于人群存在着巨大的障。大U?2%的现在就立刻需要ARVs以保持其健康的h无法获得q些药物Q而该人群有那?60万h。更何况Q还有h们试囑֢大治疗规模的各种障碍Q这些障与基础设施的关p要比与药品购买h的关pL大。?/span>
即ɘq样Q某些研Ih员还是将HPTN 052看作是会“改变游戏规则”的因素Q因为它在降低HIV传播率上有着q?00%的功效。而且事实上，它已l许多临床ȝ和决{者立刻行动v来。鉴于所有这些原因，《科学》杂志以2011q度的最大科学突破来重点推介HPTN 052研究?/span>
《科学》杂?011q的其它9开创性的U学成就名单如下?/strong>
隼鸟号太IZ?/strong>Q在l历了某些近乎灾难性的技术困隑֏令h震惊的成功恢复之后，日本的隼鸟号飞船带着来自某个大型的、S型的行星表面的埃q回了地球。这U小行星的尘埃代表了Z?5q中对一个行星体所作的W一ơ直接的采样Q而对q些颗粒的分析证实，在地球上所发现的最常见的被UC普通的球粒陨石是自这些大得多的S-型的行星?/span>
揭开人类h之谜Q通过研究古代和现代hcȝ遗传~码Q研Ih员发玎ͼ许多人现在仍然携带着从远古hcZ—诸如亚z神U的丹尼索瓦Z及至今仍未发现的非洲的hcȝ先——那里承的DNA变异株。今q的一研I揭CZq古人类是如何塑造了我们C人的免疫pȝ的，而一对南非的源泉种南方古猿的化矛_析显C，q些古代的hU动物兼具原始的和智人样的特质?/span>
捕捉一U光合蛋?/strong>Q日本研Ih员绘侧了光合体系IIQ或PSII蛋白l构的生动的l节Q植物用该蛋白将水裂解ؓ氢和氧原子。该水晶般清晰的囑փ昄了该蛋白的催化核心ƈ揭示了内部原子的具体定向。如今，U学家们已经可以q入q一对地球上的生命必不可的催化l构——该l构可能q是打开强有力的清洁能源之门的钥匙?/span>
太空中原始的气体Q用夏威LKeck望远镜来探烦遥远宇宙的天文学家结果发C2个氢气云Q它们在宇宙大爆?0亿年之后gq保持了其原有的化学。其他的研究人员发现了一颗如宇宙最早的恒星所必定是那L几乎完全没有金属的恒星，p宇宙最早的恒星所必定是那LQ但它却是在晚的多的时候Ş成的。这些发现显C，在狂暴宇宙的无尽岁月中还有未受伤害的孤立物质区域持箋存在着?/span>
对微生物l的逐步了解Q深入研Ih肠道中居住的无数的微生物昄Q每个h在其消化道中都有一个领D的dl菌Q拟杆菌、普氏菌属或瘤胃球菌属。追t研I披Ԍq些l菌中的某一U会在高蛋白饮食的时候茁壮生长，而另外一U细菌则更喜Ƣ素食者的饮食。这些及其它发现可帮助理请厘清营d疄状态时饮食和微生物之间的相互作用?/span>
一U有前途的疟疾疫苗Q对某种叫做RTS,S的疟疄苗的临床试验的早期结果ؓ疟疾疫苗研究提供了一针兴奋剂。这一正在q行中的Q包括了过15,000名的来自7个非z国家的孩子的试验o习惯于痛苦失望的疟疾研究者感到有信心Q即他们q是有可能发CU疟疄苗的?/span>
奇怪的太阳p?/strong>Q今q_天文学家W一ơ对几个遥远的行星系l进行了良好的观ƈ发现那里有些情况相当怪异。首先，NASA的开普勒天文台帮助发C一个恒星体p，该体pM的行星的轨道q行方式无法用当今的模型来解释。接着Q研Ih员发C陷在某个|见的“逆行”轨道中一颗气态巨星，一颗围l某个双星系l运行的行星以及10颗看来是在太IZ自由动的行星——它们与在我们自w太阳系中发现的M星体都不一栗?/span>
专门设计的沸?/strong>Q沸x能将xa转变为汽油，净化水质，qoI气及生产洗涤剂Q仅举数例用途）的催化剂和分子筛的多孔矿物质。今q_化学家们实通过设计了一pd更廉仗更薄及更好配备的新型沸石以处理更大的有机分子而展CZ他们的创意?/span>
清除衰老细?/strong>Q实验披Ԍ从小鼠体内清除衰老细胞或那些已经停止分裂的细胞可延后诸如白内障和肌无力等与老化有关症状的v病时间。那些体内清除了q些游荡l胞的小鼠不会比它们的未l治疗的Wgzd更长——但它们实看上L的更好，q些l果l了研究人员某些希望Q即清除衰老细胞也许还能g长我们的黄金岁月?/span>
]]>
TOP 1Q塞舌尔QSeychellesQ——最U净的奢华v?/strong>
来塞舌尔旅游无需{证Q只要一本有效护照即可。有效期?0天?/p>
塞舌风景秀丽，全境50%以上地区被辟然保护区Qn有“旅游者天堂”的誉Q?993q在世界拉塞自然保护区十大旅游点评选中名列W三?/p>
主要景点有马埃岛、普拉兰岛、拉q格岛和伯d岛等。其中马埃岛上的拉塞自然保护区占地65公顷Q拥有种c齐全的热带水果树木和成的象龟Q拉塞尔是马埃岛上最大的自然保护区。在q里Q克里奥的古朴传l与C的豪华设施共存?/p>
?果说塞舌是人间天堂Q五月谷是q天堂里的伊甸园。坐落在普拉兰岛中心的五月谷是世界上最的自然遗Q面U只?9.5公顷。因其中7000多棵h 子树而闻名于世。但是除了v椰子Q这里还有许多世界上独一无二的动植物Q堪U珍奇大观园。五月谷在四十年代的时候还是一个私人庄园，它的名字是当时的庄 园主所取?966q它成ؓ国家公园Q?983q被联合国教U文l织命名Z界自焉产?/p>
长达4公里的博瓦隆白沙滩是Ƨ洲 旅游者的圣地。细d泥的l沙和碧蓝如水晶般透明的v水每q吸引着10多万Ƨ洲有钱人来q里“朝圣”。可q儿童W拙的用沙铲堆砌着他们梦想中的城堡Q热 恋中的年Mh或者蜜月中的情侣们情享受火G的阳光，白发苍苍的老h们牵着手伴着夕阳在v滩上散步……游客可以在专业教练的陪同下潜水Q欣赏v底千变万?的珊瑚礁Q也可以U一条船Lv上钓|钓上鲜活的红x或老板鱼可以立卌当地厨师烤出鲜美lu的鱼排…?/p>
?到塞舌尔Q就不得不提h子。国宝v椰子h子果实是植物王国中最大、最重的U子Q通常?0公斤左右Q最重可?0多公斤。在?-9个月大的时候， 果肉还是胶质状时方可食用，一旦超q?个月Q果肉就会逐渐变硬Q成熟的h子果肉洁白而坚，曄有h拿来冒充象牙Q其度可想而知?/p>
当地环保意识极强。每砍一|都要报环境部审批。在h公园域Qؓ了保护热带鱼c，不但止捕鱼Q当Chq通常会劝L客拾捡贝壟?/p>
当地人热爱音乐，几乎Zh能歌善舞。当地音乐风格叫做“Sega”，据称是非z部落音乐在印度z岛国的“vz版”，节奏Ƣ快Q让人忍不住会跟着音乐轻轻摇摆。热情好客更是塞舌尔人引以自豪的民族习性?/p>
塞舌的克里奥餐和东南亚饮食很相|x原汁原味的清斎ͼ也有很强烈的辛G味道。这里龙虑֒x鱼很有名Qhg很便宜?/p>
U净指数Q★★★★★?/strong>
O指数Q★★★★★?/strong>
l合指数Q★★★★★?/strong>
脓士：
塞舌除d外，q有很多安静的外岛，岛上有酒店，各项设施齐全。该国景点较多，游览需提前做好功课?/p>
TOP 2Q斐（FijiQ——彩色的h世界
中国公民免签Q期限ؓ4个月?/p>
?位于南太^z中心、介于赤道与南回归线之间Q是U澳前往北美的必l之圎ͼ是由叁百多个周围围绕着环状珊瑚C、椰林摇曳的绿岛屿所构成的诱人度假岛国?q里到处充满南国h的塬始美感，q年׃观光业的发展Qv岸地区多已开发ؓC化的休闲度假区，饭店、俱乐部与酒吧林立，全年可见来自世界各地的观?客?/p>
普通的大v是蓝色的Q但是斐的大v却是彩色的。因为无数奇形怪状、色彩斑斓的鱼在水里畅游，大h得五彩缤U?斐济拥有300多个大小不一的岛屿，q些岛屿被环状的珊瑚C包_所以成了鱼儿的天堂。虽然岛屿众多，但是每个都很_致Q最大的岛是地来雾岛。在d?机场不远的码_每天都有很多Ҏd个小岛?/p>
׃人口E而风景秀丽，Ƨ美人士早就把斐当作度假首选之一Q甚至不大牌明星也会选择q里度蜜月。小的一个岛Q还有很多高夫l习场。游客在斐济度假Ӟ往往装束随意Q扛着整箱的啤酒和帐篷Q在z白的沙滩上情ƣ赏落日余晖Q果然是仙一L生活?/p>
?的花很多，到处都是戴着鲜花的h们，L奛_无一例外。据_把花戴在左边是表C未婚，而把花戴在两边则表示已结婚。除了男人戴花外Q这里更让h吃惊?是，男h居然也穿裙子。裙子在q里被称做“SOLO”，不仅男hqx会穿着SOLOQ甚x挥交通的警察们也是穿着SOLO执行公务的，真是街头一景?/p>
斐济
每年?月中旬都举行为期一周的U花节，U花x桑花Q或U木槿花Q是斐济的国花。节日期间岛民D行化妆游行来选DU花皇后?戴花、穿裙子{等奇怪的另类行ؓQ已l让你充分感受到q个岛国的风情了Q而飘扬在四周的h们高亢的歌声则完全带Z岛国悠闲逍遥的情调?/p>
岛上至今依然保有许多传统习俗Q例如将深v中的鱼群呼唤到浅P以利捕捉的神奇颂׃A式、传l的走火仪式{，都是斐济至今仍未消逝的秘传统?斐济的两大国_，一是鲸鱼的qQ叫“塔布阿”，一是当地的一U土产饮料“杨格纳”?/p>
斐济
?是自由港，故免E店特别?ȝ、珠宝、香水、银器、水晶制品等世界一商品皆可以免税的hD得，在有斐济政府观光局标记的免E商?旅客可安心的?买。特色品有手编的篮子、珊瑚、贝壛_品、木雕品、塔巴桌巾、印度沙丽、龟甲等。印度的金银制品色彩鲜艳作工精致?/p>
斐济为太qx岛国地区交通枢U，水、陆、空交通较发达。首都苏瓦港p重要国际v港，可泊万吨轮。苏瓦的瑙烦里机场可停靠波音737飞机Q楠q机场可起降波音747{大型客机?/p>
U净指数Q★★★★★?/strong>
O指数Q★★★★★?/strong>
l合指数Q★★★★★?/strong>
斐济
脓士：
斐济人在饮食嗜好注重讲究吃v产品Q注重菜肴的丰盛。口味一般口呌重、喜油大Q爱甜味?/p>
TOP 3Q马代夫（MaldivesQ——失落的人间天堂
虽然是落地签证，但基本与免签无异Q期限ؓ30天?/p>
马尔代夫
?印度z宽q的蓝色域中，有一串如同被白沙环绕的绿色岛?马尔代夫岛。许多游客在领略q马代夫的蓝、白、绿三色后，都认为它是地球上最后的乐园。有 人Ş定w代夫是上帝抖落的一串珍珠，也有人ŞҎ一片碎玉，q两UŞ定w很脓切，白色沙W的v岛就像一_粒珍珠Q而珍珠旁的v水就像是一片片的美玉。西 方h喜欢U呼马尔代夫为“失落的天堂”?/p>
马尔代夫
99%晶莹剔透的h+1%U净z白的沙?100%的马代夫，千万别惊讶被99%h所环绕的马代夫拥有数千种鱼类Q这里是鱼的故乡?/p>
整个马尔代夫的旅游景观全在一个度假岛屿与一个饭馆所l营的休闲气氛，因ؓ每个岛屿都是一个独立的酒店l营商开发出来的Q所以一岛一饭店成了马代夫特有的旅游文化?/p>
马尔代夫
?都马累有Z1913q的ȝ府。此外，q有Z1656q的古清真寺Q以?675q落成的奇的回教尖塔，白色的徏{上仍可以清晰地看见古兰l的?文?可供MԒ的还有古苏丹王朝的苏丹公园，它在1968q马代夫成立共和国时曾遭到破坏Q虽然今日这里只剩下了一座小的建筑Q却依然比较完整C留古苏丹 文化的精髓，看似单的历史馆内记蝲了多U文化的交融。马累是马尔代夫的购物中心，所有的商店几乎都聚集在此?/p>
马尔代夫首都、机场和旅游饭店均位于独立的岛上。岛间交通全靠乘舏V首都机动R辆较多，以摩托RZ。旅游岛上机动R辆极?/p>
U净指数Q★★★★★
O指数Q★★★★★
l合指数Q★★★★★
马尔代夫
?/strong>贴士Q?/strong>
在这里裸x止的，如被发现会被处以高额|款。禁止穿泌在餐厅用。马代夫旅游岛大多不提供牙列拖鞋等Q徏议ʎ马中国游客自行携带?/p>
TOP 4Q帕劳群岛（PalauQ——蓝l色的潜水胜?/strong>
中国公民落地{֍可，期限30天?/p>
帕劳岛
帕劳大大小340个火山岛和珊瑚岛中只?个岛有常住居民。群岛分布在南北?40公里的v面上Q全国v岸线长达1519公里。到q里来的外国?多半都是Z领略热带h风光Q摇曳的榈树，温和的v风，银白的沙滩，q有水下奇观?/p>
q里是著名的潜水圣地。帕x正式的潜水执照者可甌深v潜水许可Q这里的潜水环境是世界上许多专业潜水者梦寐以求的所在，占了七个世界W一?/p>
帕劳岛
?果你向往真正U净的v_那么帕劳便是你寻扄世外桃源。帕劳的z克岛是太qx最U净的vz生态系l之一Q免遭工业污染的最后净土。不论是艳阳高照的白 天，q是温润可h的夜晚，你都可以走在雪白l腻的沙滩上Q感受世上最最清澈透明的v水。这里的h有一U奇异的蓝绿Ԍ那样U净而又诡异Q让Z敢相信， 不敢触碰Q只怕一伸手便打破了眼前的美梦?/p>
在帕劻I有几个在别处不可能见到的潜奇观Q玫瑰花瓣一L暗红色硬珊瑚铺满底的一座山坡，无数的彩色小鱼在其中自由自在地游来游厅R?/p>
帕劳岛
q有像小桌子那么大的zR贝散落在v底，它的出水有人的背那么_，qxQR贝的厚肉是挤出壳外边的，当你去触动那些肉的时候，它们机灵?收羃hQ如果你真的被那么大的R贝夹住的话Q相信它的力量会让你没救的?/p>
?帕劳的群岛中Q有很多岛都有四面环q内陆湖，湖水没有?水清澈，呈现暗绿艌Ӏ帕劳的水母湖里有着全世界独一无二的无毒水母。据说水母湖的参观是l一理的，有时候，开q个岛的水母湖，一D|间以后，再开另一?岛的水母湖，q个关闭v来让那些受伤的水母休ȝ息，q样Q水母湖既ؓ帕劳创造了可观的旅游经，同时Q水母也得到了管理和保护?/p>
帕劳岛
q有一个值得潜水人关注的奇观是可以看见底zd石——鹦鹉螺。鹦鹉螺生长在hcL法潜到的深v里，׃鹦鹉螺的w体构造是一g格的Q因此它?天生的潜水专Ӟ它不必担心我们hcL怕的气压?/p>
在帕劻I你会重新学到什么是P什么是圎ͼ什么是光，什么是热。上帝创造帕劳似乎就是ؓ了显Cp够创造出一个多么美妙的世界?/p>
帕劳属于热带h性气候，四季都是夏天Q天天都有艳阳高照的好天气，即是在7月到10月的雨季Q也多只有午后的雷阵雨?/p>
U净指数Q★★★★★
O指数Q★★★?/strong>
l合指数Q★★★?/strong>?/strong>
帕劳岛
脓士：
帕劳Ҏ客随w带的药物检查得非常 仔细,如果一定要带药Q请携带包装印刷上有明确英文说明的药?否则会在关被没收?/p>
通用语言是英语，通用货币是美元?/p>
TOP 5Q瓦努阿图（VanuatuQ——梦中的天堂
对中国公民免{证Q原则上?0天?/p>
瓦努阿图
瓦努阿图位于太^z西南部。属拉D亚群岛，q80个岛屿（其中68个有人居住）l成。最大的的岛屿是桑托岛，面积3947qx公里?/p>
?自然对瓦努阿囄恩赐是丰厚的Q不仅给了她丰饶的土圎ͼ而且l了她多L旅游资源。瓦努阿囄80多个岛屿几乎个个都有自己的特艌Ӏ特别是塔纳岛上的伊?火山，被称为是世界上“最可亲q的火山”，思h可以站在火山口的Ҏ上观看火山在脚下L吐火Q因里喷出的岩浆多是直v直落Q很斜喷到口外。h?常把一睹这“上帝燃攄CD”作Z生之q?/p>
南太qx白沙如银Q碧波万P热带潜水观鱼、观火山口、高夫Q游艇，帆板Q沙滩运动等多项休闲׃Q您完全放松n心静享安宁……而热带各色美食，?鲜，法式大餐、中，其是椰子蟹颇值得一试。将会带l您呌极至的n受?/p>
瓦努阿图
?一定要M界上惟一的一所水下邮局Q在一个天然的h公园里，处在^?c以下坐落着瓦努阿图邮政宫方水下邮局。它的外观看h像一个v底巨大的苏打|?_距维拉港沙W?5cI每年?0000多游客到q里来潜_您可以到q里来邮寄防水明信片Q营业员会给您的明信片盖戟뀂不是用传l的以墨汁盖销?的方式Q而是使用凹凸q的日戻I印出Ҏ的凹凸纹q，表示明信片己l寄出。在您邮寄明信片的同时还可观赏欣赏世界上最qh的v底动植物?/p>
瓦努阿图
?托岛首府布干l尔港则是世界闻名的潜水胜地?942q一艘由豪华游轮改装的运兵船Q蝲着5500名美军，在此q港时触上了军自己的封港水P 不久便在q岸的珊瑚礁上沉没。此游轮距v总癄之遥Q而船首和船尾L面分别只?0c70cxQ正好成为潜水爱好者和猎奇探险者们的乐园。附q还?一处百万美金v湾，也是潜水的好d?/p>
二战l束Ӟ军不想带走重型装备Q将装备全部們ր进里。当您戴上潜水镜在?面上向下望时Q那些压路机、推土机、铁轨、吊车和大炮{虽已被 覆盖Q珊瑚遮掩，但其轮廓仍依E可L。此处还有一条长辑֍来米Q重十余吨的大鱼Q不知ؓ何，一q中竟有9个月在此同潜水者嬉戏?/p>
瓦努阿图
而o人刺Ȁ的蹦极，也源自瓦努阿图。在彭_U斯特岛Q每q都有蹦极的节日Q村民们依着大榕树以藤条l木杆搭起一个三四十c高的塔Ӟ勇士们立于塔Ӟ以藤条系I从高处蟩下，头发触地Q而皮肉无损，传ؓl技?/p>
U净指数Q★★★?/strong>
O指数Q★★★?/strong>
l合指数Q★★★?/strong>
瓦努阿图
脓士：
交通设施落后，费用昂贵。以Z。各主要岛屿都有机场。维拉港有国际机场，可直飞澳大利亚、新西兰、斐等?/p>
TOP 6Q毛里求斯（MauritiusQ——印度洋上的珍珠
因旅游目的到访的中国护照持有者可以落地签证，期限?5天?/p>
毛里求斯
毛里求斯景色优美Q风光焝丽、美丽的hW和明媚的阛_吸引着大批来自世界各地的旅游者。北部的潘普利莫塞斯花园内花木葱葱，N啑֕Q人有如入?境之感?00q才开一ơ的高大王棕随风摇曳Q清池内飘荡着巨大的睡莌Ӏ毛里求斯茶隼和_鸽是世界上的珍E动物?/p>
毛里求斯岛是火山岛，四周被珊瑚礁环绕Q岛上的地貌千姿百态。沿h狭窄q_Q中部是高原山地Q有多p和孤立的山峰Q景色颇为壮观?/p>
毛里求斯
?都\易港三面环山Q风景秀丽，是一个天然良港，地处南大西洋和印度洋之间的航道要册Ӏ在苏伊士运河通航以前Q这里是环绕好望角航行的必经之地。市 政厅、自然博物馆、美术馆、图书馆、教堂等市内主要建筑是古代和C、东方与西方风格的奇妙结合。毛里求斯大学培M大批品学g的学子?/p>
?于族裔杂、文化多元，毛里求斯的饮食亦多受克里奥而、中菜、欧z菜和印度菜{媄响，所以一K里常有集不同地方菜肴的情况。其中尤以印度菜 Ҏ里求斯饮食文化媄响最深，印度菜中的咖喱、香料和一U叫“Briyani”的菜饭被搬到毛里求斯h的日帔R食里。毛里求斯一度受法国l治Q所以法国菜 也是普及菜式Q但是受到印度菜和非z菜影响Q这U“变U”的法国菜多用G椒和香料作调呟?/p>
毛里求斯
毛里求斯大部份农业用地都以种植甘蔗ؓ主，除了用作刉蔗p外Q也用来酿制朗姆酒?/p>
?卡（SegaQ是毛里求斯一U本土独有民间音乐和舞蹈的统U。塞卡音乐来自非zԌ现在的塞卡歌舞也转变成吸引游客的表演之一。表演多q性表演?负责乐器演奏Q女性表演者负责舞y表演。多q来所使用的乐器都大同异Q包括用q皮做鼓膜的拉瓦纳手鼓QravaneQ、马拉瓦Ux沙盒 QmaravannQ、三角铁{。女舞蹈员穿上颜色鲜艳的长裙Q跟随轻快的节奏赯。岛上不酒店都提供塞卡歌舞表演?/p>
U净指数Q★★★?/strong>
O指数Q★★★?/strong>
l合指数Q★★★?/strong>
毛里求斯
脓士：
毛里求斯属亚热带h性气候。全q分夏、冬两季Q?1月至ơ年4月ؓ夏季Q沿h?7℃，中部高原22℃，h温度U?7℃；5月至10月ؓ?季、凉季，沿vq_气温24℃，中部高原19℃，h温度U?2℃?/p>
TOP 7Q图瓦卢QTuvaluQ——属于上帝的花园
入境时可得到落地{证Qؓ?0天?/p>
囄?/p>
在美丽的南太qx上，“镶嵌”着许多风景l丽的岛国，Z它们Ş象地Mؓ“一串璀璨的明珠”。在q串“明珠”之中，位于斐济以北的图瓦卢便是其中 亮丽的一颗?/p>
?瓦卢在当地语a中意为“八岛之”。但实际上，囄卢徏国时?个环形珊瑚岛组成。图瓦卢位于太^z南部，总面U只?6qx公里QMh口不?1.5万hQ属于热带vz性气候，一q四季风景如画，Z构成这个国家的9个环状珊瑚小岛称为太qx上的“九颗闪亮明珠”ƈ不过分?/p>
囄?/p>
q里W一眼看上去Q一zօ型的热带岛国景象Q穿着蓝色衬衫和短裤的警察光着脚走在街上，孩子们在珊瑚C围成的湖中嬉戏Q渔夫们用网捞上新鲜的金?鱹{下午时光常常在吸烟、品酸椰汁和小憩中度过。在很多人眼里，囄卢真的像一个“世外桃源”?/p>
国民风纯_d良好Q重视分享。来自同岛的乡亲可借住聚会所Q食物也多由同岛的乡友共同分享，q样的家族传l，Dq国民所得仅U?663金 Q?004Q的土国没有路边乞讨的现象?/p>
该国传统用餐方式乃保留原始的手抓法，不用刀汤匙等具Q客人席地而坐Q地上铺满林投叶~制而成的手工席子?/p>
囄?/p>
?服装上，岛民不论男女都著南国文化特色之一的沙龙裙QSulu Fiji / LavalavaQ，女生的SULU颜色鲜豔Q打l在旁侧Q男生的则颜色暗沉，没有pQ看D装裤Q结于中侧。而出席正式场合，h上半n多半会搭IK 豔颜色的岛屿服装QIsland wearsQ；x则I著qnz装。一般居民^日多半不IKQ即使到办公大楼上班或是部长z公Q亦以拖鞋替代皮鞋。小朋友打赤脚亦角长久之景状?/p>
当地习俗传统对于卛_d土国的h多半于脖子上套上贝壳或是当地U子制成的项鍊，以表达不舍之情。脖子上w多Q表CZh~越好?/p>
U净指数Q★★★
O指数Q★★★?/strong>
l合指数Q★★★?/strong>
囄?/p>
脓士：
据监，囄卢周围vq面q_每年上升5.6毫米Q是联合国气候变暖国际小l估计的全球^面上涨幅度的两倍。由于当地绝大多数居民生zd^面一 Cc之上，q意味着囄卢的大部分岛屿将?0q后被没?/p>
TOP 8Q密克罗D亚联邦（The Federated States of MicronesiaQ——v上的原始林
对中国公民免{，期限?0天?/p>
密克|尼西亚联邦
密克|尼西亚QMicronesiaQ是太^z三大岛之一Q意为“小岛群岛”。而位处南太^z的密克|尼西亚联邦Q中文简U“密联邦”）Q以其浪漫的岛风光Q绝的自然景观Q独特的民族风俗Q成Z界旅游热点国家?/p>
密克|尼西亚联邦?07个大岛屿组成，是世界上降雨量最多的国家Q由于四周被水环l，h成ؓ了生zȝ一切。各岛周围由环礁列布QŞ成天然内湖，林木丰茂Q空气格外清新。乘坐船Ӟ思h可以上到岛上观光游览?/p>
岛上到处是热带物产，咖啡、胡椒、香料植物、椰子、香蕉、芒果等随处可见。值得一提的是，q里名贵的深鱼U——金枪鱼Q据_密克|尼西亚拥有??0%的金枪鱼产量Q列全球之冠?/p>
密克|尼西亚联邦
q里的生态环境保护做得特别好Q坐车行q在环岛公\上犹如在国家林公园中穿行，和、静谧。一z银沙，树木葱郁的美景。高耸的椰林Q巨大的面包树，低矮的薯蓣园、芋头田Q充满了自然、原始岛屿的气息?/p>
I?着华丽、因富藏L而致富的诺鲁人；嚼着槟榔、唇齉K红的雅h、帛琉hQ粗壮高大的楚克人，以及兛_的原住民莫洛人，来往于各个岛屿之_q些 岛上充满了异域风情：密克|尼西亚有一些岛上的居民至今仍保留的一U有的奛_与岳母之间的回避C|q里的妇奻I好食肥肉Q以肥ؓ，更o人惊奇的是逢年 q节Q婚、喜、事，以送活猪ؓ最高礼品，所以在q里随处都能见到zȝ在自由活动?/p>
密克|尼西亚联邦
?到密克罗D来一定要参加特色草裙舞：传统的草裙舞Q舞姿极，青年男女们光着上nQ围上草~的裙子Q跟着音乐的节奏，载歌载舞Q激情、动感。?岛上最吸引人的地方Q还有是一座称之ؓ兰马?Nan Madol)的废城遗址。位于LU佩岛的东南岸，是一座神U的城市Q用20英尺长的x建成Q如今h们仍可见到石条的遗骸Q约100多建筑的遗q如今仍 z落在堤C边上?/p>
Lonely Planetpd丛书里有专门的一本介l密克罗D亚，q其中就包括了密克罗D亚联邦，q个q不Zh所知的原始岛的一切?/p>
U净指数Q★★★
O指数Q★★★
l合指数Q★★★
密克|尼西亚联邦
脓士：
׃人口，交通也颇ؓ落后。四大岛设有国际机场Q但只有U每日一个航班。来往外岛得靠中、小型船Ӟ可能好几天才有一班?/p>
TOP 9Q斯里兰卡（SrilankaQ——太qx上的宝石之国
斯里兰卡对中国游客免{证。前L游，可以停留30天?/p>
斯里兰卡
?里兰卡，旧称锡兰Q是个热带岛国，形如印度半岛的一滴眼泪，镶嵌在广阔的印度zv面上。“斯里兰卡”在僧伽|语中意为“乐土”或“光明富庶的土地”，?“宝石王国”、“印度洋上的明珠”的称Q被马可波罗认ؓ是最丽的岛屿，因ؓ它有丽lu的v滨，秘莫测的古城，丰富的自焉产，以及独特qh的文 化?/p>
斯国也被UCؓ“红茶之国”。斯里兰卡以U茶d于世Q始?867q的U茶U植使她成ؓ诸多U茶的地?/p>
斯里兰卡
?里兰卡品U维拉大象孤儉K斯里兰卡风景优美Q包括宗教圣山，丽的v滩，荷兰D民者留下的城堡Q供奉着佛牙的宝塔，l历了几千年的古城，建立在巨大岩石上 的宫D，甚至有大象和豹等野生动物Q除去这些，即便只是走在那里的街_完全陌生的风情都能让人喜悦。而且斯里兰卡物h低廉Q对中国游客很友好，非常适合 度假?/p>
斯里兰卡
斯里兰卡Z大米Z食，喜食鸡肉Q菜多放咖哩、G椒、椰子aQ味道辛辣、浓烈。煮EL他们饮食中最L色的一U，一般制作方法是把稻子放q大瓦罐中加水煮熟。这LE，cx微黄Q便于贮藏，长时间香味不变，可随旉用?/p>
?斯里兰卡Q最行的购买是茶叶Q手工艺品有木雕、编l品、陶瓷器和金属制品，Ambalangoda是购买斯里兰卡面L最好去处。斯里兰卡尤其以珠宝?而闻名，Ratnapura是斯里兰卡宝矌N易的中心。在斯里兰卡的各购物中心、百货商店、机场免E店、旅游商店和集市{处都可以买到斯里兰卡各式各L 物?/p>
U净指数Q★★☆
O指数Q★★☆
l合指数Q★★☆
斯里兰卡
脓士：
值得注意的是在斯里兰卡，点头和摇头的含义与中国相反，点头是表CZ是，摇头则表C是。斯里兰卡h吃饭是用x的拇指、食指、中指这三根指头拿v食物食用Q给当地人送礼物时Q不要送花Q吃饭和接受C物Ӟ都要用右手?/p>
TOP 10Q韩国济州岛QJeju IslandQ——东方夏威夷
以旅ؓ目的的游客去韩国州岛即可免{证Q如果要去韩国的其他地方当然q是需要签证的?/p>
韩国州?/p>
?州岛地处北纬33度线附近Q却h南国气候的特征Q是韩国q_气温最高、降水最多的地方。温和湿润的气候和q山活动塑造出的焝丽多彩的自然风景Q?赢得了“韩国的夏威夷”的誉Q吸引着成千上万的v内外游客前往观光。位于济州岛西南部的中文Q与湛蓝的L涛ؓ邻，和白色的沙WZQ背傍景色优的天地 渊瀑布Q是一处不可多得的旅游和休养胜地?/p>
韩国州?/p>
很多讉K外国国家元首和政府首脑曾l在中文的别墅和N下榻Q进行他们繁忙访问途中的小憩。济州岛qn有“蜜月之岛”、“浪漫之岛”的称Q韩国许多新婚夫妇都在这里度q他们浪漫的蜜月?/p>
?古以来，人济州岛U这个岛有“三多三宝”。三多是风多、石多、果树多Q三宝是指v产、植物和方言。济州岛的东部是大片适合于放牧的草地Q得该岛许多世U?以来一直是韩国的主要牧场。岛上一个占?万公L牧场是亚z最好的牧场之一。济州岛历史上曾以饲养马匚w名，如今岛上仍有3000多匹骏马Q约占韩国马 ҎL的三分之二?/p>
韩国州?/p>
岛上气候温和，适宜U植柑桔、葡萄柚和红桔，岛上的西归正是全国柑桔生的中心?/p>
Z保护果树不受岛上强劲风的R袭，果园的四周徏起了高高的石墙?/p>
州岛远d岛，岛上的一些原始习俗仍在流传。最有意思的是那里还可以看到母系C会的痕q，当家、谋生主要靠妇女。其中“v女”算是最典型的“职业妇女”了。她们常要潜入水下沿d的礁石采集贝cR鲍鱹{v参和{v产品Q而男Z却留在家里照料家务?/p>
U净指数Q★?/strong>
O指数Q★★☆
l合指数Q★★☆
韩国州?/p>
脓士：
、生鱼片、鲍鱼粥、v产火锅、烤方关鱼等都是当地有特色的食Qo人向往的济州岛州的风呛_吃还有糕饹{烤嘉吉鱹{五梅汽酒、山鸡荞麦面、盛Ҏ、荞麦刀削面{?/p>
州全境南北有公路诏通，外国人持有国际驾驶执照者可U借汽车?/p>
题目来源Q?a href="mailto:ZOJ@1992">ZOJ1992
对于一个合图Q即有有向边又有无向边的图，判断是否存在一条欧拉回路?
解法Q{Q：混合图欧拉回路用的是|络。把该图的无向边随便定向Q计每个点的入度和出度。如果有某个点出入度之差为奇敎ͼ那么肯定不存在欧拉回路。因为欧拉回路要求每点入?= 出度Q也是dCؓ偶数Q存在奇数度点必不能有欧拉回路。现在每个点入度和出度之差均为偶数。将q个偶数除以2Q得x。即是说Q对于每一个点Q只要将x条边反向Q入>出就是变入，?gt;入就是变出）Q就能保证出 = 入。如果每个点都是?= 入，那么很明显，该图存在欧拉回路。现在的问题变成了Q该改变哪些边，可以让每个点?= 入？构造网l流模型。有向边不能改变方向Q直接删掉。开始已定向的无向边Q定的是什么向Q就把网l构建成什么样Q边长容量上?。另新徏s和t。对于入 > 出的点uQ连接边(u, t)、容量ؓxQ对于出 > 入的点vQ连接边(s, v)Q容量ؓxQ注意对不同的点x不同。当初由于不心Q在q里错了好几ơ）。之后，察看是否有满的分配。有是能有Ƨ拉回\Q没有就是没有。查看流值分配，所有流量非 0Q上限是1Q流g?是1Q的边反向，p得到每点入度 = 出度的欧拉图。由于是满流Q所以每个入 > 出的点，都有x条边q来Q将q些q来的边反向QOKQ入 = Z。对于出 > 入的点亦然。那么，没和s、tq接的点怎么办？和sq接的条件是?> 入，和tq接的条件是?> 出，那么q个既没和s也没和tq接的点Q自然早在开始就已经满?= Z。那么在|络过E中Q这些点属于“中间点”。我们知道中间点量不允许有累积的，q样Q进d就出来多少Q反向之后，自然仍保持^衡。所以，pP混合图欧拉回路问题，解了?nbsp;
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define N 205
#define MAXN N
#define inf 100000000
int map[N][N];
int flow[N][N];
int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
if (source==sink) return inf;
for (i=0;i<n;i++)
for (j=0;j<n;flow[i][j++]=0);
for (;;){
for (i=0;i<n;pre[i++]=0);
pre[t=source]=source+1,d[t]=inf;
for (p=q=0;p<=q&&!pre[sink];t=que[p++])
for (i=0;i<n;i++)
if (!pre[i]&&(j=mat[t][i]-flow[t][i]))
pre[que[q++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
else if (!pre[i]&&(j=flow[i][t]))
pre[que[q++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
if (!pre[sink]) break;
for (i=sink;i!=source;)
if (pre[i]>0)
flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
else
flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
}
for (i=0;i<n;i++)
if(mat[source][i] > flow[source][i])
return 0;
return 1;
}
int main()
{
int T, degin[N],degout[N], n, m, x, y, z;
int flag;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
memset(degin,0,sizeof(degin));
memset(degout,0,sizeof(degout));
memset(map,0,sizeof(map));
for(int i = 0; i < m; i++){
scanf("%d%d%d",&x,&y,&z);
degout[x]++;
degin[y]++;
if(!z)map[x][y]++;
}
flag = 0;
for(int i = 1; i <= n && !flag; i++){
if((degin[i]+degout[i])%2)flag=1;
if(degin[i] > degout[i])
map[i][n+1] = (degin[i]-degout[i])/2;
else
map[0][i] = (degout[i]-degin[i])/2;
}
if(flag)
printf("impossible\n");
else{
if(max_flow(n+2,map,0,n+1,flow))
printf("possible\n");
else
printf("impossible\n");
}
}
return 0;
}
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define N 205
#define MAXN N
#define inf 100000000
int map[N][N];
int flow[N][N];
int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
if (source==sink) return inf;
for (i=0;i<n;i++)
for (j=0;j<n;flow[i][j++]=0);
for (;;){
for (i=0;i<n;pre[i++]=0);
pre[t=source]=source+1,d[t]=inf;
for (p=q=0;p<=q&&!pre[sink];t=que[p++])
for (i=0;i<n;i++)
if (!pre[i]&&(j=mat[t][i]-flow[t][i]))
pre[que[q++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
else if (!pre[i]&&(j=flow[i][t]))
pre[que[q++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
if (!pre[sink]) break;
for (i=sink;i!=source;)
if (pre[i]>0)
flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
else
flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
}
for (i=0;i<n;i++)
if(mat[source][i] > flow[source][i])
return 0;
return 1;
}
int main()
{
int T, degin[N],degout[N], n, m, x, y, z;
int flag;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
memset(degin,0,sizeof(degin));
memset(degout,0,sizeof(degout));
memset(map,0,sizeof(map));
for(int i = 0; i < m; i++){
scanf("%d%d%d",&x,&y,&z);
degout[x]++;
degin[y]++;
if(!z)map[x][y]++;
}
flag = 0;
for(int i = 1; i <= n && !flag; i++){
if((degin[i]+degout[i])%2)flag=1;
if(degin[i] > degout[i])
map[i][n+1] = (degin[i]-degout[i])/2;
else
map[0][i] = (degout[i]-degin[i])/2;
}
if(flag)
printf("impossible\n");
else{
if(max_flow(n+2,map,0,n+1,flow))
printf("possible\n");
else
printf("impossible\n");
}
}
return 0;
}
]]>
题目来源Q?a >POJ3107
l定一|ҎQ删除树中一个节点，剩下各子树的包含的节Ҏ最大值最，问树中有多少个这L节点?
解法QQ意选择一个节点，作ؓ根，q行遍历。对一个节点VQ设其子节点为cv[1..k]Qf[v]Z节点v为根的子树包含的节点数?
对于每一个节点VQ删除V之后剩下子树含有的节Ҏ中最大分别ؓ max{ f[cv[1]]Qf[cv[2]]Q?...f[cv[k]]QSumNode-(f[cv[1]]+f[cv[2]]+....+f[cv[k]]) }Q一ơ遍历即可求出所有删除一个节点后的最大子树包含的节点数?
#include<iostream>
#include<vector>
#include<algorithm>
#include<stdio.h>
#define MAXN 50005
using namespace std;
vector<int>ansNode;
int maxNumNode;
int n, f[MAXN];
int pointTree[MAXN];
struct Tree{
int x,y;
}tree[MAXN*2];
int len;
bool cmp(struct Tree a, struct Tree b)
{
return a.x<b.x;
}
int treedp(int parentNode,int thisNode){
int maxNode=0;
int sumChildNode=0;
int index=pointTree[thisNode];
do{
int childNode=tree[index].y;
if(childNode != parentNode)
{
f[childNode]=treedp(thisNode,childNode);
sumChildNode+=f[childNode];
if(f[childNode]>maxNode)maxNode=f[childNode];
}
index++;
}while(index<len && tree[index].x==tree[index-1].x);
if(maxNode<n-sumChildNode-1)maxNode=n-sumChildNode-1;
if(maxNode<maxNumNode){
maxNumNode=maxNode;
ansNode.clear();
ansNode.push_back(thisNode);
}else if(maxNode==maxNumNode){
ansNode.push_back(thisNode);
}
return sumChildNode+1;
}
int main(int argc,int *argv[])
{
while(scanf("%d",&n)!=EOF){
len=0;
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
tree[len].x=x;
tree[len++].y=y;
tree[len].x=y;
tree[len++].y=x;
}
sort(tree,tree+len,cmp);
pointTree[tree[0].x]=0;
for(int i=1;i<len;i++){
if(tree[i].x != tree[i-1].x)
pointTree[tree[i].x] = i;
}
ansNode.clear();
maxNumNode=n;
treedp(-1,1);
sort(ansNode.begin(),ansNode.end());
for(int i=0;i<ansNode.size();i++)
printf("%d ",ansNode[i]);
}
return 0;
}
#include<vector>
#include<algorithm>
#include<stdio.h>
#define MAXN 50005
using namespace std;
vector<int>ansNode;
int maxNumNode;
int n, f[MAXN];
int pointTree[MAXN];
struct Tree{
int x,y;
}tree[MAXN*2];
int len;
bool cmp(struct Tree a, struct Tree b)
{
return a.x<b.x;
}
int treedp(int parentNode,int thisNode){
int maxNode=0;
int sumChildNode=0;
int index=pointTree[thisNode];
do{
int childNode=tree[index].y;
if(childNode != parentNode)
{
f[childNode]=treedp(thisNode,childNode);
sumChildNode+=f[childNode];
if(f[childNode]>maxNode)maxNode=f[childNode];
}
index++;
}while(index<len && tree[index].x==tree[index-1].x);
if(maxNode<n-sumChildNode-1)maxNode=n-sumChildNode-1;
if(maxNode<maxNumNode){
maxNumNode=maxNode;
ansNode.clear();
ansNode.push_back(thisNode);
}else if(maxNode==maxNumNode){
ansNode.push_back(thisNode);
}
return sumChildNode+1;
}
int main(int argc,int *argv[])
{
while(scanf("%d",&n)!=EOF){
len=0;
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
tree[len].x=x;
tree[len++].y=y;
tree[len].x=y;
tree[len++].y=x;
}
sort(tree,tree+len,cmp);
pointTree[tree[0].x]=0;
for(int i=1;i<len;i++){
if(tree[i].x != tree[i-1].x)
pointTree[tree[i].x] = i;
}
ansNode.clear();
maxNumNode=n;
treedp(-1,1);
sort(ansNode.begin(),ansNode.end());
for(int i=0;i<ansNode.size();i++)
printf("%d ",ansNode[i]);
}
return 0;
}
]]>
最树形图法(Zhu-Liu Algorithm)Q?
1. 设最树形图的LgؓcostQ置cost??/p>
2. 除源点外Qؓ其他所有节点Vi找一条权值最的入边Q加入集合T。T是最短边的集合。加边的ҎQ遍历所有点到Vi的边中权值最的加入集合TQ记pre[Vi]边的LQmincost[Vi]边的权倹{?/p>
3. 查集合T中的Ҏ否存在有向环Q有则{到步?Q无则{到步?。这里需要利用pre数组Q枚举检查过的点作ؓ搜烦的v点，cMdfs的操作判断有向环?/p>
4. 有向环~成一个点。设环中有点{Vk1,Vk2,…,Vki}共i个点Q用Vk代替~成的点。在压羃后的图中Q更新所有不在环中的点V到Vk的距：
map[V][Vk] = min {map[V][Vkj]-mincost[Vki]} 1<=j<=iQ?/p>
map[Vk][V] = min {map[Vkj][V]} 1<=j<=I?/p>
5. cost加上T中有向边的权值d是最树形图的权值d?/p>
]]>
最\径覆盖：用尽量少的不怺单\径覆盖有向无环图Q的所有结炏V解xc问题可以徏立一个二分图模型。把所有顶点i拆成两个Ql点集中的i和Yl点集中的i',如果有边i->jQ则在二分图中引入边i->j'Q设二分图最大匹配ؓm,则结果就是n-m?br>最大独立集问题Q在Q个点的图G中选出m个点Qɘqm个点两两之间没有边．求m最大|如果图Ｇ满二分图条Ӟ则可以用二分囑配来做．最大独立集Ҏ = N - 最大匹配数?br>
]]>
// 2391828 2011-01-24 14:54:21 Accepted 3018 C++ 840 17756 redsea
#include<stdio.h>
#include<string.h>
#define MAXN 500000
#define N 20002
struct seg
{
int dx, dy, ux, uy;
int ch[4];
int total;
}sgt[MAXN];
int sgtn;
int ans;
int w(int x, int y, int dx, int dy, int ux, int uy)
{
int midx = (dx+ux)/2;
int midy = (dy+uy)/2;
if(x>=dx && x<=midx){
if(y>=dy && y<=midy)
return 0;
else
return 1;
}
else
{
if(y>=dy && y<=midy)
return 2;
else
return 3;
}
}
int init(int dx, int ux, int dy, int uy)
{
sgt[sgtn].dx = dx;
sgt[sgtn].ux = ux;
sgt[sgtn].dy = dy;
sgt[sgtn].uy = uy;
sgt[sgtn].total = 0;
for(int i = 0; i < 4; i++)
sgt[sgtn].ch[i] = -1;
sgtn++;
return sgtn-1;
}
void insert(int root, int x, int y, int a)
{
if(sgt[root].dx == sgt[root].ux && sgt[root].dx == x && sgt[root].dy == sgt[root].uy && sgt[root].dy == y){
sgt[root].total += a;
return;
}
int id = w(x,y,sgt[root].dx, sgt[root].dy, sgt[root].ux, sgt[root].uy);
int midx = (sgt[root].dx+sgt[root].ux)/2;
int midy = (sgt[root].dy+sgt[root].uy)/2;
sgt[root].total += a;
if(id == 0){
if(sgt[root].ch[id] == -1){
sgt[root].ch[id] = init(sgt[root].dx,midx,sgt[root].dy,midy);
}
insert(sgt[root].ch[id],x,y,a);
}else if(id == 1){
if(sgt[root].ch[id] == -1){
sgt[root].ch[id] = init(sgt[root].dx,midx,midy+1,sgt[root].uy);
}
insert(sgt[root].ch[id],x,y,a);
}else if(id == 2){
if(sgt[root].ch[id] == -1){
sgt[root].ch[id] = init(midx+1,sgt[root].ux,sgt[root].dy,midy);
}
insert(sgt[root].ch[id],x,y,a);
}else{
if(sgt[root].ch[id] == -1){
sgt[root].ch[id] = init(midx+1,sgt[root].ux,midy+1,sgt[root].uy);
}
insert(sgt[root].ch[id],x,y,a);
}
}
void sum(int root, int dx, int dy, int ux, int uy)
{
if(root < 0)return;
if(sgt[root].dx > ux || sgt[root].ux < dx || sgt[root].dy > uy || sgt[root].uy < dy)
return;
if(sgt[root].dx >= dx && sgt[root].ux <= ux && sgt[root].dy >= dy && sgt[root].uy <= uy)
{
ans += sgt[root].total;
return;
}else{
for(int i = 0; i < 4; i++)
{
sum(sgt[root].ch[i],dx,dy,ux,uy);
}
}
}
int main()
{
char opes[500];
char now;
int x, y, z;
int x1, x2, y1, y2;
while(scanf("%s", opes) != EOF){
now = opes[0];
getchar();
sgtn = 1;
sgt[0].total = 0;
sgt[0].dx = 1;
sgt[0].dy = 1;
sgt[0].ux = 20000;
sgt[0].uy = 20000;
for(int i = 0; i < 4; i++)
sgt[0].ch[i] = -1;
while(true){
if(now == 'E') break;
gets(opes);
if(opes[0] < '0' || opes[0] > '9'){
now = opes[0];
continue;
}
if(now == 'I'){
sscanf(opes, "%d %d %d", &x, &y, &z);
insert(0,x,y,z);
}else{
sscanf(opes, "%d %d %d %d", &x1, &x2 , &y1, &y2);
ans = 0;
sum(0,x1,y1,x2,y2);
printf("%d\n", ans);
}
}
}
return 0;
}
二维U段树?br>
]]>
// 2391682 2011-01-24 10:49:56 Accepted 1992 C++ 90 508 redsea
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define N 205
#define MAXN N
#define inf 100000000
int map[N][N];
int flow[N][N];
int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
if (source==sink) return inf;
for (i=0;i<n;i++)
for (j=0;j<n;flow[i][j++]=0);
for (;;){
for (i=0;i<n;pre[i++]=0);
pre[t=source]=source+1,d[t]=inf;
for (p=q=0;p<=q&&!pre[sink];t=que[p++])
for (i=0;i<n;i++)
if (!pre[i]&&(j=mat[t][i]-flow[t][i]))
pre[que[q++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
else if (!pre[i]&&(j=flow[i][t]))
pre[que[q++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
if (!pre[sink]) break;
for (i=sink;i!=source;)
if (pre[i]>0)
flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
else
flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
}
for (i=0;i<n;i++)
if(mat[source][i] > flow[source][i])
return 0;
return 1;
}
int main()
{
int T, degin[N],degout[N], n, m, x, y, z;
int flag;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
memset(degin,0,sizeof(degin));
memset(degout,0,sizeof(degout));
memset(map,0,sizeof(map));
for(int i = 0; i < m; i++){
scanf("%d%d%d",&x,&y,&z);
degout[x]++;
degin[y]++;
if(!z)map[x][y]++;
}
flag = 0;
for(int i = 1; i <= n && !flag; i++){
if((degin[i]+degout[i])%2)flag=1;
if(degin[i] > degout[i])
map[i][n+1] = (degin[i]-degout[i])/2;
else
map[0][i] = (degout[i]-degin[i])/2;
}
if(flag)
printf("impossible\n");
else{
if(max_flow(n+2,map,0,n+1,flow))
printf("possible\n");
else
printf("impossible\n");
}
}
return 0;
}
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define N 205
#define MAXN N
#define inf 100000000
int map[N][N];
int flow[N][N];
int max_flow(int n,int mat[][MAXN],int source,int sink,int flow[][MAXN]){
int pre[MAXN],que[MAXN],d[MAXN],p,q,t,i,j;
if (source==sink) return inf;
for (i=0;i<n;i++)
for (j=0;j<n;flow[i][j++]=0);
for (;;){
for (i=0;i<n;pre[i++]=0);
pre[t=source]=source+1,d[t]=inf;
for (p=q=0;p<=q&&!pre[sink];t=que[p++])
for (i=0;i<n;i++)
if (!pre[i]&&(j=mat[t][i]-flow[t][i]))
pre[que[q++]=i]=t+1,d[i]=d[t]<j?d[t]:j;
else if (!pre[i]&&(j=flow[i][t]))
pre[que[q++]=i]=-t-1,d[i]=d[t]<j?d[t]:j;
if (!pre[sink]) break;
for (i=sink;i!=source;)
if (pre[i]>0)
flow[pre[i]-1][i]+=d[sink],i=pre[i]-1;
else
flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1;
}
for (i=0;i<n;i++)
if(mat[source][i] > flow[source][i])
return 0;
return 1;
}
int main()
{
int T, degin[N],degout[N], n, m, x, y, z;
int flag;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
memset(degin,0,sizeof(degin));
memset(degout,0,sizeof(degout));
memset(map,0,sizeof(map));
for(int i = 0; i < m; i++){
scanf("%d%d%d",&x,&y,&z);
degout[x]++;
degin[y]++;
if(!z)map[x][y]++;
}
flag = 0;
for(int i = 1; i <= n && !flag; i++){
if((degin[i]+degout[i])%2)flag=1;
if(degin[i] > degout[i])
map[i][n+1] = (degin[i]-degout[i])/2;
else
map[0][i] = (degout[i]-degin[i])/2;
}
if(flag)
printf("impossible\n");
else{
if(max_flow(n+2,map,0,n+1,flow))
printf("possible\n");
else
printf("impossible\n");
}
}
return 0;
}
]]>
class deque {
public:
// typedefs:
typedef iterator;
typedef const_iterator;
typedef Allocator<T>::pointer pointer;
typedef Allocator<T>::reference reference;
typedef Allocator<T>::const_reference const_reference;
typedef size_type;
typedef difference_type;
typedef T value_type;
typedef reverse_iterator;
typedef const_reverse_iterator;
// allocation/deallocation:
deque();
deque(size_type n, const T& value = T());
deque(const deque<T, Allocator>& x);
template <class InputIterator>
deque(InputIterator first, InputIterator last);
~deque();
deque<T, Allocator>& operator=(const deque<T, Allocator>& x);
void swap(deque<T, Allocator>& x);
// accessors:
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rend();
size_type size() const;
size_type max_size() const;
bool empty() const;
reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// insert/erase:
void push_front(const T& x);
void push_back(const T& x);
iterator insert(iterator position, const T& x = T());
void insert (iterator position, size_type n, const T& x);
template <class InputIterator>
void insert (iterator position, InputIterator first, InputIterator last);
void pop_front();
void pop_back();
void erase(iterator position);
void erase(iterator first, iterator last);
};
]]>
class Allocator = allocator> class list
{
public:
// typedefs:
typedef iterator
typedef const_iterator
typedef Allocator<T>::pointer pointer
typedef Allocator<T>::reference reference
typedef Allocator<T>::const_reference const_reference
typedef size_type
typedef difference_type
typedef T value_type
typedef reverse_iterator
typedef const_reverse_iterator;
// allocation/deallocation:
list()
list(size_type n, const T& value = T())
template <class InputIterator>
list(InputIterator first, InputIterator last)
list(const list<T, Allocator>& x)
~list()
list<T, Allocator>& operator=(const list<T, Allocator>& x)
void swap(list<T, Allocator>& x);
// accessors:
iterator begin()
const_iterator begin() const
iterator end()
const_iterator end() const
reverse_iterator rbegin()
const_reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rend();
bool empty() const;
size_type size() const;
size_type max_size() const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
// insert/erase:
void push_front(const T& x);
void push_back(const T& x);
iterator insert(iterator position, const T& x = T());
void insert(iterator position, size_type n, const T& x);
template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last);
void pop_front();
void pop_back();
void erase(iterator position);
void erase(iterator first, iterator last);
// special mutative operations on list:
void splice(iterator position, list<T, Allocator>& x);
void splice(iterator position, list<T, Allocator>& x, iterator i);
void splice(iterator position, list<T, Allocator>& x,
iterator first, iterator last);
void remove(const T& value);
template <class Predicate> void remove_if(Predicate pred);
void unique();
template <class BinaryPredicate> void unique(BinaryPredicate binary_pr
void merge(list<T, Allocator>& x);
template <class Compare> void merge(list<T, Allocator>& x, Compare com
void reverse();
void sort();
template <class Compare> void sort(Compare comp);
};
]]>