almost 3 years ago

完结撒花!!


NOIP滚粗...
NOI滚粗...
WC滚粗...

今年还有ZJOI CTSC APIO.. 以及..NOI 感觉压力好大啊..

以下是滚粗狗的自我修养。


NEERC2015练习

听孙大大说NEERC的题目好,于是打算来写写NEERC的题目。不知道OI生涯还能不能抢救抢救。



  • [NEERC2015] Adjustment Office

给定一个n * n的矩阵, (i, j)位置元素的值为i + j, 有q次询问,每次给定一个行或一个列,求该行/列元素的和,并在询问之后将该行/列的所有元素变成0。

考虑行R, 如果R没有被询问过,则答案为R * (R中没被删除的元素数) + R中没被删除的列的编号和。发现删除一列C后,所有行中没被删除的元素数量减一,没被删除的列的编号和减C,这样就可以简单维护了。


  • [NEERC2015] Binary vs Decimal

定义bindecimal为一类正整数,其十进制表示是其二进制表示的后缀。 求第k小的bindecimal。

$$ 一个性质:10 ^ k 的二进制表示的末尾一定恰有k个0$$

这样就可以枚举答案的位数,从低到高一位一位添加0 / 1,维护当前二进制末尾k位都合法的数字集合,因为有上面那个性质,所以从低到高枚举的时候,当把一个数十进制第k位赋为1的时候,只会影响到这个数二进制中第k位之前的值。因此,这个数的二进制后k位就逐一确定了,就可以把所有答案从小到大枚举出来。要用高精度。

WARNING
向vector中加入结构体时,结构体内的数据并不是0,要通过构造函数来进行赋值。

BigInt(int x) { CL(a, 0); a[len = 0] = x; }

  • [NEERC2015] Cactus Jubilee

给你一棵仙人掌,求有多少种方案使得移动一条边之后的图形仍是仙人掌。

首先先求出仙人掌的桥边,如果删去的是桥边,那么仙人掌两个联通块之间任意连边均合法。如果删去的是环上的边,那么显然只能在新的仙人掌上的联通子树上加边。由于删去一条边的环会和周围的联通子树组成一个更大联通子树,因此先dfs出每个点所在的联通子树大小,再求出剖开一个环之后形成的新的联通子树的大小,利用这些联通子树的大小来更新答案即可。可以参考下图。


  • [NEERC2015] Distance on Triangulation

给你一个正n边形的三角剖分(告诉你n - 3条对角线的位置), 每条边的权为1。q组询问,每次询问两个点之间的最短路径长度。

据说是tourist出的题。
这题实现起来比较恶心。
由于给出的图是一个多边形的三角剖分,因此每条对角线都能将这个多边形分成两个部分,就可以采用分治的方法。类似树分治,先构出一个分治结构:每次在当前多边形中选出一条对角线,使得两部分点数尽可能均匀(可以证明最坏情况下存在任意一侧不少于n/3的分法),这条对角线两侧就形成了两个子多边形,递归下去,直到当前多边形为三角形为止,并且通过bfs计算出每个子多边形上每个点到选定的对角线两点的距离。询问的时候只要判断一下两个点是否在选定的对角线同侧,如果是则递归求解,否则可以通过之前预处理出的距离简单计算。

WARNING
构建分治结构的时候,要把边和点一并重建,不能只存点的信息,这样会TLE。


  • [NEERC2015] Easy Problemset

给你一堆题目和他们的难度,告诉你一套题目的生成规则,求最后的总难度。

模拟即可。


  • [NEERC2015] Froggy Ford

在一个平面上给你一些点,要求从x = 0这条线走到x = w, 使得中间经过的最长距离最短。你可以任意添加一个点,求添加完一个点之后的答案尽可能小,求一种最优的加点方案。

如果不加点,则可以通过一遍最短路,或者二分答案+BFS来求出最优解。

显而易见,最优情况下,添加的点一定落在某两个点连线的中点上, 把这些可能的点都加进去。这样得到了O(n^2)个点和O(n^2)条边,只要在跑最短路/二分+BFS的时候另加一维记录一下是否已经过添加点就可以了。

WARNING
这题卡SPFA。用最trivial的Dijkstra就可以了。


  • [NEERC2015] Generators

