集训队作业雅礼中学_第1页
集训队作业雅礼中学_第2页
免费预览已结束，剩余2页可下载查看

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

POIXIV2006/2007StageII雅礼中 【RidgesandValleys题目描n*n的地图每个格子的高度，要求出山谷的个数和山脊的个数，2≤n≤问题分子判断其相邻格子比这个格子高还是低即可，时间复杂度为O(n2)．【Megalopolis题目描将某条树边<ab>1≤n250000，m为操作次数问题分以1为根将树DFS一遍，计算出树的DFS序和以每个节点为根的节点对应DFS序中的区Dist[i]表示1与点i的路径的权值之和，初始的时Dist[i]=i的深度．每次将树边a→b的权值修改为0相当于将b的内对应的DFS序中区间内节点的Dist值全部减1，用一个线段树按DFS序的节点的Dist值，时间复杂度为O(mlog2n)．【TheFlood题目描m*n的地图，每个格子有一个海拔高度，初始的时候所有的格子1≤m,n≤问题分首先分析如果格子a安装了一个抽水机如何判定bA安装了一个抽水机，那么B，C，E的水都可以被清理掉．不难发现，如果格子a安装了抽水机，并且存在一条到格子b的路路径上的格子的海拔均不大于格子b的海拔，那么格子b的水就可以清理掉．有了这个结论后问题就变得简单多了：初始的时候把每个格子作为一个集O(mn(m*【RockGarden题目描平面上n个点(xiyi，你可以选择将一些点的横纵坐标交换(xiyi)→(yixi)，代价为Wi，使得满足可以用一个平行于坐标轴的周长最小的矩形来覆盖所有的n≤问题分先考虑如何交换后使得覆盖所有点的矩形的周长最小：将(xi,yi)全部交换到x=y的一侧，比如全部修改成xi≤yi后矩形的周长一定最小．xy两侧都有点的情况，设能够覆盖(pq)-(rs)，表示矩形的左下角和右上角．满ab，cd，pq，rs，当前状态下覆盖所有点矩形的周长为max(c,r)+max(d,s)–min(a,p)–min(b,q)．如max(c,s)–min(b,p)–min(a,q)，后者一定不会大于前者．相当于有四个区间，1在区2的左侧3在区4的左侧1和区3叠加1，区24142将所有的点全部移动到x=y的一侧后，Ans=maxX–minX+maxY–minY4(minXminYmaxXmaxY)，(minYminXmaxXmaxY)，(minXminYmaxY,maxX)和(minY,minX,maxY,maxX)．对这四种矩形分别判断，判断是否所有的点【TetrisAttack题目描2n个数排成一列，1,2n每个数恰好出现一次．你每次可以选择交换1≤n≤问题分lr，AlArii对应的区间为[lr]，不难发现通r–l–1次交换消除i这个数后，其他数的相对位置是不会改变的．来分析应该按怎样的顺序依次消除掉每一个数：考虑两个数x,y，它们对应的区间为数x,y对应的两个

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论