IanChen的博客

摘要： 良效冷却剂。 T1正常开，正常写，正常做，30分钟过大洋里就丢了。 T2初现端倪，看错题然后30分钟虚空做题，写完代码后发现题面完全不一样。。 之后迅速蒙了一个1e8的做法过大样例。 T3开始发现很熟悉觉得可做，于是先做T4， 脑子比较混乱，没有把dp理清楚，只能打完指数暴力回T3， T3，想了20 阅读全文

摘要： P4637 [SHOI2011] 扫雷机器人 题 AL 军工厂生产的扫雷机器人的排雷方法只有一种，那就是安全引爆。每次，机器人在所有探测到的地雷中选择一颗引爆。被引爆的地雷会接连引爆不超过他的爆炸威力范围的其它地雷，这些被间接引爆的地雷还能引起进一步的连锁爆炸。例如图中，用一个圆的半径表示地雷的爆炸 阅读全文

摘要： 用于多个数构成的集合，取任意个异或起来，的相关问题。 实际上，线性基可以视作一个集合，使得原集所有可以得到的数都可以由新集异或得到，且新集所有异或得到的数都可以由原集异或得到，以及满足新集所有数二进制最高位不同。 具体构造过程如下：假如现在插入一数x。 从最高位向最低位枚举，若x在该位为0则跳过。 阅读全文

摘要： 点双联通分量： 对一张图，若其不含割点，则其为一个点双。 1，对于点双中的两个点（除只有两点一边的特殊图），可以视作其必然存在两条不同的简单路径，使两者经过的并集为空。 2，对于点双中任意一对点，经过它们的简单路径的并集一定为点双本身，意即可以认为两点间简单路径可以通过点双内任意一点。 圆方树： 圆 阅读全文

摘要： 用途： 用于二维坐标系维护多条线段。 算法： 本质上是采用标记永久化， 对每个线段树节点维护一个标记表示该区间存在这一条线段， 查询时从上到下经过节点的标记即为该横坐标上可能经过的线段。 下面需在标记（线段）间的比较上作考虑：建议画图理解 此时对于一个区间\([l, r]\)， 找出中点\(mid\ 阅读全文

摘要： 概念 hash，也称散列，可以理解为一种思想：将复杂数据转换为一个标志，映射入简单值域中，用来方便存储与查询。 其实就像离散化可以将数字与其的大小顺序一一对应那样，不过离散化是提前预处理，先把所有目标数据获取后才能离散。 hash大多时候是使用散列函数直接计算，比如取模，这样可以保证同样的数据对应同 阅读全文

摘要： 首先，注意到方案数只与3种步数有关，与在哪出发哪结束无关，于是考虑如何求出\(sol(n,m,w)\)。 三种走法可以相互独立，最后的答案只与他们的步数有关，所以需要一个\(f[i][j]\)表示用\(j\)步走到\(i\)的方案数，简单DP可以求出，复杂度为\(O(n^2k)\)，其中k为质数个数 阅读全文

摘要： 看到距离有关可以联想到跟深度有关系，可以用深度表示距离关系。 假设现在有一操作1 v x k,那么对于v下一点u，设dep[v]为v的深度，那么两点间距离就是dep[u]-dep[v],于是u点就会增加\(x-k*(dep[u]-dep[v])=x-k*dep[u]+k*dep[v]\)。 由此来看 阅读全文

摘要： 题目的等差子序列最少只要求长度为3，那么其实就转化为对于一个数是否存在左右各一个与它差值相等的一对数，比如1 4 3 2 5中1，5对3来说就如此。 这样的关系放到数轴上就是是否存在一对数到某数的距离相等。 由于题目明确是一个排列，也就是1到n所有数一定会出现一次，那么对于某数，它左边的数没有出现的 阅读全文

摘要： n,m较小，同时又是区间问题，可以考虑区间dp。 设定\(f[i][j]\)为只在i ~ j 范围内操作的最大贡献，为了将操作表示出来可以设g[k][i][j]为在i ~ j 内操作一次的包括k点最大贡献。 通过这些可以推出： \(f[i][j]=max_{k=i}^jf[i][k-1]+f[k+1 阅读全文