给定n个线性同余随机数生成器,形如:

$$x_{i+1} = \left (ax_i + b \right ) \ mod \ c$$

最大化:

$$s = \sum_{j = 1}^{n}x_{t_j}^{(j)} $$

且满足:

$$s \ mod \ k \neq 0 $$

由于这道题的c很小,只有1000,所以可以把每个随机数生成器所能生成的数算出来。对于每个随机数生成器取出它能产生的最大的数加起来,记作s。若s不能被k整除,则s就是答案,否则从某个随机数生成器中选出一个最大的元素,使得该生成器产生的最大元素减去它不是k的倍数,用其替换即可。


  • [NEERC2015] Hypercube

给你一个四维超正方体在三维超平面中的展开图,问这个展开图是否能折成一个超正方体。

四维计算几何.. 一看就懵逼了...

超正方体完全想象不出来.. 尤其是不同晶胞之间的位置关系..

一个超正方体由8个完全等价的立方体晶胞构成(可以类比立方体中6个面)。
首先任意选定一个晶胞放到超正方体的一个位置,然后开始dfs,根据每一步走的方向(上/下/左/右/前/后)将当前晶胞在超正方体上朝对应的方向翻转90度,就得到其在展开图上相邻晶胞在超正方体上的位置了, 然后判断这个位置是否已经被占领,若已被占领则返回无解,否则将这个晶胞放进这个位置然后继续dfs下去直到返回无解或者遍历完了整个展开图。

这个翻转比较抽象.. 可以类比立方体上每个面和相邻面之间的位置关系。具体操作就是,给每个晶胞规定三个维度上的向量(x, y, z)和一个第四维上的法向量,翻转的时候进行向量变换就可以了。具体可以参考下图。


  • [NEERC 2015] Iceberg Orders

根据题目给出的证券交易市场的冰山指令规则,给你一堆买入和卖出请求,模拟整个交易过程。

比较繁琐,先挖个坑


过年玩了两天..继续开更..


  • [NEERC 2015] Jump

一道挺有趣的交互题。
交互库会生成一个长度为n(n为偶数),的01串, 让你猜这个01串是什么。
每次可以询问交互库一个长度为n的01串与原串之间相同的位数是多少。
如果相同的位数是n或n / 2, 则返回这个数,否则返回0。
其中n不超过1000,询问的次数不能超过1500。

嗯..好像可以先随便猜一个n / 2位相同的串出来..
期望次数大约是40.. 非常小的样子.. 那么就先猜一个出来
现在我们想知道每一位具体的值。 似乎将每一位单独取反之后.. 答案要么+1要么-1.. 返回值都是0
这样就没有办法判断了
把每位与第一位同时取反,然后做一次询问,这样就能得到每一位和第一位之间的关系了,这一步要进行n - 1次询问
然后枚举第一位是0还是1.. 根据之前得到的每位与第一位之间的关系,就能得出每一位的值。
对这两种情况分别做一次询问就好了。


  • [NEERC 2015] King

给你一张有向图,求哈密顿回路。其中边数与点数的差不超过20。

因为边数最多只比点数大20.. 首先把入度和出度都为1的点连成一条链, 然后给它们缩起来。
这样最多剩下20条链,压一下状态,dfs之。
在连链和dfs的过程中要注意细节。

WARNING
dfs回溯的时候.. 要把所有修改的信息都给还原了

int kk = ans[x];
ans[x] = v;
if (dfs(id[v], ss)) return true;
ans[x] = kk;

如果ans[x]没还原成kk就会炸。


  • [NEERC 2015] Landscape Improved

有w行石子,每一行石子的高度告诉你,再给你n个石子,让你把这些石子往上面放,问石子最高能堆多高。
每个放上去的石子要满足其下、左下、右下都已经有石子了。

发现最终放上去石子的形状肯定是一个金字塔形。
二分答案,枚举最高点位置。这个金字塔的左右边界可以用单调队列预处理出来。
知道左右端点之后就可以计算出需要的石子数量了。
总的复杂度为O(wlogn)
更具体的可以参考下图:

← ZJOI2015的那些事 滚粗狗的自我修养之NEERC2014练习 →
 
comments powered by Disqus