【火题合集】3.25-4.1考试

一周没写题解了。。

因为题目都太鬼了。。都不会做

发一下这一周做出来的题吧。。(一周才做出来几道题)

3.25

没A一道题

T1强行写了个主席树加了个log。。然后后来改时限卡掉了40分。。

3.26-3.27

ZZD太神辣 还是没A一道题

好像D2T1能做 然而没做了

3.29

终于有会做的题了

Description

在farmer land上,有N个farmer town,以及M条无向道路,每条道路有一定的长度。有些城镇属于Cab,而有些城镇属于Cob。由于Cob太农,Cab需要找到两个属于自己的城镇,以供紧急避农之用。当然为了节省体力,Cab想知道两个城镇的最短距离为多少。
若存在多组答案,输出任意一组(顺序不作要求)。
若无解,输出“o gi”,不包含引号。

Input

第一行为N, M。
第二行为N个整数,0代表该城镇属于Cob,1代表属于Cab。
接下来M行,每行u,v,w描述一条道路。

Output

第一行一个整数,为最短距离。
第二行两个整数,代表方案。

Data Range

\(𝑁≤10^5,𝑀≤2\times 10^5,0<𝑤≤10^9\)

Solution

大家都写的Dij然而我写的SPFA 感谢Cab没有卡我

每个点记录到该点最近的和第二近的Cab城镇。。就完了

然而还强行开小了数组TAT

代码基本上都是if了。。

T2好像能做 不管了

另外吐槽:T3我和ZZD一起看的,最后ZZD看了题解说会了,然而这次还是没做出来(虽然我在考试的时候对着题解都写不出来)

3.30

T1听说是高斯消元

T2听说是K-D树

T3比较简单然而因为看凌续寇看韩剧去了都没做

T3真™简单送分

Description

Cab最近遇到了一件棘手的任务——物理实验报告,明天就是deadline,而他还没动笔。Cab决定尽快伪造一份实验报告。当然,他希望取得尽可能高的分数。取得高分的关键如下:

  1. 有一定数量的测量数据。
  2. Cab已经知道期望的准确测量值是多少,实验报告中所有“测量数据”的平均值应恰好等于准确值。
  3. 为了不遭到老师的怀疑,测量数据必须显得有足够的随机性。形式化地说,测量数据的方差必须足够大。

Cab知道你是这方面的能手,所以这个任务就交给你了。

给定𝑤,𝑣,试构造一组合法方案(𝑛,{𝐴1,𝐴2,…,𝐴𝑛}),满足如下条件:

  1. \(10≤𝑛≤1000,|𝐴𝑖|≤10^9\)
  2. 𝐴𝑣𝑒𝑟𝑎𝑔𝑒{𝐴𝑛}=𝑤
  3. 对于测试点1,要求𝑉𝑎𝑟𝑖𝑎𝑛𝑐𝑒{𝐴𝑛}≥𝑣;对于测试点2~5,要求𝑉𝑎𝑟𝑖𝑎𝑛𝑐𝑒{𝐴𝑛}=𝑣。

其中𝐴𝑣𝑒𝑟𝑎𝑔𝑒代表平均数,𝑉𝑎𝑟𝑖𝑎𝑛𝑐𝑒代表方差。

Input

第一行为T,表示数据组数。
接下来T行,每行两个整数w,v,描述一组数据。

Output

每组数据两行:第一行输出N;第二行N个整数,描述方案。

Solution

显然只要找几个数对w方差为v然后关于w对称取数就可以了

假设n=1000,那么对于前500个数,第一次令\(k=500v\),那么第一个数为\(\lfloor\sqrt {500v}\rfloor\),然后将\(k\)变为\(500v-\lfloor\sqrt {500v}\rfloor^2\),不断这样操作就能保证所有数的方差为v。

代码就不写了= =

3.31

今天全是数学题

本来看到T2好高兴 线段树splay分块都随便做

打完才发现1操作有点鬼畜 没法求和

然后就o gi

所以还是没A一道

3.31晚

第一题以为是水题排个序连续选k个

然后就开了然后就被向总抓堕了

然而这样不对。。不过居然骗到了40分 直接虐场 爽

没A一道题

4.1

今天T1好眼熟啊

题目描述

ZLR非常喜欢玩玩具,尤其是在自己的玩具世界里当国王(。。。)。
有一天他心血来潮,用3*n-2根有重量的火柴棍将2*n个点连成了一个2*n的王国,并自名为“国王”,既然是国王,那肯定要对他的王国发号施令,不然怎么叫国王呢?ZLR想了想,他决定每次发出以下的命令之一:

  1. 换掉相邻两点之间的火柴棍,形如C x y u v w,其中w表示新火柴棍的重量。
  2. 设第l列到第r列(包括左右两端)的子图为G,求G的最小生成树中火柴棍的重量和,形如Q l r。
  3. 添加一根斜着的火柴棍,形如I x y u v w,其中w表示新火柴棍的重量。

ZLR是个天才少年,他才不屑做这种水题,请你来帮他解决吧。

输入格式

第一行两个整数n m,表示王国的列数和操作个数。
第二行n-1个数表示王国的第一行火柴棍的重量。
第三行n-1个数表示王国的第二行火柴棍的重量。
第四行n个数表示王国每一列火柴棍的重量。
接下来m行每行一个操作。

输出格式

对于每个操作2输出一行表示最小生成树中火柴棍的重量和。

数据范围

n,m≤200000,边权≤10000,操作编号c≤2。

题解

王队太鬼了

这题不看数据范围【c≤2】想死也不会做

和traffic差不多 还简单一些

每一块按左边两个点和右边两个点的联通性分四种情况,更新即可

王队、R等:这道题update绝对要写十几行

然而我四行就写完了 状态和R的一样 也不知道他们是怎么写的= =

说点什么

  Subscribe  
提醒