首页 > 其他分享 >NZOJ 模拟赛5

NZOJ 模拟赛5

时间:2024-10-07 23:43:48浏览次数:7  
标签:圆柱 dist 房间 道具 正方形 NZOJ 遗迹 模拟

T1 逃离遗迹

根据外星人的回信,在遗迹中有分布着三样道具。当三样道具都拿走后,遗迹就很快自动毁灭,所以必须要在最短时间内离开。遗迹可以看作是由N个房间(编号1..N)和N-1条长度不等通道所组成,并且任意两个房间之间有且只有一条路可以相互到达。现在我们的队员已经在编号为A,B,C的房间内拿到道具,并且准备撤退。由于只有一架直升机,所以只能在一个房间上停留。现在请你决定将直升机停在哪一个房间之上,能够使三人到达该房间的距离之和最短。

考虑最短路模型,对 $A, ~ B, ~ C$ 三个点分别作为源点跑一次最短路,扫一遍所有的点,找到 $dist[A] + dist[B] + dist[C]$ 最小的点即可。

T2 遗址

很久很久以前有一座寺庙,从上往下看寺庙的形状正好是一个正方形,在4个角上竖立着圆柱搭建而成。现在圆柱都倒塌了,只在地上留下圆形的痕迹,可是现在地上有很多这样的痕迹,专家说一定是最大的那个。
写一个程序,给出圆柱的坐标,找出由4个圆柱构成的最大的正方形,因为这就是寺庙的位置,要求计算出最大的面积。注意正方形的边不一定平行于坐标轴。
例如下图有10根柱子,其中(4,2),(5,2),(5,3),(4,3)可以形成一个正方形,(1,1),(4,0),(5,3),(2,4)也可以,后者是其中最大的,面积为10。
$![test]http://182.43.200.0:6548/upload/182.43.200.0:6548/image/20240911/20240911222325_14494.jpg$

标签:圆柱,dist,房间,道具,正方形,NZOJ,遗迹,模拟
From: https://www.cnblogs.com/YipChipqwq/p/18450848

相关文章

  • 2024 10.5&10.6 模拟赛总结
    202410.5&10.6模拟赛总结一句话总结:打的稀烂。10.6\(T1\)没什么好说的。\(T2\)是我不喜欢的类型。首先看到前\(K\)大马上就想到了二分和堆,但是想了半天也不知道堆怎么由一种状态推广到多种状态,并且要不重不漏、效率高,二分也没想出来怎么\(check\)。赛后听了评讲才发现堆......
  • [41] (CSP 集训) CSP-S 模拟 9
    A.邻面合并观察到\(m\)很小,支持我们\(mn2^{2m}\)状压枚举二进制状态,\(f_{i,j,k}\)表示到第\(i\)位的状态为\(j\),上一位状态为\(j\)(\(i,j\)为状压位)的方案数考虑转移的时候加了什么判断这一行与上一行的联通情况,如果这一行的某一个连通块和上一行正好对上了,......
  • 多校A层冲刺NOIP2024模拟赛03
    A.五彩斑斓没办法,不会统计四个点相同的,赛时没想到,写了一个神秘算法骗了80考虑倒着计算,总子矩阵有\(\frac{n(n+1)*m(m+1)}{4}\)个,减去四个角相同的矩阵数量就是答案,枚举矩阵的上下边界两条线再枚举每一列,会有两个交点,统计每种颜色的上下交点颜色一样的个数,就可以计算了点击......
  • 代码源Csp-S模拟赛Day10-11赛后总结
    代码源Csp-S模拟赛Day10-11赛后总结Day10赛时T1赛时感觉很难维护时间以及多个精灵同时到达同一格子的情况,后来想了一种做法:对于每个格子最早被遍历到的时间我们的处理是容易的,你考虑我们可以对每行每列都建一棵线段树(数据范围保证了\(rc\leq5e5\),所以总空间大致是一个\(4rc......
  • 2024/10/07 模拟赛总结
    \(20+55+25+0=100\),压线拿到小饼干!#A.A可以发现\(u_i=A,v_i=B,w_i=C\)至少有一个成立,将这些点抽象到三位空间中。则原长方体一定被一个从\((1,1,1)\)出发的长方体打穿,但是似乎重叠部分比较难实现对于从底打到顶的长方体,可以用后缀\(\max\)解决,然后原长方体就变成了阶梯......
  • CSP2024 前集训:csp-s模拟9
    前言T1状压挂了\(10pts\),貌似做法是假的,但是一下午也没调出来哪儿假了,但是错误率很低,几百组能有一组错的。T2赛时数据锅了赛后重测了,赛时想到线段树但是没能具体实现,最后无奈写暴力。T3、T4没看。T1邻面合并\(m\le8\)所以考虑状压表示每一行哪些地方被覆盖,对与相邻两......
  • [42] (多校联训) A层冲刺NOIP2024模拟赛03
    今天的乐子今天的乐子2昨天晚上做梦梦见自己被关进戒网瘾学校里面的老师全和疯子一样然后我和这帮疯子老师比疯疯子老师发现他们没我疯所以就把我放了今天的乐子3lhx罗曼蒂克的辟谷A.五彩斑斓赛时的想法\(n^4\)的做法,设\(f_{i,j,k,l}\)表示以\((i,j)......
  • 多校A层冲刺NOIP2024模拟赛03 -- T4 量子隧穿问题
    多校A层冲刺NOIP2024模拟赛03--T4量子隧穿问题$$HZOI$$感觉是这两天最有意义的题吧。\(n\)句话题意我是巴甫洛夫的狗,我又重生了,重生在薛定谔的家里。薛定谔是抖S,于是给我铃声。我开始狂跑不止。为什么没流口水没删除我给定\(n\)个点,对于\(i\)存在一条外向连的单向......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛03
    Rank炸了,触底反弹A.五彩斑斓(colorful)签,又没签上。考虑如何一步步优化暴力。最暴力的思想\(\mathcal{O(n^4)}\)枚举每个矩形,判断四个顶点颜色。稍微优化些,两次\(\mathcal{O(n^2)}\)跑出对于行/列每个点下一个与之颜色相同的坐标,利用容斥全部减去不合法的方案数,然后再枚......
  • CSP2024 前集训:多校A层冲刺NOIP2024模拟赛03
    前言T1没想到正难则反,脑瘫了没敢用bitset(复杂度擦边但卡常能过),T2空间开大了挂了\(100pts\),\(T3\)是原。T1五彩斑斓部分分\(20pts\):\(O(n^4)\)暴力。部分分\(20+?pts\):进行一些优化,极限数据下仍是\(O(n^4)\)。部分分\(60\sim100pts\):bitset优化一下,\(O(\f......