zcmimi's blog

arrow_backdfs共23篇文章

avatar
zc
2020-10-21 21:57:52

查看原题

点击跳转

在dfs的过程中维护一个栈st

假设当前遍历节点为x,栈顶st[tp]

x与栈顶形成一个括号对,那么弹出栈顶,将新的栈顶权值+1

栈顶权值表示:

如果有新的右括号入栈,以这个右括号结尾,能形成多少合法括号串

avatar
zc
2020-10-13 21:01:06

查看原题

点击跳转

首先将所有RNA序列插入trie

然后用病毒模版片段trie上搜索

对于?,可以匹配任意一种

对于*,可以选择

  1. 不匹配,*当作没有
  2. 匹配,下一个停止用*匹配
  3. 匹配,下一个继续用*匹配
avatar
zc
2020-09-23 21:26:00

查看原题

点击跳转

使用ida*

首先将数组离散化为1,2,\dots,n

一次翻转最多只能改变一对相邻数的差,

因此对于一个序列,有多少对相邻的数差不为1,就至少要翻转多少次。

估价函数:

a[n+1]=n+1;
int h(){
    int cnt=0;
    for(int i=1;i<=n;++i)cnt+=(a[i]!=a[i+1]+1&&a[i]!=a[i+1]-1);
    return cnt;
}
avatar
zc
2020-09-08 20:15:00
查看原题

点击跳转

首先两次dfs找出任意一条直径

设直径为序列A,L_i为点i到直径左端的距离,R_i为点ii到直径右端的距离

可以发现这条直径把树分割成了若干棵子树,直径上每个点对应一颗子树

mxd_ii点对应子树的最大深度

从左到右枚举,直到mxd_i<L_i,得到l

从右到左枚举,直到mxd_i<R_i,得到r

序列Alr之间的点都是必须经过的点

avatar
zc
2020-06-04 12:21:00
查看原题

点击跳转

[WC2011]最大XOR和路径

avatar
zc
2020-06-02 13:14:00
查看原题

点击跳转

(以下长度定义为边权异或和)

首先钦定一条1到n的路径

容易发现可以通过环来增广路径

路径到环中间的路程要走两次,相当于没有

那么把所有环的长度插入线性基,

直接随意找一条1到n的路径,然后求这条路径长度在线性基上最大能异或成多少即可

假设1到n有一条更好的路径,那么会和刚才钦定的路径形成一个环,相当于异或时已经考虑过了

avatar
zc
2020-04-26 16:20:00
查看原题

点击跳转

两次dfs即可

第一次dfs:

计算出每个点的子树,包含这个点,答案最大是多少

显然S_x=v_x+\sum\limits_{y\in son_x} [S_y>0]S_y

(若x为黑点v_x=-1,否则v_x=1)

第二次dfs:

通过x的父亲的答案来计算出x的答案

如果x目前的答案>0,则从x的答案减去x目前的答案

如果这个结果>0,那么x的答案加上这个结果

感觉直接看代码可能更直观

avatar
zc
2020-03-02 02:05:00
查看原题

点击跳转

线段树合并的时候取\min(\text{交换前},\text{交换后})

avatar
zc
2020-02-14 00:06:00
查看原题

点击跳转

首先可以dfs处理出所有路径的重要度(路径两端子树大小乘积)

然后就是树型dp处理出每个点影响的范围的重要度总和

最后取最大值就可以了

f(dis,x)表示与x距离不超过dis的所有路径的重要度

f(1,x)=\sum val(edge)

f(k,x)=\sum f(k-1,to)-f(k-2,x)

avatar
zc
2020-01-28 01:17:00
查看原题

点击跳转

求仙人掌直径

1/3
Search
search