NOIP2018集训日志

[mathjax]

10-14

30分钟看完题,感觉今天的题稍微简单一些

T1貌似是直接找一条最长的没有旁支的链,然后所有边长×2-链长,30分钟水完了

T2字符串哈希搞一搞(用的map,把两个字符串中间用特殊字符隔开直接扔到map里面维护),又是30分钟

T3……字符串很简单,关键是方案数?不看了不看了,神仙题(
感觉是一个类似于dp/记搜的东西,又30分钟写完了,一发过了大样例

接下来搞搞T2

今天暴力得分大概160?期望得分200左右

???AK了?第二题没开O2用map也可以过?……这次题太水啦

10-15

知识:二分答案 图的遍历 单调队列 DP

T1

实数二分答案,check时维护一个并查集,将所有之间距离大于二倍val的教徒合并,同时将靠墙距离大于val的教徒和墙合并

然后判断如果上面的墙和左边的墙在一个集合里则无法从左下角到达右下角

T2

看一眼可以知道,这张图是一个树套环,所以有自环和重边的图是一颗树,跑树的直径即可(送了十分)

对于图中唯一的环,我们可以求出环上每一个点的最长链作为权值,问题即转变为:一个环,环上点有权值,边有权值,求一个区间中两端点和所有边的权值总和的最大值

倍长这个环变成链,边权前缀和一下,就可以得到每一个区间的权值总和如下:(\(pre\)为边权前缀和,\(a\)为点权)$$pre[r]+a[r]-(pre[l-1]-a[l])$$

用单调队列维护一下就可以\(O(n)\)求出来了,注意限制队列中首尾元素的距离在\(n\)以内

T3

首先你需要看出,在没有传送枪的时候,你每一条边都至少需要走两遍

观察传送枪的使用方式,易得以下结论:

  • 每一个点至多到一次
  • 传送枪不可能向下用(已经下去过了为什么还要下去)
  • 传送枪不可能横着用(同理)
  • 只有两个传送门——相当于你只能在一个到过的地方放下传送门,之后你可以在任何地方(一般只有他的下面有意义)不耗时地传送到这个门的地方

所以,传送枪只能向上传送;如果祖先节点放过了传送门,接下来的节点都不能放下传送门

想清楚了之后,考虑现在你到了\(p\)节点,之前在祖先都没有放下过传送门,有两种方案

  • 在这里放下传送门,接下来在所有的子树中,你都可以选一条最长的链,在它的最下面传送上来,进而省掉一个这条链的长度(\(O(\log^2 n)\)求出)
  • 在这里不放下传送门,接下来在所有的子树中递归计算这个相同的东西(\(O(n)\)求出)

然后就做完了,总体复杂度\(O(n \log^2 n)\)

10-16

知识:DP 树链剖分 广义圆方树

T1

首先明确题意,从一号节点出发,一号节点会耗时;经过a个木桩耗时v捆绑在一起(即只能走a的整数倍);切换轻功时当前节点是否可以用这个轻功都可以,数据中没有体现

然后就是一个类似于完全背包的东西了,维护条件时要判断一个区间中有没有1的存在,前缀和一下就好啦

时间复杂度\(O(nk^2)\),似乎有个\(O(nk)\)的神仙算法,利用了前缀和之类的东西

T2

首先,这道题\(O(qk\log^2 n)\)是可以过的

出题人:树剖后把点按dfn排序,相邻两个点(包括第一个和最后一个)路径点权求和,所有的和加起来除以二就是答案

我:树剖后把点按dfn排序,相邻两个点(包括第一个和最后一个)路径上打标记,最后所有打标记的点权值求和就是答案

T3

树形的40分:树剖

没有修改的20分:参见NOIP2009 最优贸易

剩下的:毒瘤广义圆方树(未完)

10-17

NormalGod讲课

T1

枚举一个数列的收益,对另一个数列二分最少选多少个数使得和大于收益,反过来再做一次

或者:两个数列排序后从大到小维护两个前缀和,每次在小的那一个和里加上下一个数,过程中维护最大值

T2

考虑已经会了\(O(n\log n)\)的01序列排序

所以参考快排的思想,取出一个数,把小于它的数视为0,大于的视为1,排序后分治递归一下,\(O(n\log^2 n)\)

接下来想01序列怎么做:考虑分治(归并)

当前有一个两段分别排序的01序列,考虑只要把划线的那一段翻转一下即可:$$000000000000000\underline{\overline{1111111111111111100000000000000}}111111111111111$$交换复杂度\(O(n\log n)\)

T3

考虑dp,状态为每一个联通块的大小,打表发现状态数只有40000左右(未完)

T4

字符串哈希,构造一种正着和反着都可以算的哈希,从字符串两侧往中间推,遇到一样的就贪心切掉

T5

操作1使得每一个字母排序后相同的串本质相同,所以可以用\(\text{ABCD}\)的数量确定一种字符串

所以有\(f[i][j][k]\)代表每一个\(\text{ABC}\)各有\(ijk\)个的串的排列有多少种

用\(m\)个魔法在这个图上连边,问题转化为在一张图上从一个固定的起始点走一个最长路径,缩点+拓扑排序更新即可

T6

(断线重连中)

T9

考虑一个只有正数的数列,你先选一个最大的,接下来要选第二个,你有两种方法

  • 在边上一个没有干扰的地方另选一个
  • 不选这个了,转而选它边上的两个

明显其他方案都没有这个收益大,对于第二个,我们可以把这三个数缩为一个,这个数对它两侧的影响仍然有效,用一个堆维护一下

T10

将每一个位置视为一个变量\(a_i\),有它周围九个量的异或为这个值,使它为零可以得到\(n\times m\)个式子,直接高斯消元复杂度\(O(n^3 m^3)\),我们需要优化

(掉线啦)发现所有其他的格子都可以用第一行和第一列的数表示(但是最后一行和最后一列不可以),所以直接解最后一行和最后一列的方程组即可(\(O(n^3)\))

以上是上午讲课内容,以下为下午的

T11

考虑计算在没有重复元素时的方案数,然后减去重复的内容,有答案等于$$C^{k}_{n}-C^{k-2}_{m}$$其中\(m\)为两个相同元素两侧的元素个数之和

T13

考虑产生收益的编号序列,有一段连续的编号\([l, r]\),当链接每一个点的总点数大于\(k\)时终止,把\(l\)加一,取答案,再把\(r\)加一,继续操作

统计点数时的操作参考前一天的T2“开荒”一题的做法,求和除以二 / 打标记

10-19

知识:巧妙问题转化 欧拉回路 树链剖分 KMP

T1

题目相当于一开始手里抓着整个序列 a 的异或,一次操作可以将手上的数与序列中的某个数换过来

所以,在理想序列中如果出现了在上面序列和上面的异或和中没有的数则无解

然后,考虑离散化初始序列和异或和,把上下序列的对应两项之间连一条边,这条边代表把对应的位置的数交换为理想数列的数,可以证明每个联通块都有欧拉回路

答案即为所有联通块个数加上他们的大小,注意如果初始序列异或和如果单独为一个联通块则也需要考虑

T2

树剖,然后将密道从小到大排序,每次标记密道两段路径上未被标记的边的答案为当前密道长度

T3

先KMP出来所有目标串位置(待完成+T2)

10-23

知识:组合数 DP 分块

T1

k只有20,观察杨辉三角的前20列,发现操作本质即为在一段区间上加上杨辉三角的某一列的一段;往左边看,发现左边(即k-1阶差分数组)全是1

所以维护一个k阶差分数组,每次修改时给k阶的数组加上一个1,然后给接下来的k-1阶最后减去一个数使其变成0

最后累加即可,复杂度\(O(nk)\)

T2

考虑一张有n个节点的图,总共有\(2^{\frac{n(n-1)}{2}}\)种方案,为了好看,设它为\(A_{n}\)

设f[i]为大小为i的连通图的方案数,这个不太好求,于是再设一个g[i]为大小为i的不联通图的大小,有$$g[i]=\sum^{j<i}_{j=1}C^j_n\times A_{n-j}\times f[j]$$$$f[i]+g[i]=A_i$$意思即为选一个1号节点和其他j-1个节点组成一个联通块,剩下的n-j个点之间随便连边

设\(dp[i][j]\)为选了i个点,最大联通块大小为j的方案数,有……,复杂度\(O(n^3)\),得到了五十分

再设\(dp[i]\)表示最大联通块小于等于i时的方案数有$$dp[i]=\sum^{j\leq k}_{j}dp[i-j]\times f[j]\times\text{C}^{j-1}_{i-1}$$求出\(dp[k]-dp[k-1]\)即是答案,时间复杂度\(O(n^2)\)

T3

大力分块即可

10-25

知识:DP 最小生成树/Kruskal重构树 树状数组/主席树 单源最短路

T1

首先枚举结束状态的颜色

然后观察题解发现,一个瓶子要么直接被染成目标颜色,要么先被染成一个较小的数然后再染成目标颜色

于是设f为前i个瓶子染成目标颜色的最小代价,每次转移选择接下来的一个区间,先把他们染成这个区间中数值最小的颜色,再染成目标颜色,相似地设一个g数组倒着做一遍

最后答案即为找任意一个目标颜色的瓶子,他的左边的f加上他右边的g,然后取最小

T2

先建出最小生成树/Kruskal重构树,然后对于每一条边,枚举子树大小较小的那个中的节点,计算另一个子树中能够和他产生贡献的节点个数,主席树/离线树状数组统计一下

T3

建图跑堆优化Dijkstra,将模L意义下相同并互相可达的点缩成一个,同时只有包含起点或终点或某条线段的端点的点在途中是有意义的,所以只保留这些点

然后通过某种记载在看不懂的代码中的神奇的魔法可以把边数优化成\(O(n)\),然后就可以过了

10-26

知识:期望 最短路 \(\text{bitset}\)模拟 主席树 常数优化

T1

设\(i\)个不同的数的期望交换次数为\(f[i]\),有两种可能性

  • 第一个数碰巧在他应该在的第一个位置,剩下的期望交换个数即为\(f[i-1]\),概率为\(\frac{1}{i}\)
  • 第一个数不在他的位置,交换一下把他放到第一个位置,期望交换个数为\(f[i-1]+1\),概率为\(\frac{i-1}{i}\)
    $$f[i]=\frac{f[i-1]}{i}+\frac{(i-1)(f[i-1]+1)}{i}$$

递推即可,注意常数优化

T2

\(O(n^2)\)预处理出离每一个点的距离小于\(i\)的点集,用\(\text{bitset}\)存下,每次询问直接\(\text{or}\)到一起然后\(\text{count}\)即可得到\(60\)分

然后手写一个\(\text{bitset}\)常数优化一下即可得到\(100\)分

T3

倒过来主席树维护即可,注意卡\(256\text{M}\)空间

10-29

知识点:区间DP,以及打暴力的自信

T1

T2

T3

发表评论

电子邮件地址不会被公开。 必填项已用*标注