2 Richard_for_OI

尚未进行身份认证

不忘初心,不负韶华。选择了这条路,就不要再回头了。

等级
TA的排名 6w+

「NewCoder1C」保护

Problemnnn个点的树,以1为根,给mmm条路径。 每次询问给vvv、kkk,求一个在满足u-v这条路径至少被kkk条前面给出的路径完全包含的条件下距离根最近的那个点uuu。(输出u−vu−vu-v的距离)Solution由于查询路径只会是直上直下的,所以我们把每条路径拆成两段直上直下的。对于一条路径u−vu−vu-v(dep[u]≤dep[v]dep[u]≤dep[v...

2018-09-12 09:08:42

[Apio2012] Guard

Solution有一些个位置一定是不能存在忍者的。于是我们把这些位置拿走,给所有的数据重标号。 做法:开一个长度为 nnn 的数组,对于一定是 000 的一段我们全赋为 111 。最终我们把为 111 的扔掉即可。可以用差分///线段树维护。若重标号后, n=kn=kn=k,那么所有草丛都必须有忍者。特判掉。 而若一个区间 AAA 完全包含另一个 BBB ( AAA 是大的 ),那么...

2018-09-10 15:33:33

[BZOJ4771] 七彩树

Problemn个节点的有根数,每个节点拥有一个颜色。边权为1。 现在有m个查询,每个问题有两个整数x和d,表示询问x的字数中depthdepthdepth不超过dep[x]+ddep[x]+ddep[x] + d的所有点中出现来多少种本质不同的颜色。Solution每个点的贡献都是111,那么若有颜色相同的点对(i,j)(i,j)(i,j),那么lca(i,j)lca(i,j)lc...

2018-07-23 17:02:32

[NOI2018]网上同步赛游记

Day1T1一看这个东西有好多暴力分呀,打一下吧。然后就写了树和链的。和zg大佬聊了一下,他说他只写了离线的,然后我就一直在想这个离线的做法,就连通块呗。但是跟暴力分也差不多,就算了吧。 然后最终只有50pts50pts50pts。 原因是:spfaspfaspfa这个东西,它已经死了。(原话是:你为什么要写一个平方级的算法呢?) 正解是kruskalkruskalkruskal重构...

2018-07-20 20:03:12

逆元与组合数

线性逆元打表inv[i]inv[i]inv[i]为模PPP(P需要是质数)意义下iii的逆元,那么有inv[i]=(P−Pi)×inv[Pinv[i]=(P−Pi)×inv[Pinv[i]=(P-\frac{P}{i})×inv[P%i]i]i]%PPP。 写成代码如下。ll inv[N];inv[0] = 1; inv[1] = 1;for(int i = 2; i < N;...

2018-07-15 20:47:47

[TJOI2017]不勤劳的图书管理员

Solution1分块+块内树状数组。可以踩掉标算,甚至碾压。#include <cstdio>#include <cstring>#include <cmath>#define rint register int#define N 50010#include <algorithm>typedef long long ll;...

2018-07-13 18:03:20

【NOIP2017】day1 t2 时间复杂度

complexityNOIP2017我认为最毒瘤的题。没有之一。码农题,从去年难为我到现在。给出一些tips。①要先读入进来,再判断语法错误!!!②在存循环类型时候,’F’用1表示,’E’用-1表示,这样你可以省不少力气。③程序运行不到的地方,出现语法错误也是会报错的。特别注意变量的问题,都要判断进去。④存n这个量的时候,用一个较大的数(比如1333...

2018-07-12 17:21:45

左偏树

左偏树是一种稳定O(logN)的可并堆算法。 为了做到这个复杂度,我们要保证这么两个事情。以小根堆为例。 1、lson(x)与rson(x)均小于等于x。(just like heap) 2、我们定义一个点的dist(x) = dist(rson(x)) + 1。那么性质就是:必有dist(lson(x)) ≥ dist(rson(x))。(不满足的话我们可以swap,这倒不是问题) ...

2018-06-27 21:39:55

字符串系列(六)——回文自动机

想不到吧我还在更新哈哈哈哈哈。 今天带来一个2014年发明的算法——回文自动机。 既然写了这篇博客,那我就说得全面一些。回文自动机这个算法也称回文树。 可以类比一些其他的自动机,回文自动机也是有许多节点、许多next、许多fail的。1、节点的那些事每个节点都表示一个回文子串(注意了啊,只表示一个,SAM才是一类),且任意两个节点所表示的串必定不全等。(可以用数归证明...

2018-06-15 17:48:36

bzoj2555: SubString 后缀自动机+LCT

2555: SubStringTime Limit: 30 Sec  Memory Limit: 512 MBSubmit: 4189  Solved: 1284[Submit][Status][Discuss]Description懒得写背景了,给你一个字符串init,要求你支持两个操作(1):在当前字符串的后面插入一个字符串(2):询问字符串s在当前字符串中出现了几次?(作为连续子串)你必须在...

2018-06-14 13:14:00

[NOIP2017 d2t3] 逛公园

Problem给一张有向图(无重边、自环,如果有的话应该会麻烦许多吧)。求从1~n有多少种走的方案?其中每一种方案中,走的距离均不超过最短路+K。多组测试数据 + 此题数据范围 = NOIP2017卡常神题。Solution提供一种优美的做法——记忆化搜索。 建一个正图、一个反图。跑一次反向最短路(常用技巧)。 f[u][k]表示dis(u, n) ≤ MinDis(u, ...

2018-06-11 22:33:12

Luogu P3676 小清新数据结构题

Problem一棵有点权树,每个节点都有一个s表示其子树权值和。支持点权修改,以及查询x为根时,所有节点s的平方和。Solution(一)考虑没有换根,即对于所有查询均有x=1 点修改u的权值,设增量为a。根据树的性质,只有path(1, u)上的点的s会被更改。 考虑这次修改对答案的贡献。 ⇒∑i∈path(1,u)(si+a)2−∑i∈path(1,u)s2i⇒∑i∈pa...

2018-06-11 09:52:12

伪Top-Tree——[Bjoi2014]大融合(bzoj4530)

朴素的LCT是不维护虚边以及轻儿子的。但是这道题需要动态维护这么一个子树大小,就可以考虑维护一下虚边。一个节点x,维护两个:虚儿子的子树大小之和,以及整棵子树大小。然后这题就结束了。注意long long。这辈子都不可能写真正的top-tree的。只能写写伪top-tree这样来维持一下生计。#include <cstdio>#include <algorithm>#d...

2018-06-10 23:16:03

LuoguP1501 [国家集训队]Tree II

这题细节巨多!!!!!!当同时维护乘法、加法标记时,根据运算先后,要先下放乘法标记。给一个节点×v:本节点、子树和、乘法标记、加法标记均要×v。然而改完之后还是只有5分。56061...

2018-06-07 21:44:19

Link-Cut-Tree

What is Link-Cut-Tree?动态树(Link-Cut-Tree),也称LCT,是一种可以维护一个有根树森林改变形态、合并、分离、查询等操作的数据结构。由Robert Tarjan(他可以说是算法大师了,前面的文章中我是提过他的)为首的团队提出。在学习动态树前,要先明白splay的原理。在下面的一段中,会详细介绍splay的rotate与splay两个操作,请大家暂时忘掉有根树森林之...

2018-06-07 14:53:34

谈虚树dp——bzoj2286与bzoj3572

Problem1一棵n个节点的有边权树,m次询问,每次问k个点。要求删除边权总和最小,使得这k个点均不与1连通。朴素Treedp考虑一个dp,dp[i]表示i这棵子树中,所有关键点均不与i连通的最小代价。有转移方程:(j是i的直系儿子)(1)j如果是关键点:f[i] = min(f[i], val[edge(i<=>j)])(2)otherwise,f[i] = min(f[i], f...

2018-06-03 22:40:15

bzoj2456 mode

此题的“众数”出现次数一定是超过一半的。因此考虑用不同的两个数去互相抵消,最后剩下谁,那它就是答案。代码很短(来自黄学长):#include<cstdio>int n,t,x,tot;int main() {    scanf("%d",&n);    for(int i=1;i<=n;i++) {        scanf("%d",&x); if(...

2018-05-28 13:50:59

bzoj4300 绝世好题

4300: 绝世好题Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 2628  Solved: 1437[Submit][Status][Discuss]Description给定一个长度为n的数列ai,求ai的子序列bi的最长长度,满足bi&bi-1!=0(2<=i<=len)。Input输入文件共2行。第一行包括一个整数n。第二...

2018-05-28 11:24:56

*【ZJOI2010】基站选址 线段树优化dp难题

个人觉得这道题很难.......最近我要总结几篇“dp系列”了。令dp[i][j]表示,在第i个位置建造第j个基站时的最小代价。为了方便,我们令n = n + 1,K = K + 1。给最后一个点的c赋0,d和w都赋inf(0x3f3f3f3f,如果用0x7fffffff会爆int),这样的好处是最后一个站一定建造(否则inf就变成答案了,这数字也太大了),且计算进去了前n个的全部的代价。(可以脑...

2018-05-26 21:24:25

[Noi2015]程序自动分析

4195: [Noi2015]程序自动分析Time Limit: 10 Sec  Memory Limit: 512 MBSubmit: 2854  Solved: 1326[Submit][Status][Discuss]Description 在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本:假设x1,x2,x3,…代表程序中出现的变量,给定...

2018-05-26 11:16:44

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!