over 1 year ago

感觉大爷们都做过poi压,那我就做做看吧

poi2007

旅游景点atr
题意:
从前有n(<=20000)个城市,m(<=200000)条边,经过每条边要一定时间。有个人想去编号1..k+1(<=20)城市。有很多对要求表示去过i城市后经过j城市算j去过(i,j<=k+1),在去过i城市前去了j城市只算经过,不算去过。问去完1..k+1最后到达n最短时间
题解:
k次spfa少不了辣~~ 又因为奇奇怪怪的限制条件,就写个状压f[s][i]表示去过城市为s,当前在i最小时间
听说这题常数感人,为什么我没感觉?

办公楼biu
题意:
有n(<=100000)个人,m(<=2000000)对人有关系。没关系的人必须在一栋楼里,问最多能把他们分到几栋楼里
题解:
实在膜得不行
首先一个naive想法就是把补图建出来看有几个联通块。
考虑从前往后处理每个未被并入别人联通块的人,bfs看那些人要和他在一个联通块中。
先将与他相连的人标记出来,访问一遍当前所有有用的人,将没被标记的人删除并加入队列,这样就能得到他所在联通块所有的人了
分析一下复杂度。当访问到一个人时,若他没被标记就会把他加入队列,以后去打个标记,每个人只会这样做一次,复杂度O(n+m)。若他被标记,就产生一次无用遍历,一个标记最多产生一次无用遍历,这部分是O(m)的,所以总复杂度O(n+m)。
现在我们需要一种数据结构能遍历每个当前有用的人,每个人的遍历O(1),支持删除。没错就是链表了(做这题前的ljm表示链表是什么可以吃吗

对称轴osi
题意:
n(3<=n<=100000),表示了多边形的点数。然后在后面n行每行两个整数x和y(-100000000<=x, y<=100000000),依次表示多边形的顶点坐标。多边形不一定是凸的,但是不自交——任何两条边都只有最多一个公共点——他们的公共端点。此外,没有两条连续的边平行。问多边形有多少条对称轴。
题解:
实在神得不行
以前做manacher的时候做的这题。考虑对称轴过的点一定是多边形顶点或边中点,先把中点加入。
从对称轴过的点开始向左右看,yy下发现边是对称的,就用点积叉积判相等做manacher。

Zap
题意:
(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个正整数,分别为a,b,d。(1<=d<=a,b<=50000)。询问有多少对i,j满足i<=a,j<=b,gcd(i,j)=d
题解:
积性函数经典题。。

山峰和山谷Grz
题意:
一个nn的地图,每个点有高度。与一个点相邻的点是周围8个点。我们定义一个格子的集合S为山峰(山谷)当
且仅当:1.S的所有格子都有相同的高度。2.S的所有格子都联通3.对于s属于S,与s相邻的s’不属于S。都有ws >
ws’(山峰),或者ws < ws’(山谷)。问有多少山峰山谷
题解:
水题

大都市meg
题意:
给一颗树,边权为1。m个操作,将一条边权值改为0或询问一个点到根路径和
题解:
dfs序,树状数组,水题

洪水pow
题意:
有一个nm(n,m<=1000)的地图,每个点有海拔。现在下雨了,每个点积水inf,水会按物理原则向上下左右流。现在要抽干k个指定点的水。在一个点放水泵,就会一直抽到没水。问最少多少水泵
题解:
考虑一个点什么时候不用水泵也能抽干水。就是只沿低于或等于他的格子走,能走到一个水泵。
就把关键点按高度从小到大排序。每次bfs按上面规则走,若能走到一个之前的关键点走过的点,就代表他能走到一个水泵。因为此时他的高度不小于所有走过的点,然后贪心即可。

石头花园SKA
题意:
第一向限有n(<=100000)个石头,给出他们坐标和重量。现在可以将一个石头从(x,y)搬到(y,x)代价是他的重量。找一种方案,使包括所以石头的矩形(长宽和x,y轴平行)周长最小,周长相等时代价最小
题解:
我yy了一下觉得好像同时翻到x=y上方或下方一定最优,做了就wa了。看别人题解,周长是这样的,但代价还有两种奇奇怪怪的情况看不懂,去问他们都忘了TAT看来要成为世界未解之谜了

立方体大作战tet
题意:
有n(n<=50000)对东西叠在一起,一对东西相邻时可消除,消除后就上面掉下来。可以交换相邻两个东西。问全部消除最少操作数。保证答案小于1000000
题解:
若两对物品是1 .... 2 ..... 2 .... 1一定是先消2更优 若是1.... 2 .... 1 ... 2 先消1消2都一样
因为保证答案小于1000000,开个栈模拟就好
如果泥想写splay当然也是资磁的~~

驾驶考试egz
题意:
有n(<=100000)条从南到北的路,每条路长度m(<=100000),有k(<=100000)条从东西或西东的路,第i条路在hi位置连接di和di+1。就是一个这样的图
现在能在任意位置添加p条东西或西东的路。以每条南北路位置0为起点,位置m为终点。只能按路的方向走,最多比加边前多多少起点能到达每个终点。
题解:
两个结论很明显。1、要到达所有终点等价于能到达最左和最右(即1、n)。2、若i能到1,则此时2..i-1都能到1。到n也类似
推出结论:能到达最左右的点是连续的。因为若i< j,i和j能到左右。对于i< k < j,i能到右,k则能到右,j能到左,k则能到左
那如果我们做出l[i],r[i]表示i到左右最少要添多少条边(明显l递增,r递减),枚举i,单调找一个j < i,使l[i]+r[j]<=p更新答案就行了
现在来看如果作出l和r
下面是ljm的辣鸡做法(做l的情况)
考虑一个dp。f[i][j]表示第i条路,j高度到达最左至少要加多少条边
对于i在高度j有到i-1的边,f[i][j]=f[i-1][j]
对于没有的j,f[i][j]=f[i-1][j]+1
然后当j>k,f[i][j]可以更新f[i][k]。因为k可以先走上去
那我们可以先把每个数都加1,再把不用加1的人减1。只有减1的人会破坏单调增,所以把他扔给下面所以人取个min
于是这个东西可以用claris老司机教的神到不行的维护上下界的线段树搞。
加减打标记,取min不打,直接对这个区间改上界。然后每走到一个节点,有标记直接改上下界,传掉他的标记和他孩子的标记后,用他的上下界限制孩子上下界,回溯时用孩子上下界更新他的上下界
(在线段树大功告成AC后,ljm突然发现——这东西弄个最长 * * 子序列就好了吧??!

天然气管道Gaz
题意:
给出天然气井和中转站坐标。现在需要将中转站和天然气井连接起来。每个中转站必须被连接到正好一个钻油井,反之亦然。 Mary特别指名,建设的天然气管道必须从某个天然气井开始,向南或者向东建设。Mary想知道怎么连接每个天然气井和中转站,使得需要的天然气管道的总长度最小。
题解:
对于天然气(x1,y1)->中转站(x2,y2)曼哈顿距离是x2-x1+y1-y2。其实只有一种情况

堆积木Klo
题意:
给出一个n(<=100000)个数序列,现能从中删若干个。问最多能有有多少ai=i
题解:
一眼最长上升子序列~~ 一秒wa~~
冷静分析一下,f[i]表示使ai最终位置为ai最多多少个 * * *
那f[i]继承f[j]需要的条件是:1、i>j 2、ai>aj 3、i-j>=ai-aj
3转化为i-ai>=j-aj
考虑将ai从小到大加入,这样保证了ai>aj.若此时i-ai>=j-aj,便能保证i>j。那对i-ai开个树状数组就行了

砝码Odw
题意:
公司有m个(<=100000)容器可以装n(<=100000)个砝码。他们想装尽量多的砝码。每个容器可以装的砝码总重量不能超过每个容器的限制wi。任何两个砝码中总有一个的重量是另外一个的整数倍,当然他们也可能相等。
题解:
以前做的。。
好提亚
首先贪心尽量取小的 然而我不知道怎么放 于是膜了题解
因为两两互为倍数,所以不同的种类是log级别的
将重量排序 第i种重量作为第i位的底弄出个新进制,可以将容量写成新进制。然后每位是可加的,高位能向低位借位,低位不能向高位合,然后贪心就好
为什么是正确的呢?我觉得本质是因为重量数很少,并且两两相关,就可以做出容量对每种重量的影响,并且可以调整
低位不能合高位是因为他们必在不同容器中

四进制的天平Wag
题意:
从前有个人想要用天平和砝码称出重量n(<=10^1000)物品,他有所有重量为4的幂的砝码,数量无限。物品放左边,砝码可放左右。问最少用多少砝码,以及最少砝码情况下方案数
题解:
肯定是a+n=b的形式(a,b,n是四进制数),砝码数是a,b的数位和。所以就写个数位dp,从低位往高位弄。f[i][o]表示搞完i位,b是否进位最小值,g[i][o]记录对应方案数。有个小优化就是在每一位上,要么让a=0,要么让b=0,因为如果他们都大于0,让他们同时-1更优



poi2008

砖块Klo
题意:
N(<=100000)柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.
题解:
很显然,对于k个柱,把他们都调整到中位数是最优的。所以我们需要一种数据结构,兹磁加入、删除、查找第k大、求和,我用的是线段树

海报PLA
题意:
N(<=250000)个矩形,排成一排. 现在希望用尽量少的矩形海报Cover住它们.(海报是长方形的,不能贴到矩形外面)
题解:
很显然,对于那个最低的,我们至少要一张长是这个的海报,那么可以贪心一下,让这张的宽从最左到最右,然后递归处理左右,这样做出来是最优的。考虑哪些矩形需要新加入一张海报,就是那些只沿比他高的海报往左(右)走不到和他一样高的海报,那就规定从左往右扫,单调队列就行了

CLO
题意:
n(<=100000)个点,m(<=200000)条边,问能否将某些边定向使每个点1入度
题解:
1入度就是基环+外向树,对于一个联通块,能搞个环套树的条件是有至少一个环,也就是边数>=点数。并查集就好了

激光发射器SZK
题意:
多边形相邻边垂直,边长为整数,边平行坐标轴。要在多边形的点上放一些激光发射器和接收器。满足下列要求: 1发射器和接收器不能放置在同一点; 2发射器发出激光可以沿壁反射,最终到达一个接收器; 3发射器只能沿角平分线发射激光。求:最多可放置多少对发射器和接收器?点数4<=n<=100000
题解:
觉得是个几何题就膜了题解。。竟然是直接输出n/2。。看完题解觉得很对。。

账本BBB
题意:
有个长n(<=1000000)序列,每个数是1或-1,一开始给你p,每到ai,p+=ai,使最后和为q,要求中途不能出现负数。现有2种操作:1、某位取反。2、序列最后一个数移到最前面。每种操作有各自花费,问最少花费
题解:
首先要知道,1和-1个数是固定的,1尽量放前面,-1尽量放后面。
考虑答案一定是将某段后缀移到前面,然后取反一些位,我们枚举将哪里开始后缀移到前面。
枚举到一个位置时,贪心先把1和-1个数修改正确,然后找出前缀和最小的那个点,看要使他合法,需要翻转几次。这里修改1,-1数量使之正确其实不需要暴力改,直接处理这样改对最差点影响就行了。可以证明,最差的点合法后,所有点都合法。假设我们枚举到位置i,到位置j(j>i)的和就是s[j]-s[i-1],s[i-1]是固定的,最差的那个j就是s[j]最小的那个。到位置j(j< i)的和是s[n]-s[i-1]+s[j],也是一样的道理。

BLO
题意:
n(<=100000)个点,m(<=500000)条边,对每个点,问删掉他后有多少对点不连通
题解:
割点随便搞搞就好了。。

枪战Maf
题意:
有n(n<=1000000)个人,每个人手里有一把手枪。一开始所有人都选定一个人瞄准(有可能瞄准自己)。然后他们按某个顺序开枪,且任意时刻只有一个人开枪。因此,对于不同的开枪顺序,最后死的人也不同。问最多和最少死多少人
题解:
一直在想基环—内向树dp想不到只好膜题解了。。
居然是贪心orz!
先看死最多
对于一个简单环,最多n-1。对于一个环套树,最多n-叶节点数
然后死最少
简单环n/2
环套树的话,由于叶节点不会狗代,先把他们加入队列。从队列取出x,他对y开枪,少了个人指z,若此时指着z的人都狗代了,那z也入队。这个贪心正确是因为决策z是否入队时,让z入队,z的父亲节点就药丸,最多让一个可能成为答案的人狗代。z不入队,就是z不对父亲节点开枪,那z就要先狗代,这样至少让一个可能成为答案的人狗代了。环套树最后环上可能没有一个点入队,这时还要特判些什么东西,我就(bu)不(ji)说(de)了

Poc
题意:
有n(<=1000)个字符串,每个长度<=100。现有m(<=100000)个操作,交换某两个字符串的两个字符。对于每个字符串,问所有时刻中,与他完全相同的字符串最多有多少个
题解:
hash一下,写个splay,打个标记就好

KUP
题意:
有个nn(n<=2000)的矩阵,每个位置有非负数。给出k找一个子矩阵,使他的和属于[k,2k]
题解:
跪漆子超神orz
若有一个数在[k,2k],直接输出。
若没有,由于没有非负数,大于2k的数都不能取,将他们标记出来。
此时,剩下所有数小于k
考虑给你一个子矩阵,和大于2k,是否一定有解
我们按行尽量将矩阵和平分,分成x,y(x>y)。若x,y中有一个属于[k,2k]直接输出。
若没有:
1、x>y>2k 随便选x那半或y那半继续平分
2、x>2k,y< k 选x继续平分
注意到不可能出现x< k && y< k,因为x+y>2k
那这样一直分下去,变成一行就分列,由于每个数都小于k,所有不会出现和大于2k分着分着就分不动了,因此一定有解
无解的情况是什么?和最大的子矩阵和< k
那我们就找一个极大子矩阵判无解以及构造解
由于没有负数,极大子矩阵就可以用悬线法搞

Lam
题意:
对于一个长度为n(<=1000)的数列p,数列中任意两个数互质。准备一个无限长的储存器。然后从p1开始,把储存器中p1倍数位置都赋值为p1,把储存器中p2倍数位置都赋值为p2,把储存器中p3倍数位置都赋值为p3。。。把储存器中pn倍数位置都赋值为pn。最后求每个pi在储存器中出现的比例,用分数表示。
题解:
因为后面会覆盖前面,所有从后往前弄
pi被pj覆盖的位置为lcm(pi,pj),由于保证两两互质,所以就是pi * pj的倍数。(如果不保证那应该就要2^n容斥了。。
设ai为pi的答案
本着pj所有覆盖的位置中为pi倍数的数是均匀的的理念,我们推出ai=1/pi-1/pi * sigma(aj)=(1-sigma(aj))/pi (i+1<=j<=n)
然后就用一个高精度分数s存着sigma。s=p/q,上面(1-s)那一块就变成(q-p)/q,若p与q互质,那q-p与q也互质,就不用约分辣~~
然而s累加的时候要高精度约分


想了想就弃疗了。。看题解他的式子是ai=((ai+1 * (pi+1 -1))/pi
就相当于把sigma除了i+1那部分都用ai+1算掉。。这样就只用单精度约分了。。

Per
题意:
给你一个序列s,你把这个序列的所有不同排列按字典序排列后,求s的排名mod m。|s|<=300000
题解:
式子很容易推吧。。涉及除法就把m分解了一个个算最后CRT合并吧。。具体看代码吧。。

POD
题意:
给出一个具有N(<=26)个结点的无向图,将其分成两个集合S1,S2. 这两个集合的点的个数一样多,但连接它们的边最少。
题解:
C(26,13)枚举。。位运算优化。。

Sta
题意:
给出一个N(1000000)个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大
题解:
深度之和就是到他的距离之和吧。。tree dp不用说了吧。。

Tro
题意:
平面上有N个点. 求出所有以这N个点为顶点的三角形的面积和 N<=3000
题解:
规定第一个点枚举最左最下点,再按极角枚举第二个点,然后叉积算面积。注意叉积公式,可以记录一个之前的和啥的,就不用枚举第三个点了。。(不吹不黑,ljm口胡的点到直线距离也可以做,不过连我自己都不想打了233


poi2009

石子游戏Kam
题意:
有N(1000)堆石子,除了第一堆外,每堆石子个数都不少于前一堆的石子个数。两人轮流操作每次操作可以从一堆石子中移走任意多石子,但是要保证操作后仍然满足初始时的条件谁没有石子可移时输掉游戏。问先手是否必胜。
题解:
考虑某个人拿掉第i堆x个后,他后面的人可以拿掉i+1堆x个从而抵消。。
于是很像个阶梯博弈。。由于拿掉第n堆无法抵消。。就像阶梯博弈的第一级台阶一样。。于是阶梯的奇数级异或就相当于与n奇偶性相同异或。。

救火站Gas
题意:
给你一棵树n(<=100000),现在要建立一些消防站,有以下要求: 1. 消防站要建立在节点上,每个节点可能建立不只一个消防站。 2. 每个节点应该被一个消防站管理,这个消防站不一定建立在该节点上。 3. 每个消防站可以管理至多s个节点。 4. 消防站只能管理距离(两点间最短路径的边数)不超过k(<=20)的结点。请问至少要设立多少个消防站。
题解:
很妙的一道题啊。。想当年我想了两个星期(其实当天下午就想弃疗看题解,结果根本不知道题解在写什么玩意儿

← 日常训练之图论 日常训练杂题 →